Žinių pagrindai

Kai Y=X+Z, o Z∼N(0,N) yra nepriklausomas nuo įėjimo realusis Gauso triukšmas, kurio reikšmės nepriklausomos ir vienodai pasiskirsčiusios, N>0, ir vidutinė įėjimo galia E[X²]≤P, kanalo pralaidumas yra C=(1/2)log₂(1+P/N) bitų vienam kanalo panaudojimui.

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.

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ᵢ₋₁).

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

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

Virš F₂ imkime H=[A|Iₘ] ir G=[Iₙ₋ₘ;A].

Gautam r=c+e, kai Hc=0, sindromas yra Hr=He.

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

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²).

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.

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

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.