Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revisionNext revision | Previous revision | ||
| courses:b4m33pal [2025/01/21 09:24] – linha.v | courses:b4m33pal [2026/02/14 22:18] (current) – [Teoretická část] ferociousfossa | ||
|---|---|---|---|
| Line 32: | Line 32: | ||
| ...Chybí jedna otázka | ...Chybí jedna otázka | ||
| - | === 16.1. === | + | === 16.1. Varianta A === |
| == Binomiální haldy == | == Binomiální haldy == | ||
| - Vytvořit 2^n-1 haldu a odstranit nejmenší prvek v největším stromě | - Vytvořit 2^n-1 haldu a odstranit nejmenší prvek v největším stromě | ||
| Line 42: | Line 42: | ||
| == Izomorfismy == | == Izomorfismy == | ||
| - udělat certifikát, | - 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. | ||
| + | |||
| + | |||
| + | === Několik úloh dle tématu === | ||
| + | {{ : | ||
| + | |||
| ==== Implementační část ==== | ==== Implementační část ==== | ||
| {{: | {{: | ||
| + | {{: | ||
