Wykształcenie zdolności badania istnienia, oraz rozróżniania i przeliczania obiektów kombinatorycznych. Wskazanie możliwości wykorzystania tych zdolności, w celu szacowania wielkości danych i zasobów niezbędnych do rozwiązania danego problemu i badania jego złożoności.
Prerequisites
Ukończone studia licencjackie z nauk matematyczno-przyrodniczych lub technicznych.
Scope
Wykład
Elementy kombinatoryki: metody przeliczania obiektów kombinatorycznych oznaczonych i nieoznaczonych, twierdzenie Polya (12 godz.).
Elementy teorii grafów: spójność, skojarzenia, twierdzenie Halla, cykle Hamiltona, kolorowanie wierzchołków i krawędzi grafów, zagadnienia ekstremalnej teorii grafów, Twierdzenie Turana i Ramseya (6 godz.).
Metoda probabilistyczna Erdösa (6 godz.).
Elementy teorii obliczeń: funkcje obliczalne, maszyny Turinga, tezy Churcha (6 godz.).
Ćwiczenia
Elementy kombinatoryki: rozpoznawanie obiektów kombinatorycznych w zadaniu z treścią; odniesienia do pojęcia funkcji działającej na zbiorach skończonych, które są dowolne, różnowartościowe, „na”, malejące, niemalejące; wykorzystanie znanych wzorów w celu zliczenia rozpoznanych obiektów (5 godz.); stosowanie zasad: podziałowej, włączeń i wyłączeń, podwójnego zliczania, do obiektów kombinatorycznych oznaczonych (5 godz.); stosowanie twierdzenia Polya do zliczania obiektów kombinatorycznych nieoznaczonych (4 godz.).
Elementy teorii grafów: rozpoznawanie pojęć teorii grafów w zadaniach z treścią, stosowanie znanych algorytmów teoriografowych w celu rozwiązania tych zadań (2 godz.); znajdowanie oszacowań małych liczb Ramseya, dowodzenie twierdzeń dotyczących grafów i liczb Ramseya z wykorzystaniem klasycznych technik dowodu poznanych na wykładzie (2 godz.).
Metoda probabilistyczna Erdösa: dowodzenie faktów dotyczących struktur kombinatorycznych z wykorzystaniem metod: naiwnej, wartości oczekiwanej i Lokalnego Lematu Lovásza (6 godz.).
Elementy teorii obliczeń: konstruowanie programów dla maszyn Turinga, badanie obliczalności funkcji (4 godz.).
Kolokwium (2 godz.).
Teaching methods
Wykład konwersatoryjny, ćwiczenia dyskusyjne.
Learning outcomes and methods of theirs verification
Outcome description
Outcome symbols
Methods of verification
The class form
Assignment conditions
Sprawdzian z zadaniami o zróżnicowanym stopniu trudności, pozwalający na ocenę czy i w jakim stopniu, student osiągnął wymienione efekty kształcenia głównie w zakresie umiejętności i kompetencji.
Konwersacja podczas wykładu w celu weryfikacji wyższych poziomów efektów kształcenia w zakresie wiedzy i umiejętności.
Egzamin pisemny i w razie konieczności egzamin ustny weryfikujący efekty kształcenia w zakresie wiedzy i kompetencji.
Na ocenę z przedmiotu składa się ocena z ćwiczeń (50%) i ocena z egzaminu (50%). Warunkiem przystąpienia do egzaminu jest uzyskanie pozytywnej oceny z ćwiczeń. Warunkiem zaliczenia przedmiotu jest uzyskanie pozytywnych ocen z ćwiczeń i z egzaminu.
Recommended reading
W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa, 1989.
C.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002 (seria Klasyka Informatyki).
Diesel, Grach Theory, Springer-Verlag, Heidelberg, Gradule Test In Mathematics, Vol. 173.
Kościelski, Teoria obliczeń, WUW, Wrocław, 1997.
Further reading
Z. Palka, A. Ruciński, Wykłady z kombinatoryki, cz. I, WNT, Warszawa, 1998.
W. Lipski, Kombinatoryka dla programistów, WNT, 2005.
