navigation
hledat
Toto je starší verze dokumentu!
Obsah
Společné okruhy státnicových otázek
- Stránky předmětu: oficiální link
1. Amortizovaná složitost. Prioritní fronty, haldy (binární, d-regulární, binomiální, Fibonacciho), operace nad nimi a jejich složitost. (A4M33PAL)
2. Neorientované a orientované grafy, jejich reprezentace. Prohledávání grafu (do hloubky a do šířky), topologické uspořádání, souvislost, stromy, minimální kostra. (A4M33PAL)
Pája
Minimální kostra:
3. Lexikální analyzátor, syntaktický strom, syntaktický analyzátor shora dolů, LL(1) gramatiky, rozkladové tabulky. (A4M33PAL)
mildedan
http://cs.wikipedia.org/wiki/Form%C3%A1ln%C3%AD_jazyk#
syntaktický analyzátor shora dolů: Muller, K., Programovací jazyky - 3.1
Lexikální analyzátor
Lexikální analyzátor prostřednictvím vstupního systému (DKA) čte posloupnost znaků tvořící zdrojový kód programu a transformuje ji na posloupnost lexikálních symbolů. Lexikální symboly jsou terminální symboly pro následnou syntaktickou analýzu a jednotlivé symboly mohou mít atributy (například symbolem může být cislo a jeho atributem hodnota.
4. Algoritmy vyhledávaní v textu s lineární a sublineární složitostí, (naivní, Boyer-Moore), využití konečných automatů pro přesné a přibližné hledání v textu. (A4M33PAL)
5. Algoritmus, správnost algoritmu, složitost algoritmu, složitost úlohy, třída P, třída NP. (A4M01TAL)
Pája
6. NP-úplné a NP-těžké úlohy, Cookeova věta, heuristiky na řešení NP-těžkých úloh, pravděpodobnostní algoritmy.(A4M01TAL)
7. Metoda větví a mezí. Algoritmy pro celočíselné lineární programování. Formulace optimalizačních a rozhodovacích problémů pomocí celočíselného lineárního programování. Toky a řezy. Multi-komoditní toky.(A4M35KO)
belohji1
relevantní zdroje
8. Nejkratší cesty. Úloha obchodního cestujícího. Heuristiky a aproximační algoritmy. Metoda dynamického programování. Problém batohu. Pseudo-polynomiální algoritmy.(A4M35KO)
vejmema1
9. Rozvrhování na jednom procesoru a na paralelních procesorech. Rozvrhování projektu s časovými omezeními. Programování s omezujícími podmínkami.(A4M35KO)
Nahoru
