Randomizacja w algorytmach i geometrii obliczeniowej 1000-2M20RGO
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).
Rodzaj przedmiotu
seminaria doktoranckie
Tryb prowadzenia
Założenia (opisowo)
Koordynatorzy przedmiotu
Efekty kształcenia
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.
Kryteria oceniania
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.
Literatura
* 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.
Więcej informacji
Więcej informacji o poziomie przedmiotu, roku studiów (i/lub semestrze) w którym się odbywa, o rodzaju i liczbie godzin zajęć - szukaj w planach studiów odpowiednich programów. Ten przedmiot jest związany z programami:
Dodatkowe informacje (np. o kalendarzu rejestracji, prowadzących zajęcia, lokalizacji i terminach zajęć) mogą być dostępne w serwisie USOSweb: