δ : Q × Σε → P(Q) ükskõik mis tähe puhul või ka ilma sisendita (ε) läheb ühte Q kõigi alamhulkade hulgast. (üleminekufunktsiooni asemel on hoopis relatsioon) Olgu . Siis hulga A alamhulkade hulk on järgmine: Teoreem: Iga mittedeterministik automaat N=(Q, Σ, δ, Q0, F), mis aktsepteerib keelt A, on teisendatav sama keelt aktsepteerivaks deterministlikuks lõplikuks automaadiks M = (Q’, Σ, δ′, Q0′, F′). Kui mittedeterministlikul on k olekut, siis talle vastaval deterministlikul võib olla kuni 2k olekut. T: eeldame, et N-is pole ε-üleminekuid. 4 Regulaarsete avaldiste ja lõplike automaatide samaväärsus. Teoreem: Regulaarse avaldisega defineeritud keel on aktsepteeritav (mittedeterministliku) lõpliku automaadiga. T: vastavalt avadlise struktuurile saame rekursiivselt teha automaadi: Teoreem: Lõpliku automaadi poolt aktsepteeritav keel on defineeritav regulaarse avaldisega.
3. Kuidas mõjutab looduslik valik populatsiooni geneetilist struktuuri? Looduslik valik saab mõjutada järglaspõlvkondade geneetilist struktuuri ainult nende tunnuste kaudu, mille individuaalsed erinevused väheselgi määral sõltuvad genotüübist. 4. Milles seisneb loodusliku valiku evolutsiooniline tähtsus? Darwini teooria, mille kohaselt liikide evolutsioon toimub loodusliku valiku toimel, lähtub eeldusest, et organismide tunnused on vanematel ja järglastel mittedeterministlikul kombel erinevad. Seega vanemad ja nende järglased on üksteisest siiski erinevad. 5. Mis on suguline valik ? Suguline valik on emas- või isasisendite poolt teostatav sugupartneri valik mingite isendite kvaliteeti näitavate omaduste alusel. 6. Milles seisneb stabiliseeriva valiku tähtsus? Stabiliseeriv valik ehk säilitav valik on loodusliku valiku vorm, mis mõjub mingile liigile suhteliselt püsivas elukeskkonnas. Stabiliseeriva valiku mõjul väheneb
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. Graafis kõigi tippude läbimiseks lühima tee leidmine. NPC klass NP ülesannete grupid, mis on taandatavad teineteisele. Näiteks on kõik eelnevad ülesanded taandatavad seljekotiülesandele.
annaabi.ee 
