Metoda naiwna i metoda wartości oczekiwanej w kombinatoryce, ich aspekt algorytmiczny (4 godz.).
Lokalny Lemat Lovásza i jego zastosowanie (3 godz.).
Metoda prawdopodobieństw warunkowych i estymatorów pesymistycznych w problemie derandomizacji algorytmów (3 godz.).
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.).
Losowe techniki gier szacujące złożoność algorytmu (2 godz.).
Klasy złożoności: RP, Co-RP, BPP, ZPP (2 godz.).
Algorytmy geometryczne: otoczka wypukła punktów płaszczyzny, podziały binarne płaszczyzny, średnica zbioru punktów (4 godz.).
Algorytmy w teorii liczb: testy dla liczb pierwszych (4 godz.).
Ćwiczenia
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.).
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.).
Dowodzenie prostych zależności między klasami złożoności poznanymi podczas zajęć (4 godz.).
Zespołowa analiza co najmniej jednego współczesnego artykułu dotyczącego zagadnień omawianych podczas zajęć (10 godz.).
Learning outcomes and methods of theirs verification
Outcome description
Outcome symbols
Methods of verification
The class form
Assignment conditions
Warunki zaliczenia poszczególnych zajęć:
Sprawdzanie stopnia przygotowania studentów oraz ich aktywności w trakcie ćwiczeń.
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.
Konwersacja podczas wykładu w celu weryfikacji wyższych poziomów efektów kształcenia w zakresie wiedzy i umiejętności.
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.
Recommended reading
R. Motwani, P. Raghavan, Randomized Algorithms, Algorithms and Theory of Computation, Handbook, CRS Press 1998.
N. Alon, J.H. Spencer, The probabilistic Method in Interscience Series in Discrete Mathematics and Optimization, 2000.
M.O. Rabin, Probabilistic Algorithms for testing Primality, Journal of Number Theory 12(1), 1980.
Further reading
J. Beck, An Algorithmic Paproch to the Lovász Local Lemma, in Random Structures and Algorithms, vol.2 (4) 1991.
R. Diestel, Random Graphs, in Graph Theory.
Notes
Przedmiot oferowany również w semestrze IV.
Modified by dr Alina Szelecka (last modification: 05-06-2020 12:18)