Cvičení z Algoritmů a Datových Struktur II

... se v ZS 2005/2006 koná v pátek od 9:00 v S7 a od 10:40 v S1.

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 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.

Můžete si stáhnout textík o algoritmech okolo teorie čísel (řešení kongruencí, randomizované testování prvočíselnosti a RSA).

Náměty na zápočtové programy

• Variace a`la Aho-McCorasicková:
  • je dána množina slov; nalezněte všechny dvojice slov (x,y) takové, že x je podslovem y. (zabráno)
  • 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). (zabráno)
  • "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. (zabráno)
• Příhrádkové třídění řetězců (v lineárním čase)
• Maximální tok Dinicovým algoritmem
• Maximální tok Dinicovým algoritmem pro sítě s jednotkovými kapacitami (využijte toho, že vždy vypadne celá cesta a vůbec neukládejte kapacity ani rezervy)
• Maximální tok Goldbergovým algoritmem
• 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árování v bipartitiním grafu redukcí na toky v sítích (opět Dinic pro jednotkové kapacity, ale můžete jej zkusit přeformulovat přímo v řeči párování a volných střídavých cest, vyjde jednodušší program)
• Hledání maximálního párovaní v obecném grafu Edmondsovým algoritmem (viz přednáška z Kombinatoriky a grafů 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.
• Dekodér DTMF (frekvenční telefonní volby) (pomocí FFT)
• Násobení matic Strassenovým algoritmem (rozumně efektivní)
• Konstrukce Voroného diagramu (Fortunův alg. nebo metoda rozděl a panuj)
• 3D konvexní obal
• Konstrukce splňujícího ohodnocení formule pro E3E3-SAT (klauzule délky 3, každá proměnná v právě třech klauzulích)
• Sčítání čísel ve Fibonacciho soustavě (v lineárním čase)
• Rabin-Millerův test prvočíselnosti (s dlouhými čísly)
• Vygenerování náhodného prvočísla s rovnoměrným rozdělením
• (*) RSA (s alespon 256-bitovými klíči, aby to mělo smysl)