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.).
Efekty uczenia się i metody weryfikacji osiągania efektów uczenia się
Opis efektu
Symbole efektów
Metody weryfikacji
Forma zajęć
Warunki zaliczenia
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.
Literatura podstawowa
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.
Literatura uzupełniająca
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.
Uwagi
Przedmiot oferowany również w semestrze IV.
Zmodyfikowane przez dr Robert Dylewski, prof. UZ (ostatnia modyfikacja: 09-04-2017 16:24)
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.