Zápočtové úlohy z ADS2
- 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-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á.