|
1 maruza: Algoritm va uning ta’riflari. Asosiy savollar
|
| bet | 16/16 | | Sana | 10.11.2022 | | Hajmi | 103.1 Kb. | | #29813 |
Bog'liq 1 maruza Algoritm va uning ta’riflari maktabgacha-katta-yoshdagi-bolalarini-kasblar-bilan-tanishtirish, 10.Қаршиева Мa j q i- buyruqlarning asl belgilari boshqacha bo'lishi kerak. Agar bu shart bajarilsa, mashina chaqiriladi deterministik , aks holda - noaniq ... Mashina alohida vaqtda ishlaydi.
Shunday qilib, Tyuring mashinasining har bir lahzada, uning keyingi xatti -harakatlarini aniqlash mumkin bo'lgan to'liq tavsifi quyidagilarni o'z ichiga oladi:
mashinaning ichki holati, lentaga yozilgan so'z va ma'lum bir vaqtda o'qiladigan belgi. Tyuring mashinasining to'liq holati chaqiriladi konfiguratsiya
Tyuring mashinasining ishlashi konfiguratsiyalar ketma -ketligi sifatida ifodalanishi mumkin k 1® k 2®…® k n.
Dastlabki konfiguratsiya - chapdagi bo'sh bo'lmagan belgini holatga o'qish q 1
Standart yakuniy konfiguratsiya - mashina oxirgi holatga kirdi:
Agar mashina yakuniy holatga kirgan bo'lsa, bu kirish so'ziga qo'llaniladi, agar u abadiy ishlayotgan bo'lsa, u holda mashina bu so'zga taalluqli emas.
MT - bu kirish alifbosi, davlatlar alifbosi va dasturidan iborat to'plam. M = ... A - kirish alifbosi Q - ichki alifbo P - dastur
Mashina dasturini quyidagicha sozlash mumkin:
1) buyruqlar ro'yxati: a j q i® a k q n S
2) jadval yordamida
|
a 0
|
a 1
|
a 2
|
q 0
|
a k, q m, S
|
|
|
q 1
|
|
|
|
3) predikat grafigi yordamida (tepaliklar holatlar, har bir buyruq yoyga to'g'ri keladi)
Turing mashinasi dizayni:
Tyuring mashinasini yaratish - uning dasturini tuzish. U ikki bosqichda amalga oshiriladi:
1) hal qilinayotgan masala algoritmining og'zaki tavsifi
2) algoritmning og'zaki tavsifini Tyuring mashinasi tiliga tarjima qilish (buning uchun, A, Q, NS)
Misol: f (n) = n + 1 funktsiyasini hisoblaydigan Tyuring mashinasini qurish, bu erda n ikkilik tizimda berilgan.
A={0,1,a 0), Q to'plami dasturni tuzish jarayonida aniqlanadi.
Algoritm:
1. Boshni o'ta o'ng holatidan o'ta chapga siljitish
2. agar o'ta o'ng holatida mashina 0 ni o'qisa, uni 1 -katakka qo'ying va to'xtating, agar bosh 1 o'qisa, uni 0 -katakchaga qo'ying va chapga bir qadam siljiting.
2 -qadamni takrorlang
Misol: Lentaga tabiiy kasr raqami yozilgan. Bu raqamni 1 ga ko'paytiradigan Tyuring mashinasini qurish kerak. Dastlab bosh raqamning birinchi raqamini ko'rsatadi. Biz olamiz: A = (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a 0), Q = (q 1, q 2, q 0). P - jadvalga qarang.
|
|
|
|
|
|
q 1
|
0> q 1
|
1> q 1
|
2> q 1
|
3> q 1
|
4> q 1
|
q 2
|
1 = q 0
|
2 = q 0
|
3 = q 0
|
4 = q 0
|
5 = q 0
|
|
|
|
|
|
a 0
|
5> q 1
|
6> q 1
|
7> q 1
|
8> q 1
|
9> q 1
|
a 0 <="" td="" “" "”" "‘" "’";">
|
6 = q 0
|
7 = q 0
|
8 = q 0
|
9 = q 0
|
0<="" td="" “" "”" "‘" "’";">
|
1 = q 0
|
Umumiy fikr - boshni raqamning oxirgi raqamiga o'tkazing va agar bu raqam 9 bo'lmasa, uni bittaga ko'paytiring, aks holda uni nolga aylantiring va oldingi katakka o'ting.
Mashinalarning tarkibi:
Mashinalarning tarkibi - bu ikkita mashinaning ketma -ket bajarilishi.
T 1=(A 1, 1 -savol, P 1) T 2=(A 2, 2 -savol, P 2) 1 -savolÇ 2 -savol=Æ
Tarkibi mashinalar T 1° T 2 mashinani chaqirdi T(A, Q, NS), qaerda A=A 1È A 2; Q=(1 -savolÈ 2 -savol)\{q 10} (q 10- oxirgi holat T 1). Avtomobil T quyidagi qoidaga muvofiq ishlaydi: U- ba'zi so'zlar, T(U)=T 1° T 2(U)=T 2(T 1(U))
Teorema. Mashinalarning tarkibi T 1° T 2 mavjud.
1 -savol={q 10, q 1,…, q n}
2 -savol={q 20, q` 1 , …, q` n), keyin Q ni qurish uchun q 10 holatini olib tashlaymiz va uni qayta nomlaymiz q n +1, bu ikkinchi mashinaning boshlang'ich holatiga to'g'ri keladi va boshqa barcha holatlar q` i = q n + 1 .
Tyuring hisoblangan funktsiyalar:
F (x 1 ... x n) funktsiya deyiladi Tyuring hisoblab chiqilgan agar argumentlar qiymatlari berilganida bu funksiyaning qiymatini hisoblaydigan Tyuring mashinasi bo'lsa. F (x 1… x n) funktsiyasi natural sonlar to'plamida berilgan, lekin algoritmlar nazariyasi NÈ (0) natural sonlarning kengaytirilgan to'plamini ko'rib chiqadi.
Lentadagi f (x 1 ... x n) funktsiyasining argumentlari quyidagi so'z bilan ifodalanadi:
Har bir bahsda bu bahsning qiymatiga teng bo'lgan tayoqlar bor. Agar f funktsiyasi x 1 ... xn o'zgarmaydigan qiymatlar majmui bo'yicha aniqlangan bo'lsa, Tyuring mashinasining ishlashi natijasida qatorda yozilgan shunday tayoqlar qolishi kerak. lenta, bu to'plamdagi funktsiyaning qiymatiga teng. Agar berilgan funktsiyada f funktsiyasi aniqlanmagan bo'lsa, Tyuring mashinasi cheksiz ishlashi kerak.
Nazorat savollari
1. Аlgoritmlar turlarini ayting.
2. Hisoblashda algoritmlarning oʼrni.
3. Аlgoritmlar orqali yechiluvchi masalalarga misollar keltiring.
|
| |
