SylabUZ
Nazwa przedmiotu | Metody probabilistyczne w informatyce |
Kod przedmiotu | 11.9-WK-IiEP-MPI-Ć-S14_pNadGenP3Z4E |
Wydział | Wydział Matematyki, Informatyki i Ekonometrii |
Kierunek | Informatyka i ekonometria |
Profil | ogólnoakademicki |
Rodzaj studiów | pierwszego stopnia z tyt. licencjata |
Semestr rozpoczęcia | semestr zimowy 2020/2021 |
Semestr | 6 |
Liczba punktów ECTS do zdobycia | 5 |
Typ przedmiotu | obieralny |
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 |
Wykład | 30 | 2 | - | - | Egzamin |
Ćwiczenia | 30 | 2 | - | - | Zaliczenie na ocenę |
Poznanie możliwości stosowania metod probabilistycznych w informatyce.
Rachunek prawdopodobieństwa, Matematyka dyskretna 1.
Wykład
1. Metoda naiwna i metoda wartości oczekiwanej w kombinatoryce, ich aspekt algorytmiczny (4 godz.).
2. Lokalny Lemat Lovásza i jego zastosowanie (3 godz.).
3. Metoda prawdopodobieństw warunkowych i estymatorów pesymistycznych w problemie derandomizacji algorytmów (3 godz.).
4. Algorytmy typu Las Vegas i Monte Carlo. Przykłady ilustrujące te typy: Min-Cut, RandAuto, RandQS, Find; analiza działania, losowe parametry, klasyfikacja (6 godz.).
5. Losowe techniki gier szacujące złożoność algorytmu (2 godz.).
6. Klasy złożoności: RP, Co-RP, BPP, ZPP (2 godz.).
7. Algorytmy geometryczne: otoczka wypukła punktów płaszczyzny, podziały binarne płaszczyzny, średnica zbioru punktów (4 h).
8. Algorytmy grafowe: pary najkrótszych ścieżek, uogólnienie problemu Min_Cut, minimalne drzewo rozpinające (2 godz.).
9. Algorytmy w teorii liczb: testy dla liczb pierwszych (4 godz.).
Ćwiczenia
1. Samodzielna analiza dowodów faktów w których wykorzystano metody naiwną, wartości oczekiwanej i Lokalny Lemat Lovásza na bazie literatury anglojęzycznej; czytelne przedstawianie tych dowodów innym słuchaczom kursu (10 godz.).
2. Konstrukcja algorytmów deterministycznych znajdujących obiekt kombinatoryczny na bazie metod derandomizacji zastosowanych do wcześniej poznanych twierdzeń o istnieniu, których dowody wykorzystywały metodę naiwną i metodę wartości oczekiwanej (4 godz.).
3. Dowodzenie prostych zależności między klasami złożoności poznanymi podczas zajęć (4 godz.).
4. Zespołowa analiza co najmniej jednego współczesnego artykułu dotyczącego zagadnień omawianych podczas zajęć (10 godz.).
Kolokwium zaliczeniowe (2 godz.).
Wykład konwersatoryjny, wykład tradycyjny, ćwiczenia dyskusyjne
Opis efektu | Symbole efektów | Metody weryfikacji | Forma zajęć |
Warunki zaliczenia poszczególnych zajęć:
1. Sprawdzanie stopnia przygotowania studentów oraz ich aktywności w trakcie ćwiczeń.
2. Praca pisemna pozwalające na ocenę czy, i w jakim stopniu student osiągnął wymienione efekty kształcenia głównie w zakresie wiedzy umiejętności.
3. Konwersacja podczas wykładu w celu weryfikacji wyższych poziomów efektów kształcenia w zakresie wiedzy i umiejętności.
4. Prezentacja materiału przygotowanego przez studenta samodzielnie i/lub w grupie.
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.
1. R. Motwani, P. Raghavan, Randomized Algorithms, Algorithms and Theory of Computation, Handbook, CRS Press 1998.
2. N. Alon, J.H. Spencer, The probabilistic Method in Interscience Series in Discrete Mathematics and Optimization, 2000.
3. M.O. Rabin, Probabilistic Algorithms for testing Primality, Journal of Number Theory 12(1), 1980.
1. J. Beck, An Algorithmic Paproch to the Lovász Local Lemma, in Random Structures and Algorithms, vol.2 (4) 1991.
2. R. Diestel, Random Graphs, in Graph Theory.
Zmodyfikowane przez dr Alina Szelecka (ostatnia modyfikacja: 05-06-2020 12:23)