navrh-ADS2-ucitelske.md 3.1 KB
Newer Older
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
# Návrh na společné ADS2 + Automaty a gramatiky pro učitele

## Anotace

Přednáška o algoritmech a základech teoretické informatiky.
Navazuje na NTIN060 (ADS1), nahrazuje NTIN061 (ADS2) a NTIN071 (Automaty a gramatiky).

## Sylabus

1. 	Vyhledávání v textu (1.5 přednášky)
	* notace pro řetězce
	* algoritmus Knuth-Morris-Pratt
	* algoritmus Aho-Corasicková

1. 	Toky v sítích (1.5 přednášky)
	* sítě, toky a řezy
	* Fordův-Fulkersonův algoritmus
	* Edmondsův-Karpův algoritmus (FF s nejkratší cestou)
	* párování v bipartitním grafu
	* vrcholově/hranově disjunktní cesty v grafech

1. 	Základní geometrické algoritmy v rovině (1 přednáška)
	* konvexní obal
	* princip zametání roviny řízeného událostmi

1. 	Převoditelnost problémů a třídy časové složitosti (2 přednášky)
	* polynomiální transformace a redukce mezi rozhodovacími problémy
	* nedeterministické algoritmy, třídy P a NP
	* NP-úplnost

1. 	Aproximační algoritmy (1 přednáška)
	* použití aproximačních algoritmů, poměrová a relativní chyba
	* jeden až dva jednoduché příklady aproximačních algoritmů (knapsack, bin-packing, rozvrhování na paralelních strojích) včetně horního odhadu pro jejich poměrovou (nebo relativní) chybu
	* aproximační schéma: princip a příklad

1.	Konečné automaty (1 přednáška)
	* základní pojmy: slova už známe z vyhledávání v textu,
	  jazyk je vlastně totéž co rozhodovací problém
	* definice konečného automatu (DFA), syntaxe a sémantika, regulární jazyk
	* příklad: 0^n1^n není regulární, důkaz principem holubníku
	* příklad: v KMP uvážíme uzávěr zpětných hran a máme DFA
	* regulární pumping lemma (zobecnění myšlenky předchozího důkazu)
	* příklad: 1^{prvočíslo} není regulární
	* součin automatů

1.	Regulární výrazy (1 přednáška)
	* nedeterministický konečný automat (NFA)
	* ekvivalence DFA ↔ NFA
	* λ-přechody, ekvivalence λ-NFA ↔ NFA
	* uzavřenost na množinové operace
	* regulární výrazy popisují právě regulární jazyky

1.	Gramatiky (1 přednáška)
	* gramatiky, jimi generované jazyky
	* pravé a levé lineární gramatiky generují regulární jazyky
	* obecné lineární gramatiky generují i neregulární jazyky
	* bezkontextové gramatiky, derivační stromy, jednoznačnost
	* Chomského normální forma
	* algoritmus testující příslušnost slova do bezkontextového jazyka
	  pomocí dynamického programování

1.	Turingovy stroje (1 přednáška)
	* obousměrný konečný automat
	* bez důkazu: obousměrné automaty jsou stejně silné jako jednosměrné
	* Turingův stroj (TM)
	* TM může příjímat zastavením (rekurzivně spočetné jazyky), přijímat stavem
	  (rekurzivní jazyky) nebo vydávat výstup na pásce (vyčíslitelné funkce)
	* neformálně: vztah mezi TM a RAMem
	* TM jsou ekvivalentní s obecnými gramatikami
	* univerzální Turingův stroj, kódování strojů (bez detailů konstrukce)
	* halting problem je rekurzivně spočetný, ale není rekurzivní
	* Postova věta => doplněk halting problemu není rekurzivně spočetný