Машина Тюрінга
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
М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) серед мінімальних (таким чином досягається стійкість сортування). Він міня