Hledej
Zobraz:
Univerzity
Kategorie
Rozšířené vyhledávání
12 659 projektů
0 nových
Úvod do teoretické informatiky
«»
| Přípona |
Typ studijní materiál |
Stažené 0 x |
| Velikost 1,5 MB |
Jazyk český |
ID projektu 10668 |
| Poslední úprava 21.08.2017 |
Zobrazeno 422 x |
Autor: aladeen |
Sdílej na Facebooku |
||
| Detaily projektu | ||
- Cena:
6 Kreditů - kvalita:
73,8% -
Stáhni
- Přidej na srovnání
- Univerzita:Vysoká škola báňská - Technická univerzita Ostrava
- Fakulta:Fakulta elektrotechniky a informatiky
- Kategorie:Technika » Informatika
- Předmět:-
- Studijní obor:-
- Ročník:-
- Formát:PDF dokument (.pdf)
- Rozsah A4:261 stran
Tento učební text má sloužit jako základní studijní materiál pro kursy teoretické informatiky zabývající se teorií jazyků a automatů a teorií algoritmické vyčíslitelnosti a složitosti. Text existuje ve dvou verzích. Základní verze je určena pro kurs „Úvod do teoretické informatikyÿ (ÚTI) v bakalářském studiu, rozšířená verze pak pro kurs „Teoretická informatika (TI) v magisterském studiu. Nepředpokládá se ovšem, že v omezeném čase bakalářského kursu se probere celá základní verze; ta má posloužit vedoucímu kursu k sestavení konkrétního plánu typicky zahrnujícího (jen) podmnožinu látky obsažené ve studijním textu. Rozšířená verze obsahuje verzi základní a navíc je obohacena o kapitoly označené jako „rozšiřující část. Text byl použit (a dopracován) v bězích kursů ÚTI a TI v letním semestru r. 2006/07; pro další běhy je plánováno další vylepšování a doplňování.
V této úvodní sekci je podán stručný nástin obsahu textu a jsou uvedeny pokyny ke studiu; sekce je zakončena poznámkami o vzniku textu a poděkováním lidem, kteří k němu významně přispěli.
V této úvodní sekci je podán stručný nástin obsahu textu a jsou uvedeny pokyny ke studiu; sekce je zakončena poznámkami o vzniku textu a poděkováním lidem, kteří k němu významně přispěli.
Klíčová slova:
formální jazyky
automaty
bezkontextové jazyky
složitost
vyčíslitelnost
algoritmy
Obsah:
- Úvod 1
1 Základní pojmy 7
1.1 Množiny 7
1.2 Relace 11
1.2.1 Ekvivalence 13
1.2.2 Uspořádání 13
1.3 Funkce 15
1.4 Grafy 17
1.5 Stromy 20
1.6 Výroková logika 21
1.7 Další značení 23
1.8 Cvičení 24
2 Formální jazyky 29
2.1 Formální abeceda a jazyk 29
2.2 Některé operace s jazyky 35
2.3 Cvičení 40
3 Konečné automaty a regulární jazyky 45
3.1 Motivační příklad 45
3.2 Konečné automaty jako rozpoznávače jazyků 53
3.3 Modulární návrh konečných automatů 61
3.4 Dosažitelné stavy, normovaný tvar 65
3.5 Cvičení 71
3.6 Minimalizace konečných automatů 74
3.7 Ekvivalence konečných automatů; minimální automaty 82
3.8 Regulární a neregulární jazyky 85
3.9 Nedeterministické konečné automaty 89
3.10 Uzávěrové vlastnosti třídy regulárních jazyků 105
3.11 Cvičení 108
3.12 Regulární výrazy 110
4 Bezkontextové jazyky 119
4.1 Motivační příklad 119
4.2 Bezkontextové gramatiky a jazyky 124
4.3 Jednoznačné gramatiky 133
4.4 Cvičení 136
4.5 Zásobníkové automaty 138
5 Úvod do teorie vyčíslitelnosti 153
5.1 Problémy a algoritmy k jejich řešení 153
5.2 Turingovy stroje 163
5.3 Model RAM (Random Access Machine) 177
5.4 Simulace mezi výpočetními modely; Churchova-Turingova teze 184
5.5 Rozhodnutelnost a nerozhodnutelnost 188
6 Úvod do teorie složitosti 197
6.1 Složitost algoritmů 197
6.2 Asymptotická složitost, odhady řádového růstu funkcí 209
6.3 Polynomiální algoritmy, třídy složitosti, třída PTIME 218
6.4 Nedeterministické polynomiální algoritmy, třída NPTIME 223
6.5 Polynomiální převeditelnost, NP-úplné problémy 229
A Řešení příkladů 235