1-ma’ruza: Algoritm tushunchasi. Algoritmni asosiy ta‘riflari, xossalari va ularning turlari, Oddiy klassik algoritmlar. Tyuring mashinasi va tezisi

Algoritm asosiy turlar.

Har qanday algoritm mantiqiy tuzilishiga, ya’ni bajarilishiga qarab uch asosiy turga bo‘linadi:

• Chiziqli
• Tarmoqlanuvchi
• Takrorlanuvchi

Chiziqli algoritmlar. Bu turdagi algoritmlarda hech qanday shart tekshirilmaydi. Shu sababli barcha ko‘rsatmalar ketma-ket bajarib boriladi. «G‘ishtlar sonini hisoblash», «Doira yuzini hisoblash» algoritmlari chiziqli algoritmlarga misol bo‘ladi. Lekin hayotimizdagi juda ko‘p jarayonlar shartlar asosida boshqariladi.

• Chiziqli algoritmlar. Bu turdagi algoritmlarda hech qanday shart tekshirilmaydi. Shu sababli barcha ko‘rsatmalar ketma-ket bajarib boriladi. «G‘ishtlar sonini hisoblash», «Doira yuzini hisoblash» algoritmlari chiziqli algoritmlarga misol bo‘ladi. Lekin hayotimizdagi juda ko‘p jarayonlar shartlar asosida boshqariladi.
• Tarmoqlanuvchi algoritmlar. Shartga muvofiq bajariladigan ko‘rsatmalar ishtirok etgan algoritmlar tarmoqlanuvchi algoritmlar deb ataladi. Algoritmlarning bu turi hayotimizda har kuni va har qadamda uchraydi. Eshikdan chiqishimiz eshik ochiq yoki yopiqligiga, ovqatlanishimiz qornimiz och yoki to‘qligiga yoki taomning turiga, ko‘chaga kiyinib chiqishimiz ob-havoga, biror joyga borish uchun transport vositasini tanlashimiz to‘lash imkoniyatimiz bo‘lgan pulga bog‘liqdir. Demak, tarmoqlanuvchi algoritmlar chiziqli algoritmlardan tanlash imkoniyati bilan farqlanar ekan.

Takrorlanuvchi algoritm. Masalalarni tahlil etish jarayonida algoritmdagi ba’zi ko‘rsatmalar takroran bajarilishini kuzatish mumkin. Hayotimizda juda ham ko‘p jarayonlar takrorlanadi. Masalan, darslarning har hafta takrorlanishi, har kuni nonushta qilish va hokazolar. Ko‘satmalari takroriy bajariladigan algoritmar takrorlanuvchi algoritmlar deb ataladi.

Takrorlanuvchi algoritm. Masalalarni tahlil etish jarayonida algoritmdagi ba’zi ko‘rsatmalar takroran bajarilishini kuzatish mumkin. Hayotimizda juda ham ko‘p jarayonlar takrorlanadi. Masalan, darslarning har hafta takrorlanishi, har kuni nonushta qilish va hokazolar. Ko‘satmalari takroriy bajariladigan algoritmar takrorlanuvchi algoritmlar deb ataladi.