"lahenduvateks" - 1 õppematerjal

Teoreetilibe informaatika kordamisküsimused

Turingi masina mahuline keerukus S(M) n mitu pesa kulub Magasinmäluga masina ajaline keer ­ üleminekute arv Mahuline ­ magasini täituvus. Ajaline keerukus ­ algoritmi n-astmelise sisendi jaoks tehtav sammude arv f(n). Asümptootilised hinnangud sisendandmete mahu piiramatul kasvamisel. Polünomiaalse keerukusega algoritmid: O(nd) Ülesanded, mille jaoks leidub polünomiaalse keerukusega algoritm, nim reaalselt lahenduvateks. Keskmine ja halvim keerukus. 34. NP ja NP-täielikud ülesanded. Ülesannete keerukuse klassid. Põhiline on polünomiaalse keerukusega ülesannete klass ­ reaalselt lahenduvad. NP ­ mittedeterministlikult polünomiaalne. Ülesanded, mis on lahendatavad mittedeterministlikul Turingi masinal polünomiaalse ajaga. Nt lausearvutuse valemis true leidmine. Seljakotiülesanne (leia max erinevaid asju seljakotti, nii, et ei ületataks kaalu). Graafis tee leidmine Hamiltoni meetodil.