1 Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va xotira hajimi bo‘yicha qiyinchiliklar


Algoritmik yechilmaydigan masalalar



Download 101,89 Kb.
bet14/19
Sana14.06.2022
Hajmi101,89 Kb.
#672007
1   ...   11   12   13   14   15   16   17   18   19
Bog'liq
1 Algoritm murakkabligini statik va dinamik o‘lchovlari. Vaqt va

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.

Download 101,89 Kb.

Do'stlaringiz bilan baham:
1   ...   11   12   13   14   15   16   17   18   19




Ma'lumotlar bazasi mualliflik huquqi bilan himoyalangan ©hozir.org 2024
ma'muriyatiga murojaat qiling

kiriting | ro'yxatdan o'tish
    Bosh sahifa
юртда тантана
Боғда битган
Бугун юртда
Эшитганлар жилманглар
Эшитмадим деманглар
битган бодомлар
Yangiariq tumani
qitish marakazi
Raqamli texnologiyalar
ilishida muhokamadan
tasdiqqa tavsiya
tavsiya etilgan
iqtisodiyot kafedrasi
steiermarkischen landesregierung
asarlaringizni yuboring
o'zingizning asarlaringizni
Iltimos faqat
faqat o'zingizning
steierm rkischen
landesregierung fachabteilung
rkischen landesregierung
hamshira loyihasi
loyihasi mavsum
faolyatining oqibatlari
asosiy adabiyotlar
fakulteti ahborot
ahborot havfsizligi
havfsizligi kafedrasi
fanidan bo’yicha
fakulteti iqtisodiyot
boshqaruv fakulteti
chiqarishda boshqaruv
ishlab chiqarishda
iqtisodiyot fakultet
multiservis tarmoqlari
fanidan asosiy
Uzbek fanidan
mavzulari potok
asosidagi multiservis
'aliyyil a'ziym
billahil 'aliyyil
illaa billahil
quvvata illaa
falah' deganida
Kompyuter savodxonligi
bo’yicha mustaqil
'alal falah'
Hayya 'alal
'alas soloh
Hayya 'alas
mavsum boyicha


yuklab olish