Mavzu: Normal va murakkab algoritmlar (4 soat) Reja

Masalan, x1,x2,...,xn o’zgaruvchilarning ixtiyoriy soniga bog’liq bo’lgan ko’paytirilgan koeffitsientlarni ko’rib chiqing. Yunon matematigi Diophantusning xotirasiga bunday ko’payishlarni ba’zi diafantlar deb atashadi. Bizni bunday ko’payuvchi butun sonlarga (Diofantin) ildizga ega ekanligi qiziqtiradi. Qadimgi matematikalar pilinomlarning butun sonlari bilan ham qiziqishgan, masalan, Pifagor teoremasi bilan ular x2+y2=z2 tenglamani ko’rib chiqishgan. Evlid bu tenglamaning barcha butun yechimini topishga imkon beradigan formulalar beradi. Diophantusning o’zi boshqa tenglamalar qatorida ax2+bx+c=y2 tenglamani ko’rib chiqdi va ba’zi bir alohida holatlar uchun uni hal qildi.

19-20 asrlar oxirida Gilbert diofantin tenglamalari masalasini 19-asrning 20- yillariga qoldirgan eng muhim muammolar qatoriga kirdi. U bu masalani quyidagicha ifodalagan:”O’zboshimchalik bilan nomalum bo’lgan va butun son ratsional sonli koeffitsientlar bilan ixtiyoriy

Diofantin tenglamasi berilsin. Bu tenglamani butun sonli ratsional sonlarda yechib bo’ladimi yoki yo’qligini aniqlash uchun cheksiz sonli operatsialardan keyin qanday usulni ko’rsating”.

Diofantin tenglamasi berilsin. Bu tenglamani butun sonli ratsional sonlarda yechib bo’ladimi yoki yo’qligini aniqlash uchun cheksiz sonli operatsialardan keyin qanday usulni ko’rsating”.

Nazorat savollari:

1. 
   Normal algoritm nima?
   
2. 
   Normal algoritmning avfzalligi?
   
3. 
   Markovning normal algoritmini tushuntirib bering
   
4. 
   Murakkab algoritmlar nima?
   
5. 
   Murakkablik qanday baholanadi?
   
6. 
   Murakkablikni o’sishi nima?
   
7. 
   Algoritm qadami nima?
   
8. 
   “Ajrat va hukumron bo’l” algoritmni tushuntirib bering?
   
9. 
   Bo'lib tashla va hukmronlik qil paradigmasi nima?
   
10. 
    Qurumsoq algoritmi nima?
    
11. 
    Bo'lib tashla va hukmronlik qil paradigmasi afzalliklari qanday?