Pokročilá algoritmizace

1. Máme jazyk aa*bb*cc* kolik existuje slov délky n
2. Navrhněte automat bez epsilon přechodu, který přijímá slova s levenshtein vzdálenosti 1, formou grafu
3. Upravte automat z B), aby mohl vyhledávat v textu, forma tabulky, důvod jestli je deterministický nebo ne

1. Definujte pojem silně souvislá komponenta grafu G
2. Rozhodněte, jestli platí: Všechny dvojice SCC v grafu jsou disjunktní (nesdílí hranu, ani vrchol)
3. Navrhněte efektivní algoritmus a určete jeho asymptotickou složitost, který najde všechny dvojice izolovaných SCC (není mezi nimi žádná hrana)

1. Mějme LCG, kde je modul roven 10, byl tam jeho výstup, kde byla perioda 4, určete všechny ostatní parametry LCG
2. LCG, M = 36, 1 ⇐ A, C < 36, kolik máme možnosti všech dvojic A,C, aby byla perioda 36
3. uveďte hodnoty parametrů LCG z B), aby měl periodu 1 a A,C>4
4. Lehmer generátor, kde byl příklad jeho výstupu zase s nějakou periodou a M=9, určete ostatní parametry

1. 2 kružnice, obě o 10 vrcholech, do obou přidejte 2 hrany, aby nebyly izomorfní, odůvodněte proč nejsou izomorfní
2. graf na obrazku neni spravny. hrany jdou z ruznych vrcholu. na druhem obrazku hrany jdou ze stejneho vrcholu.
3. to stejné, ale aby byly izomorfní a kolik izomorfismu existuje
4. Navrhněte algo, který dostane na vstupu 2 kružnice délky n, kde se vložily 2 hrany do každé, a určí, jestli jsou izomorfní

…Chybí jedna otázka

1. Vytvořit 2^n-1 haldu a odstranit nejmenší prvek v největším stromě
2. Potom odvození kolik porovnání musíme udělat když máme p stromů

1. automat produkuje n krát písmeno c, a druhý má jazyk takový že hammingova vzdálenost od prvního jazyka je max 3, abeceda byla {a,b,c}

1. na příkladu s kružnicí vysvětlit asymptotické složitosti

1. udělat certifikát, udělat dva neizomorfní stromy, a teoretická otázka že pokud v úplném grafu odstraníme 2 hrany, které nesdílí vrchol, a u druhého úplného grafu uděláme to stejný, tak jestli existuje izomorfismus z jednoho do druhého nebo ho tím porušíme.

1. Nakreslit certifikat, co nemel jasny koren (bylo to neco jako 00101100010111)
2. Asymptoticka slozitost tvorby certifikatu s n uzly a jednim uzlem stupne n-1
3. nepamatuji si

jazyky `L1={a, ab, abb, …}` `L2={ba, bab, babb, …}` `L3={bba, bbab, bbabb, …}` `L=L1 U L2 U L3`, `K=L1*L2*L3`

1. Kolik je kombinaci pro slovo K delky n > 10.
2. Je `L ⊂ K` nebo `K ⊂ L`?
3. Automat ktery prijima slova L
4. Automat ktery najde slova L + do tabulky a jestli se jedna o DFA nebo NFA (vysvetlit)

1. Dve haldy obsahujici 16 a 23, kolik stromu ma merge tehle dvou
2. Kolik stromu maji haldy s `n-1` a `n-2` prvky a kolik po merge
3. Kdyz mam haldu `2^(n-1)` kolik musim udelat porovnani pro nalezeni minima

1. Udelat orientovany graf se 4 SCC, kde jsou alespon dve komponenty jine
2. V jakem bode bude mit Tarjan nejvice vrcholu v zasobniku kdyz zacne nahore vlev (z grafu A))
3. Jaka je asymptoticka slozitost upraveneho Tarjana, ktery vypisuje pri nalezeni SCC vsechny predchozi vrcholy.