13-ma'ruza. Np bilan bog'liq muammolar. Hisoblash qobiliyatsizligi Maruzachi o’qituvchi: katta o’qituvchi Ganihodjayeva Dilfuza Ziyavutdinovna Reja

13-ma'ruza. NP bilan bog'liq muammolar. Hisoblash qobiliyatsizligi

Maruzachi o’qituvchi: katta o’qituvchi Ganihodjayeva Dilfuza Ziyavutdinovna

Reja

1. Kirish

2. Algoritmik echilmaydigan muammolarga misollar

3. Cantorning diagonal usuli

4. NP sinfi.

Hisoblangan har qanday funktsiyani turli xil algoritmlar (tanlangan universal ijrochi uchun turli xil dasturlar) bilan belgilash mumkin va har qanday universal ijrochi yordamida hisoblash mumkin: Turing va Post mashinalari, normal Markov algoritmlari va boshqalar, ammo algoritmik hisoblanmaydigan funktsiyalar ham mavjud.

Ammo u yoki bu sinfning algoritmik echimini topib bo'lmaydi, bu biron bir muammoni xuddi shu texnikadan foydalanib hal qilish mumkin emas degani emas.

Algoritm kontseptsiyasining rasmiylashtirilishi algoritmik echimlar mavjud bo'lmagan muammolar mavjudligini o'rganishga imkon berdi.