Ciklo invariantai ir visiškas korektiškumas
Invariantas nustato korektiškumą tik įvykdžius jam taikomas įrodymo pareigas.
Esminės žinios
Ciklo įrodymas pradžioje nustato invariantą, išsaugo jį per kiekvieną iteraciją, vykdomą esant teisingai ciklo sąlygai, ir kartu su klaidinga sąlyga iš jo išveda baigiamąją sąlygą. Visiškam korektiškumui taip pat būtinas baigimas, pavyzdžiui, griežtai mažėjantis neneigiamas sveikasis variantas.
Sąlygos ir taikymo ribos
- Pradinė sąlyga turi užtikrinti invarianto galiojimą prieš ciklą, o ciklo kūnas turi išsaugoti invariantą.
- Vien invarianto išsaugojimas neįrodo nei reikiamo rezultato gavimo, nei ciklo baigtinumo.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Invarianto galiojimas prieš ciklą, jo išsaugojimas, galutinė sąlyga išėjus iš ciklo ir mažėjantis variantas gerai pagrįstoje aibėje; dvejetainės paieškos pavyzdys.
2026-10-10 · Keturios įrodymo prievolės; netikrinta programa nesertifikuojama.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-loop-invariants
- Versija
- university-reference.1
- Struktūruotas žinyno įrašas
- Universitetinis žinynas