Žinių pagrindai

Skirtingų raktų palyginimams reikia pakankamai šakų, kad būtų galima atskirti jų išsidėstymo tvarkas.

Paieškos grafuose aplanko pasiekiamas viršūnes skirtinga tvarka.

Briaunų svoriai lemia, kuris trumpiausių kelių metodas tinka.

Baigtinis instrukcijų rinkinys gali valdyti veiksmus neribotoje įrašomojoje juostoje.

Sąryšis yra kortežų iš deklaruotų reikšmių sričių aibė.

Mikrobūsenų tikimybės kiekybiškai nusako statistinę entropiją.

Tankio operatorius aprašo kvantines statistines būsenas.

Bendroji grynoji būsena gali būti neišreiškiama posistemių būsenų tenzorine sandauga.

Imti imtis iš jungtinio įėjimo dydžių modelio, siekiant apytiksliai nustatyti išėjimo dydžio skirstinį.

Maišos lentelė priskiria raktus lizdams, o kolizijas sudarančius raktus saugo grandinėje.

AVL dvejetainiame paieškos medyje kiekvienos viršūnės pomedžių aukščiai skiriasi ne daugiau kaip vienetu.

Dvejetainė maksimumo krūva masyve saugo dvejetainį medį, kurio visi lygiai, išskyrus galbūt paskutinį, užpildyti, o paskutinio lygio viršūnės išdėstytos iš kairės į dešinę be tarpų; kiekvienos tėvinės viršūnės raktas yra ne mažesnis už jos vaikų raktus.

Sudarykite maksimumo krūvą, sukeiskite jos šaknį su paskutiniu aktyviu elementu, sumažinkite aktyvią krūvą ir atkurkite krūvos tvarką; kartokite.

Dinaminio programavimo metu apibrėžiami daliniai uždaviniai ir rekurentiniai sąryšiai, tikrinama aciklinė priklausomybių tvarka ir baziniai atvejai, o kiekvienas reikalingas dalinis uždavinys sprendžiamas vieną kartą, įsimenant rezultatus arba sprendžiant nuo mažesnių uždavinių prie didesnių.

Teigiamiems sveikiesiems skaičiams a₁,…,aₙ ir tikslinei sumai T≥0 galioja D(i,t)=D(i−1,t) arba [t≥aᵢ ir D(i−1,t−aᵢ)], kur D(0,0)=tiesa, o kitos pradinės būsenos yra klaidingos.

Pradžioje nustatoma d(s)=0, o kiti atstumai prilyginami begalybei; tada kiekviena orientuota briauna relaksuojama per |V|−1 iteracijų.

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šą.

Baigtiniams X,Y galioja H(X|Y)=Σy p(y)H(X|Y=y) ir H(X,Y)=H(Y)+H(X|Y).

Baigtiniams skirstiniams p,q galioja D(p‖q)=Σx p(x)log₂[p(x)/q(x)]≥0, o lygybė galioja tada ir tik tada, kai p=q.

Jei baigtinių reikšmių atsitiktiniai dydžiai X→Y→Z sudaro Markovo grandinę, t. y. Z yra sąlygiškai nepriklausomas nuo X, kai žinomas Y, tai I(X;Z)≤I(X;Y).

Dvejetainiame prefiksiniame kode nė vienas visas kodinis žodis nėra kito kodinio žodžio pradinis segmentas, todėl galima iš karto nuosekliai dekoduoti.

Pakartotinai sujunkite du mažiausią tikimybę turinčius šaltinio simbolius arba jau sudarytus mazgus, tada dvi šakas pažymėkite 0 ir 1; žymų sekos kelyje nuo šaknies iki lapo yra kodiniai žodžiai.

Baigtinės abėcėlės nepriklausomiems vienodai pasiskirsčiusiems X₁,…,Xₙ dydis −n⁻¹log₂p(X₁,…,Xₙ) konverguoja pagal tikimybę į H(X₁).

Entropijos sparta yra limₙ H(X₁,…,Xₙ)/n, kai ši riba egzistuoja.

Realiųjų skaičių aibėje apibrėžtam tikimybės tankiui f, kai integralas apibrėžtas, h(X)=−∫f(x)log₂f(x)dx.