Amaliyot ishi №1 Mavzu

Mukammal tushuntirish

Hisiblashda talab etiladigan resurslar, hisoblash murakkabligi,kiritish uzunligi vazifasini bajarish uchun mo`ljallangan.

Turing mashinasi modeli hisoblashda model hisob-kitoblar maydoni zarur va hisoblash resurslari sifatida ishlatiladi va baholanadi. resurs kiritish orqali hisoblash uchun zarur o'zgartirishlar beriladi, normal kiritish uzunligi nisbatan eng qiyin ishlarni ko`rib chiqadi.

Shu nuqtai nazardandan gapirganda, bugungi kunda dunyodagi barcha kompyuterlar Turihg mashinasi modeli bo`lgan fon Neyman modeli sifatida ham ishlatish mumkin

Hisoblash murakkabligi muammosi bilan bir qatorda, polinom vaqt algoritm faqat bir muammo bilan hal bo'ladigan deb hisoblanadi.

hisoblash nazariyasi murakkabligi bo`yicha eng mashhur javobsiz muammosi,   hisoblanadi.

 bu sinf  muammolari barcha ko'phad vaqtida hal qilinishi mumkin tegishli bo'lsin, NP- unda murakkab muammolar deyarli, shuningdek, muhim muammo mavjud Ko'pchilik tadqiqotchilar, NP qiyin muammo ko'phad vaqtida hal qilish mumkin emas deyishadi. Bunday hisoblash murakkabligi nazariyasi doirasida ko'ra, muammo bir "jiddiy" muammo bo'lishi ko'rsatilgan muammolar edi, ya'ni, qiyin NP ekanligini ko'rsatadi.

Lekin boshqa tomondan, bu an'anaviy doirasida tomonidan "itoatsiz" bilan bo'lgan bir muammo bo'ladi, yoki bir necha yondashuv qilingan, negadir bir amaliy nuqtai nazardan hal qilinishi mumkin emas. Odatda misollar va stokastik algoritm va shunga o'xshash va hamjihatlikni algoritm mavjud.

Coin Toss to'g'ri javob chiqishi ehtimoli tomonidan muammolarni sinfini aniqlash uchun imkon beruvchi Turing mashinasi modelini (ehtimollik Turing mashinasi modeli) joriy etdi. Misol uchun, bir tomonlama xato ruxsat ehtimollik Turing mashinaning ko'phad vaqt bilan belgilanadi.Mumkin muammo sinf R tegishli. soni berilgan muammo sintez soni, yaxshi ma'lumki bir sinf R ga tegishli yoki yo'qligini aniqlaydi. An hamjihatlikni algoritm faqat taxminiy olingan, lekin pozitsiyani turgan bo'lishi, bir aniq yechim emas. taxminiy yechim (muammo yoki yo'q nisbiy xato, yoki aksincha ijobiy konstantasi ko'ra funktsiyasi tomonidan ba'zi hollarda) aniq hal qilinishiga nisbatan nisbiy xato ijobiy konstantasi tomonidan bostirilgan bo'ladi. Nisbiy xatolik ijobiy doimiy emas   yilda bostirilgan A yechim   taxminiy deb ataladi. yondashuv algoritm ijobiy doimiy   "A" kiritish "uchun uzunligi   "Ning ko'phad vaqtida   Bu taxminan bir yechim olish mumkin yoki yo'qligini,aniqlaydi. Hatto bir xildagi NP-qattiq muammo bilan, bu nuqtai nazardan, turli xususiyatlari bilan bor, deb topildi. NP ham qiyin muammo, har qanday ijobiy doimiy berilgan Bu   , yuqorida ma'noda ko'phad vaqtida   bir tomondan taxminan bir yechim olish mumkin narsalar bor   sharti ostida   vaqt ko'phadning in  Bu taxminiy hal bo'lishi mumkin   Bu, shuningdek, hajmi bir chegarasi bor, deb muammoni ma'lum qiladi. ikkinchisi muammo bo'lgan sinflardan biri sifatida sinf MAX SNP ma'lum. MAX SNP qiyin muammo nafaqat aniq yechimini balki, "yechilmaydigan" muammoni ham yaxshi taxminiy hal olish tomonidan, bajariladi. Hatto, bu ma'noda "yechilmaydigan" muammoga yondashuv algoritm bir darajaga ma'lum o'sha ya'ni bor, deb ta'kidlash lozim. Boshqa so'z bilan aytganda, bu yaxshi yondashuv stavkasining har qanday qator erishish oson emas, ammo ma'lum bir yondashuv nisbatiga erishish bo'lsa, negadir bir muammo ham bor. Lekin kamaytirilishi mumkin qanchalik bu muammolarni taxminiy darajasi, bu juda qiyin muammo bo'lib, odatda hisoblanadi.Hisoblash nazariyasi murakkabligi, bunday shartlari "itoatkor bo'lsin.", shuningdek, bir xil chiqib ketishga kelgan muammoning murakkabligi o'rganish imkoni bor. Masalan "berilgan muammo samarali parallel hal qilish mumkin yoki yo'qligini" nuqtai nazardan, shuningdek, bular amaliy muhim ahamiyatga ega. Ma'lum bir muammo uchun, paralelizm muammolarini hal qilishi mumkin. Bu muammolarning bir qismi bilan Shimoliy karolinada shug`ullanadi. Muammo protsessor ko'paytirish, bu sinfiga oid, bu miqdorda samarali muammolarni hal qilish mumkin bo'ladi. ko'phad vaqt algoritm bilan ba'zi muammolar, bu sinf uchun jiddiy muammo hisoblanadi. Bunday muammo hisoblash tezligi ham protsessorlar soni ortib bormoqda.