Теория Алгоритмов

Мiнiстерство освiти і науки, молоді та спорту України

Полтавський національний технічний  університет

імені Юрія Кондратюка

 

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

 

Кафедра комп’ютерних та інформаційних  технологій та систем

 

 

 

 

 

Курсова робота

 

з дисципліни «Теорія алгоритмів»

 

 

 

 

 

 

 

Виконав:  студент групи 201-ТН

Травкін П.А.

Керівник роботи:   Гвоздик Д.М.

          

 

 

 

 

 

 

 

 

 

 

 

 

 

Полтава 2011

 

Зміст

 

 

1. Умова задачі…………………………………………………………………………………..…2
2. Вступ…………………...……………………………………………………………………………3
3. Опис алгоритму………………………………………….………………………………….…4
4. Приклад………………….……………………………………………………………………..…7
5. Лістинг програми..………………………………………………………………………......8
6. Результат роботи програми…………………………………………….……………16
7. Висновок.……………………………………………………………………………………….17
8. Література………………………………………………………………..……………………18

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Умова задачі

Скласти Машину Тьюрінга для перетворення числа в десятковій системі числення в систему з основою 16

(наприклад Вхідні дані: 255 Вихідні дані: FF).

Вимоги до програми:

Можливість перегляду  коду МТ.

Покрокова візуалізація роботи програми.

Інтерфейс під Windows! Не консольний.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Вступ

 

Теорія алгоритмів - дисципліна що вивчає як саме поняття алгоритму, так і поняття алгоритмічної розв'язності задач.

Перші, та найчисленніші  застосування теорія алгоритмів мала в математичній логіці, адже вона виникла саме як розділ математичної логіки. Теорія алгоритмів є фундаментом програмування та інформатики.

Поштовхом до виникнення теорії алгоритмів, як окремого розділу математики, стала невдача в знаходженні алгоритмів розв'язку деяких масових проблем. Найвідомішими з них були проблема істинності для арифметичних формул, проблема істинності для формул числення предикатів першого порядку та десята проблема Гільберта про розв'язність діофантових рівнянь.

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

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

Пошук формальних моделей  алгоритму проводився в двох напрямах:

Опис точного математичного  поняття алгоритмічної машини та обчислюваності на ній. Першою формальною моделлю алгоритмічної машини, була машина Тьюрінга, яка моделювала елементарні дії при реалізації алгоритму людиною (А. Тьюрінг, Е. Пост 1936). Зараз відомо багато різновидностей машин Тьюрінга. З пізніших формальних моделей алгоритмів відзначимо також нормальні алгоритми (А. Марков 1952) та регістрові машини (Д. Шепердсон, Г. Стерджіс 1963). Модифікація регістрових машин - машини з натуральночисельними регістрами.

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

Першими формальними моделями алгоритмічно обчислюваних функцій  були лямбда-означувані функції (А.Чорч 1932) та загальнорекурсивні функції (К. Гьодель 1934). Вказані класи визначались як функції, графіки яких породжуються численнями λ-конверсій і численнями Ербана-Гьоделя. У 1936 р. С. Кліні поширив поняття загальнорекурсивної функції на випадок часткових функцій, увівши поняття частково рекурсивної функції, а також описав клас частково рекурсивних функцій у чисто функціональних термінах. У 1943 р. Е. Пост запропонував модель обчислюваних функцій на основі введених ним числень спеціального вигляду (канонічних систем).

У 1936 р. А. Чорч і С. Кліні довели, що класи загальнорекурсивних та λ-означуваних функцій збігаються. На основі цього факту та аналізу ідей, які привели до вказаних понять, А. Чорч висунув знамениту тезу, про збіг класу АОФ із класом загальнорекурсивних функцій. С. Кліні узагальнив цю тезу для випадку часткових функцій. Доведений А. Тьюрінгом у 1937 р. збіг класів ЧРФ і функцій обчислюваних на машині Тьюрінга, став ще одним підтвердженням тези Чорча. Пізніше такі збіги були встановлені для всіх відомих формальних моделей АОФ. Тому є всі підстави вважати, що кожна з названих вище формальних моделей адекватно уточнює інтуїтивне поняття АОФ.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1. Теоретична  частина

1.1 Опис алгоритму

Десяткова система числення  – це позиційна система числення із основою 10. Кожне число в якій записується за допомогою 10-ти символів, цифр - 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Запис числа формується за загальним принципом: на n-й позиції (справа наліво від 0) стоїть цифра, що відповідає кількості n-х степенів десятки у цьому числі.

 Шістнадцяткова система числення (шістнадцяткові числа) –  позиційна система числення за  основою 16. 

Звичайно в якості  шістнадцяткових чисел використовуються десяткові цифри від 0 до 9 і латинські букви від A до F для позначення цифр від 1010 до 1510, тобто (0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F).

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

Розглянемо алгоритм переводу чисел з десяткової системи в шістнадцяткову:

На початковому етапі  ми маємо десяткове число. На стрічці  машини  потрібно це число подати у вигляді «палок». «Палки» будемо записувати в комірки після символу «#». Так як на стрічці ми маємо лише число, запишемо алгоритм для установлення символу «#» після усих символів. Для цього ми маємо перескочити всі символи і дійшовши до пустого символа (лямди «λ») замінити його на «#».

q₀0→q₀0R (зустріли «0» - перескочили і рухаємося вправо)

q₀1→q₀1R

q₀2→q₀2R

q₀3→q₀3R

q₀4→q₀4R

q₀5→q₀5R

q₀6→q₀6R

q₀7→q₀7R

q₀8→q₀8R

q₀9→q₀9R

q₀ λ →q₁#L (дійшли до символу «λ», замінили її на символ «#», змінили стан, повернулися вліво)

Тепер, щоб здійснити заміну числа на «палки», потрібно віднімати  від даного числа одиницю і  відповідно ставити «палку» після  символу «#». Після того як ми розвернулися вліво, ми натрапляємо на якесь число. Віднімемо від нього 1.

q₁8→q₂7R  (при відніманні змінюємо стан і рухаємось вправо, щоб поставити потім «І» після «#»)

q₁7→q₂6R

q₁6→q₂5R

q₁5→q₂4R

q₁4→q₂3R

q₁3→q₂2R

q₁2→q₂1R

q₁1→q₂0R

Якщо зустріли «0», потрібно змінити це число на 9, і від  попереднього відняти 1.

q₁0→q₁9L (стан не змінюємо для того щоб потім число перед «0» зменшити на одиницю (зациклюємо), за вище описаним алгоритмом, вліво рухаємося щоб знайти число перед «0»).

Тепер нам потрібно перескочити всі «9» для того щоб знайти символ «#»:

q₂9→q₂9R

Тепер, коли ми зменшили число  на «1» і вибрали рух вправо, ми потрапляємо на символ «#»:

q₂#→q₃#R  (при перескакуванні через «#» міняємо стан і рухаємося вправо)

Тепер ми зустрічаємо пустий символ «λ», який маємо замінити на «I»:

q₃ λ →q₄ІL

q₃І→ q₃ІR (якщо ми після символу «#» знаходимо «палку», нам потрібно її перескочити і знайти пустий символ)

Поставивши «палку», ми розвертаємося щоб знову відняти від числа 1 і поставити наступну «палку». Розвернувшись ми зустрічаємо «#», перескакуємо, змінивши стан на 1, таким чином зациклюємо всі попередні дії:

q₄І→ q₄ІL

q₄#→q₁#L 

При відніманні числа ми дійдемо до ситуації, коли перед  діезом ми зустрінемо 0, замінемо його на 9, а символ перед нулем не знайдемо. Тоді ми, зустрічаючи пустий символ «λ», розвертаємось в право і замінюємо всі змінені «9» на пусті символи. Таким чином, перед символом «#» ми будемо отримувати результат переведення числа.

q₁ λ →q₅ λR

q₅9→q₅ λR

Замінивши «9» і перейшовши вправо, ми потрапляємо на символ «#», перескакуємо через нього, змінивши стан:

q₅#→q₆#R

Тепер потрібно пройти всі  «палки», дійшовши до пустого символу «λ» розвернутися і замінити «палку» на пустий символ «λ» (видалити її):

q₆І→ q₆ІR

q₆ λ →q₇ λL

q₇І→ q₈ λL (змінюємо стан, щоб не видалити всі «палки»)

Замінивши одну «палку», перескакуємо решту «палок», доходимо до «#» перескакуємо його, не змінюючи стану.

q₈І→ q₈ ІL

q₈#→q₈#L

Замінимо пустий символ «λ» перед символом «#» на 1:

 q₈ λ → q₇1R (змінюємо стан, розвертаємось вправо)

Знову потрапляємо на символ «#», перескакуємо, змінивши стан на 7, таким чином зацикливши попередні дії заміни палок на числа.

q₉#→q₇#R

Тепер після символу «#» з кожним кроком буде видалятися «палка», а число до символу «#», збільшуватимемо на 1:

q₈0→q₉1R

q₈1→q₉2R

q₈2→q₉3R

q₈3→q₉4R

q₈4→q₉5R

q₈5→q₉6R

q₈6→q₉7R

q₈7→q₉8R

q₈8→q₉9R

q₈9→q₉AR

q₈A→q₉BR

q₈B→q₉CR

q₈C→q₉DR

q₈D→q₉ER

q₈E→q₉FR

 

F замінимо на нуль, а число перед F збільшимо на 1 (якщо перед ним стоїть пустий символ «λ» – замінимо його на одиницю):

q₈F→q₈OL

q₈ λ →q₉1R

q₉0→q₉0R  (перескочимо число перед знаком «#»)

q₉1→q₉1R

q₉2→q₉2R

q₉3→q₉3R

q₉4→q₉4R

q₉5→q₉5R

q₉6→q₉6R

q₉7→q₉7R

q₉8→q₉8R

q₉9→q₉9R

Завершимо програму коли після  команди q₆ λ →q₇ λL, перейшовши вліво зустрінемо пустий символ «λ» і потрапимо на решітку «#» :

q₇#→q*

Отже алгоритм матиме вигляд:

q₀0→q₀0R

q₀1→q₀1R

q₀2→q₀2R

q₀3→q₀3R

q₀4→q₀4R

q₀5→q₀5R

q₀6→q₀6R

q₀7→q₀7R

q₀8→q₀8R

q₀9→q₀9R

q₀ λ →q₁#L

q₁8→q₂7R 

q₁7→q₂6R

q₁6→q₂5R

q₁5→q₂4R

q₁4→q₂3R

q₁3→q₂2R

q₁2→q₂1R

q₁1→q₂0R

q₁0→q₁9L

q₂9→q₂9R

q₂#→q₃#R 

q₃ λ →q₄ІL

q₃І→ q₃ІR

q₄І→ q₄ІL

q₄#→q₁#L 

q₁ λ →q₅ λR

q₅9→q₅ λR

q₅#→q₆#R

q₆І→ q₆ІR

q₆ λ →q₇ λL

q₇І→ q₈ λL

q₈І→ q₈ ІL

q₈#→q₈#L

 q₈ λ → q₇1R

q₉#→q₇#R

q₈0→q₉1R

q₈1→q₉2R

q₈2→q₉3R

q₈3→q₉4R

q₈4→q₉5R

q₈5→q₉6R

q₈6→q₉7R

q₈7→q₉8R

q₈8→q₉9R

q₈9→q₉AR

q₈A→q₉BR

q₈B→q₉CR

q₈C→q₉DR

q₈D→q₉ER

q₈E→q₉FR

q₈F→q₈OL

q₈ λ →q₉1R

q₉0→q₉0R 

q₉1→q₉1R

q₉2→q₉2R

q₉3→q₉3R

q₉4→q₉4R

q₉5→q₉5R

q₉6→q₉6R

q₉7→q₉7R

q₉8→q₉8R

q₉9→q₉9R

q₆ λ →q₇ λL

q₇#→q*

 

 

 

 

Приклад

Переведемо число 10 з десяткової системи в шістнадцяткову:

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

.

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Практична реалізація

Лістинг програми

Наведемо код форми:

Form1.h

#pragma once

#include "TuringMachine.h"

namespace MachineTuring {

using namespace System;

using namespace System::ComponentModel;

using namespace System::Collections;

using namespace System::Windows::Forms;

using namespace System::Data;

using namespace System::Drawing;

/// <summary>

/// Summary for Form1

///

/// WARNING: If you change the name of this class, you will need to change the

///          'Resource File Name' property for the managed resource compiler tool

///          associated with all .resx files this class depends on.  Otherwise,