2- ma`ruza. Saralash algoritmlari. Kvadratik, logarifmik va chiziqli qiyinchilikdagi saralash algoritmlari

2- ma`ruza. Mavhum ma'lumotlar turi(ADT). Algoritmning formal tasnifi. Tasvirlash usullari. Blok-sxema ko`rinishida algoritmni tasvirlash.

dotsent Bo`ronova Gulnora Yodgorovna

Reja:

• Algoritm formal ta`rifi
• Mavhum ma`lumotlar turlari
• Algoritmlarni tahlili qilish va baholash
• Algoritmni tasvirlash usullari
• Algoritm turlari

Algoritm tushunchasi

• Avvalo algoritm tushunchasi IX asrda yashab ijod etgan buyuk bobokalonimiz Muhammad al-Xorazmiy nomi bilan uzviy bogʻliqligini tushuntirish lozim. Algoritm soʻzi al-Xorazmiyning arifmetikaga bagʻishlangan asarining dastlabki sahifasidagi “Dixit Algoritmi” (“dediki al-Xorazmiy” ning lotincha ifodasi) degan jumlalardan kelib chiqqan.
• Algoritm nima degan savolga, u asosiy tushuncha sifatida qabul qilinganligidan, uning faqat tavsifi beriladi, ya’ni biror maqsadga erishishga yoki qandaydir masalani yechishga qaratilgan koʻrsatmalarning (buyruqlarning) aniq, tushunarli, chekli hamda toʻliq tizimi tushuniladi.
• Algoritm tushunchasi aniq shaklda 20-asr boshlarida D. Gilbert, K. Gyodel, S. Klin, A. Chyorch, E. Post, A. Tyuring, N. Viner, A. A. Markov singari olimlarning asarlari tufayli shakllandi.

Algoritm tushunchasi

• Eng qadimiy raqamli algoritmlardan biri Yevklid algoritmi (miloddan avvalgi III asr) deb hisoblanadi - ikki sonning eng katta umumiy boʻluvchisini topish. Algoritmlarning zamonaviy nazariyasi nemis matematikasi Kurt Gyodel (1931) asarlari bilan boshlandi, ular oʻzlarining rasmiy, izchil aksiomalar tizimi doirasida yechib boʻlmaydigan muammolar mavjudligini koʻrsatdi.
• Algoritmlar nazariyasi boʻyicha birinchi fundamental ishlar 1936-yilda paydo boʻlgan. Tyuring mashinasi, Post va Chyorch tomonidan λ-hisobi taklif etiladi. Ushbu mashinalar algoritmning formallashtirilgan rasmiylashtirilishi edi.
• Algoritmni bajarayotgan kishi – ijrochi, asosiy algoritmni aniqlashtiruvchi algoritm – yordamchi algoritm ekanligini ham ta’kidlab oʻtish joiz. Umuman, algoritmning qanday maqsadga moʻljallanganligidan qat’iy nazar uni muvaffaqiyat bilan bajarish mumkinligini aytib oʻtish lozimdir.