Alqoritm Alqoritm

Dövrü alqoritm - Alqoritmin hər hansı mərhələsi təkrar-təkrar yerinə yetirilirsə belə alqoritm dövru alqoritm adlanır.

 

 

Alqoritmik problemlərdə ümumiliyi pozmadan həmişə arqumentləri mənfi, olmayan tam qiymətlər alan funksiyanın mənfi olmayan tam qiymətlərinin tapılmasından söhbət gedir. Ümumiliyi pozmadan bunu həmişə qəbul etmək olar. Qiyməti müəyyən alqoritm vasitəsilə tapılan funksiyalara hesablanan funksiyalar deyilir. Bu tərif intuitivdir.

Dəqiq riyazi deyil. Çünki burada alqoritm anlayışından istifadə olunur. Arqumentlərinin heç də hamısında təyin olunmayan funksiyalar, yəni arqumentlərinin müəyyən hissəsində təyin olunmuş funksiyalara qismən funksiyalar deyilir. Qiyməti hər hansı alqoritmin tətbiqi ilə tapıla bilən qismən funksiyalara hesablanan qismən funksiyalar deyilir. Bu vaxta qədər məlum bütün hesablanan qismən funksiyalar məlum olmuşdur ki, qismən rekursiv funksiyalardır. Rekursiv funksiyaların isə ciddi riyazi tərifi var. Bundan sonra biz funksiya dedikdə ilkin verilənlər üzərində müəyyən əməllər ardıcıllığı, yığımı başa düşəcəyik.

Deməli, bizə məlum olan alqoritmin hər birinə biz müəyyən funksiya kimi baxa bilərik. Klini belə bir tezisi irəli sürmüşdür ki, alqoritmik hesablanan qismən funksiyalar sinfi ilə qismən rekursiv funksiyalar sinfi üst-üstə düşür. Qeyd edək ki, hesablanan qismən funksiyaların tərifi intuitiv olduğu halda qismən rekursiv funksiyaların tərifi dəqiq riyazi şəkildə verilir. Klinidən bir qədər əvvəl Çerç belə bir tezis vermişdir ki, hər yerdə təyin olunmuş hesablanan qismən funksiyalar sinfi ilə qismən rekursiv funksiyalar sinfi eynidir.

Bu iki tezis birləşdirilib Klini-Çerç tezisi adı ilə verilir. Tezisin əhəmiyyəti ondan ibarətdir ki, hər hansı problemi əks etdirən funksiyaların rekursiv funksiyalar tərifini ödədiyini bilsək onun həll alqoritminin olduğu birbaşa aydındır. Lakin o, problemi əks etdirən funksiya rekursiv funksiya tərifini ödəmədikdə deyirik ki, Klini-Çerç tezisinə görə həmin məsələnin həll alqoritmi yoxdur. Beləliklə, rekursiv funksiya anlayışını verməliyik. Onun tərifini və xassələrini göstərməklə, alqoritmin tərifini dəqiqləşdirmək olar.

Alqoritmin tərifini dəqiqiləşdirmək üçün yuxarıdakı birinci yanaşmadır. İkinci yanaşma Türinq-Post maşını nəzəriyyəsidir. Türinq-Post bir-birindən asılı olmayaraq elə nəzəri hesablama aparatı yaratmışlar ki, orada funksiyaların qiymətlərini hesablamaq mümkündür. Məlum olmuşdur ki, bu vaxta kimi məlum alqoritmlərin hamısını Türinq-Post maşınında yerinə yetirmək mümkündür. Beləliklə, hər hansı problemi Türinq-Post maşınında həll etmək olursa, deməli, onun həll alqoritmi var. Bu da bir daha Klini-Çerç tezisinə inam yaradır.

Alqoritmin tərifinin dəqiqləşməsi üçün üçüncü yanaşma "Normal-Markov alqoritmi" nəzəriyyəsidir. Bu nəzəriyyəyə görə baxılan problemin ilkin verilənləri sözlər şəklində yazılır. Söz dedikdə müəyyən sonlu simvollar yığımı başa düşülür. Bu nəzəriyyəyə görə hər bir əməliyyat sözlər üzərində əməliyyata gətirilir. Yenə də bu vaxta qədər məlum alqoritmlərin hamısı Normal-Markov alqoritmi vasitəsilə yerinə yetirilə bilir. Deməli, Normal-Markov alqoritmi nəzəriyyəsi də alqoritmin tərifinin dəqiqləşməsidir və Normal-Markov alqoritmi ilə yerinə yetirilən hesablanan funksiya rekursiv funksiyadır. Beləliklə, bu yanaşmaların üçünün də müəyyən mənada ekvivalent olduğu aydın olur.