Algoritm tushunchasi Tyuring mashinalari



Download 52,08 Kb.
bet1/5
Sana05.07.2022
Hajmi52,08 Kb.
#740626
  1   2   3   4   5
Bog'liq
Algoritm tushunchasi Tyuring mashinalari


Reja:
Kirish

  1. Algoritm tushunchasi

  2. Tyuring mashinalari

  3. Tyuring mashinasida algoritmni realizatsiya qilish

  4. Tyuring nazariyasining asosiy gipotezasi

Xulosa
Foydalanilgan adabiyotlar

Kirish
Matemetik mantiqiyot ( shuningday-oq, simvollıq mantiqiyot deb te nomlanadi )- matematik usullar bilan rivojlandırılıp etilayotgan mantiqiyot.” Marematikalıq mantiqiyot” fani bárshe fanlarding asli bo'lishiga qat'iy nazar, uni o'zlar oldiga fundamental fan sifatida chuqurroq o'rganish XIX asrda noevklid geometriyaning paydo bo'lishidan boshlangan.


“Matematik mantiqiyot ” fani mantiqiyot usullarinian keng foydalanilib kelinbekte. Masalan, matematik tahlil -fanida limitke ega bo'lmagan izbe -izliklerdiń, tekis uzliksiz bo'lmagan funkciyalardıń izohin berishda predikatlar olgebrası usullarinian foydalanilib, yuqorida keltiritgan tushunchalarding aniq izohin beriladi.
Matematikaliq mantiqiyot faniniini tamalǵI maqsadinae matematikaning eng ahmiyetli tusiniklerin dalillashlik, teorema, keltirib shigáriw tusinikleri, shakll aksiomatik nazariya tamalinda oqiwshillarga etkazib berish kirei. Bundan tisqari matematikaliq mantiqiyot fani oqiwshilardi ravon o'ylashga o'rgatadi.
Fannin tamalǵI voziypasi talabalarga bilim berish jo'rligida ularding abstract fikrle qobiliyatini kusheytiriwge yo'naltirilgan
Bu kurs jumisinda biz Tyuring mashinalari, onin qaytip ishlashi, algoritmlar, Tyuring mashinasinda algoritmlarni realizasiya qiliwdi, natural sonlar qo'shlarish algoritmi, Evklid algoritmi, algoritmlar nazariyasinda tamalǵI gipotezalarga haqqinda toliq maǵliwmat keltirdik.

Matematikaning asosiy tushunchalaridan biri algoritm (olgorifm) tushunchasi dir. «Algoritm» lafzi IX-asrda ijodiy etgan ulug' matematik vatandoshimiz Abu Abdullo Muhammad ibn Muso ol -Xorazmiy isminingń lotincha Olgorithmi tarzida buzib yozilishinan kelib chiqqan. Har biri «awa » yoki «yaq» degan javob taqozo etuvchi ayrim sanoqli -cheksiz matematik yoki mantiqlik muammolar sinfin ko'raylik. Chekli son qadamda bu sinfdagi har qanday so'rovga biz javob bera oladigan jarayonlik (prosedura) bormi? Agar o'shanaqa prosedura mavjud bo'lsa, u holda u berilgan so'rovlar sinfi uchun yechuvchi prosedura yoki yechuvchi algoritm (olgorifm) deb aytiladi. Yechuvchi prosedurani izlash muammosinia bu sinf uchun yechilish muammosi deb aytiladi. Shakll tizimlar uchun yechilish muammosini kun tartibiga birinchi qo'ygan olimlardan Shryoder (1895), Lyovengeym (1915) va Gilbertlarni (1918) ko'rsatish mumkin. Masalan, quyidagilar yechuvchi algoritmlarga misol bo'la oladi :


1. Sonlar ustida arifmetik amallardi bajarish qoidalari.
2. Kvadrat chiqarish qoidasi.
3. Eng katta umumiy bo'luvchin topish qoidasi (Yevklid algoritmi ).
4. Kvadrat tenglamading yechimini topish qoidasi.
5. n -tartibli ko'phadlarding hosilan topish qoidasi.
6. Rostional funksiyani integralroq qoidasi.
Yuqorida keltiritgan har bitta misolda mushtarak tipli (turdagi ) muammolar sinfi bilan yumush ko'rishlikga to'g'ri keladi. Mushtarak turdagi muammolar sinfi ommaviy muammo deb aytiladi. Bunday tabaqalarning masalalari bitta biridan xolos ifodasi dagi parametrlar bilan farq etadi. Masalan ax2bx  +c = 0 Kvadrat tenglamading yechimini topish masalasinde a, b va c parametrlar qatnashadi. Ularning baholarini o'zgartirish yo'li bilan bitta sinfga tegishli turli xil muammolarga kelamiz.
Aytilganlarni hisobga olib algoritmding quyidagi intuitiv ta'rifini berish mumkin.
1-ta'rif. Berilgan ommaviy muammo dagi borlik masalalarni umumiy mushtarak shaklda, aniq ma'lumki bo'lgan usul bilan yechish jarayonine algoritm deb aytamiz. Bunday ta'rifni qat'iy deb hisoblash mumkin emas. Darhaqiqat, unda aniq mundarijasi noma'lum so'zlar uchraydi. Xususan, bu «usul» lafziga da tegishli. O'sha sababli da algoritmding bu qat'iy bo'lmagan ta'rifiga intuitiv ta'rif deb aytiladi
Endi algoritmding xarakterli xususiyatlarin ko'rib o'taylik.
1. Algoritmding diskretligi. Algoritm -miqdorlarni o'shanaqa ketma-ket qurish jarayoniki, boshlang'ich holatda miqdorlarding dastlabki chekli tizimsi berilgan bo'lib, har bitta navbatdagi momentte miqdorlar tizimsi ma'lumki aniqlangan qonun (dastur ) asosida avvalgi holat dagi miqdorlar tizimidan paydo qilildi.
2. Algoritmding daterminasiyalanuvchanligi (aniqlanguvchanligi). Boshlang'ich holatdan farq etuvchi boshqa holatda aniqlangan miqdorlar tizimsi ilgarigi hollarda unum etilgan miqdorlar tizimsi qirg'oqlari bitta baholi aniqlangadi.
3. Algoritm qadamlarining unsurarligi. Ilgarigi miqdorlar tizimidan keyingisini hosil qilish qonuni oddiy qadamlardan iborat bo'lishi zurur.
4. Algoritmding ommaviyligi. Boshlang'ich miqdorlar tizimini ayrim potensial cheksiz to'plamtan tanlov mumkin.
5. Algoritmding xotimalikligi. Miqdorlarni topish jarayoni chekli bo'lishi va xotima (masalaniń yechimini ) berishi zurur.
Algoritm tusinigin aniqlawdaǵI muammolar
Matematika tarixinda mushtarak turdegi so'rovlar kompleksininge “ha” yoki “yaq” va mushtarak turdegi so'rovlar klasi “hisoblanuvchi ' yoki “hisoblanuvchi emas” degan javoblar berilishi mumkin bo'lgan algoritmlarni izlash uzoq davom qildi. Ayrim vaqtlarda bu izlanishlar xotimasiz tugadi. Bu hollarda, tabiiyki, algoritmding mavjudligiga guman bilan qaraladi.
1- misol. Fermaning «buyuk teoremasi» deb ataluvchi tasdiqni qaraymiz. 1637-yillar atrofida Ferma quyidagi teoremaning tasdiqi o'zida borligin e'lon qildi :
« x n + y" = z" tenglama n > 2 Bo'lganda o'ng butun son baholi x, y, z, n qarorga ega emas». Bu teorema faqatgina 2000-yilda Angliya olimi Endryu Uals tomonidan tasdiqlandi. ■
2- misol. 1900-yilda Parijda o'tkazilgan ikkinchi xalqaro matematiklar kongressida umon matematigi David Gilbert yechilishi zarurli boMgan 23 matematik muammolar ro'yxatini o'qib berdi. Bu ro'yxatda Cilbertning 10 - muammosi deb atalgan quyidagi muammo ham mavjud edi : «Koefficiyentleri butun sonlardan iborat bo'lgan har qanday olgebraik tenglamading butun sonli yechimi bormi? ». Gilbert butun sonli koefficiyentlerden iborat bo'lgan har qanday olgebraik tenglama butun sonli qarorga egami degan muammoni hal qildilik (hal qildilik ) algoritm yaratuv kerakligini ko'rsatdi.
Matematikada butun sonli koefficiyentlerge ega boMgaalgebraik tenglamalar Diofant tenglamalari1 deyiladi. Masalan

Ko'rinishdagi tenglamalar diofant tenglamalari boMadi, ulardan birinchisi uchlar o'zgaruvchili va ikkinchisi bitta o 'zgaruvchili tenglama dir. Umumiy holda tenglama xohlagan sondagi o'zgaruvchilarga bogMiq boMishi hamda bunday tenglamalar butun sonli yechimlarga ega boMishi ham, ega bo'llarmasligi ham mumkin. Masalan , x2 +y 2 - 2xz = 0 cheksiz ko’p butun sonli yechimlarga ega, 10x5 +7x2  +5 = 0 tenlama bo’lsa butun sonli yechimlarga ega emas.
Bitta o'zgaruvchili diofant tenglamasining hamma butun sonli yechimlarini topish algoritmi anchadan buyon bor. Aniqlanganki, agar


Download 52,08 Kb.

Do'stlaringiz bilan baham:
  1   2   3   4   5




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