Algoritmas nusako efektyviai įvykdomus žingsnius; sprendimo procedūra turi baigti darbą su kiekviena leistina įvestimi.
Esminės žinios
Algoritmas nusako apskaičiuojamus žingsnius rezultatui gauti. Uždavinio, kurio atsakymas yra „taip“ arba „ne“, sprendimo procedūra turi pateikti teisingą atsakymą ir baigti darbą su kiekviena įvestimi iš deklaruotos jos taikymo srities.
Sąlygos ir taikymo ribos
Nurodykite įvesties pateikimo būdą, leistinas operacijas ir reikalaujamą rezultatą.
Procedūra, kuri su kai kuriomis įvestimis gali veikti amžinai, nėra visur apibrėžta to uždavinio sprendimo procedūra.
Šaltiniai · 4
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Efektyviai įvykdomi žingsniai ir visur apibrėžtai sprendimo procedūrai keliami reikalavimai.
2026-10-10 · Žodyno apibrėžtis palyginta su Kembridžo pateiktu sprendimo uždavinio aprašu.
Pagrindinių žinių peržiūra
2026-10-10 · Fresh primary-source inspection of the complete compact record, including every statement, equation, quantity and material condition, followed by independent AI editorial review. This check does not certify all linked lessons or every passage of every cited publication.
Šaltiniai iš kitų vietų
Skiriasi taikymo ribos ar susitarimas
A computational method maps declared inputs to outputs, illustrated by a finite-list procedure.
This practical course does not independently formalise every total decision-procedure condition.
University of Helsinki, Department of Computer Science
Nėra algoritmo, kuris visada baigtų darbą ir kiekvienai programos bei įvesties porai Tiuringo pilname skaičiavimo modelyje teisingai nustatytų, ar ta programa galiausiai sustos su ta įvestimi.
Neneigiamoms sąnaudų funkcijoms T(n)=O(g(n)) reiškia, kad egzistuoja konstantos c>0 ir n₀, tokios, kad T(n)≤cg(n) kiekvienam n≥n₀. Nurodant laiko ar atminties sudėtingumo rėžį, būtina apibrėžti skaičiavimo modelį, įvesties dydžio matą ir analizuojamą atvejį.
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. Jis vieną kartą perskaito baigtinę simbolių eilutę, ją priima, kai galutinė būsena priklauso F, ir atpažįsta reguliariąją kalbą.
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. Kiekviename žingsnyje intervale išsaugomi visi galimi atitikmenys, o jo dydis sumažinamas perpus.
Norint gauti didžiausią suderinamų intervalų skaičių, reikia pakartotinai rinktis anksčiausiai pasibaigiantį iš likusių intervalų ir atmesti su juo persidengiančius intervalus. Pakeitus pirmąjį optimalaus sprendinio intervalą šiuo pasirinktu intervalu, galimų likusių intervalų aibė negali sumažėti; tuo grindžiamas įrodymas sukeitimu. Rikiuojant pagal pabaigos laiką, laiko sudėtingumas yra O(n log n).
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ą. Pasirinktos vienodo svorio briaunos nebūtinai priklauso kiekvienam optimaliam sprendiniui.