Průběh MSZZ
Společné okruhy státnicových otázek
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)
3. Lexikální analyzátor, syntaktický strom, syntaktický analyzátor shora dolů, LL(1) gramatiky, rozkladové tabulky. (A4M33PAL)
Nutné pojmy
Jazyk - množina slov složená pomocí konečné abecedy
Gramatika - seznam pravidel, která popisuje daný jazyk. Obsahuje terminály (konstanty), neterminály (proměnné) a počáteční neterminál S. Příklad: S → Ak, A → l. Vygeneruje jazyk: {nic, lk}
Bezkontextová gramatika - taková gramatika kde na levé straně jsou pouze neterminály
Regulární gramatika - bezkontextová gramatika, kde na pravé straně je maximálně jeden neterminál a jeden terminál.
DKA - Deterministický konečný automat - pro danou sekvenci znamků rozhodne jestli přijímá nebo nepřijímá. Obsahuje stavy, abecedu, přijímací stavy a tabulku přechodů - co se má stát pro každou kombinaci stavu a znaku na vstupu. Deterministický znamená že pro každý vstup a stav existuje jenom jeden přechod.
Derivační strom - gramatika přepsaná do stromu tak, že kořen je S, vnitřní uzly jsou neterminály a listy terminály.
Lexikální analyzátor
Lexikální analyzátor je první součástí překladače. Na vstupu dostává text a generuje lexikální symboly, které jsou terminálními symboly pro syntaktickou analýzu. Ignoruje části textu jako whitespace, komentáře atd. Lexikální symboly jsou popsány regulárními výrazy nebo regulární gramatikou. Analyzátor je obvykle implementován pomocí DKA. Jednotlivé symboly mohou mít také atributy - např. hodnotu proměnné.
Příklad:
Vstup: int i = 15;
Výstup: <integer> <ident i> <assignment> <number 15> <semicolon />
Syntaktický analyzátor shora dolů
LL(1) gramatiky
LL1 gramatika je postavena tak, aby se v žádném okamžiku nedostala do situace, ve které by mohlo jít zpracování vstupu více cestami (tj. zpracování je deterministické). Zásobníkový automat gramatiky je vždy schopen rozhodnout na základě svého stavu a prvního nezpracovaného znaku, do kterého dalšího stavu má přejít.
Průběh analýzy shora
Syntaktický analyzátor bere výstup s lexikálního analyzátoru a kontroluje jeho správnost podle LL(1) gramatiky. Realizuje se zásobníkovým automatem. Na začátku je na zásobníku počáteční neterminál. V každém kroku automat rozvine neterminály podle gramatiky. Když už to nejde dál rozvinout - je tam terminál - automat se podívá na vstup a porovná vstup s terminálem. Pokud se liší, vyhodí chybu. Pokud jsou stejné, posune vstup na další znak a odebere terminál ze zásobníku. Když je zásobník prázdný, slovo bylo přijato.
FIRST a FOLLOW
K rozvinutí neterminálů je potřeba rozkladová tabulka. Ta se z LL(1) gramatiky spočítá pomocí funkcí FIRST a FOLLOW.
FIRST(A) je množina terminálů, které mohou být na prvním místě když na levé straně je A
FOLLOW(A) má cenu počítat jenom když FIRST(A) obsahuje prázdný znak. Podíváme se na pravé strany pravidel a zjistíme jaké terminály mohou být hned za A.
Rozkladová tabulka
Rozkladová tabulka se používá pro rozvinutí neterminálů v syntaktické analýze. Je to tabulka neterminálů na terminály. Nedřív jí vyplníme podle FIRST. Pokud FIRST obsahuje prázdný znak, vyplníme také FOLLOW.
Syntaktický strom
Abstraktní syntaktický strom je výstupem překladače u interpretovaných jazyků. Je to strom, jehož vnitřní uzly jsou operátory a uzly operandy. Je abstraktní v tom smyslu, že neobsahuje všechny detaily původního kódu (jako to obsahuje derivační strom). Používá se pro zjednodušování a optimalizaci běhu kódu - např. když je operand disjunkce(OR) a levá větev vyjde true, můžeme přeskočit vyhodnocování pravé větve.
Zdroje
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)
Jak se spočítá BCS
BCS je tabulka indexovaná znaky abecedy značící vzdálenost znaků od konce vzorku. Když tam znak není, je vzdálenost délka vzorku.
5. Algoritmus, správnost algoritmu, složitost algoritmu, složitost úlohy, třída P, třída NP. (A4M01TAL)
6. NP-úplné a NP-těžké úlohy, Cookeova věta, heuristiky na řešení NP-těžkých úloh, pravděpodobnostní algoritmy.(A4M01TAL)
belohji1
Pouze copy-paste ze slidu, navic bez toku. Lepsi si projit slidy
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)
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