|
Raqamlar to'plami
Algoritmlar nazariyasida bir nechta o'zgaruvchilarning funktsiyalarini o'rganishni bitta o'zgaruvchining funktsiyalarini o'rganishga kamaytirishga imkon beradigan usul keng tarqalgan. Bu raqamlar to'plamlari va ularning sonlari o'rtasida bijektiv moslik bo'lishi uchun raqamlar to'plamini raqamlashga asoslangan va uning sonini raqamlar to'plami va raqamlar bo'yicha aniqlaydigan funktsiyalar umumiy rekursivdir. Masalan, ikkita mustaqil o'zgaruvchini o'z ichiga olgan funktsiya uchun (x, y), bu xaritalash h (x, y) quyidagicha bo'lishi mumkin:
1 -rasm.
(X, y) juftlari qisman tartiblangan N (2) to'plamni hosil qilsin. Agar h (x, y) = n berilgan bo'lsa, unda teskari xaritalash mavjud: x = h -1 1 (n) va y = h -1 2 (n), ya'ni h (h -1 1 (n), h -1 2 (n)) = n. Bu har qanday juftlik (x, y) uchun n sonini hisoblash imkonini beradi va aksincha, x va y qiymatlarini hisoblash uchun n sonini ishlatadi:
Bu qoidalar yordamida h 2 (x, y, z) = h (h (x, y), z) = n va aksincha, uchlik raqamlari - x qiymatlari bo'yicha sonlarni hisoblash mumkin. , y, z. Masalan, agar h 2 (x, y, z) = n bo'lsa, u holda z = h -1 2 (n), y = h -1 2 (h -1 1 (n)), x = h -1 1 ( h -1 1 (n)), h 2 (x, y, z) = h (h (h -1 1 (h -1 1 (n)), h -1 2 (h -1 1 (n)) ), h -1 2 (n)). Uchlik (x, y, z) qisman tartiblangan N (3) to'plamni hosil qiladi. Xuddi shunday, ixtiyoriy sonlar uchun bizda:
h n-1 (x1, x2,…, xn) = h (h… h (h (x1, x2), x3)… x n-1), xn). Agar h n -1 (x1, x2, ..., xn) = m bo'lsa, u holda xn = h -1 2 (m), x n -1 = h -1 2 (h -1 1 (m)),. .. .................................., x2 = h -1 2 (h -1 1 (. .. h -1 1 (m) ...)), x1 = h -1 2 (h (... h (m) ...)).
N (1), N (2), ..., N (i), ..., N (n) to'plamlar sonining raqamlanishini hisobga olgan holda, bu erda N (i) - sonlar (i) to'plamlar to'plami. , biz ixtiyoriy M = N (1) N (2) ... N (i) .. N (n) sonlarning birlashgan raqamlanishini o'rnatishimiz mumkin, bu erda M N. Har qanday n N uchun bizda h (x1, x2, ..., xn) = h (hn -1 (x1, x2, ..., xn), n -1).
Agar h (x, 1x, 2 ..., x) n = m bo'lsa, u holda hn -1 (x, 1x, 2 ..., x) n = h -1 1 (m), n = h -1 2 (m) +1. Yuqoridagi formulalar yordamida x1, x2, ..., xn qiymatlarini tiklashingiz mumkin.
Shunga o'xshash ma'lumotlar.
Tyuring mashinasining ishlashi:
Algoritmning uchta asosiy tushunchasidan ikkinchisi mashina matematikasi bilan bog'liq. Algoritm har qanday vaqtda eng oddiy operatsiyalarni bajarishga qodir bo'lgan eng oddiy deterministik qurilma hisoblanadi. Asosiy model - Tyuring mashinasi.
Tyuring mashinasi uchta alifbo bilan ishlaydi:
1. kiritish alifbosi A={a 0…a n), uning yordamida kirish, oraliq, chiqish ma'lumotlari yoziladi. a 0- bo'sh belgi (ahamiyatsiz nol, Ù, V, #), a 1- 1 yoki |
2. ichki alifbo yoki davlatlar alifbosi Q={q 0…q m}, q 0- oxirgi holat q 1- dastlabki holat q 0 ... q n- ish sharoitlari
3. Alfavit siljishi (L, W, H) yoki (-1, +1, 0) (chapda, o'ngda, joyida)
Tyuring mashinasi quyidagi qismlardan iborat:
1) tasma, har ikki yo'nalishda ham cheksiz. Potentsial cheksizlik har bir lahzada yakuniy so'z lentaga yozib qo'yilishini anglatadi, lekin agar kerak bo'lsa, kerakli miqdordagi katakchani so'zning chap va o'ng tomonida to'ldirish mumkin. Lenta hujayralarga bo'linadi, ularning har birida kirish alifbosining faqat bitta belgisi mavjud. Bo'sh katakchalarda bo'sh belgi bor. Agar hujayradagi ma'lumotlarni o'chirish kerak bo'lsa, unda bo'sh belgini yozish kifoya.
2) nazorat qilish qurilmasi(UU), u dastur yordamida Tyuring mashinasini boshqaradi. UU har bir vaqtda alifbo holatidan faqat bittasida bo'lishi mumkin Q.
3) bosh(o'quvchi va yozuvchi) vaqtning har bir daqiqasida quyidagi harakatlarni bajaradi
Hujayraga yozilgan belgini o'qiydi
Uni alifbodagi boshqa belgi bilan almashtiradi A yoki xuddi shunday qoldiradi
Ip bo'ylab o'ngga, chapga bitta hujayraga o'tadi yoki joyida qoladi
Tyuring mashinasi qoidasi:
Tyuring mashinasi, holatda q i va qahramonni o'qish a j, xarakterini yozadi a k, davlatga o'tadi q e, smenani amalga oshiradi. Shu bilan birga, ular mashinaning bitta buyruqni bajarganini aytishadi: a j q i® a k q e S SÎ (L, P, N)
Buyruqlar to'plami MT dasturi deb ataladi.
Do'stlaringiz bilan baham: |
