Algoritmlarni loyihalash Fan: Algoritmlarni loyihalash ki fakulteti at kafedrasi A. Xoitqulov

Algoritmik hal qilinmaydigan masalalar

• Ba’zi bir masalalarning algoritmik hal etilmasligini isbotlash uchun klassik masala – “to’xtash masalasi” qabul qilingan.
• Teorema. Algoritmik hal etilmaslik. Shunday masalalar borki uning yechimini olish uchun umumiy algoritm (Tyuring mashinasi) mavjud emas, bu masalalarni tavsiflovchi kirish ma’lumotlari qo’llaniladigan algoritmlar ishlamaydi yoki cheksiz davom etadi.

Masalalar yechishning umumiy usuli mavjud emas

• 1-masala. 𝝅 sonida 𝑥 sonining taqsimlanishini hisoblash:
• 𝝅 = 3,141592 … , 𝑓9(1) = 5.
• 𝝅 = 48𝑎𝑟𝑐𝑡𝑔(1/18) + 24𝑎𝑟𝑐𝑡𝑔(1/57) − 20𝑎𝑟𝑐𝑡𝑔(1/239).
• Ixtiyoriy 𝑛 uchun 𝑓𝑥(𝑛) funktsiyani hisoblash masalasi.

2-masala. Mukammal sonlarni hisoblash:

• Mukammal son – bu o’zining bo’luvchilari yig’indisidan tashkil topgan son, masalan:
• 𝑆(1) = 1 = 1
• 𝑆(2) = 6 = 1 + 2 +3
• 𝑆(3) = 28 = 1 + 2 + 4 + 7 + 14.
• Ixtiyoriy berilgan 𝑛 soni uchun 𝑆(𝑛) ni hisoblash masalasi.

3-masala. Gilbertning o’ninchi muammosi:

• Faraz qilaylik 𝑛- darajali butun koefitsientli 𝑃𝑛(x) ko’phad berilgan bo’lsin.
• 𝑃𝑛(x) = 0 tenglamaning butun sonli yechimini olish algoritmi mavjudmi?

Mustaqil ishlash uchun savollar