Cvičení z Algoritmů a Datových Struktur II
... se v ZS 2008/2009 koná v pátek od 9:00 v S7.
Přihlašujte se, prosím, pomocí SISu.
Zápočet dostanete za naprogramování libovolného netriviálního algoritmu z přednášky, nebo i jiného; každopádně domluva je předem nutná. Účast na cvičení je polehčující okolností :)
Informace o přednášce (syllabus, učební texty atd.) získáte na stránce přednášejícího.
Některé další učební texty najdete u mé loňské přednášky.
Co jsme dělali
| datum | téma |
|---|---|
| 3. 10. | Dva prvky se zadaným součtem. Robin Hood a body na přímce. Minimální kostra grafu s hranami ohodnocenými malými čísly. Medián sjednocení dvou setříděných posloupností. |
| 10. 10. | Řetězce a operace s nimi. Třídění (pomocí stromů, přihrádkově). Lexikograficky minimální rotace řetězce. Burrows-Wheelerova transformace a její inverze. |
| 17. 10. | Vyhledávání v textu: Knuth-Morris-Pratt a Aho-Corasicková. |
| 24. 10. | Rozcvička: počítání kombinačních čísel. Další cvičení na vyhledávání: superlinearita (počet výskytů i velikost množin slov hlášených ve stavech), počítání výskytů, problém censora (proč verze pro více slov není lineární a jak zařídit aby byla?). |
| 31. 10. | Rozcvička: Volby. Počítání na hradlových sítích. Základy booleovských obvodů. Obvod pro porovnávání dvojkových čísel. |
| 7. 11. | Opět hradlové sítě: Sčítání, odčítání a násobení čísel. |
| 14. 11. | Rozcvička: Mícháme karty. Počítáme součiny čísel až na i-té. |
| 21. 11. | Rozcvička: Variace na Hanojské věže. Toky v sítích: Fordův-Fulkersonův algoritmus. |
| 28. 11. | Rozcvička: Asfaltérův problém. Toky v sítích: Dinicův algoritmus. Párování v bipartitním grafu. |
| 5. 12. | Rozcvička: Přičítáme jedničku. Toky v sítích: Goldbergův algoritmus. |
| 12. 12. | Vylepšení analýzy Goldbergova algoritmu. Diskrétní Fourierova transformace. |
| 19. 12. | Hrajeme si s Fourierovou transformací. Násobení polynomů a spektrální analýza signálu. |
| 9. 1. | Převádíme problémy mezi sebou. |
| 16. 1. | Rozcvička: Implicitní reprezentace stromů. NP-úplnost. |
Náměty na zápočtové programy
- Variace à la Aho-Corasicková:
- je dána množina slov; nalezněte všechny dvojice slov (x,y) takové, že x je podslovem y.
- je dána množina slov a text; spočítejte, kolikrát se které slovo v textu vyskytuje (v čase lineárním se součtem délek všech slov a délky textu).
- "cenzorův problém" – je dán seznam zakázaných slov a text T (bez mezer). Odstraňte z textu všechny výskyty zakázaných slov; tím ovšem mohou vzniknout nové, tak je odstraňte také, atd. To vše v lineárním čase.
- Je dán řetězec, najděte jeho lexikograficky minimální rotaci (v lineárním čase).
- Je dán řetězec, najděte v něm nejdelší palindromický podřetězec (v lineárním čase).
- Je dán řetězec a číslo K, najděte nejčastější podřetězec délky K (v průměrně lineárním čase).
- Příhrádkové třídění řetězců (v lineárním čase)
- Maximální tok Dinicovým algoritmem
- Maximální párování v bipartitním grafu pomocí Dinicova algoritmu
- Nalezení maximální množiny hranově disjunktních cest mezi zadanými dvěma vrcholy v orientovaném grafu. (Toky a rozklad toku na cesty.)
- Maximální tok Goldbergovým algoritmem s výběrem nejvyššího vrcholu s přebytkem
- Maximální tok algoritmem Tří Indů
- Určování stupně hranové (vrcholové) souvislosti zadaného neorientovaného grafu (redukce na toky v sítích, nejlépe Dinicovým algoritmem pro jednotkové kapacity)
- Hledání maximálního párovaní v obecném grafu Edmondsovým algoritmem (viz přednáška z Kombinatoriky a grafů I)
- Je dán bipartitní graf s ohodnocenými vrcholy. Nalezněte minimální vrcholové pokrytí, tj. množinu vrcholů s minimálním součtem ohodnocení takovou, že každá hrana grafu sousedí s aspoň jedním z vybraných vrcholů. (Hlídáme bipartitní město různě drahými hlídači.)
- Hledání maximálního toku minimální ceny
- Násobení polynomů za pomoci FFT
- (*) Násobení dlouhých čísel za pomoci FFT
- (*) Efektivní implementace FFT pomocí instrukcí MMX/SSE/VIS/AltiVec
- Konstrukce Voroného diagramu (Fortunův alg. nebo metoda Rozděl a panuj)
- Je dána množina obdélníků v rovině (strany rovnoběžné s osami), spočítejte obsah a obvod jejich sjednocení (hint: zametání).
- Je dána množina úseček v rovině, spočítejte, kolik mají průsečíků (hint: zametání).
- 3D konvexní obal
- Rabinův-Millerův test prvočíselnosti (s dlouhými čísly)
- (*) Šifrovací algoritmus RSA (s alespoň 256-bitovými klíči, aby to mělo smysl)
- (*) Zkuste dokázat následující větu: Je-li jazyk L regulární (tj. dá se rozhodnout nějakým konečným automatem, respektive popsat regulárním výrazem), pak existuje booleovský obvod hloubky O(log n), který ho rozpoznává.