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.