Машина Тюрінга
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?ндекси, оскільки до цього вони в нім не містилися.(Надалі скорочено викладу приводитимуться переважно математичні записи роботи алгоритму).
Крок № 3:
П. 2:
Крок № 4:
П. 2:
Крок № 5:
П. 2:
Слід зазначити, що в результаті цього проходу вершина Х6 не поміняла своєї ваги, оскільки вже мала максимально можливу.
Крок № 6:
П. 2:
Крок № 7:
Крок № 8:
Крок № 9:
Крок № 10:
П. 2: М=0, виконується п. 3.
Отже, на даний момент отриманий граф, усі вершини якого набули максимально можливих значень. А оскільки масив вершин, що змінили вагу, порожній, те управління передається третьому пункту алгоритму, який відмічає довгий шлях. Слід особливо відмітити, що, як видно з попередніх обчислень, максимальні ваги вершин можуть бути досягнуті при просуванню по різних дугах. Для більшої наочності прикладу нижче приведений вид графа на цьому етапі:
На етапі виконання третього пункту алгоритму критерієм для виділення дуги, як і для алгоритму знаходження найкоротшого шляху, являється збіг різниці вагів відповідних вершин з вагою самої дуги. Таким чином, починаючи з вершини Х8 отримаємо:
Крок № 11: Для виділеної вершини x8
П. 3:
, тому дуга виділяється.
, дуга не виділяється .
дуга не виділяється.
виділяється вершина .
Крок № 12: Для виділеної вершини x7
П. 3:
, тому дуга виділяється.
, і дуга виділяється, одночасно
дуга не виділяється
виділяється вершина X1, та X2
Крок № 13: Для виділеної вершини Х6
П. 3:
, тому дуга виділяється.
, дуга не виділяється
виділяється вершина х3,
Крок № 14: Для виділеної вершини Х5
П. 3:
, тому дуга не виділяється.
, і дуга виділяється, одночасно
слід зазначити, що вершина не виділяється, оскільки вже виділена.
Крок № 15: Для виділеної вершини х4
П. 3:
, і дуга виділяється,
Слідує відмітити, що вершина не виділяється, оскільки вже виділена.
Крок № 16: Для виділеної вершини х3
П. 3:
і дуга виділяється
Слідує відмітити, що вершина не виділяється, оскільки вже виділена.
Крок №17: Для виділеної вершини х2
П.3:
і дуга виділяється,
Слідує відмітити, що вершина не виділяється, оскільки вже виділена.
рок №18: Для виділеної вершини х1
П.3:
Оскільки в цю вершину не входить не оної дуги і більше немає відмічених вершин, переходжуватимемо до етапу складання довгого шляху.
Отже сполучаючи дуги за принципом: кінцевий індекс попередньої - початковий наступний, отримуємо три довгих шляхів завдовжки 14:
Дуги-претенденти:
Найдовший шлях :
Для більшої наочності зображує граф у своєму кінцевому стані, нанісши на нього значення вагів вершин, ваги дуг, а так само виділивши довгий шлях :
Приведемо табличний метод запису процесу :
X1X2X3X4X5X6X7X8M000000001034200502,3,4,7034240505,7034287505,6034287506,7034287514803428751480342875148
Висновок: в процесі виконання курсового проекту було побудовано алгоритми сортування методом простого вибору , зроблені відповідні контрольні приклади, а також алгоритм пошуку довгого шляху на графах.
Машина Тюрінга
Основні поняття
Машина Тюрінга - це кінцевий автомат, забезпечений безконечною стрічкою і читаючою/записоючю голівкою (просто голівкою). Як і автомат, машина Тюрінга (МТ) описується п'ятіркою (X, Y, Q ?, ?. Тут:={x0, x1, x2 ., xn} - вхідний алфавіт, що містить порожню букву x0;={y0, y1, y2.,yn} - вихідний алфавіт;={q0, q1, q2 ., qm} - безліч внутрішніх достатків, причому q0 - Стоп-стан (у цьому стані МТ не працює);
d: QX >Q -функція переходів в наступний стан;
l: QX >Y -функція виходів.
У свою чергу, Y=XU, де U={R, L, S}- команда на переміщення голівки: R -зрушитися управо, L -вліво, S - стояти на місці.
Задавая МТ [5], замість двох функцій можна користуватися однією(що поєднуєх работу входу и виходу): j: QX QXU, зіставляється кожній парі (qi, xj) вихідну трійку (qk, u, xl), uU. Функція j повнвстю описує работу МТ і називається логічною функцією машини Тюрінга. Таблиця цієї функції називається функціонально схемо, або програмою машини Тюрінга. На кожному такті работи МТ головка оглядає в деякій комірці символ xj, а сама МТ знаходиться в деякому стані qi, що описується вхідно парою (qi, xj). В залежності від вхідної пари МТ виконує команду (qk, u, xl), uU, т.е. записує в оглядову комірку символ xl, пересуває головку в залежності від значення u и переходить в новий стан qk. Якщо на деякому этапі работи МТ переходить в СТОП-стан, то подальші зміни в машині не відбуваються - машина зупиняється.
Послідовність вхідних символів, записаних у комірки стрічки, називатимемо вхідним словом. Сукупність на стрічці слова і стану МТ для комірки стрічки, що оглядає в даний момент, називається конфігурацією в МТ. Конфігурація вказує вхідну пару і визначає подальшу роботу МТ. Якщо з деякої початкової конфігурації через деяке число тактів МТ приходить до Стоп-стан, то говоритимемо, що МТ застосовна до вхідного слова; послідовність символів на стрічці у момент зупинки називатимемо результатом перетворення вхідного слова МТ при даній початковій конфігурації, або просто вихідним словом. Якщо ж Стоп-стан МТ не настає, то говоритимемо, що МТ не застосовна до вхідного сл?/p>