1-мавзу. “Ma’lumotlar bazasi” fanining maqsadi, vazifalari, asosiy tushunchalar, ta’riflar va rivojlanish tendensiyalari

Boole va boshqa olimlar mantiqiy xulosa algoritmlarini keng muhokama qildilar va XIX asrning oxiriga kelib matematik fikrlashning umumiy tamoyillarini mantiqiy xulosa sifatida rasmiylashtirishga harakat qilindi.

1900-yilda Devid Gilbert (1862-1943) 23 ta masalalar ro‘yxatini taqdim qildi va bu masalalar XX asrning deyarli oxirigacha matematiklar tomonidan yechilishi mumkinligini bashorat qildi. Ushbu masalalardan biri natural sonlarni o‘z ichiga olgan har qanday mantiqiy fikrning rostligini aniqlash algoritmi mavjudmi degan masala hisoblanadi. Bu mashhur yechimni izlash muammosi (Entscheidungsproblem) hisoblanadi. Aslida, Gilbert tomonidan berilgan ushbu masala samarali isbotlash protseduralarining kuchini cheklaydigan asosiy chegaralar mavjudligini aniqlash uchun mo‘ljallangan.

1930-yilda Kurt Gyodel (1906-1978) Frege va Rassellning birinchi darajali mantig‘ida har qanday rost fikrni isbotlashning samarali tartibi mavjudligini ko‘rsatdi.

1931 yilda Gyodel hisoblash uchun haqiqiy chegaralar mavjudligini ko‘rsatdi. U taklif qilgan to‘liqsizlik teoremasi shuni ko‘rsatadiki, tabiiy sonlarning xususiyatlarini tavsiflash uchun yetarlicha ifodalanadigan har qanday tilda ularning rostligini biron bir algoritm yordamida o‘rnatib bo‘lmaydi degan ma’noda isbotlanmaydigan haqiqiy fikrlar mavjud.

Chyorch-Tyuring izlanishlarida Tyuring mashinasi ixtiyoriy hisoblash funksiyasini bajarishi mumkinligini ko‘rsatadi. Bundan tashqari, Tyuring Tyuring mashinasi tomonidan hisoblab bo‘lmaydigan ba’zi funksiyalar mavjudligini ko‘rsatdi.

Murakkablikdagi polinom va eksponensial o‘sish o‘rtasidagi farq birinchi marta 1960-yillarning o‘rtalarida Kobxem va Edmonds tomonidan ta’kidlangan.

Murakkablikdagi polinom va eksponensial o‘sish o‘rtasidagi farq birinchi marta 1960-yillarning o‘rtalarida Kobxem va Edmonds tomonidan ta’kidlangan.

Yechilmaydigan masalani qanday tanish mumkin? Bunday metodlardan biri Stiven Kuk va Richard Karp tomonidan taklif qilingan NP-to‘liqlik nazariyasidir. Kuk va Karp NP-to‘liqlik bo‘lgan kanonik kombinatorial qidiruv va fikrlash muammolarining katta sinflari mavjudligini ko‘rsatdi. NP-to‘liqlik masalasi sinfiga olib keluvchi ixtiyoriy masalalar sinfi yechilmaydigan masalalar hisoblanadi. Bu birinchi kompyuterlarning paydo bo‘lishi bilan bog‘liq nazariyaga teskari hisoblanadi. Kompyuterlar tezligining doimiy ortib borishiga qaramay, intellektual tizimlarning xarakterli xususiyati resurslardan tejamkor foydalanish hisoblanadi.