Differences
This shows you the differences between two versions of the page.
| Next revision | Previous revision | ||
| courses:b4m33pal [2025/01/21 09:22] – created linha.v | courses:b4m33pal [2025/01/22 12:31] (current) – Add photos linha.v | ||
|---|---|---|---|
| Line 31: | Line 31: | ||
| ...Chybí jedna otázka | ...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, | ||
| + | |||
| + | === 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 ==== | ==== Implementační část ==== | ||
| {{: | {{: | ||
| + | {{: | ||
