1. SylabUZ
2. Faculty of Mathematics, Computer Science and Econometrics
3. winter term 2020/2021
4. Informatics and Econometrics - First-cycle studies leading to Bachelor's degree
5. Probabilistic Methods in Computer Science

Generate PDF for this page

Probabilistic Methods in Computer Science - course description

Aim of the course

Poznanie możliwości stosowania metod probabilistycznych w informatyce.

Prerequisites

Save changes

Rachunek prawdopodobieństwa, Matematyka dyskretna 1.

Scope

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.).
5. Kolokwium zaliczeniowe (2 godz.).

Teaching methods

Wykład konwersatoryjny, wykład tradycyjny, ćwiczenia dyskusyjne

Learning outcomes and methods of theirs verification

Outcome description	Outcome symbols	Methods of verification	The class form

Assignment conditions

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.

Recommended reading

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.

Further reading

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.

Notes

Modified by dr Alina Szelecka (last modification: 05-06-2020 12:23)