statnice:spolecne [OI-Wiki]

Tato stránka je pouze pro čtení. Můžete si pouze prohlédnout zdrojový kód, ale ne ho měnit. Zeptejte se správce, pokud si myslíte, že něco není v pořádku.
====== Společné okruhy státnicových otázek ======

  * Oficiální zadání: [[http://www.feld.cvut.cz/cz/education/master/topicsOI.html|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) =====

Pája

{{:statnice:01_fronty_haldy.doc|DOC}}

{{:statnice:01_fronty_haldy.pdf|PDF}}



[[http://www.algoritmy.net/article/3024/Amortizovana-slozitost|Amortizovaná složitost]]	 

{{:statnice:amortized_complexity_accounting_method_explained.pdf|}}

[[http://www.algoritmy.net/article/15/Binarni-halda|Binární halda]]	

[[http://www.algoritmy.net/article/1504/D-regularni-halda|D-regulární halda]]

[[http://www.algoritmy.net/article/1531/Binomialni-halda|Binomiální halda]] 

[[http://cs.wikipedia.org/wiki/Fibonacciho_halda|Fibonacciho halda]]

===== 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

{{:statnice:02_grafy.doc|Formát DOC}}

{{:statnice:02_grafy.pdf|Formát PDF}}


[[http://www.algoritmy.net/article/1369/Graf|Graf]]	

[[http://www.algoritmy.net/article/1399/Prohledavani-do-sirky|Prohledávání do šířky]] 

[[http://www.algoritmy.net/article/1378/Prohledavani-do-hloubky|Prohledávání do hloubky]] 

[[http://www.algoritmy.net/article/1381/Topologicke-usporadani|Topologické uspořádání]] 

[[http://www.algoritmy.net/article/104/Strom|Strom]] 

Minimální kostra:	

[[http://www.algoritmy.net/article/1396/Boruvkuv-algoritmus|Borůvkův algoritmus]]

[[http://www.algoritmy.net/article/1393/Jarnik-Primuv-algoritmus|Jarník-Primův algoritmus]]	

[[http://www.algoritmy.net/article/1417/Kruskaluv-algoritmus|Kruskalův algoritmus]] 	

[[http://www.algoritmy.net/article/1673/Edmondsuv-algoritmus|Chu-Liu-Edmondsův algoritmus]]




===== 3. Lexikální analyzátor, syntaktický strom, syntaktický analyzátor shora dolů, LL(1) gramatiky, rozkladové tabulky. (A4M33PAL) =====
mildedan, vavradav

==== 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 ===
  * [[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) =====

Pája Mrázek - mrazepa1

{{:statnice:hledani_v_textu.doc|Otázka 4 ve formátu doc}} - 100%

{{:statnice:hledani_v_textu.pdf|Otázka 4 ve formátu pdf}} - 100%


[[http://www.algoritmy.net/article/1559/Naivni-algoritmus|Naivní algoritmus]]

[[http://www.algoritmy.net/article/1615/Hammingova-vzdalenost|Hammingova vzdálenost]]

[[http://www.algoritmy.net/article/1699/Levenshteinova-vzdalenost|Levenshteinova vzdálenost]]

===== 5. Algoritmus, správnost algoritmu, složitost algoritmu, složitost úlohy, třída P, třída NP. (A4M01TAL) =====

Pája

{{:statnice:05_algoritmus_spravnost_tridy_p_np.doc|Formát DOC}}

{{:statnice:05_algoritmus_spravnost_tridy_p_np.pdf|Formát PDF}}


[[http://www.algoritmy.net/article/3973/Korektnost-algoritmu|Korektnost algoritmu]]	

[[http://www.algoritmy.net/article/102/Asymptoticka-slozitost|Asymptotická složitost]]

[[http://www.algoritmy.net/article/3024/Amortizovana-slozitost|Amortizovaná složitost]]

[[http://www.algoritmy.net/article/5774/Tridy-slozitosti|Turingův stroj a třídy složitosti]]

===== 6. NP-úplné a NP-těžké úlohy, Cookeova věta, heuristiky na řešení NP-těžkých úloh, pravděpodobnostní algoritmy.(A4M01TAL) =====

Pája

{{:statnice:06_tridy_npc_nphard.doc|Formát DOC}}

{{:statnice:06_tridy_npc_nphard.pdf|Formát PDF}}


[[http://www.algoritmy.net/article/5774/Tridy-slozitosti|Turingův stroj a třídy složitosti]]

[[http://www.algoritmy.net/article/8053/Turinguv-stroj--SAT|Cookeova věta]]

===== 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}}


==== relevantní zdroje ====
  * [[http://en.wikipedia.org/wiki/Branch_and_bound]]
  * {{:statnice:07_ilp_basics.pdf|Slidy z přednášek týkající se základů formulace úloh ILP, Metoda větví a mezí}}
  * {{:statnice:07_toky.pdf|Slidy z přednášek - Toky, multikomoditní toky}}

===== 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) =====

Pája

   * {{:statnice:08_ko_nejkratsi_cesty_tsp_heuristiky_batoh.doc|DOC}}

   * {{:statnice:08_ko_nejkratsi_cesty_tsp_heuristiky_batoh.pdf|PDF}}





[[http://www.algoritmy.net/article/5521/Batoh|Batoh]]

[[http://www.algoritmy.net/article/5407/Obchodni-cestujici|Obchodní cestující]]

[[http://www.algoritmy.net/article/36597/Nejkratsi-cesta|Nejkratší cesta]]

[[http://www.algoritmy.net/article/5108/Dijkstruv-algoritmus|Dijkstrův algoritmus]]

[[http://www.algoritmy.net/article/7478/Bellman-Forduv-algoritmus|Bellman-Fordův algoritmus]]

[[http://www.algoritmy.net/article/5207/Floyd-Warshalluv-algoritmus|Floyd-Warshallův Algoritmus]]







===== 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) =====

[[http://www.algoritmy.net/article/37707/McNaughtonuv-algoritmus|McNaughtonův algoritmus]]

[[http://www.algoritmy.net/article/37826/Urovnovy-algoritmus|Úrovňový algoritmus]]






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