MüNDƏrcat mühaziRƏ 1 Verilənlər. Alqoritmlər və verilənlərin strukturu

Alqoritmin Kolmoqorov tərifi: Alqoritm — müəyyən ciddi qaydalar əsasında yerinə yetirilən hesablamalar sistemidir ki, o bir neçə addımdan sonra hökmən qoyulmuş məsələnin həllinə gətirir.
Alqoritmin Markov tərifi: Alqoritm - dəyişən ilkin verilənlərdən axtarılan nəticəyə gətirən hesablama prosesini müəyyən edən dəqiq təlimatdır.
Öz sözlərimizlə alqoritmə belə tərif verə bilərik:
Alqoritm - müəyyən tip məsələlərin həlli üçün sonlu sayda addımlarla ilkin verilənlərdən son nəticə almaq üçün sonlu əməliyyatlar ardıcıllığı və ya təlimatdır.
1931-ci ildə alman riyaziyyatçısı Kurt Hedel (Kıırt Friedrich Gödel) tərəfindən isbat edilmiş teoremi müasir alqoritmlər nəzəriyyəsinin mənbəyi hesab etmək olar. O, göstərdi ki, bəzi riyazi problemlər müəyyən sinif alqoritmlərlə həll edilə bilməz. Hedelin bu işi alqoritm nəzəriyyəsinin inkişafına təkan verdi. Alqoritmlər nəzəriyyəsinə aid ilk sanballı işlər 1930-cu illərin ortalarında Alan Türinq (Alan Mathison luring), Alonzo Çerç (Alonzo Church} və Emil Post (Post Emil Leo) tərəfindən nəşr edildi. Onlar tərəfindən təklif edilmiş Türinq maşını, Post maşını və rekursiv hesablanan Çerç funksiyaları sinfi alqoritmin ilk formal təsvirləri idi ki, bu alqoritmlərdə ciddi hesablama modelləri istifadə olunmuşdu. Bu işlərin inkişafı nəticəsində alqoritmik həll edilməzlik problemlərinin mövcudluğu isbat edildi. Alqoritmik həll edilməzlik o deməkdir ki, elə ümumi alqoritm (Türinq maşını) yoxdur ki, istənilən alqoritmin və onun ilkin verilənlərinin təsvirinə görə, bu verilənlərlə bu alqoritmin icrasının dayanacağını və ya sonsuz işləyəcəyini müəyyən etmək mümkün olsun. Bu problemlərin bir neçəsi ilə tanış olaq.
1. ədədinin yazılışında, məsələn, 9 rəqəminin paylanması.
f(n) = i funksiyasını tapaq. Burada, n - ədədinin onluq yazılışında ardıcıl 9 rəqəmlərinin sayı, i isə n sayda ardıcıl 9 rəqəmləri içərisində, vergüldən sonra ən solda duran 9 rəqəminin sıra nömrəsidir. Məlumdur ki,
= 3,141592 ...və
= 48arctg (1/18) + 24arctcj(l/57) - 20arctg(l/239).
ədədinin qiymətində f(l)=5 olur. Məsələ ixtiyari n üçün f(n) funksiyasını tapmaqdan ibarətdir, äədədi irrasional və transendent ədəd olduğu üçün biz n ədədinin onluq yazılışında 9 rəqəminin və eləcə də digər rəqəmlərin paylanması haqqında heç bir məlumat bilmirik. f(n) funksiyasının hesablanması ədədinin n sayda ardıcıl 9 rəqəmi alınana qədər ayrılması ilə əlaqədardır. Lakin, biz f(n) funksiyasının hesablanması üçün ümumi metod bilmirik, ona görə də bir neçə n üçün hesablama sonsuz davam edə bilər. Biz, hətta, prinsipcə, ixtiyari n üçün məsələnin həllinin olubolmadığını da bilmirik. Bu ədədinin təbiəti ilə bağlıdır.