Teorie složitosti: Porovnání verzí
Smazaný obsah Přidaný obsah
m Robot: přidáno {{Autoritní data}}; kosmetické úpravy |
m Úprava rozcestníku za pomoci robota: Graf - změna odkazu/ů na Graf (teorie grafů) |
||
Řádek 21:
Rozhodovací problém je jeden ze základních typů problémů teorie složitosti, který má pouze dva možné výstupy ANO či NE. Případně [[Dvojková soustava|binárně]] 0 nebo 1. V [[Formální jazyk|jazyku]], kde členy jazyka jsou případy s odpovědí ANO a ostatní členy s odpovědí NE. Je třeba pomocí algoritmu rozhodnout, jakým způsobem zadaný vstup s tímto jazykem odpovídá. Jestliže algoritmus vrátí ANO pak je vstup přijat, jinak odmítnut. Algoritmus počítá [[charakteristická funkce|charakteristickou funkci]] jazyka.
Příkladem rozhodovacího problému je [[Graf (teorie grafů)|graf]] a máme rozhodnout zda je to [[souvislý graf]] či ne. Formální jazyk je pak množina všech souvislých grafů a pouze je třeba rozhodnout, jak graf reprezentovat v binární podobě.
Formální jazyky (a problémy nad nimi) jsou nad nějakou abecedou, která nemusí být nutně binární.
| |||