====== Pokročilá algoritmizace ======

===== Zkouška leden 2025 =====
==== Teoretická část ====
=== 13.1. ===
== Automaty ==

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

== SCC ==

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

== Generátory ==

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

== Grafy ==

  - 2 kružnice, obě o 10 vrcholech, do obou přidejte 2 hrany, aby nebyly izomorfní, odůvodněte proč nejsou izomorfní
  - graf na obrazku neni spravny. hrany jdou z ruznych vrcholu. na druhem obrazku hrany jdou ze stejneho vrcholu.
  - to stejné, ale aby byly izomorfní a kolik izomorfismu existuje
  - 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

=== 16.1. Varianta A ===
== Binomiální haldy == 
  - Vytvořit 2^n-1 haldu a odstranit nejmenší prvek v největším stromě
  - Potom odvození kolik porovnání musíme udělat když máme p stromů
== Automaty ==
  - 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}
== Kruskal, Boruvka, Prim == 
  - na příkladu s kružnicí vysvětlit asymptotické složitosti
== Izomorfismy == 
  - 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.

=== 16.1. Varianta B ===
== Certifikaty ==
  - Nakreslit certifikat, co nemel jasny koren (bylo to neco jako 00101100010111)
  - Asymptoticka slozitost tvorby certifikatu s n uzly a jednim uzlem stupne n-1
  - nepamatuji si
== Jazyky ==
jazyky `L1={a, ab, abb, ...}` `L2={ba, bab, babb, ...}` `L3={bba, bbab, bbabb, ...}`
`L=L1 U L2 U L3`, `K=L1*L2*L3`
  -  Kolik je kombinaci pro slovo K delky n > 10. 
  - Je `L ⊂ K` nebo `K ⊂ L`?
  - Automat ktery prijima slova L
  - Automat ktery najde slova L + do tabulky a jestli se jedna o DFA nebo NFA (vysvetlit)
== Binomialni haldy ==
  - Dve haldy obsahujici 16 a 23, kolik stromu ma merge tehle dvou
  - Kolik stromu maji haldy s `n-1` a `n-2` prvky a kolik po merge
  - Kdyz mam haldu `2^(n-1)` kolik musim udelat porovnani pro nalezeni minima
== Graf 4x4 jen s vertikalnimi a horiz hranami (bez diagonal) ==
  - Udelat orientovany graf se 4 SCC, kde jsou alespon dve komponenty jine
  - V jakem bode bude mit Tarjan nejvice vrcholu v zasobniku kdyz zacne nahore vlev (z grafu A))
  - Jaka je asymptoticka slozitost upraveneho Tarjana, ktery vypisuje pri nalezeni SCC vsechny predchozi vrcholy.


==== Implementační část ====
{{:courses:13.1.25_impl.webp?direct&400|}}{{:courses:16.1.25-impl1.jpg?direct&400|}}{{:courses:16.1.25-impl2.jpg?direct&400|}}
{{:courses:22.1.25a.jpg?direct&400|}}{{:courses:22.1.25b.jpg?direct&400|}}