Mavzu: Algoritmlarning matematika bilan bog’liqligi (8 soat) Reja

Mavzu: Algoritmlarning matematika bilan bog’liqligi (8 soat)


Reja:
1. Rekursiv funksiyalar
2. Cheklanmagan regestrli mashina
3. Chorch tezisi
4. Algoritmlar nazariyasining tadbiqlari
5. Tipik masalalar: Saralash va izlash masalalari uchun algoritmlar va ularning murakkabligi.
6. Rekursiv hisoblashlar masalasi uchun algoritmlar va ularning murakkabligini aniqlash


Tayanch iboralar:
Rekursiya, funksiya, Chorch tezisi, Dumli rekursiyalar, Dumsiz rekursiyalar, algoritmlar, EHM, Dasturlash tillari, Saralash, Izlash, Binar izlash, daraxt, massiv, Selection sort, Bubble sort, Insertion sort, Quick sort, Merge sort,
1. Rekursiv funksiyalar

Ta'rif: Funksiya o'ziga o'zi to'g'ridan-to'g'ri yoki qandaydir vosita orqali murojaat qilish jarayoniga rekursiya deyiladi va bunday funksiya rekursiv funksiya deb ataladi.

Rekursiyani to'g'ri tashkil qilish shartlari
Har qanday to'g'ri tuzilgan rekursiya asosini ikkita shart tashkil qiladi.

1. 
   Rekursiya asos sharti
   
2. 
   Funksiyaning o'ziga o'zgartirilgan argument bilan murojaat qilish.
   

Rekursiv funksiya qaysidir vaqtga kelib o'ziga murojaat qilishni to'xtatishi kerak bo'ladi. Aynan shu narsani rekursiya asos sharti ta'minlab beradi. Hikoyamizdagi misolga qaytadigan bo'lsak, Abdullajon summa() funksiyasiga bir necha marta murojaat qildi va oxirida funksiyaga keluvchi massivda faqat bitta element qolganda to'xtadi. Bu masala uchun arrayda yagona element qolishi asos shart bo'lib xizmat qiladi va shu yerga yetganda dastur to'xtashi kerakligini bilib oladi. Rekursiv funksiya tuzishda asos shartni to'g'ri qo'yish juda ham muhim hisoblanadi. Hali bunga yana to'xtalamiz.
Keyingi shartda o'zgartirilgan argument deganda, odatda masala boshidagi argumentdan kichikroq argument tushiniladi (ba'zi hollarda kattaroq bo'lishi mumkin). Misolimizda, Abdullajon har safar summa() funksiyasiga murojaat qilganda undagi massiv hajmini bittaga kamaytirib bordi. Bu narsa ham juda muhim, chunki bir xil argument bilan qayta-qayta murojaat qilinganda yoki argument notog'ri o'zgartirilganda funksiya o'zini cheksiz marta chaqirishiga to'g'ri kelib qoladi. Bu haqida ham batafsil yana gaplashamiz.