Výpočetní strom - Computation tree

A výpočetní strom je reprezentace pro výpočetní kroky a nedeterministický Turingův stroj na zadaný vstup.[1] Výpočet strom je zakořeněný strom uzlů a hran. Každý uzel ve stromu představuje jeden výpočetní stav, zatímco každá hrana představuje přechod k dalšímu možnému výpočtu. Počet uzlů stromu je velikost stromu a délka cesty od kořene k danému uzlu je hloubka uzlu. Největší hloubka výstupního uzlu je hloubka stromu. Listy stromu se nazývají výstupní uzly.

Ve výpočetním stromu pro a rozhodovací problém, každý výstupní uzel je označen Ano nebo Ne Pokud strom, T, se vstupním prostorem X, pokud a cesta pro x končí v uzlu označeném jako ano, pak je akceptován vstup x. Jinak je odmítnuta.[2]

Hloubka výpočetního stromu pro daný vstup je výpočetní čas pro Turingův stroj na tomto vstupu.[1]

Výpočetní stromy byly také použity ke studiu výpočetní složitosti problémů v systému Windows výpočetní geometrie a reálné číslo výpočty.[3][4]

Reference

  1. ^ A b Griffor, E. R. (1999), Příručka teorie vypočítatelnosti „Studium logiky a základy matematiky, 140, Elsevier, s. 595, ISBN  9780080533049.
  2. ^ Moret, Bernard M. E. (1998), Teorie výpočtu, Addison-Wesley, str. 338, ISBN  9780201258288.
  3. ^ Ben-Or, M. (1983), „Dolní hranice pro algebraické výpočetní stromy“, Proc. 15. Annu. Symp. Teorie výpočtu, str. 80–86, doi:10.1145/800061.808735.
  4. ^ Grigorjev, Dima; Vorobjov, Nicolai (1996), „Spodní hranice složitosti pro výpočetní stromy se základními branami transcendentální funkce“, Teor. Comput. Sci., 157: 185–214, doi:10.1016 / 0304-3975 (95) 00159-X.