Žinių pagrindai

Sukurkite patikrinamą fizikos tyrimo įrašą, patikrinkite ir patikslinkite vežimėlio modelį su apibrėžtomis ribomis, išsaugokite duomenų apdorojimo istoriją ir suplanuokite, kaip užtikrinti duomenų surandamumą bei tinkamas dalijimosi sąlygas.

Bitas turi dvi galimas būsenas; fiksuoto ilgio dvejetainis žodis be ženklo koduoja sveikąjį skaičių.

Šenono entropija matuoja neapibrėžtį nurodytame tikimybių skirstinyje.

Algoritmas nusako efektyviai įvykdomus žingsnius; sprendimo procedūra turi baigti darbą su kiekviena leistina įvestimi.

Bendrajame skaičiavimo modelyje nėra visur apibrėžto algoritmo, kuris nustatytų, ar programa sustos, kiekvienai programai ir įvesčiai.

Didysis O nusako augimo viršutinį rėžį: nuo tam tikro įvesties dydžio nagrinėjama funkcija neviršija pastoviu daugikliu padaugintos palyginamosios funkcijos.

Deterministinį baigtinį automatą sudaro baigtinė būsenų aibė Q, baigtinė abėcėlė Σ, visur apibrėžta perėjimo funkcija δ:Q×Σ→Q, pradinė būsena q₀ ir priimančiųjų būsenų aibė F.

Reguliariosios išraiškos, sudarytos iš raidžių, tuščiojo žodžio ir tuščiosios kalbos taikant sąjungą, konkatenaciją ir Kleene žvaigždę, aprašo tiksliai tas kalbas, kurias atpažįsta DFA arba NFA.

Bekontekstę gramatiką sudaro baigtinė kintamųjų aibė, terminalinių simbolių abėcėlė, taisyklės A→w, kurių kairėje pusėje yra vienas kintamasis, ir pradinis kintamasis.

Nedeterministinis dėklinis automatas papildo baigtinį valdymo mechanizmą vienu neriboto dydžio dėklu, kuriame paskutinis įdėtas elementas išimamas pirmas.

Atpažintuvas priima kiekvieną savo kalbos žodį, tačiau gavęs kalbai nepriklausantį žodį gali veikti be galo.

Kiekvienai netrivialiai kalbos savybei klausimas, ar Tiuringo mašinos atpažįstama kalba ją turi, yra algoritmiškai neišsprendžiamas pagal mašinos aprašą.

Jei sąnaudos f,g yra neneigiamos nuo tam tikro momento, f=Θ(g) reiškia, kad c₁g(n)≤f(n)≤c₂g(n) visiems pakankamai dideliems n, kai konstantos c₁,c₂>0.

Jei operacija i pakeičia būseną Dᵢ₋₁ į Dᵢ, apibrėžiame ĉᵢ=cᵢ+Φ(Dᵢ)−Φ(Dᵢ₋₁).

3CNF formulėje su m klauzulių kiekvienam literalo pasirodymui sukurkite viršūnę.

Fiksuotą deterministinę Tiuringo mašiną su baigtiniu juostų skaičiumi, veikiančią per laiką t(n)≥n, galima imituoti vienajuoste mašina per O(t(n)²) laiką, saugant juostų turinį bei galvučių žymeklius ir peržiūrint juos kiekviename imituojamame žingsnyje.

Deterministinio sprendimo algoritmo laiko sąnaudos matuojamos žingsnių skaičiumi, o atminties sąnaudos – naudojamų atminties langelių skaičiumi; blogiausio atvejo ribos nustatomos imant maksimumą tarp vienodo užkoduoto ilgio įvesčių.

Jei kalba yra reguliarioji, egzistuoja toks p≥1, kad kiekvieną priimamą žodį x, kurio |x|≥p, galima išskaidyti į uvw taip, kad |uv|≤p, |v|≥1 ir uvᵐw būtų priimamas visiems m≥0.

Kalba {0ⁿ1ⁿ:n≥0} nėra reguliarioji.

DFA kalba yra tuščia tada ir tik tada, kai iš jo pradinės būsenos nepasiekiama jokia priimančioji būsena.

Baigtinės bekontekstės gramatikos kalbos priklausymo problema yra išsprendžiama: gramatika pertvarkoma į Chomskio normaliąją formą ir netuščiam įvesties žodžiui išvardijami riboto ilgio išvedimai.

Baigtinės bekontekstės gramatikos atveju lentelėje Iⱼ saugomos taisyklės su tašku [A→β·γ,k], kur k yra pradžios pozicija.

Kai T(n)=aT(n/b)+f(n), T(1)=Θ(1), pažymėkime q=log_b a.

DSPACE(s(n)) ir NSPACE(s(n)) apima sprendimo uždavinių kalbas, kurias deterministinės ir nedeterministinės Tiuringo mašinos atpažįsta naudodamos O(s(n)) darbinės atminties.

Laiko riba t(n)≥n čia vadinama konstruojama laiko atžvilgiu, jei Tiuringo mašina, gavusi unarinę įvestį 1ⁿ, gali per O(t(n)) laiko užrašyti 1ᵗ⁽ⁿ⁾.

Jei s(n)≥log n yra pagal atmintį konstruojama funkcija, tai NSPACE(s(n))⊆DSPACE(s(n)²).

Logaritminės atminties daugelio į vieną redukcija apskaičiuoja f taip, kad x∈A tada ir tik tada, kai f(x)∈B, naudodama tik skaitomą įvestį, O(log n) darbinę juostą ir tik rašomą išvestį.

NL=coNL: nedeterministine logaritmine atmintimi sprendžiamų kalbų papildiniai taip pat priklauso NL.

Laiko požiūriu konstruojamoms funkcijoms f,g≥n, kurioms f(n)log f(n)=o(g(n)), DTIME(f(n)) yra tikrasis DTIME(g(n)) poaibis.

Jei S yra atminties požiūriu konstruojama funkcija, S(n)≥n ir s(n)=o(S(n)), tai DSPACE(s(n))⊊DSPACE(S(n)).