Машина Тюрінга

 

Мiнiстерство освiти України

Одеський державний полiтехнiчний унiверситет

Кафедра системного програмного забезпечення

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

з дисципліни

"Теорiя алгоритмiв та обчислювальних процесiв"

СПЗТА.09105- 01 81 01

Виконав студент групи АС-091

Білоус І. В.

Викладач

Нестеров Ю.М.

Загальна оцiнка ______

Дата ______

Одеса - 2010

МИНІСТЕРСТВО ОСВІТИ ТА НАУКИ УКРАЇНИ

ОДЕСЬКИЙ НАЦІОНАЛЬНИЙ ПОЛІТЕХНІЧНИЙ УНІВЕРСИТЕТ

Інститут компютерних систем

Кафедра системного забезпечення

ЗАВДАННЯ

На курсовий проект з дисципліни

"Алгоритми і структури даних"

Студенту: Білоусу І.В. группы: АС - 091

. Тема проекту "Разработка эфективного алгоритму "

. Выходные данные к проекту Алгоритм - А3 алгоритм сортування методом простого вибору, С2- нахождения найдовшого шляху в графі, МТ 9 - синтез машини Тюрінга що розмічає послідовність чисел з кроком 3,тобто необхідно поставити * замісь 0 після кожного третього числа .

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

. Список графіческого материала :

. Блок-схемы алгоритма сортування, графа та машини Тюрінга, .

. Основная литература до проекту:

) МВ до курс. работи з курсу «Теорія алгоритмів» /: ОНПУ, 1999

) МВ до практ. заняттям з курсу «Теорія алгоритмів» /: ОНПУ, 1996

Дата видачі завдання:23.01.2010

Дата захисту проекта: __________

Керівник : Нестеров Ю.М.

Завдання прийняв до виконання: __________

АНОТАЦІЯ

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

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

Зміст

Вступ

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

.1 Постановка задачі

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

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

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

.5 Матиматичний опис

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

. Алгоритм знаходження найдовшо шляху

.1 Постановка задачі

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

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

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

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

3. Машина Тюрінга

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

.2 Постановка задачі

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

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

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

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

.7 Функціональна схема

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

Висновок

Перелік літератури

. Додаток 1

Вступ

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

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

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

Алгоритм простим вибором

алгоритм граф тюрінг

Постановка задачі

Алгоритм простим вибором - це дуже природний спосіб сортування. Зазвичай він першим спадає на думку людині, що зіткнулася з необхідністю впорядкування таблиці. Він є досить простим в освоєнні і тому зручний. Сортування простим вибором не можливе, доки не буде відомо всі елементи масиву, також його недоліком є досить значна затрата часу на впорядкування масиву порівняно з іншими видами сортувань. Ідея його така. Знайдемо в таблиці елемент з найменшим значенням і поміняємо його місцями з першим елементом. Після цього ті ж дії виконаємо з N, що залишилися (без першого), - 1 елементами таблиці, потім з N - 2 елементами і т. д., поки не залишиться один елемент - останній. Він буде найбільшим.

Цей метод для послідовності прямокутників різної висоти. Два перші елементи вже впорядковано. Потім відшукується мінімальний серед інших. Якщо елементи в послідовності можуть бути рівними, то відшукується перший (I) серед мінімальних (таким чином досягається стійкість сортування). Він міняється місцями з третім.

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

Наступником методу простого вибору є - сортування модифікованим методом простого вибору.

Цей метод ґрунтується на алгоритмі пошуку мінімального елементу. У масиві А(1.n) відшукується мінімальний елемент, який ставиться на перше місце . Для того, щоб не втратити елемент, що стоїть на першому місці, цей елемент встановлюється на місце мінімального . Потім в такій же послідовності, виключаючи перший елемент, відшукується мінімальний елемент і ставиться на друге місце і так далі n - 1 раз доки не встане на своє місце передостанній n - 1 елемент масиву А, перемістивши максимальний елемент в самий кінець.

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

Відмітимо, що для перестановки елементів місцями необхідно знати їх порядкові номери, алгоритм перестановки елементів масиву був розглянутий раніше. Алгоритми введення початкового масиву і виведення цього ж масиву після сортування зображені на малюнках 16 і 24 відповідно. Алгоритм пошуку в масиві мінімального елементу і його номера буде аналогічний розглянутому алгоритму пошуку максимального елементу. Проте, в цьому алгоритмі будуть внесені зміни. Для того, щоб визначити які зміни слід внести розглянемо виконання сортування цим методом з акцентом на пошук мінімального елементу на конкретному прикладі. Нехай початковий масив містить 5 елементів (2,8,1,3,7). Кількість переглядів згідно з модифікованим методом простого вибору дорівнюватиме 4. Покажемо в таблиці 1, як змінюватиметься початковий масив на кожному перегляді.

Таблиця 1.

Номер перегляданню масиву іЗавдань масивМінімальний елементПереставлюваний елементМасив після перестановкиНомерЗначенняНомерЗначення1(2,8,1,3,7)3112(1,8,2,3,7)21,(8,2,3,7)32281,(2,8,3,7)31,2,(8,3,7)43381,2,(3,8,7)41,2,3,(8,7)57481,2,3,7,8

З даних, приведених в таблиці 1, випливає, що пошук мінімального значення в масиві на кожному перегляді здійснюється в скороченому масиві, який спочатку починається з першого елементу, а на останньому перегляді масив, в якому шукається мінімальний елемент починається вже з четвертого (чи n - 1) елементу. При цьому можна помітити, що номер першого елементу масиву для кожного пошуку і перестановки співпадає з номером перегляду i.

Введемо наступні позначення:

К- номер мінімального елементу- номер елементу масиву

М і А(К) - одне і теж значення мінімального елементу масиву- номер що переставляється з мінімальним елементу

А(i) - значення елементу, що переставляється.

Тоді циклічний алгоритм сортування модифікованим методом простого вибору виглядатиме таким чином (сх.2).

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

.У вхідній підпослідовності елементів вибирається елемент з найменшим ключем.

. Цей елемент міняється місцями з першим елементом a1.

Ці операції потім повторюються з n, що залишилися, - 1 елементами, потім з n - 2 елементами, поки не залишиться тільки один елемент - найбільший.

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

[]n - масив даних з n елементів- кількість елементів,j - індекси елементів масиву- змінна, що зберігає значення елемента який обмінюють місцями[i] - i-тий елемент масиву[j] - j-тий елемент масиву- обмін елементів місцями

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

.Масив даних A[]n подається на вхід, після чого входить в цикл по змінні

і(n-1),0 .

.Функцією цього циклу є прохід по всіх значеннях масиву, окрім останнього(n-1).

.Після проходження першого значення циклу по і, цикл по j(n),i+1 проходить всі інші значення які стоять після першого значення, порівнюючи ці значення із першим.

. Якщо знаходиться найближчий елемент A[i]>A[j], який більший за перший, то тоді повертаємось до циклу по j, якщо ж ні, то елементи обмінюємо місцями. 5. Данy послідовність дій потібно проробити для всих елементів.

.Після проходження циклів, вони завершають свою роботу.

.Новоутворений масив данихA[] виводиться на екран .

Опис процедури Obmin

. Змінній k значення першого елемента k=A[i]

. На місце першого записується знайдений менший елементA[i]=A[j].

. На місце знайденого меншого елемента записується перший елемент A[j]=k. Таким чином елементи обмінюються .

Покроковий опис схеми алгоритмів

мал.1 Опис основної схеми

Блок №1

Ввод масиву А, який містить n елементів.

Блок №2

Цикл по і, починається із 0, триває до n-1.

Блок №3

Цикл по j, починається із i+1, триває до n.

Блок №4

Умова, яка порівнює елементи.

Блок №5

Процедура обміну місцями елементів.

Блок №6

Вихід з циклу по j.

Блок №7

Вихід з циклу по і.

Блок №8

Вивід на екран новоутвореного масиву А.

Мал1.2 Опис процедури Obmin

Блок №1

Надання змінній k значення і -ого елементу.

Блок №2

Надання і - тому елементу значення j-ого елемента.

Блок №3

Надання j - ому елементу значення k.

Математичний опис

1. i:=1
2. k привласнюваний індекс найменшого елементу підпослідовності ai,., an.

3. Якщо i?k, то ai і ak обмінюємо місцями.

. I:=i+1. Якщо i<?n, то переходимо на п. 2, інакше сортування закінчене.

Для складання алгоритму рішення цієї задачі скористаємося, як завжди, методом покрокової деталізації. Звернемо увагу на те, що для отримання результату нам потрібне N - 1 раз знаходити мінімальне значення в таблиці, довжина якої зменшується і визначається тим, який раз ми приступили до пошуку мінімуму. Так, в 1-й раз ми шукаємо мінімум серед елементів A1, A2,.., AN, в 2-ій - серед A2,.., AN, в i -й - серед Ai,.., AN. І ще один важливий момент. Оскільки після знаходження мінімального елементу його треба буде поміняти місцями з іншим елементом таблиці, то треба запам'ятати номер мінімального. Отже, перший крок деталізації можна представити таким оператором циклу : := 1

I<=N - 1

накінець знайти мінімальний елемент і його номер в таблиці Ai,.., АN (1) поміняти місцями Аi і мінімальний елемент (2)

:= I+1

кінець

Ще раз приведемо розроблений раніше алгоритм пошуку мінімуму.

1. K:= I; X:= A[I]; J:= I+1

якщо J<=N

інакше якщо A[J]<X

тоді X:= A[J]; K:= J

кінець

кінець

Після виконання цих дій значенням змінної Х буде значення мінімального серед елементів Ai,.., AN, а значенням До - номер цього елементу. Отже, пункт 2 можна записати конкретніше:

поміняти місцями елементи A1 і AK (2)

Відомо, що в загальному випадку для взаємної перестановки в пам'яті двох змінних потрібна третя, допоміжна, :

. C:= A[I]; A[I] := A[K]; A[K] := C.

Помітимо, проте, що в нашій конкретній ситуації ця третя змінна не потрібна, оскільки її роль грає змінна Х з пункту 1:

. A[K] := A[I]; A[I] := X.

Ми заощадили одне привласнення, але це немало, оскільки дії виконуються в циклі багаторазово.

Тепер можна записати повністю алгоритм сортування простим вибором.

алг ВИБІР(цілий N, дроб таб A[1: N])

арг A, N

рез A

нач дроб X, цілий I, J, K := 1

якщо I<=N - 1

інакше K:= I; X:= A[I]; J:= I+1

якщо J<=N

інакше якщо A[J]<X

тоді X:= a[J];K:= J

кінець:= J+1 кінець[K] := A[I]; A[I] := X; := I+1

кінець

кінець.

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

Показане вище сортування працює за таким принципом:

1. Із заданого рядка масиву елементів знаходиться найменший. Цей елемент ставиться на перше місце, і рядок відповідно записується під індксом і=1

. Потім із рядка під індексом i=1 вибирається найменший елемент окрім прешого, і міняється із другим, тобто N-1.

. Із рядка і=2 вибираємо найменший елемент, і міняємо його із третім N-2.

. Із рядка і=3 вибираємо найменший елемент, і міняємо його із N-3. Оскільки в даному випадку елемент що стоїть на четвертій позиції є найменший, то він там і залишається.

. Із рядка і=4 вибираємо найменший елемент, і міняємо його із N-4.

. Із рядка і=5 вибираємо найменший елемент, і міняємо його із N-5.

. Із рядка і=6 вибираємо найменший елемент, і міняємо його із N-6.

. Із рядка і=7 вибираємо найменший елемент, і міняємо його із N-7.

.Оскільки всі елементи відсортовані, то рядок і=7 записуємо в результат.

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

Постановка задачі

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

Очевидно, що до кожної вершини можуть йти від вершини X н декілька шляхів суми довжин дуг по різних шляхах різні . При пошуку найдовшого шляху слід вибирати максимальну суму. Хвилі поширення ваги по різних шляхах доходять до кожної вершини послідовно, при черговій хвилі необхідно залишити або стару вагу вершини, або замінити його на новий (більший). Тому при розрахунку ваги вершини X i за рахунок хвилі, що підійшла до неї по дузі (X j, X i), виробляється обчислення ваги V i по формулі

i =max(V i, V j + l ji).

Ваги вершин в процесі поширення хвилі можуть мінятися неодноразово. При кожній зміні ваги V i вершини це збільшення ваги необхідно передати вершинам результату X i, тобто потрібні спеціальні засоби, що відбивають факти отримання вершиною нової ваги і передачу його іншим вершинам. Як такий засіб використовується масив номерів вершин, що отримали нову вагу(при кожній зміні ваги номер вершини включається в цей масив, якщо його там не було, при передачі ваги виключається).

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

1.Усі вершини графа отримують ваги V i =0, номер вершини X н

заноситься в масив М номерів вершин, що змінили вагу. Інші вершини X i не потрапляють в масив М.

1. Якщо масив М порожній, виконується п. 3, інакше вибирається з

виключенням з його чергова вершина X i і перераховуються ваги вершин, що належать результату G(X i) вершини X i, :

Якщо вага V j змінюється, то номер j включається з приведенням подібних в М. Знову виконується п. 2.

1. Якщо вага

   , то робиться висновок, що шляхи з вершини X н до вершині X k не існує, інакше виконується процедура виділення дуг, рухаючись в зворотному порядку перевіряємо чи виконується умова Xi - X j = l ij, для входів вершини X i, якщо воно виконується, то вершина X j і дуга l ij виділяються.

4. Після виділення дуг будуються довгі шляхи, довжини яких рівні V k.

ЗАУВАЖЕННЯ

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

але. При кожній зміні ваги V i вершини це збільшення ваги необхідно передати вершинам результату X i, тобто потрібні спеціальні засоби, що відбивають факти отримання вершиною нової ваги і передачу його іншим вершинам. Як такий засіб використовується масив номерів вершин, що отримали нову вагу(при кожній зміні ваги номер вершини включається в цей масив, якщо його там не було, при передачі ваги виключається).

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

З самої структури алгоритму очевидно, що для його функціонування потрібні:

.Масив М - масив дуг-зв'язності в осередках з номерами i, j якого знаходитиметься вага відповідної дуги l ij.

. Xi - вершини графа.

. Vi - ваги відповідних вершин .

. G(Xi) - результат перерахованих вагів вершин Xi.

. tt - індекси верши при їхньому розрахунку.

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

Схема хвилевого алгоритму знаходження найдовшого шляху виконується

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

Опис процедури CountTop2

Функція розраховує ваги усіх вершин шляхом надання їм нульового значення. Після чого вершина Хн заноситься у масив номерів вершин М. Масив перевіряється на пустоту, якщо умова відбувається, то процедура закінчується, інакше вершина, індекс якої був занесений у масив М, перевіряється на те, чи вага вершини буде меншо, ніж вага новообчисленої. Якщо умова правдива, то вершині надається більша вага, а її індекс заноситься до масиву М.Після цього перевіряється чи залишились не обраховані вершини у правдивому результаті повертаємось на етап перевірки порівняння вагів вершини даної, та ново обрахованої, якщо ж ні, то повертаємось на етап перевірки пустоти масиву індексів.

Опис процедури MarkArrow

Рухаємось у зворотному напрямку, тобто у масив М заносимо кількість входів G-1 . Потім робимо перевірку умови X i - X j = l ij. При правдивості умови переходимо до розмітки дуги lij. Потім перевіряєм маси в на порожність. При позитивному результаті закінчуємо процедуру. При негативному - повертаємось на етап перевірки умови X i - X j = l ij.

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

У масив М заносимо індекси усіх виділених вершин. Робимо перевірку на те чи сума усіх виділених дуг рівна вазі останньої вершини. Якщо так - будуємо шлях. Перевіряємо масив на порожність. Якщо умова правдива - закінчуємо процедуру, якщо ні переходимо на етап перевірки рівності суми шляхів дуг та віги останньої вершини.

Покроковий опис схеми алгоритмів

Мал. 2 Опис основної схеми Найдовший шлях

Блок №1

Функція розрахунку вагів вершин CountTop2

Блок №2

Функція розмітки дуг MarkArrow

Блок №3

Функція зібрання знайдених шляхів BuildWays

Мал 2.1Опис процедури CountTop2

Блок №1

Усім вершинам надається значення 0. В масив М записується індекс першої вершини.

Блок №2

Перевірка на порожність масиву М.

Блок №3

Вибір із масиву індекс вершини.

Блок №4

Перевірка на те чи вага вершини менша ніж нова вага вершини V(Gi)+1.

Блок №5

Запис у масив М індексу вершини що змінила свою вагу. Надання вазі вершини нове значення.

Блок №6

Перевірка на наявність вершин.

Мал. 2.2 опис процедури MarkArrow

Блок №1

Занесення у масив М кількість входів G-1

Блок №2

Перевырка умови X i - X j = l ij.

Блок №3

Виділяємо дугу lij

Блок №4

Перевірка на пустоту масиву М

Мал. 2.2 опис процедури BuildWays

Блок №1

Занесення у масив М кількість входів входів

Блок №2

Перевырка умови на те чи сума дуг дорівнює вазі останньої вершини.

Блок №3

Будуємо шлях Way

Блок №4

Перевірка на пустоту масиву М.

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

Для детального опису дії хвилевого алгоритму пошуку довгого шляху скористаємося графом що задається таблиці зв'язності :

x1x2x3x4x5x6x7x8x13425x212x343x434x56x63x75x8

Таким чином, знаючи таблицю зв'язності можна побудувати граф для наочнішої ілюстрації прикладу :

Отже, на першому проході хвилевого алгоритму виконується пункт 1, тобто встановлюються значення вагів усіх вершин в нуль, і поміщає в масив М індекс початкової вершини, математично це можна записати так:

Крок № 1:

П. 1:

На другому проході, оскільки. М<>0, виконується пункт 2, з масиву М забирається перший елемент, цей індекс надається індексній змінній i

складається безліч результатів для вершини Х i, а потім обчислюються ваги суміжних вершин :

Крок № 2:

П. 2:

Як видно з приведених записів, в результаті цього проходу чотири вершини отримали нові ваги, і відповідно в масив М потрапили їх індекси, оскільки до цього вони в нім не містилися.(Надалі скорочено викладу приводитимуться переважно математичні записи роботи алгоритму).

Крок № 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: Q×X ?Q -функція переходів в наступний стан;

l: Q×X ?Y -функція виходів.

У свою чергу, Y=X×U, де U={R, L, S}- команда на переміщення голівки: R -зрушитися управо, L -вліво, S - стояти на місці.

Задавая МТ [5], замість двох функцій можна користуватися однією(що поєднуєх работу входу и виходу): j: Q´X ® Q´X´U, зіставляється кожній парі (qi, xj) вихідну трійку (qk, u, xl), uÎU. Функція j повнвстю описує работу МТ і називається логічною функцією машини Тюрінга. Таблиця цієї функції називається функціонально схемо, або програмою машини Тюрінга. На кожному такті работи МТ головка оглядає в деякій комірці символ xj, а сама МТ знаходиться в деякому стані qi, що описується вхідно парою (qi, xj). В залежності від вхідної пари МТ виконує команду (qk, u, xl), uÎU, т.е. записує в оглядову комірку символ xl, пересуває головку в залежності від значення u и переходить в новий стан qk. Якщо на деякому этапі работи МТ переходить в СТОП-стан, то подальші зміни в машині не відбуваються - машина зупиняється.

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

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

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

Розмітка чисел з кроком 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

. Джон Хопкрофт, Раджив Мотвані, Джеффрі Ульман РОЗДІЛ 8. Введение в теорію машин Тьюрінга // Введення в теорію автоматів, мов та обчислень = Introduction to Automata Theory, Languages, and Computation. - М.: «Вільямс», 2002

Мiнiстерство освiти України Одеський державний полiтехнiчний унiверситет Кафедра системного програмного забезпечення

Больше работ по теме: