Rozdíly

Zde můžete vidět rozdíly mezi vybranou verzí a aktuální verzí dané stránky.

--- statnice:spolecne [2011/06/06 13:51]
pajamrazek
+++ statnice:spolecne [2025/01/03 18:23] (aktuální)
@@ Řádek 1: / Řádek 1: @@
-====== Společné okruhy státnicových otázek ======
+==== Průběh MSZZ ====
-  * Stránky předmětu: [[http://www.feld.cvut.cz/cz/education/master/topicsOI.html|oficiální link]]
+{{:statnice:prubeh_SZZ_aktualni.pdf|}}
-  * [[http://milde.cz/spolecne.pdf|Vypracované společné otázky od Romana Václavíka]]
+{{:statnice:statnice_prubeh.pdf|}}
+====== Společné okruhy státnicových otázek ======
+  * [[http://www.feld.cvut.cz/cz/education/master/topicsOI.html|Oficiální zadání]]
+  * [[https://docs.google.com/document/d/1-kJn5p6ZUBr9Ys7XdyYvToysACymCxurxkx3MFbHc54/edit|Destilace toho nejdůležitějšího]]
+  * {{:statnice:fen_statnice_obecne.pdf|Stručně vypracované otázky PDF}}
+  * {{:statnice:fen_statnice_obecne.odt|Stručně vypracované otázky ODT}}
+  * {{:statnice:oi-vytah-spol.pdf|Výtah společné části}}
 ===== 1. Amortizovaná složitost. Prioritní fronty, haldy (binární, d-regulární, binomiální, Fibonacciho), operace nad nimi a jejich složitost. (A4M33PAL) =====
@@ Řádek 13: / Řádek 21: @@
 {{:statnice:01_fronty_haldy.pdf|PDF}}
+Chyba: nesmysl u merge binomiální haldy
@@ Řádek 61: / Řádek 71: @@
 ===== 3. Lexikální analyzátor, syntaktický strom, syntaktický analyzátor shora dolů, LL(1) gramatiky, rozkladové tabulky. (A4M33PAL) =====
-mildedan
+mildedan, vavradav
-http://cs.wikipedia.org/wiki/Form%C3%A1ln%C3%AD_jazyk#
+==== 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.
-[[http://www.algoritmy.net/article/69/LL1-gramatika|LL1 gramatika]]
+==== 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é.
-[[http://en.wikipedia.org/wiki/Parse_tree|Parse tree]]
+Příklad:
+  Vstup: int i = 15;
+  Výstup: <integer> <ident i> <assignment> <number 15> <semicolon />
-syntaktický analyzátor shora dolů: [[http://service.felk.cvut.cz/courses/X36PJP/Skripta_prednasky.pdf|Muller, K., Programovací jazyky]] - 3.1
+==== Syntaktický analyzátor shora dolů ====
-== Lexikální analyzátor ==
+=== LL(1) gramatiky ===
-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ů.
+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.
-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.
+=== 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 ===
+  * [[http://service.felk.cvut.cz/courses/X36PJP/Skripta_prednasky.pdf|Muller, K., Programovací jazyky]]
+  * [[http://www.algoritmy.net/article/100/Konstrukce-prekladace|Algoritmy.net, Konstrukce Překladače]]
+  * [[http://www.algoritmy.net/article/69/LL1-gramatika|Algoritmy.net, LL1 gramatika]]
 ===== 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) =====
@@ Řádek 89: / Řádek 125: @@
 [[http://www.algoritmy.net/article/1699/Levenshteinova-vzdalenost|Levenshteinova vzdálenost]]
+==== 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) =====
@@ Řádek 119: / Řádek 158: @@
 [[http://www.algoritmy.net/article/8053/Turinguv-stroj--SAT|Cookeova věta]]
+[[statnice/spolecne/reseni_prikladu_ze_zkousek_tal|Řešení příkladů ze zkoušek TAL]]
 ===== 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
-Neobsahuje toky!
   * {{:statnice:07_ko_ilp.doc|ILP, formulace úloh, algoritmy}}
+//Pouze copy-paste ze slidu, navic bez toku. Lepsi si projit slidy//
@@ Řádek 141: / Řádek 181: @@
    * {{:statnice:08_ko_nejkratsi_cesty_tsp_heuristiky_batoh.pdf|PDF}}
@@ Řádek 158: / Řádek 197: @@
 [[http://www.algoritmy.net/article/5207/Floyd-Warshalluv-algoritmus|Floyd-Warshallův Algoritmus]]
+{{:statnice:slidy_-_knapsack.pdf|}}
+{{:statnice:slidy_-_tsp.pdf|}}
@@ Řádek 170: / Řádek 211: @@
 [[http://www.algoritmy.net/article/37826/Urovnovy-algoritmus|Úrovňový algoritmus]]
+{{:statnice:slidy_-_scheduling.pdf|}}

statnice/spolecne.1307361099.txt.gz · Poslední úprava: 2025/01/03 18:20 (upraveno mimo DokuWiki)

Nahoru