§ 23. Паняцце правільнасці і складанасці алгарытму

23.2. Правільнасць алгарытму

Алгарытм валодае ўласцівасцю масавасці, паколькі зыходнымі данымі для яго можа быць любая канечная паслядоўнасць сімвалаў. Алгарытм не валодае гэтай уласцівасцю, калі ён працуе толькі на абмежаваным наборы зыходных даных, але на астатніх наборах не працуе ці працуе няправільна.

Пад уласцівасцю правільнасці разумеюць адпаведнасць вынікаў работы алгарытму ўмове задачы.

Праверыць уласцівасць правільнасці некаторых алгарытмаў дастаткова проста, для гэтага можна ўзяць некалькі прыкладаў зыходных даных, для якіх вынік відавочны, і пратэсціраваць алгарытм на іх, але даказаць правільнасць алгарытму дастаткова складана, бо яго неабходна праверыць на ўсіх магчымых наборах даных (а іх у сілу масавасці можа быць вельмі шмат).

Доказ правільнасці алгарытму называецца верыфікацыяй.

Доказ правільнасці алгарытму — адзін з найбольш цяжкіх, а часам і асабліва стомных этапаў стварэння алгарытму.

Ідэя матэматычнага доказу карэктнасці праграм (верыфікацыі) звычайна зводзіцца да доказу таго факта, што праграма (падпраграма) з’яўляецца карэктнай адносна яе ўваходнай і выхадной спецыфікацыі. Найбольш вядомы метад, які называецца метадам індуктыўных сцверджанняў, быў прапанаваны ў 1967 г. Флойдам, хоць сама ідэя яго ўзыходзіць да Цьюрынга (1950).

Доказ правільнасці пабудаванага алгарытму не можа быць праведзены эксперыментальна, г. зн. з дапамогай прагону праграмы, якая рэалізуе дадзены алгарытм на розных тэстах. Неабходны строгі матэматычны доказ правільнасці.

Прагон праграмы на розных тэстах дазваляе правесці доказ правільнасці работы праграмы ў цэлым. Гэты прыём — самая распаўсюджаная працэдура доказу правільнасці праграмы. Лічыцца, што праграма працуе правільна, калі выдадзеныя ёй адказы могуць быць пацверджаны вядомымі метадамі ці вылічаны ўручную.

Прынцып верыфікацыі быў прапанаваны Венскім кружком у 20-я гг. XX ст. Члены кружка меркавалі, што ў навуцы павінны застацца два класы навуковых прапаноў — аналітычная праўда, якая не мае прадметнага зместу, і фактычная праўда, эмпірычныя факты канкрэтных навук, значэнне якіх можа быць праверана спецыяльным спосабам — прынцыпам верыфікацыі.  Аднак хутка стала відавочным, што такі прамы верыфікацыянізм немагчымы ў тых выпадках, калі мы маем справу з падзеямі мінулага, з агульнымі меркаваннямі і г. д.