Курсова робота Машина Тюрінга

Вступ

1. Теоретичні відомості

1.1. Алгоритм сортування методом простого виробу

1.1.1. Словесний Вербальний опис алгоритму

1.1.2.Структура даних

1.1.3. Опис схеми алгоритму

1.1.4. Контрольний приклад

1.2. Хвилевий алгоритм пошуку довгого шляху на графі

1.2.1. Структури даних

1.2.2. Опис процедури BuildWays

1.2.3. Контрольний приклад

Розділ 2. Опис Машини Тюрінга

1.1. Основні поняття

1.2. Постановка завдання

1.3. Ідея вирішення

1.4. Словесний опис алгоритму

1.5. Використовувані символи на стрічці

1.6. Структури даних

1.7. Функціональна схема МТ

1.8. Приклад роботи МТ

Розділ 3. Програма

3.1. Опис програми командами машини Тюрінга

3.2. Опис програми на мові програмування

Висновки

Список використаних джерел

Розвиток теорії алгоритмів починається з доказу К. Геделем теорем про неповноту формальних систем, що включають арифметику, перша з яких була доведена в 1931 р. Виникле у зв'язку з цими теоремами припущення про неможливість алгоритмічного дозволу багатьох математичних проблем (зокрема, проблеми виводимості в численні предикатів) викликало необхідність стандартизації поняття алгоритму. Перші стандартизовані варіанти цього поняття були розроблені в 30-х роках XX століття в роботах А. Тюрінга, А. Чьорча та Е. Поста.

Алгоритм - це однозначна послідовність елементарних дій, що забезпечують рішення будь-якої задачі з деякого класу, тобто такий набір інструкцій, який можна реалізувати чисто механічно, незалежно від розумових.

Постановка задачі. Побудувати машину Тюрінга для опису алгоритмів арифметичних дій(віднімання, ділення) в десятковій системі числення.

У розділі 1 наведені основні теоретичні відомості, щодо алгоритму сортування методом простого вибору і алгоритму знаходження найдовшого шляху.

Розділ 2 описує машину Тюрінга. Йдуть теоритичні відомості про машину з прикладами.

Розділ 3 містить в собі опис програми командами машини Тюрінга і опис програми на мові програмування, яка була задана в моїй постановці задачі.

Після виконання даної курсової роботи я зробив деякі висновки:

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

Хвилевий алгоритм знаходження найдовшого шляху – це є той самий алгоритм знаходження найменшого шляху, тільки попередньо усім вершинам надаються ваги із значенням 0. Автоматично буде шукатись найдовший шлях. Також можна зауважити, що коли були знайдені дуги, то не всі вони були використанні у побудові найдовшого шляху.

Алгоритм машини Тюрінга був побудований таким чином, що кожен крок контролює одну послідовність непустих значень, і коли були пройдені три такі кроки, то на місці пустоти записується «*», коли ж послідовність закінчується. То машина зупиняється.