"lindipositsioonide" - 1 õppematerjal

Rekursiooni ja keerukusteooria eksami konspekt

(vasaktuletust). Kas aga neil keeltel on ühisosa? See on Posti vastavuse probleem, mis pole lahenduv. 28 Algoritmide keerukuse hindamine. Algoritmi keerukuse sõltuvus arvutamismudelist. DEF: Algoritmi keerukus on funktsioon f : N → N, mis seab sisendandmete mahule n vastavusse algoritmi sammude arvu (ajaline keerukus) või kasutatava mälu mahu (mahuline keerukus). ajaline keerukus – taktide / konfiguratsioonide arv; 
 mahuline keerukus – kasutatud lindipositsioonide arv. Teoreem: Olgu t(n) > n. Iga mitme lindiga Turingi masinal ajalise keerukusega O(t(n)) töötava programmi jaoks leidub ekvivalentse funktsionaalsusega programm ühe lindiga Turingi masinal, nii et tema ajaline keerukus on O(t2(n)). Teoreem: Olgu t(n) > n. Iga ühe lindiga mittedeterministlikul Turingi masinal ajalise keerukusega O(t(n)) töötava programmi jaoks leidub ekvivalentse funktsionaalsusega programm ühe lindiga deterministlikul