Vyčíslitelnost a složitost, kapitola první, základní pojmy, potenční množina, schéma zápisu problému, algoritmická řešitelnost, Turingův stroj.
Pro pochopení vyčíslitelnosti a složitosti budeme potřebovat znát následující základní pojmy, které se budou dále objevovat v textu.
Definice 1: Potenční množina
Potenční množina je taková množina Ρ(M), která obsahuje všechny podmnožiny množiny M.
Definice 2: Schéma zápisu problému
Problém XY: název problému
Instance: popis vstupu (zadání) problému
Výsledek: popis výstupu (výsledku) dané instance; v určitých případech může být Výsledek
nahrazen Otázkou, na kterou lze odpovědět ANO nebo NE
Vlastnosti problémů
Definice 3: Algoritmická řešitelnost
Problém je algoritmicky řešitelný, pokud existuje algoritmus, který na vstupu přijme specifikovanou instanci problému a pro každou takovou instanci vrátí výstup, který je očekávaným výsledkem a výpočet vždy skončí.
Příklad:
Problém XY: druhá mocnina čísla
Instance: přirozená čísla
Výsledek: přirozená čísla
Definice 4: Algoritmická rozhodnutelnost
Problém je algoritmicky rozhodnutelný, pokud existuje algoritmus, který na vstupu přijme specifikovanou instanci problému a pro každou takovou instanci vrátí výstup ANO nebo NE a výpočet vždy skončí.
Příklad:
Problém XY: lichá čísla
Instance: přirozená čísla
Výsledek: Je číslo liché?
Definice 5: Částečná rozhodnutelnost
Problém je částečně rozhodnutelný, pokud existuje algoritmus, který na vstupu přijme specifikovanou instanci problému a pro každou instanci, pro kterou vrátí výstup ANO, výpočet skončí.
Turingův stroj
Turingův stroj je velice podobný konečným automatům, je shodně tvořen sadou přechodových funkcí (řídícím mechanizmem) a vstupními daty, které si u Turingova stroje představujeme jako nekonečně dlouhou pásku. Tato páska je ukončena z levé strany, pravá strana putuje až do nekonečna. Zásadní rozdíl je v pohybu stroje, kdy po vstupní pásce se může posunovat jak dopředu tak i dozadu hlava, jež dokáže nejen číst, ale i zapisovat data. Další rozdíl oproti konečným automatům je ten, že žádný počáteční stav nesmí být shodný s žádným koncovým stavem.
Turingův stroj může využívat pásku stejným způsobem jak paměť. Může na ni ukládat data, která později použije ke své činnosti. Může část dat, která jsou zapsána na pásce, přeskočit a pokračovat úsekem, který začíná dál od aktuální pozice čtecí/zapisovací hlavy. V případě, že Turingův stroj používá pásku jako paměť, může si jednotlivé úseky paměti označit speciálními znaky, aby měl k jejich následnému využití lepší přístup. Z tohoto důvodu rozeznáváme u Turingova stroje dvě abecedy:
- vstupní abeceda – konečná množina symbolů vstupních dat
- pásková abeceda – konečná množina symbolů, které Turingův stroj umí číst a zapisovat
Prázdné pole na pásce je označováno znakem # (blank). Páska obsahuje vstupní řetězec, za kterým se nachází již jen samé znaky # až do nekonečna. Vymažeme-li z pásky nějaký symbol, bude nahrazen tímto prázdným polem #.
Definice 6: Turingův stroj
Turingův stroj je algoritmus, který obsahuje stavy, ve kterých se může nacházet, vstupní a páskovou abecedu, přechodové funkce, pomocí nichž se dostáváme z jednoho stavu do dalšího, počáteční stav a seznam koncových stavů: M = (Q, Σ, Γ, δ, q0, F), přičemž
- Q – konečná neprázdná množina všech stavů
- Σ – konečná neprázdná množina symbolů bez znaku #, tedy vstupní abeceda
- Γ – konečná neprázdná množina symbolů včetně množiny Σ, tedy pásková abeceda
- δ – přechodové funkce, stanoví do kterého stavu má přejít, jaký symbol zapsat, kam posunout čtecí hlavu (L = doleva, R = doprava, N = neposouvat), a to v závislosti na stavu původním a znaku, který se zde nachází
- q0,očáteční stav
- F – množina koncových stavů
Definice 7: Konfigurace Turingova stroje
Konfigurace Turingova stroje je prvek (slovo) uqv, přičemž q ∈ Q, u,v ∈ Σ. Počáteční konfigurace je q0w, přičemž w ∈ (Σ \ {#}).
Příklad:
Konfigurace Turingova stroje abcq0abcd znamená, že stroj se nachází ve stavu q0 a na pásce je uloženo slovo abcabcd, přičemž hlava je umístěna na čtvrtém symbolu zleva, teda nad písmenem a.
Přihlaste se k odběru novinek.