SylabUZ

Wygeneruj PDF dla tej strony

Kombinatoryczne podstawy informatyki - opis przedmiotu

Informacje ogólne
Nazwa przedmiotu Kombinatoryczne podstawy informatyki
Kod przedmiotu 11.0-WK-IDP-KPI-Ć-S14_pNadGenAN32Q
Wydział Wydział Matematyki, Informatyki i Ekonometrii
Kierunek Inżynieria danych
Profil ogólnoakademicki
Rodzaj studiów pierwszego stopnia z tyt. inżyniera
Semestr rozpoczęcia semestr zimowy 2017/2018
Informacje o przedmiocie
Semestr 6
Liczba punktów ECTS do zdobycia 6
Typ przedmiotu obowiązkowy
Język nauczania polski
Sylabus opracował
  • dr hab. Ewa Drgas-Burchardt, prof. UZ
Formy zajęć
Forma zajęć Liczba godzin w semestrze (stacjonarne) Liczba godzin w tygodniu (stacjonarne) Liczba godzin w semestrze (niestacjonarne) Liczba godzin w tygodniu (niestacjonarne) Forma zaliczenia
Ćwiczenia 30 2 - - Zaliczenie na ocenę
Laboratorium 15 1 - - Zaliczenie na ocenę
Wykład 30 2 - - Egzamin

Cel przedmiotu

Celem kursu Kombinatoryczne podstawy informatyki jest zapoznanie studentów z podstawowymi metodami zliczania obiektów kombinatorycznych oznaczonych i nieoznaczonych. Umiejętności te mogą i powinny być wykorzystane w celu szacowania wielkości danych i zasobów niezbędnych do rozwiązania danego problemu  oraz badania jego złożoności obliczeniowej. Ponadto kurs ma na celu pokazanie studentom metod probabilistycznych w kombinatoryce i informatyce oraz sposobów ich derandomizacji.

Wymagania wstępne

Podstawy rachunku prawdopodobieństwa,  analizy matematycznej.

Zakres tematyczny

Wykład:

1.      Metody przeliczania obiektów kombinatorycznych oznaczonych (10  godz.)

2.      Metody przeliczania obiektów kombinatorycznych nieoznaczonych, twierdzenie Polya (6 godz.)

3.      Metoda probabilistyczna Erdösa, derandomizacja metody probabilistycznej metodą prawdopodobieństw warunkowych (8 godz.)

4.      Algorytmy zrandomizowane, ich typy i charakterystyki (6 godz.).

Ćwiczenia:

1.      Elementy kombinatoryki oznaczonej:

a.      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 (4 godz.)

b.      stosowanie zasad: podziałowej, włączeń i wyłączeń, podwójnego zliczania, rekurencji (6 godz.)

2.      Stosowanie twierdzenia Polya do zliczania obiektów kombinatorycznych nieoznaczonych (6 godz.)

3.      Metoda probabilistyczna Erdösa: znajdowanie struktur kombinatorycznych z wykorzystaniem metod: naiwnej, wartości oczekiwanej (6 godz.)

4.      Deterministyczne znajdowanie obiektów kombinatorycznych, których istnienie wynika z metody probabilistycznej  (metoda prawdopodobieństw warunkowych) (2 godz.)

5.      Analiza algorytmów zrandomizowanych i ich parametrów losowych (4 godz.)

6.      Kolokwium (2 godz.).

Laboratorium:

1.    Rozwiązywanie bardziej skomplikowanych zadań obliczeniowych z zakresu prowadzonych ćwiczeń z wykorzystaniem wybranego pakietu matematycznego lub samodzielnie napisanego programu komputerowego.

Metody kształcenia

Wykład konwersatoryjny; wykład tradycyjny; ćwiczenia dyskusyjne; laboratoria audytoryjne.

Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się

Opis efektu Symbole efektów Metody weryfikacji Forma zajęć

Warunki zaliczenia

Na ocenę z przedmiotu składa się ocena z laboratorium (25%), ocena z ćwiczeń (50%) oraz ocena z egzaminu (25%).

Warunkiem zaliczenia przedmiotu jest uzyskanie pozytywnych ocen z laboratorium, ćwiczeń i egzaminu.

Literatura podstawowa

  1. Z. Palka, A. Rucinski, Wykłady z kombinatoryki, cz. I, WNT, Warszawa, 1998.
  2. K.A. Ross, Ch.R.B. Wright, Matematyka dyskretna, PWN, Warszawa, 1996.
  3. Diesel, Grach Theory, Springer-Verlag, Heidelberg, Gradule Test In Mathematics, Vol. 173.
  4. N. Alon, J. Spencer, The Probabilistic Method, Wiley, second edition, 2000.
  5. R. Motwani, P. Raghavan, Randomized Algorithms. Cambridge University Press, second edition 2000.

Literatura uzupełniająca

  1. W. Lipski, Kombinatoryka dla programistów, WNT, 2005.
  2. W. Lipski, W. Marek, Analiza kombinatoryczna, PWN, Warszawa, 1989.
  3. C.H. Papadimitriou, Złożoność obliczeniowa, WNT, Warszawa 2002 (seria Klasyka Informatyki).

Uwagi


Zmodyfikowane przez dr Robert Dylewski, prof. UZ (ostatnia modyfikacja: 09-04-2017 16:27)