Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій icon

Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій



НазваниеФормальні моделі алгоритмів та алгоритмічно обчислюваних функцій
страница1/4
Дата конвертации17.09.2012
Размер0.83 Mb.
ТипДокументы
  1   2   3   4



Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій

1. МАШИНИ З НАТУРАЛЬНОЗНАЧНИМИ РЕГІСТРАМИ

Машина з натуральнозначними регiстрами (скорочено МНР) є iдеалiзованою моделлю комп’ютера. МНР мiстить, взагалі кажучи, нескiнченну кiлькiсть регiстрiв, вмiстом яких є натуральнi числа. Регiстри нумеруємо натуральними числами, починаючи з 0, позначаючи їх R0 , R1 , ..., Rn , ... Вмiст регiстру Rn позначаємо ’Rn .

Послiдовнiсть (’R0 , ’R1, ..., ’Rn , ...) вмiстiв регiстрiв МНР назвемо конфiгурацiєю МНР.

МНР може змiнити вмiст регiстрiв згiдно виконуваної нею команди. Скiнченний список команд утворює програму МНР. Команди програми послiдовно нумеруємо натуральними числами, починаючи з 1. Номер команди в програмі називатимемо адресою команди. МНР-програму з командами I1 , I2 ,..., Ik будемо позначати I1I2...Ik. Довжину (кiлькiсть команд) МНР-програми P позначимо |P|.

Команди МНР бувають 4-х типiв.

Тип 1. Обнулення n-го регiстру Z(n): ’Rn : 0.

Тип 2. Збiльшення вмiсту n-го регiстру на 1 S(n): ’Rn :’Rn+1.

Тип 3. Копіювання вмісту регістру T(m,n): ’Rn :’Rm

(при цьому ’Rm не змiнюється).

Тип 4. Умовний перехiд J(m,n,q): якщо ’Rn =’Rm , то перейти до виконання q-ї команди, iнакше виконувати наступну за списком команду програми.

Число q в команді J(m,n,q) назвемо адресою переходу.

Команди типiв 1-3 називають арифметичними. Пiсля виконання арифметичної команди МНР повинна виконувати наступну за списком команду програми.

Виконання однiєї команди МНР назвемо кроком МНР.

Зауважимо, що формальними моделями алгоритмів є саме МНР-програми, поняття МНР використовується для опису функціонування МНР-програм.

Виконання програми МНР починає, перебуваючи в деякiй початковiй конфiгурацiї, з виконання 1-ї за списком команди. Наступна для виконання команда програми визначається так, як описано вище. Виконання програми завершується (програма зупиняється), якщо наступна для виконання команда вiдсутня (тобто номер наступної команди перевищує номер останньої команди програми). Конфiгурацiя МНР в момент завершення виконання програми називається фiнальною, вона визначає результат роботи МНР-програми над даною початковою конфiгурацiєю.

Якщо МНР-програма ^ P при роботi над початковою конфiгурацiєю (a0, a1, ...) нiколи не зупиняється, цей факт позначаємо P(a0, a1, ...), якщо ж коли-небудь зупиниться, цей факт позначаємо P(a0, a1,...). Якщо МНР-програма P при роботi над початковою конфiгурацiєю (a0, a1, ...) зупиняється iз фiнальною конфiгурацiєю (b0, b1, ...), цей факт позначатимемо так: P(a0, a1, ...)(b0, b1, ...).

МНР-програми як моделі алгоритмів є фінітними об’єктами, тому обмежимося розглядом скінченних конфігурацій. Конфiгурацiю вигляду (a0, a1, ..., aп , 0, 0, ...), в якiй ’Rm= 0 для всiх m>n, назвемо скiнченною. Таку конфігурацію позначаємо (a0, a1, ..., an ). Зрозуміло, що якщо МНР-програма P починає роботу над скiнченною початковою конфiгурацiєю, то в процесi виконання P МНР перебуватиме тiльки в скiнченних конфiгурацiях.

МНР-програми P та Q назвемо еквiвалентними, якщо при роботi над однаковими початковими конфiгурацiями вони або обидві зупиняються з однаковими фiнальними конфiгурацiями, або обидвi не зупиняються.

МНР-програма ^ P обчислює часткову n-арну функцiю f:NпN, якщо f(a1, a2, ..., aп)=bP(a1, a2, ..., aп)(b,...).

Замiсть P(a1, a2 ,...)(b,...) надалі будемо писати P(a1 , a2 ,...)b.

Функцiю f:NпN називають МНР-обчислюваною, якщо iснує МНР-програма, яка обчислює цю функцiю.

Кожна МНР-програма обчислює безліч функцій, заданих на N, але, зафіксовуючи наперед арність функцій (тобто кількість компонент початкових конфігурацій), отримуємо, що кожна МНР-програма обчислює єдину функцію заданої арності.

Зауважимо, що кожну функцiю, задану на N, можна трактувати як предикат, інтерпретуючи значення 1 та 0 як істиннісні значення “Т” та “F” відповідно. В цьому випадку в ролі предикату виступає його характеристична функція.

Розглянемо приклади МНР-програм для функцій та предикатів.

Приклад 1. МНР-програма для всюди невизначеної функції:

  1. J(0,0,1)

Приклад 2. МНР-програма для предикату "x=y":

  1. J(0,1,3)

  2. J(0,0,4)

  3. S(2)

  4. T(2,0)

Приклад 3. МНР-програма для функцiї f(x, y)=x+y:

  1. J(1,2,5)

  2. S(0)

  3. S(2)

  4. J(0,0,1)

Приклад 4. МНР-програма для функцiї f(x)=2x:

  1. T(0,1)

  2. J(1,2,6)

  3. S(0)

  4. S(2)

  5. J(0,0,2)

Приклад 5. МНР-програма для функцiї f(x, y)=x-y:

  1. J(0,1,5)

  2. S(1)

  3. S(2)

  4. J(0,0,1)

  5. Т(2,0)

Приклад 6. МНР-програма для функцiї f(x, y)=

  1. J(0,1,7)

  2. J(0,2,6)

  3. S(1)

  4. S(2)

  5. J(0,0,1)

  6. Z(2)

  7. Т(2,0)

Приклад 7. МНР-програма для функцiї f(x, y)=max(x, y):

  1. J(0,2,5)

  2. J(1,2,6)

  3. S(2)

  4. J(0,0,1)

  5. Т(1,0)

Приклад 8. МНР-програма для функцiї f(x)=x/2:

  1. J(0,2,6)

  2. S(2)

  3. S(2)

  4. S(1)

  5. J(0,0,1)

  6. Т(1,0)

Приклад 9. МНР-програма для функцiї f(x)=[x/2]:

  1. J(0,2,7)

  2. S(2)

  3. J(0,2,7)

  4. S(2)

  5. S(1)

  6. J(0,0,1)

  7. Т(1,0)

Приклад 10. МНР-програма для функцiї f(x)=sg(x):

  1. J(0,1,4)

  2. Z(0)

  3. S(0)

Приклад 11. МНР-програма для функцiї f(x, y)=xy,

  1. J(3,1,9)

  2. J(0,2,6)

  3. S(2)

  4. S(4)

  5. J(0,0,2)

  6. Z(2)

  7. S(3)

  8. J(0,0,1)

  9. Т(4,0)



2. МАШИНИ ТЬЮРIНГА

Пiд (детермінованою) машиною Тьюрiнга (скорочено МТ) будемо розумiти впорядковану 5-ку (Q,T,, q0 ,q*), де:

Q скiнченна множина внутрiшнiх станiв;

T  скiнченний алфавiт символiв стрiчки, причому T мiстить спецiальний символ порожньої клiтки ;

 : QTQT{R,L,}  однозначна функцiя переходiв;

q0Q  початковий стан;

q*Q  фiнальний стан.

Функцiю переходiв на практицi задають скiнченною множиною команд одного з 3-х видiв: qapbR, qapbL та qapb, де p, qQ, a, bT, QT. При цьому, як правило, не для всiх пар (q,a)QT iснує команда з лiвою частиною qa. Це означає, що функцiя не є тотальною. Проте зручніше вважати функцію тотальною, тому для всiх пар (q,a)D неявно (не додаючи вiдповiднi команди вигляду qaqa), вводимо довизначення (q,a)=(q,a,).

Неформально МТ складається з скiнченної пам’ятi, роздiленої на клiтки нескiнченної з обох бокiв стрiчки та голiвки читання-запису. В кожнiй клiтцi стрiчки мiститься єдиний символ iз T, причому в кожен даний момент стрiчка мiстить скiнченну кiлькiсть символiв, вiдмiнних вiд символа . Голiвка читання-запису в кожен даний момент оглядає єдину клiтку стрiчки.

Якщо МТ знаходиться в станi q та голiвка читає символ a, то при виконаннi команди qapbR (команди qapbL, команди qapb) МТ переходить в стан p, замiсть символу a записує на стрiчцi символ b та змiщує голiвку на 1 клiтку направо (відповідно на 1 клiтку налiво, залишає голiвку на мiсцi).

Конфiгурацiя, або повний стан МТ  це слово вигляду xqy, де x,yT*, qQ. Неформально це означає, що на стрiчцi записане слово xy, тобто злiва i справа вiд xy можуть стояти тiльки символи , МТ знаходиться в станi q, голiвка читає 1-й символ пiдслова y.

Конфiгурацiю вигляду q0x, де 1-й та останнiй символи слова x вiдмiннi вiд , називають початковою. Конфiгурацiю вигляду xq*y називають фiнальною. Пiсля переходу до фiнального стану, отже, до фiнальної конфiгурацiї, МТ зупиняється.

Нехай МТ знаходиться в конфiгурацiї xcqay, де x,yT*, a, cT, qQ. Пiсля виконання команди qapbR (команди qapbL, команди qapb) МТ перейде до конфiгурацiї xcbpy (вiдповiдно до конфiгурацiї xpcby, конфiгурацiї xcpby).

Кожна МТ задає вербальне вiдображення T* T* таким чином.

МТ М переводить слово uT в слово vT*, якщо вона з почат-кової конфiгурацiї q0u переходить до фiнальної конфiгурацiї xqy, де qF*, xy=v, , {}* . При цьому перший та останнiй символи слова v вiдмiннi вiд , або v=. Цей факт записуємо так: v=M(u).

Якщо МТ M, починаючи роботу з початкової конфiгурацiї q0u, нiколи не зупиниться, кажуть, що M зациклюється при роботi над словом u. Тодi M(u) не визначене.

МТ M1 та M2 еквiвалентнi, якщо вони задають одне і те ж вербальне вiдображення.

МТ M обчислює часткову функцiю f:Nk→N, якщо вона кожне слово вигляду переводить в слово у випадку (x1,...,xk)Df , та M() невизначене при (x1,...,xk)Df .

Функцiя називається обчислюваною за Тьюрiнгом, або МТ-обчислюваною, якщо iснує МТ, яка її обчислює.

Зауважимо, що кожна МТ обчислює безліч функцій натуральних аргументів та значень, але зафіксовуючи наперед арність функцій, дістаємо, що кожна МТ обчислює єдину функцію заданої арності.

Розглянемо приклади МT.

Приклад 1. МТ, яка обчислює функцiю x+y:

q0| q0|R

q0# q0|R

q0 q1L

q1|  q*

Приклад 2. МТ, яка обчислює функцiю f(x, y) =x-y:

q0| q1R

q1| q1|R

q1# q1#R

q1 q2L

q2| q3L

q3| q3|L

q3# q3#L

q3 q0R

q2# q*|

q0# q4R

q4 q*

Приклад 3. МТ, яка обчислює функцiю f(x, y)=

q0| q1R

q1| q1|R

q1# q1#R

q1 q2L

q2| q3L

q3| q3|L

q3# q3#L

q3 q0R

q2# q*|

q0# q4R

q4| q4R (єдина відмінність від МТ для f(x, y) =x-y )

q4 q*

Приклад 4. МТ, яка обчислює функцiю f(x)=sg(x):

q0 q*

q0| q1|R

q1| q1R

q1 q*

Приклад 5. МТ, яка обчислює предикат "x парне":

q0| q1R

q1| q0R

q0 q*|

q1 q*

Приклад 6. МТ, яка обчислює функцiю f(x, y)=x+2y:

q0| q0|R

q0# q0#R

q0 q1L

q1| q2R

q2| q2|R

q2 q3|L

q3| q3|L

q3 q1|L

q1# q4|L

q4| q4|L

q4 q5R

q5| q*

Приклад 7. МТ, яка обчислює функцiю f(x)=2x

q0| q0|R

q0 q1aL

q1| q1|L

q1 q2R

q2| q3R

q3| q3|R

q3a q3 aR

q3 q4L

q4a q5R

q5a q5 aR

q5 q6 aL

q6a q6 aL

q6 q4aL

q4| q4|L

q4 q2R

q2a q2|R

q2 q*

Приклад 8. МТ, яка обчислює функцiю f(x, y)=xy

q0# q1R

q1| q1R

q1 q*

q1a q1|R

q0| q2R

q2| q2|R

q2# q3#R

q3| q4R

q4| q4|R

q4a q4 aR

q4 q5 aL

q5| q5|L

q5a q5 aL

q5 q3|R

q3a q6 aL

q6| q6|L

q6# q6 #L

q6 q0R

q3 q7L

q7# q7L

q7| q7L

q7 q*

Приклад 9. МТ, яка обчислює функцiю f(x)=[x/3]:

q0 q*

q0| q1L

q1| q2L

q2| q2|R

q2 q3L

q3 a q3 aL

q3| q4aL

q4| q4|L

q4 q0R

q1 a q0 a

q2 a q0 a

q0a q0|R

Приклад 10. МТ, яка кожне слово хТ* переводить в слово х#х

(тут #T).

q0 t q0 tR для всіх tT

q0 q1#L

q1 t q1 tL для всіх tT

q1 q2R

q2 t qt R для всіх tT

qt p qt pR для всіх tT, pT{#}

qt  q't tL для всіх tT

q't p q't pL для всіх tT, pT{#}

q't  q2tR для всіх tT

q2# q*#

  1   2   3   4




Похожие:

Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій iconПараметри-процедури І параметри-функції
...
Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій iconТипи алгоритмів способи запису алгоритмів
Блок модифікації – використовується для зміни в залежності від попередніх значень
Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій icon8 Основні типи виробничих функцій. 2 Линийна виробнича функція
Виробнича функція Леонтьєва ( вфл ) в моделі “витрати  випуск ”. Ця функція записується
Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій iconНаближення функцій. Задача інтерполяції
Задача наближення функцій виникає при розв’язанні багатьох задач ( обробка експериментальних даних, чисельне диференціювання та інтегрування...
Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій iconРеалізація функцій менеджменту на підприємствах залізничного транспорту
Аналіз реалізації основних функцій управління дтго „Південно-Західної залізниці” 27
Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій iconСаморегуляція функцій організму”
Роль нервової системи у координації функцій організму та взаємозв’язку його з навколишнім середовищем
Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій iconЛабораторна робота №2 “ багатофакторні лінійні економетричні моделі ”
Мета роботи: Набуття практичних навичок побудови економетричної моделі у вигляді багатофакторної класичної лінійної регресії, її...
Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій iconЛабораторна робота №2 “ Багатофакторні лінійні економетричні моделі” Варыант №24
Мета роботи: Набуття практичних навичок побудови економетричної моделі у вигляді багатофакторної класичної лінійної регресії, її...
Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій iconІнтегрування раціональних функцій
Раціональні функції складають важливий клас функцій, інтеграли від яких завжди виражаються через елементарні функції. Нехай треба...
Формальні моделі алгоритмів та алгоритмічно обчислюваних функцій iconN лабораторна робота №3 “Нелінійні економетричні моделі”
Мета роботи: Набуття практичних навичок побудови економетричної моделі у вигляді нелінійної регресії (на основі неокласичної виробничої...
Разместите кнопку на своём сайте:
Документы


База данных защищена авторским правом ©rushkolnik.ru 2000-2014
При копировании материала обязательно указание активной ссылки открытой для индексации.
обратиться к администрации
Документы