Машина Тюрінга
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
?ва при даній конфігурації.
Оскільки МТ перетворить допустимі вхідні слова в деякому алфавіті у вихідні слова в тому ж алфавіті, то з математичної точки зору МТ ( це просто певний алгоритм для перетворення машинних слів. Тим самим за допомогою машини Тюрінга уточнюється інтуїтивне поняття алгоритму.
Постановка завдання
Розмітка чисел з кроком k заданим на стрічці, тобто необхідно замість 0 поставити символ * після кожного k-ого числа. Вихідні дані зберегти. Кодувати число n як n=n+1 одиниць. Після завершення роботи голівка зліва від послідовності над першим 0.
Ідея вирішення
Пропустити k послідовності символів 1, про факт завершення судимо по появі 0. Замість 0 записати * і рухатися далі, поки послідовність не закінчиться, після встановити голівку над першим 0 після останнього числа послідовності.
Словесний опис алгоритму
1.Встановлюємо голівку над першою одиницею послідовності.
2.Перевірка символу, якщо 1| то крок управо і на п.2, інакше на п.3
.Перевірка символу, якщо 1| то крок управо і на п.3, інакше на п.4
.Якщо поточний символ 1, то крок вліво записати *, крок управо і перейти на п.2; інакше п.5.
.Якщо 0, то крок вліво і на п.5, інакше крок управо і зупинка.
Використовувані символи на стрічці
По умові завдання на стрічці в обов'язковому порядку мають бути присутніми символи 0 і 1, оскільки весь порожній простір стрічки заповнений символами 0, а за допомогою символу 1 кодуються самі числа.
Окрім вище вказаних використовуватиметься символ *, використовуваний для відмітки кожного k-ого числа.
Структури даних
Введемо наступні позначення:
Для команд, що оперують з вмістом комірки:
Z=x - перевірка наявності символу х - записати в поточну ячйка символ .
Для команд переміщення голівки:
- R - зрушити управо на одну комірки у.
- L - зрушити вліво на одну комірку.
GRx,y(w),[GLx,y(w)] - рухатися управо [вліво], пропускаючи групи символів поки не зустрінеться комірку з символом w, причому параметр у може бути відсутнім.
Функціональна схема М.Т.
В данной М.Т. аварійні ситуациї по причині математичих неспівпадінь неможливі, єдиною причиною некоректної работи машини Тюрінга можуть бути лише фізичні(апаратні) проблеми управління машиною, але даний тип виключних ситуацій на алгоритмічному рівні обробити неможливо.
Q01*10Rq11Rq220Rq31Rq230Rq41Rq340Rq51Rq450Lq71Lq66*Rq270Lq71Rq8*Rq880!Q0
Приклад роботи М.Т.
ТактСтанСитуація на стрічці0Q1…0 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .1Q1…0 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .2Q2…0 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .3Q2…0 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .4Q3…0 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .5Q3…0 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .6Q3…0 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .7Q3…0 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .8Q4…0 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .9Q4…0 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .10Q4…0 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .11Q4…0 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .12Q4…0 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .13Q5…0 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .14Q6…0 1 1 0 1 1 1 0 1 1 1 1 0 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .15Q2…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .16Q2…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .17Q3…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .18Q3…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .19Q3…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .20Q4…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .21Q4…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .22Q4…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .23Q4…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .24Q4…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .25Q4…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .26Q5…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .27Q6…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 0 1 1 0 0 . . .28Q2…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 * 1 1 0 0 . . .29Q2…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 * 1 1 0 0 . . .30Q2…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 * 1 1 0 0 . . .31Q3…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 * 1 1 0 0 . . .32Q4…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 * 1 1 0 0 0 . . .33Q5…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 * 1 1 0 0 0 0 . . .34Q7…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 * 1 1 0 0 0 0 . . .35Q7…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 * 1 1 0 0 0 0 . . .36Q7…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 * 1 1 0 0 0 0 . . .37Q7…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 * 1 1 0 0 0 0 . . .38Q8…0 1 1 0 1 1 1 0 1 1 1 1 * 1 0 1 1 0 1 1 1 1 1 * 1 1 0 0 0 0 . . .
Висновок
Після виконання даної курсової роботи я зробив деякі висновки:
Сортування методом простого вибору - це найперше сортування яке приходить до розуму, адже алгоритм виконання цього сортування є простим і досить зрозумілим. Таким, що навіть звичайна людина зможе без особливих проблем його зрозуміти. Також сортування простим вибором має і свої недоліки - це час, який затрачається на його обробку, а також громіздкість при покроковому виконанні алгоритму.
Хвилевий алгоритм знаходження найдовшого шляху - це є той самий алгоритм знаходження найменшого шляху, тільки попередньо усім вершинам надаються ваги із значенням 0. Автоматично буде шукатись найдовший шлях. Також можна зауважити, що коли були знайдені дуги, то не всі вони були використанні у побудові найдовшого шляху.
Алгоритм Машини Тюрінга був побудований таким чином, що кожен крок контролює одну послідовність непустих значень, і коли були пройдені три такі кроки, то на місці пустоти записується *, коли ж послідовність закінчується. То машина зупиняється.
Список літератури
1. Паулін О.Н. Методичні вказівки до курсової работи з дисципліни Алгоритми та структури даних - Одеса, ОНПУ 2004
. Томас Х. Кормен, Чарльз І. Лейзерсон, Рональд Л. Рівест, Кліффорд Штайн Алгоритми: побудова та аналіз = INTRODUCTION TO ALGORITHMS. - 2-ге ивид. - М.: Вільямс, 2006.
. Колмогоров А.Н. Теорія інформацїї і теорія алгоритмів. - М.: Наука, 1987
. Джон Хо