Методические указания

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

“Теория алгоритмов и вычислительных процессов”

для студентов специальности 7.080403

“Построение эффективных алгоритмов и машин Тьюринга”

Составитель: Олег Николаевич Паулин

______________________________________________________

Одесский государственный политехнический университет

270044, Одесса, проспект Шевченко, 1

Министерство образования и науки Украины

ОДЕССКИЙ ГОСУДАРСТВЕННЫЙ ПОЛИТЕХНИЧЕСКИЙ

УНИВЕРСИТЕТ

О.Н. Паулин

МЕТОДИЧЕСКИЕ УКАЗАНИЯ

К КУРСОВОЙ РАБОТЕ ПО ДИСЦИПЛИНЕ

"ТЕОРИЯ АЛГОРИТМОВ И ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ"

"Построение эффективных алгоритмов и машин Тьюринга"

Одесса ОГПУ 2004

Методические указания к курсовой работе по дисциплине "Теория алгоритмов и вычислительных процессов". "Построение эффективных алгоритмов и машин Тьюринга". Для студентов специальности 7.080403. / Сост. О.Н. Паулин - Одесса: ОГПУ, 2004. - 36 с.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ .................................................................................. 3

1. СОДЕРЖАНИЕ И ПОРЯДОК ВЫПОЛНЕНИЯ КУРСОВОЙ РАБОТЫ .......................................................................................... 4

1.1. Общие положения ............................................................... 4

1.2. Задания на разработку ......................................................... 6

1.3. Рекомендации по выполнению курсовой работы ............. 8

2. ПРИМЕРЫ ВЫПОЛНЕНИЯ КУРСОВОЙ РАБОТЫ ......... 10

2.1. Разработка эффективных алгоритмов ................................ 10

2.2. Построение машин Тьюринга ............................................. 14

Список литературы .......................................................... 29

Приложение А. Образец титульного листа к пояснительной записке ............................................................................................ 30

Приложение Б. Образец бланка задания на разработку ...... 31

Приложение В. Оформление схем алгоритмов ..................... 32

Приложение Г. Сравнение алгоритмов сортировки ............. 34

Приложение г Сравнение методов сортировки массивов

Пусть n обозначает число сортируемых элементов, а С и М – соответственно количество необходимых сравнений ключей и пересылок элементов. Для всех трёх простых методов сортировки Н. Виртом [6] получены замкнутые аналитические формулы (табл. 1). Заголовки столбцов “Максимальные”, “Минимальные” и “Средние” определяют соответственно минимальные, максимальные и ожидаемые средние значения для всех n! перестановок n элементов.

Таблица 1

Метод сортировки	Значения
	Минимальные	Максимальные	Средние
Простые включения	C = n-1 M = 2(n-1)	(n^2-n)/2-1 (n^2+3n-4)/2	(n^2+n-2)/4 (n^2-9n-10)/4
Простой выбор	C = (n^2-n)/2 M = 3(n-1)	(n^2-n)/2 n^2/4+3(n-1)	(n^2-n)/2| n(ln(n)+0.57)
Простой обмен (метод пузырька)	C = (n^2-n)/2 М = 0	(n^2-n)/2 (n^2-n)1.5	(n^2-n)/2 (n^2- n)0.75

Для усовершенствованных методов нет достаточно простых и точных формул. Можно только сказать, что стоимость вычислений равна c(i)n^1.2 в случае сортировки Шелла и с(i)nln(n) - в случаях пирамидальной и быстрой сортировок

Примечательны следующие моменты.

1. Преимущество сортировки бинарными включениями по сравнению с сортировкой простыми включениями ничтожно мало, а в случае уже имеющегося порядка вообще отсутствует.

2. Сортировка методом «пузырька» определенно является наихудшей среди всех сравниваемых методов. Её улучшенная версия - шейкер-сортировка всё-таки хуже, чем сортировка простыми включениями и простым выбором (кроме вырожденного случая сортировки уже рассортированного массива).

3. Быстрая сортировка превосходит пирамидальную сортировку в отношении 2 к 3. Она сортирует массив с элементами, расположенными в обратном порядке, практически так же, как уже рассортированный.

В заключение можно сказать, что сортировка простым выбором является лучшим из простых методов, а быстрая сортировка - лучшим алгоритмом сортировки из всех рассмотренных в [6]. Отметим также, что улучшенные версии простых алгоритмов эффективны при больших значениях n (n  20); если же n < 20, то целесообразнее использовать простые алгоритмы.

34

В В Е Д Е Н И Е

Теория алгоритмов и практика их построения и анализа занимают важное место в образовании специалистов по программному обеспечению автоматизированных систем (специальность 7.080403). В освоении этой теории и выработке алгоритмического мышления большая роль отводится курсовому проектированию. Данные методические указания предназначены для оказания помощи студентам при решении ключевых вопросов теории и практики проектирования алгоритмов: разработке эффективных алгоритмов и построению машин Тьюринга как модели вычислительного процесса.

Задание выбирается из списка алгоритмов покрытия, на графах или сортировки. и списка операций, выполняемых машиной Тьюринга. Задания варьируются от простейших до довольно трудных (обозначены "*"). Для облегчения процесса выполнения курсовой работы приводятся рекомендации и примеры построения алгоритмов с подробными решениями; комментарии к примерам выделены курсивом.

Пример 2.1 предложен доц. Рувинской В.М., а примеры 2.2 – 2.4 – ст. преп. С.Л. Зиноватной.

3