5-mavzu: Algoritmik yechilmaydigan muammolar. Mayxil teoremasi. Algoritmik darjalar

5-MAVZU: Algoritmik yechilmaydigan muammolar. Mayxil teoremasi. Algoritmik darjalar

• REJA:
• 1. Algoritmik yechilmaydigan muammolar.
• 2. Mayxil teoremasi.
• 3. Algoritmik darajalar.

Foydalanilgan adabiyotlar.

• 1. Горбатов В.А., Останков Б.Л., Фролов С.А . Регулярные структуры автоматного управления / Под ред. В .А .Горбатова . М., «Машиностроение», 1980.
• 2. Горбатов В.А., Павлов П .Г ., Четвериков В.Н. Логическое управление информационными процессами. М., « Энергоатомиздат », 1984.
• 3. Гроссман И., Магнус В. Группы и графы. М ., «Мир», 1971.
• 4. Дорофеев Г. В., П о тап о в М . К., Розов Н. X. Пособие по математики для поступаю щ их в вузы. М., «Наука», 1976.
• 5. Евстигнеев В. А. Применение теории графов в программировании. М., «Наука», 1985.
• 6. Ерусалимски й Я. М. Дискретная математика: теория, задачи, приложения. М., «Вузовская книга», 2000

Algoritmik yechilmaydigan muammolar Har bir aniq belgilangan masalani algoritmi mavjud bo’lmasa, shuning uchun dastur yordamida yechish mumkin emas. Algoritmga ega bo‘lmagan masalalar yechilmaydigan masalalar deyiladi. Biz yozilishi kerak bo'lgan ilovalarda duch keladigan muammolarning aksariyatini algoritm yordamida hal qilish mumkin. Biroq, matematikaning turli sohalarida (masalan, mantiq, o'yin nazariyasida) paydo bo'ladigan bir qator qiziqarli muammolar hal bo'lmaydi.

Algoritmga ega bo'lmagan uchta muammo tasvirlangan. Biz buni hal qiladigan dastur bor yoki yo'qligini bilmaydigan oddiy "aylantiring va palindromga qo'shing" muammosini tavsiflaymiz. Biz aslida buning uchun Python dasturini yozyapmiz, lekin bu to'g'ri dastur emas, chunki u ba'zi kiritishda cheksiz tsikl yaratishi mumkin. Muammoning har bir kirishda tugaydigan algoritmi bor yoki yo'qligini hech kim bilmaydi. Hisoblashning murakkabligi palindromni yaratish mumkin emasligini aniqlashdir. Shuningdek, biz ikkita taniqli hal qilib bo'lmaydigan muammolarni tasvirlaymiz: to'xtash muammosi va Vang kafel muammosi. Ikkala masala uchun ham algoritm mavjud emasligining matematik isboti mavjud.