navrh-ADS2-ucitelske.md 3.1 KB
Newer Older
Martin Mareš's avatar
Martin Mareš committed
1
# Návrh na společné ADS2 + Automaty a gramatiky pro učitele
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

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

36
1.	Konečné automaty (1.5 přednáška)
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
	* 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í

62
1.	Turingovy stroje (1.5 přednášky)
63
64
65
66
67
68
69
70
71
72
	* 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ý