|
1-ma’ruza. Algoritm tushunchasi. Algoritmni asosiy ta`riflari, xossalari va ularning turlari Oddiy klassik algoritmlar. Algoritm tushunchasi
|
| bet | 6/9 | | Sana | 17.05.2024 | | Hajmi | 48,86 Kb. | | #240309 |
Bog'liq 1-MavzuIkkinchi yoʻnalish algoritm tushunchasini bevosita aniqlash bilan bogʻliq: 1936-1937-yillarda, A.Tyuring3 Chyorch ishlaridan bexabar holda yangi funksiyalar sinfini kiritdi. Bu funksiyalarni “Tyuring boʻyicha hisoblanuvchi funksiyalar” deb atadilar. Bu sinf ham yuqorida aytilgan xossalarga ega edi va buni Tyuring tezisi deb aytamiz. 1937-yilda A.Tyuring isbotladiki, uning hisoblanuvchi funksiyalari -aniqlanuvchi funksiyalarning oʻzi va, demak, umumrekursiv funksiyalarning xuddi oʻzi ekan. Shuning uchun Chyorch tezisi bilan Tyuring tezisi ekvivalentdir.
1936-yilda E. Post (Tyuring ishlaridan bexabar holda) aynan Tyuring erishgan natijalarga mos keladigan natijalarni e’lon qildi va 1943-yilda, 1920-1922-yillardagi nashr etilmagan ishlariga asoslanib, toʻrtinchi ekvivalent tezisni nashr etdi. Shunday qilib, algoritm tushunchasini bevosita aniqlashga va soʻngra uning yordamida hisoblanuvchi funksiya tushunchasini aniqlashga birinchi boʻlib bir-biridan bexabar holda E. Post va A. Tyuring erishdilar.
Post va Tyuring algoritmik jarayonlar ma’lum bir tuzilishga ega boʻlgan “mashina” bajaradigan jarayonlar ekanligini koʻrsatishdi. Ular ushbu “mashinalar” yordamida barcha hisoblanuvchi funksiyalar sinfi bilan barcha qismiy rekursiv funksiyalar sinfi bir xil ekanligini koʻrsatdilar va demak, Chyorch tezisining yana bitta fundamental tasdigʻi yuzaga keldi.
Uchinchi yoʻnalish – Rossiya matematigi A.Markov4 tomonidan ishlab chiqilgan normal algoritmlar tushunchasi bilan bogʻliq.
1.3. Algoritmlarning murakkabligi
Algoritmlarning murakkabligi. Hisoblash muammolari cheklangan xotira resurslaridan foydalangan holda oqilona vaqt ichida yechilishi kerak. Bu algoritmning vaqt va fazoviy murakkabligi tushunchasiga olib keladi. Qoida tariqasida, algoritm turli vaqtlarni bajarishi mumkin boʻlgan turli xil amallarni oʻz ichiga oladi.
Algoritmlarni baholash uchun koʻpgina mezonlar mavjud. Odatda kirituvchi berilganlarni koʻpayishida masalani yechish uchun kerak boʻladigan vaqt va xotira hajmlarini oʻsish tartibini aniqlash muammosi qoʻyiladi. Har bir aniq masala bilan kiritiladigan berilganlarni miqdorini aniqlovchi qandaydir sonni bogʻlash zarur. Bunday son masalaning kattaligi deb qabul qilinadi. Masalan, ikkita matritsani koʻpaytirish masalasining oʻlchami boʻlib, matritsalar kattaligig xizmat qilishi mumkin. Graflar haqidagi masalada oʻlcham sifatida graf uchlarining soni boʻlishi mumkin.
Algoritm sarflanayotgan vaqt masalaning oʻlchami funksiyasi sifatida algoritmni vaqt boʻyicha qiyinligi deb nomlanadi. Bunday funksiyaga masalaning kattaligi oshganda limit ostidagi oʻzgarish asimptotik qiyinlik deb aytiladi.
|
|
Bosh sahifa
Aloqalar
Bosh sahifa
1-ma’ruza. Algoritm tushunchasi. Algoritmni asosiy ta`riflari, xossalari va ularning turlari Oddiy klassik algoritmlar. Algoritm tushunchasi
|
