Randomizacja w algorytmach i geometrii obliczeniowej

monograficzne
seminaria doktoranckie

Matematyka dyskretna, Algorytmy i struktury danych, Rachunek prawdopodobieństwa i statystyka. Pomocne, ale nie konieczne jest przejście przez kurs z Algorytmiki.

w sali

Po krótkim wprowadzeniu w kombinatoryczne aspekty rachunku prawdopodobieństwa kurs będzie się skupiał głównie na algorytmach, które korzystają z technik probabilistycznych, ze szczególnym naciskiem na algorytmy geometryczne. Pokrótce zostanie dokonany przegląd klasycznych algorytmów randomizowanych tj. min-cut Kargera, zrandomizowany quicksort, czy zrandomizowane zaokrąglanie, itp., po czym przejdziemy do bardziej współczesnych rozwiązań takich jak algoriytmiczne ujęcie lokalnego lematu Lovásza, rozrzedzanie grafu i szacowanie objętości wypukłych politopów. Przedstawimy też algorytmy geometryczne takie jak lokalizacja punktu, przeszukiwanie zakresu, a także metryczne włożenia, redukcje wymiarów itp.

i. Podstawowe pojęcia rachunku prawdopodobieństwa: przestrzeń losowa, zmienne losowe, niezależność zdarzeń; Wprowadzenie do kombinatoryki rachunku prawdopodobieństwa; Przykłady (1 wykład).

ii. Lokalny lemat Lovásza i jego zastosowania w algorytmach (2 wykłady).

iii. Grafy losowe (2 wykłady).

iv. Potęga wyboru, 2 metody (1 wykład).

v. Zrandomizowane zaokrąglanie (1 wykład).

vi. Przestrzenie zakresów oraz ε-sieci (1 wykład).

vii. Przeszukiwanie zakresów; lokalizacja punktu (1 wykład).

viii. Metryczne włożenia i redukcja wymaru (2 wykłady).

ix. Łańcuchy Markowa oraz losowe spacery po grafach (1 wykład).

x. Algorytm k-SAT Schöninga (1 wykład).

xi. Rozrzedzanie grafów (1 wykład).

xii. Wypukłe politopy (1 wykład).

* Alon and Spencer, The Probabilistic Method.

* Motwani and Raghavan, Randomized Algorithms.

* Mitzenmacher and Upfal, Probability and Computing.

* Feller, An Introduction to Probability Theory and Its Applications, Part I.

* Wybrane publikacje z ostatnich lat.

Wiedza:

* Znajomośc podstawowych i wybranych zaawansowanych metod probabilistycznych używanych w informatyce.

* Stosunkowo szerokie obeznanie z klasycznymi i nowoczesnymi problemami algorytmicznymi.

* Zrozumienie wagi dowodów matematycznych.

Umiejętności:

* Umiejętność stosowania pojęć rachunku prawdopodobieństwa do analizy algorytmów.

* Umiejętność doboru narzędzi rachunku prawdopodobieństwa oraz w razie potrzeby ich adaptacji do rozwiązywania problemów algorytmicznych i kombinatorycznych.

Kompetencje społeczne:

* Świadomość własnych ograniczeń i potrzeby rozwijania swojej wiedzy.

* Rozwój umiejętności czytania artykułów naukowych, jeśli trzeba w obcym języku, w celu rozszerzenia swojej wiedzy.

* Zdolność do precyzyjnego formułowania pytań i pogłębiania własnego zrozumienia tematu oraz zdolność do znajdywania luk w swoim rozumowaniu.

Doktorant zna tendencje rozwojowe nauk przyrodniczych i ścisłych oraz

związane z nimi dylematy współczesnej cywilizacji, doktorant zna właściwy dla swojej dyscypliny dorobek na poziomie pozwalającym na twórcze jej rozwijanie, metodologię badań w swojej dyscyplinie, umie korzystać ze źródeł (książek, artykułów itp.) przedstawiających wyniki w swojej dyscyplinie także w języku obcym, umie przedstawiać zaawansowane idee i wyniki w swojej dyscyplinie, umie zorganizować samokształcenie w swojej dyscyplinie, jest gotów do podejmowania zadań naukowca w społeczeństwie.

Będziesz musiał wykonać 2-3 zadania domowe z oceną. Uczniowie, którzy uzyskają co najmniej 50 procent ocen z prac domowych, będą mogli przystąpić do egzaminu głównego.

Głównym egzaminem będzie egzamin domowy, po którym nastąpi krótkie ustne. Na ocenę końcową składa się 50% sumy ocen z prac domowych i 50% egzaminu głównego.

Doktoranci mają możliwość (a) przedstawienia referatu z listy wybranych ostatnich prac LUB (b) rozwiązania trudnego zadania domowego (oznaczonego gwiazdką), przygotowując się do pracy naukowej.