Návrhy na zápočtové práce ADS2, ZS 2011/12 V práci popište algoritmus, ideu jeho správnosti, vhodné nebo použité datové struktury, časovou a paměťovou složitost. Případně důležité místa alg., kde hrozí špatná implementace. Text má být matematický / informatický, správný a informativní. Řetězce 1. Je dána množina slov; nalezněte všechny dvojice slov (x,y) takové, že x je podslovem y. 2. 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). 3. 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. 4. Je dán řetězec, najděte jeho lexikograficky minimální rotaci (v lineárním čase). 5. 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). 6. Najdětě nejdelší řetězec, který se v daném textu vyskytuje alespoň dvakrát. 6u. Přihrádkové třídění řetězců (v lineárním čase) Toky, řezy a párování 7. Maximální párování v bipartitním grafu pomocí Dinicova algoritmu 8. 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.) 9. Nalezení maximální množiny vrcholově disjunktních cest mezi zadanými dvěma vrcholy v orientovaném grafu. 10. Maximální tok Goldbergovým algoritmem s výběrem nejvyššího vrcholu s přebytkem 11. Maximální tok algoritmem Tří Indů 12. 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) 12b. dtto: -vrcholové- 13. 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ě schopnými a drahými hlídači.) 14. Hledání maximálního toku minimální ceny 14b. Hledání maximálního toku minimální ceny v bipartitním grafu Fourierova transformace 15. Násobení polynomů za pomoci FFT 16. Násobení polynomů za pomoci FFT v Z_p 17. (*) Násobení dlouhých čísel za pomoci FFT Geometrie 18. Konstrukce Voroného diagramu (Fortunův alg. nebo metoda Rozděl a panuj) 19. 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í). 20. Triangulace mnohoúhelníku (rozklad na sjednocení trojúhelníků) 21. 3D konvexní obal Teorie čísel 22. Rabinův-Millerův test prvočíselnosti (s dlouhými čísly), případně nějaký jiný pravděpodobnostní test Různé 23. Nalezení nejdelší cesty v kaktusovém grafu (to je neorientovaný graf, jehož každá hrana leží na nejvýše jednom cyklu). 24. Nalezení všech možných vzdáleností mezi přístavy na (stromové) říční síti.