Algorytmy Probabilistyczne (Randomized Algorithms)
Wykłady
- Poniedziałek 15:30-17:00, sala D
Ćwiczenia
- Poniedziałek 17:15-18:45, 306
- Środa 13:45-15:15, 301
Kolokwium (9/04)
Egzamin końcowy 20/06/2001, godz. 13:30, sala 414
WYNIKI cz. I i II (+ OCENY PROJEKTÓW)
Wyniki egzaminu i wpis ocen
- Poniedziałek, 25.06, według planu
Prowadzący zajęcia
Dyżury
- Wtorek 12-13:00
- Czwartek 13-14:00
- można się umówić w innym terminie
- Projekt zaliczeniowy 13/05/2001 (zawiera instrukcję składania projektów)
| Lp. | Data | Temat | Wykład | Zadania, problemy, uwagi |
| 1 | 12/02 | Wprowadzenie. Losowy Quicksort. | ||
| 2 | 19/02 | Min-Cut. Algorytmy Las Vegas i Monte Carlo. | ps , pdf | |
| 3 | 26/02 | Klasy złożonosci RP, ZPP, PP i BPP. Drzewa gier. | ps , pdf | |
| 4 | 5/03 | Drzewa gier (cd.). Zasada minimaksowa. | ps , pdf | zad.dom. ps , pdf |
| 5 | 12/03 | Zasada Yao. Ograniczenie dolne dla algorytmów losowych. | ps , pdf | problem ps , pdf |
| 6 | 19/03 | Algorytm losowego wyboru. Przesyłanie pakietów w sieciach. | ps , pdf | |
| 7 | 26/03 | Losowe przesyłanie pakietów w n-kostce. | ps , pdf | Zmiana w alg. V-B (i) |
| 8 | 2/04 | Analiza algorytmu Valianta i Brebnera. Projektowanie obwodów scalonych. | ps , pdf | Programowanie liniowe |
| 9/04 | KOLOKWIUM | |||
| 16/04 |
|
|||
| 9 | 23/04 | Projektowanie obwodów scalonych (losowe zaokrąglanie). | ps , pdf | |
| 30/04 |
|
|||
| 10 | 7/05 | Algorytmy geometryczne. | slajdy, notatki | zadania (ćwiczenia) |
| 11 | 14/05 | Generowanie powłoki wypukłej zbioru punktów na płaszczyźnie. | ps , pdf | zadania |
| 12 | 21/05 | System kryptograficzny RSA. Testowanie czy p jest liczbą pierwszą. | ps , str6.ps | |
| 13 | 28/05 | Losowe algorytmy równoległe. | ps , pdf | |
| 14 | 4/06 | Analiza algorytmu losowego MIS. | ps , pdf | uzupełnienie definicji |
Literatura
- Randomized Algorithms by Rajeev Motwani and Prabhakar Raghavan, plus prace na tematy nie występujące w książce.
- A.V. Aho, J.E. Hopcroft, J.D. Ullman, Projektowanie i analiza algorytmów komputerowych, PWN, Warszawa, 1983
- E.M. Reingold, J. Nievergelt, N. Deo, Algorytmy kombinatoryczne, PWN, Warszawa, 1985
- T. Cormen, Ch. Leiserson, R. Rivest, Wprowadzenie do Algorytmów,
- E. Kofler, Wstęp do teorii gier, Biblioteka Matematyczna, W-wa 1963
- M. deBerg, M. van Kreveld, M. Overmars, O. Schwarzkopf(Cheong),
Computational Geometry - Algorithms and Applications, Springer, 2000, ISBN 3-540-65620-0.
Linki
Powtórka z Rachunku PrawdopodobieństwaBiblioteka Wydziałowa
DMANET
Randomized Alg Literature Search
NP optimization problems
ADRES
Edyta Szymańskapokój 204
829-2657
Zakład Matematyki Dyskretnej
Wydział Matematyki i Informatyki UAM
Matejki 48/49
60-769 Poznań