Бағдарламаның дұрыстығын дәлелдеу әдісмтемесі

Қарастырылп отырған әдістеме төбелеріне жады операторлары, ал доғаларына оператордан операторға көшу сәйкестендірілген граф түріндегі алгоритмдердің дұрыстығын дәлелдеуге арналған. Бір төбені кіріс төбесі деп аламыз, оған бағдарламаның орындаулы басталатын оператор сәйкес келеді, ал шығыс төбелері бірнеше болуы мүмкін.Кіріс және шығыс төбелері сәйкесінше кіріс және шығыс тілдерімен белгіленген деп есептейміз.

Алгоритмнің дұрыстығын дәлелдеу дегеніміз төмендегідей тұжырымды дәлелдеу деген сөз: «Егер кіріс деректері кіріс шартын қанағаттандырса, онда алгоритм ақырлы қадамнан кейін жұмысын тоқтатып, шығыс деректері талап етілген шығыс шартына сейкес келеді».

Тәжірибе жүзінде, мұндай тұжырымды 2-ге бөледі:

«Егер кіріс деректері кіріс шартын қанағаттандырса, онда алгоритм ақырлы қадамнан кейін жұмысын тоқтатып, шығыс деректері талап етілген шығыс шартына сейкес келеді».

«Егер кіріс деректері кіріс шартын қанағаттандырса, онда алгоритм ақырлы қадамдардан кейін жұмысын аяқтайды».

(1) тұжырым ғана дәлелденген алгоритм жартылай дұрыс немесе жартылай түзетілген деп аталады. Егер де (1) және (2) бар болса, онда алгоритм дұрыс немесе түзелген деп аталады.

(2) тұжырымды дәлелдеу жеңе алмайтын қиындықтар тудырғанда, (1) ғана дәлелдеумен шектелетіндігін айта кетейік. Мысалға, ұқсастық облысы белгісіз болатын итерациялық алгоритмдер сондай. Ондай кезде, егер алгоритм құптауға болатын уақытта жұмысын аяқтаса, онда жауаптың дұрыстығы кепілденеді.

1. Бинарлық іздеу

Екілік (Бинарлық) іздеу - Сұрыпталған массив элементтерінің классикалық алгоритмделініп ізделінуі. Яғни, х қатарының у берілген санын немесе бөлімін табу үшін, оны жақындаған сайын екіге бөліп отыру болып табылады.

Бинарлық іздеу ағашы бинарлы ағаш мәліметтер құрылымы. Әр түйіннің ішінде кілт және массив элементтерінің мәні болады. Ішкі сол ағаштың түйіндерінің кілттері ішкі оң жақ ағаштарының түйіндерінің кілттерінен кіші болады.

1. Бөліп ал да басқар принципіне негізделген алгоритмдерді талдау.