Žinių pagrindai

Grafai vaizduoja porinius ryšius; medžiams taikoma acikliškumo sąlyga.

Sąsaja apibrėžia operacijas; įgyvendinimas lemia sąnaudas.

Invariantas nustato korektiškumą tik įvykdžius jam taikomas įrodymo pareigas.

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ė.

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ų.

Surikiuotame masyve su tiesiogine prieiga palyginkite ieškomą reikšmę su viduriniu raktu ir atmeskite tą pusę, kurioje jos negali būti; kartokite, kol rasite atitinkantį raktą arba likęs intervalas bus tuščias.

Padalyti masyvą į dvi beveik lygias dalis, kiekvieną rekursyviai surikiuoti ir sulieti surikiuotas dalis, pakartotinai parenkant kitą raktą pagal rikiavimo tvarką.

Norint gauti didžiausią suderinamų intervalų skaičių, reikia pakartotinai rinktis anksčiausiai pasibaigiantį iš likusių intervalų ir atmesti su juo persidengiančius intervalus.

Jungiame neorientuotame svoriniame grafe, jei pasirinktų briaunų aibė priklauso kuriam nors minimaliam jungiamajam medžiui ir nė viena iš šių briaunų nekerta pjūvio, galima pridėti mažiausio svorio šį pjūvį kertančią briauną ir išlaikyti šį invariantą.

Nagrinėkite briaunas nemažėjančia svorių tvarka: pridėkite briauną tada ir tik tada, kai jos galinės viršūnės priklauso skirtingoms esamoms jungumo komponentėms, o tada tas komponentes sujunkite.

Pridėkite elementą į masyvo galą, jei jame yra laisvos vietos; masyvui užsipildžius, skirkite dvigubai didesnę talpą ir nukopijuokite esamus elementus.

Srautas orientuotame tinkle neviršija neneigiamų pralaidumų ir tenkina srauto tvermę visose viršūnėse, išskyrus šaltinį s ir santaką t.

Pradėjus nuo nulinio srauto, paieška į plotį randamas trumpiausias s–t kelias liekamajame tinkle, o srautas padidinamas mažiausiu šio kelio liekamuoju pralaidumu, atnaujinant tiesioginių ir atvirkštinių briaunų pralaidumus.

Turint N kompleksinių koeficientų aⱼ, apibrėžiama yₖ=Σ_(j=0)^(N−1)aⱼωᴶᴷ, kur ω=e²πⁱ⁄ᴺ.

Kai N yra dvejeto laipsnis, suskirstykite daugianario koeficientus pagal lyginius ir nelyginius indeksus, rekursyviai transformuokite kiekvieną pusę ir sujunkite reikšmes pagal p(z)=p_even(z²)+zp_odd(z²).

Turint n įrašų su sveikaisiais raktais 0≤k<U, pagal raktą pridėti įrašus į U krepšelių galus, išlaikant įterpimo tvarką, tada sujungti krepšelius raktų didėjimo tvarka.

Neneigiamus sveikuosius raktus išreikškite d skaitmenų B pagrindo sistemoje ir stabiliai rikiuokite pagal kiekvieną skaitmenį nuo mažiausiai iki labiausiai reikšminio.

Baigtinio orientuotojo grafo viršūnes galima išdėstyti taip, kad kiekvienai briaunai u→v viršūnė u eitų prieš v, tada ir tik tada, kai grafas yra aciklinis.

Baigtiniame orientuotajame acikliame grafe (DAG) su sveikaisiais briaunų svoriais nustatykite d(s)=0, o kitoms viršūnėms – d(v)=∞, apdorokite viršūnes topologine tvarka ir relaksuokite kiekvieną išeinančią briauną u→v pagal d(v)←min(d(v),d(u)+w(u,v)).

Eilučių sufiksų A[i:],B[j:] ilgiausio bendro posekio ilgį pažymėkime L(i,j).