Mavzu : Algoritm murakkabligini statik va dinamik o’lchovlari. Vaqt va xotira hajmi bo’yicha qiyinchiliklar reja

2.6 Algoritmik yechilmaydigan masalalar
Muammolarni baham ko'ring yolg'iz va katta.
Masalan:
5 + 7 =? Yagona muammo.
x + y =? Katta muammo.
Paradoksal bo'lgan ob'ektlarni olish yoki paradoksal ob'ektlar mavjud bo'lgan muammolarni hal qilish algoritmlari tubdan hal qilib bo'lmaydigan bo'lishi kerak.
Masalan, paradokslar:
1-misol:
Hilbertning 10-muammosi.
D. Gilbert 1901 yilda diofant tenglamalarini yechishda quyidagi masalani ilgari suradi:
Ixtiyoriy Diofant tenglamasi uchun qandaydir butun son yechimini aniqlaydigan algoritmni toping.
F(x, y, …)=0
Bu noma'lumlar uchun butun ko'rsatkichli va butun son koeffitsientli polinom
anxn + an-1xn-1 +… + a2x2 + a1x + a0 = 0
Yuqoridagi tenglama uchun ma'lum bir yechim mavjud bo'lib, u har bir butun son ildizidan iborat xi bo'luvchi hisoblanadi a0 ... Qayerda a0 asosiy omillarga ajrating va har bir omilni ildizga muvofiqligini tekshiring.
1970 yilda leningradlik matematik Yu.Matiyasevich Diofant tenglamasini umumiy shaklda yechishning algoritmik imkonsizligini matematik tarzda isbotladi.
2-misol:
Ferma teoremasi:
Bunday butun sonlar mavjud emas a, b, s, n (n>2) buning uchun tenglik
a + bn = cn
Bu teorema ko'p qiymatlar uchun isbotlangan n va maxsus holatlar uchun tekshiriladi, lekin teoremaning umumiy isboti hali yaratilmagan.
3-misol:
Goldbax muammosi.
X. Xolbax 1742 yilda Eylerga yo‘llagan maktubida muammoni shunday shakllantirgan:
Har bir butun sonni isbotlang N³ 6 uchta tub sonning yig'indisi sifatida ifodalanishi mumkin
N= a+ b+ c
Bu shuni anglatadiki, siz har qanday butun songa ruxsat beradigan algoritmni topishingiz kerak N³ 6 kamida bitta parchalanishni uchta oddiy atamaga toping.
Eyler bu muammoni tez-tez hal qilishni taklif qildi: hatto uchun N bu muammo echilishi mumkin va ikkita oddiy atamaga parchalanishga teng.
I. Vinogradov 1937 yilda buni g'alati ekanligini isbotladi N uchta oddiy atamani topish mumkin, lekin juft sonlar uchun yechim hali topilmagan.
O (1) - Dasturdagi amallarning aksariyati faqat bir marta yoki bir necha marta bajariladi. Doimiy murakkablik algoritmlari. Ma'lumotlar hajmidan qat'i nazar, har doim bir xil vaqtni talab qiladigan har qanday algoritm doimiy murakkablik.