SylabUZ
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 2022/2023 |
Semestr | 6 |
Liczba punktów ECTS do zdobycia | 6 |
Typ przedmiotu | obowiązkowy |
Język nauczania | polski |
Sylabus opracował |
|
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 |
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.
Podstawy rachunku prawdopodobieństwa, analizy matematycznej.
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.
Wykład konwersatoryjny; wykład tradycyjny; ćwiczenia dyskusyjne; laboratoria audytoryjne.
Opis efektu | Symbole efektów | Metody weryfikacji | Forma zajęć |
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.
Zmodyfikowane przez dr Alina Szelecka (ostatnia modyfikacja: 19-05-2022 21:46)