Hledej
Zobraz:
Univerzity
Kategorie
Rozšířené vyhledávání
12 659 projektů
0 nových
Základy teoretické informatiky
«»
| Přípona |
Typ studijní materiál |
Stažené 0 x |
| Velikost 1,0 MB |
Jazyk český |
ID projektu 10669 |
| Poslední úprava 21.08.2017 |
Zobrazeno 419 x |
Autor: aladeen |
Sdílej na Facebooku |
||
| Detaily projektu | ||
- Cena:
6 Kreditů - kvalita:
72,4% -
Stáhni
- Přidej na srovnání
- Univerzita:Univerzita Palackého v Olomouci
- Fakulta:Přírodovědecká fakulta
- Kategorie:Technika » Informatika
- Předmět:-
- Studijní obor:-
- Ročník:-
- Formát:PDF dokument (.pdf)
- Rozsah A4:92 stran
Tento text distančního vzdělávání si klade za cíl představit čtenáři základní disciplíny teoretické informatiky, konkrétně formální jazyky, automaty, vyčíslitelnost a složitost. Vzhledem k omezenému rozsahu textu jsou v něm zahrnuty pouze nejzákladnější informace z dotyčných disciplín. Pro pochopení látky je nezbytná znalost základů teorie množin, algebry a výrokové logiky včetně odpovídající matematické notace.
Cílová skupina
Text je určen posluchačům bakalářského studijního programu Aplikovaná informatika, provozovanému v kombinované formě na Přírodovědecké fakultě Univerzity Palackého v Olomouci.
Cílová skupina
Text je určen posluchačům bakalářského studijního programu Aplikovaná informatika, provozovanému v kombinované formě na Přírodovědecké fakultě Univerzity Palackého v Olomouci.
Klíčová slova:
formální jazyky
automaty
vyčíslitelnost
Turingovy stroje
složitost
informatika
Obsah:
- 1 Formální jazyky a automaty 4
1.1 Základní pojmy 4
1.2 Chomského hierarchie gramatik 11
1.3 Konečné automaty 14
1.3.1 Nedeterministické konečné automaty 19
1.3.2 Vzájemný vztah nedeterministických a deterministických konečných automatů 21
1.3.3 Vztah konečných automatů k regulárním jazykům 23
1.4 Regulární výrazy 29
1.5 Zásobníkové automaty 36
2 Vyčíslitelnost 47
2.1 Turingovy stroje 47
2.1.1 Nedeterministické Turingovy stroje 53
2.2 Jazyky a problémy 57
2.2.1 Příklad jednoduchého rekurzivního jazyka 57
2.2.2 Konvence pro popis Turingových strojů 59
2.2.3 Churchova-Turingova teze 61
2.2.4 Rozhodovací problémy 62
2.2.5 Problém zastavení Turingova stroje 65
3 Složitost 69
3.1 Úvodní pojmy 69
3.1.1 Složitost Turingova stroje a nedeterministického Turingova stroje 71
3.2 Třídy složitostí P a NP 73
3.3 NP-úplné problémy 81
3.3.1 Vybrané NP-úplné problémy 84
3.4 Využití výpočetně obtížných úloh 88
Rejstřík 91