NDMI025 - Pravděpodobnostní algoritmy

LS 2011 - Jiří Sgall

Termíny zkoušek v září

Budu zkoušet ve čtvrtek 15. 9., ve středu 21. 9. a v úterý 27. 9., vždy dopoledne od 9:00 hodin. Přihlašte se prosím předem mailem. Další termíny případně po individuální domluvě. Zřejmě ale nebudu k dispozici 29. a 30. 9.!

Úkoly a cvičení

Pro zápočet je třeba polovina bodů z úkolů, tj. 16 bodů.

Výsledky


 suma
 1. série 2. série
 3. série
 4. série
úloha
 max=32
 1
 2
 3
 4
 1
 2
 3
 4
 1
 2
 3
 4
 1
 2
 3
 4
Martin Babka 33
 2
 3
 2
 2
 4
 2
 2
 2
 2
 2
 2
 2
2
 2
 2
Martin Balko 18
 0
 2
 2
 2
 1
2
 1
 1
 3

2
 2

Vojtech Bardiovský 27
 2
 1
 2
 2
 4
 2
 2
2
2
 0
 2
 2
 2
 2
Jan Bulánek 24
 2
 3
 2
 2
 2
 2
 2
 2
 2
 2
 2
 1



Peter Černo 32
 2
 3
 2
 2
 1
 2
 2
 2
 2
 4
 2
 2
 2
 2
2
Michal Danilák
















Jan Dědeček 17
 1
2
 2
2
 2
 2
 1
 3


2
0
Martin Doucha 17
 1
 1
 2
 2

2
2
 2
 2
 1


2
Michal Dzetkulič 8
 2
 2
 2
 2











Jindřich Ivánek 13
 2
 2
 1
 2

2


1
1
 2
0
Pavel Kasík 10
 0
 1
 2
 2
 0
 1

1
 1
 2




Dušan Knop 13
 1
 2
 2
 2



1
 1
 2
 0
0
2
Martin Koutecký 14
 2
2
 2



0
 1
 1
 0
 2
 2
2
Martin Kupec
















Lukáš Mach 17
 2
 2
 2
 2

2
 2
 2
 1


2

Jakub Melka 21
 1
 3
 2
 2


2
 1
 1
 1
 0
 2
 2
 2
 2
František Polach 15
 0
 0
 1
 0
 1
 2
 2
 2
 2
 2
 2
 0
 1

0
Anna Shirokova
















Kateřina Štíchová
















Peter Šufliarsky 4
 0
 2
 2
 0











Václav Vlček 18
 2
 1
 2
 0
 2
 1
 2
 2




2
 4
Marek Vlk 23
 0
 2
 2
 2
 1
 1
 2
 2
 2
 2
 2
 3
2
0
Jan Volec 22
 2
 3
 2
 2
2
 2
 2
 2
 2
 2
 1



Probraná témata

Probraná látka podle přednášek

1. (7.3.)

2. (28.3.)
3. (4.4.)
4. (4.4.)
5. (11.4.)
6. (18.4.)
7. (18.4.)
8. (2.5.)
9. (9.5.)
10. (9.5.)
11. (16.5.)
12. (23.5.)

Probraná témata v LS 2009

Anotace

Přenáška o použití náhodnosti v algoritmech a protokolech. Náhodnost umožňuje řešit některé úlohy, které jsou bez jejího použití neřešitelné nebo řešitelné méně efektivně. Probereme základní techniky pro návrh a analýzu takových algoritmů a protokolů, ilustrované na konkrétních problémech. Předpokládá se znalost základních pojmů z teorie pravděpodobnosti (např. STP064) a teorie algoritmů (např. DMI026).

Osnova

Literatura

R. Motwani, P. Raghavan: Randomized algorithms.
M. Mitzenmacher, E. Upfal: Probability and Computing: Randomized Algorithms and Probabilistic Analysis

Další informace

Přednáška se nekoná každý rok, předpokládám její opakování za 2 roky.