Algoritm haqda tushuncha

2-Modul
Reja:

1. 
   Algoritm haqda tushuncha
   
2. 
   Algoritm murakkabligi haqda tushuncha
   
3. 
   Knut-Morris-Pratt algoritmi va uning murakkabligi
   

Mavzu: Knut-Morris-Pratt algoritmi va uning murakkabligi

4. 
   Algoritm haqda tushuncha
   

Algoritm — maʼlum bir turga oid masalalarni yechishda ishlatiladigan amallarning muayyan tartibda bajarilishi haqidagi aniq qoida (dastur). Kibernetika va matematikaning asosiy tushunchalaridan biri. Oʻrta asrlarda sanoqning oʻnli tizimi boʻyicha toʻrt arifmetik amal bajariladigan qoidani A. deb atashgan. "Bu qoidalarni matematikaga IX asrda al-Xorazmiy kiritgan. Yevropada bunday qoidalar uning tugilgan yurtiga nisbatan lotinchalashtirilgan (Algoritmus yoki Algorithmus shaklida „algorizm“ deyilgan), keyinchalik „algoritm“ga aylangan". Fanda „Yevklid algoritmi“, „Gʻiyosiddin Koshiy algoritmi“, „Laure algoritmi“, „Markov algoritmi“ deb ataluvchi algoritmlar maʼlum. Algoritm tushunchasi tobora kengayib borib, kibernetikaning nazariy va mantiqiy asosi hisoblangan algoritmlar nazariyasi paydo boʻldi. Oʻzbekistonda bir necha ilmiy tadqiqot muassasalari va hisoblash markazlarida algoritmdan foydalanish sohasida samarali ishlar olib borilmoqda. Masalan, Oʻzbekiston Fanlar Akademiyasi „Kibernetika“ ilmiy ishlab chiqarish birlashmasida, Oʻzbekistondagi barcha universitetlarda, Toshkent davlat texnika universitetida, Oʻzbekiston Respublikasi Makroiqtisod va statistika vazirligi qoshidagi Hisoblash markazi va boshqa muassasalarda olib borilayotgan ishlar bunga misol boʻla oladi^[1].

5. 
   Algortim murakkabligi
   

Algoritm deb hisoblash yoki masalani yechish jarayonlarining ketma-ketligi yig’indisi tushuniladi. Algoritmlar biror dasturlash tiliga bog’liq bo’lmaydi, ular istalgan tilda kod yozilgan taqdirda ham bir xil natijaga olib keladigan instruksiyalardir.
Ammo barcha instruksiyalar ham algoritm bo’lavermaydi. Algoritm bo’lishi uchun, instruksiya bir necha xarakteristikalarga ega bo’ladi:

• 
  Barcha qadamlar aniq koʻrsatilgan boʻlishi kerak
  
• 
  Input va Output turi aniq belgilangan bo’lishi kerak
  
• 
  Chegarali. Algoritm doimiy siklga tushib qolmasligi, ohirgi qadamlarigacha yetib borishi zarur
  
• 
  Oson. Algoritm istalgan dasturlash tilida amalga oshirish mumkin bo’ladigan darajada oson tuziladi