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.
Wymagania wstępne
Ukończone studia licencjackie z nauk matematyczno-przyrodniczych lub technicznych.
Zakres tematyczny
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.).
Metody kształcenia
Wykład konwersatoryjny, ćwiczenia dyskusyjne.
Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się
Opis efektu
Symbole efektów
Metody weryfikacji
Forma zajęć
Warunki zaliczenia
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.
Literatura podstawowa
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.
Literatura uzupełniająca
Z. Palka, A. Ruciński, Wykłady z kombinatoryki, cz. I, WNT, Warszawa, 1998.
W. Lipski, Kombinatoryka dla programistów, WNT, 2005.
Ta strona używa ciasteczek (cookies), dzięki którym nasz serwis może działać lepiej. Korzystając z niniejszej strony, wyrażasz zgodę na ich używanie. Dowiedz się więcej.