1. SylabUZ
2. Wydział Matematyki, Informatyki i Ekonometrii
3. semestr zimowy 2019/2020
4. Matematyka - pierwszego stopnia z tyt. licencjata
5. Metody probabilistyczne w informatyce

Wygeneruj PDF dla tej strony

Metody probabilistyczne w informatyce - opis przedmiotu

Cel przedmiotu

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

Wymagania wstępne

Zapisz zmiany

Rachunek prawdopodobieństwa, Matematyka dyskretna 1.

Zakres tematyczny

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 godz.).
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.).

Metody kształcenia

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

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ęć:

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.

Literatura podstawowa

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.

Literatura uzupełniająca

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.

Uwagi

Przedmiot oferowany również w semestrze VI.

Zmodyfikowane przez dr Alina Szelecka (ostatnia modyfikacja: 19-06-2019 07:33)