MU_KR_TA / PRIL

Приложение А

Образец титульного листа

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

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

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

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

з дисципліни

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

СПОТА.98213 - 01 81 01

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

...(мiсце для пiдпису) ... (прізвище та iнiцiали)

Керiвник ... (посада)

...(мiсце для пiдпису) ... (прізвище та iнiцiали)

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

Дата

...

... (пiдписи членiв комісiї)

Одеса – 2000

Приложение Б

Образец заполнения

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

Одеський ДЕРЖАВНИЙ полiтехнiчний унiверситет

Факультет автоматики та обчислювальноi технiки

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

З а в д а н н я

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

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

студенту Ковальову С.Д. групи АС - 982

1. Тема проекту "Розробка ефективного алгоритму та машини Тьюрiнга" ___________________________________________________________

2. ВихIднi данi до проекту Алгоритм - С2: шейкер-сортирування, 12 чисел; машина Тьюрiнга - МТ7: складання двох помiчених чисел a и b; сума знаходиться справа вiд послiдовностi чисел. _________________________________________________________

3. Змiст розрахунково-пояснювальноi записки (перелiчити тi питання, якi треба розробити): 1. Алгоритм шейкер-сортирування. 2. Функцiональнi схеми МТ, якi виконують операцiю складання; аналiз аварiних ситуацiй 4. Перелiк графічного матерiалу (вказати обов’язковi рисунки):

Л1.Основна схема алгоритму та схеми алгоритмiв його процедур

Л2. Схема алгоритму та функцiональна схема машини Тьюрiнга, приклад розв’язання задачі

5. Основна лiтература до проекту: 1) МУ к курс. работе по курсу «Теория алгоритмов» /: ОГПУ, 1999 2) МУ к практ. занятиям по курсу «Теория алгоритмов» /: ОГПУ, 1996

6. Додатковi матерiали до проекту ЕСПД

___________________________________________________________

Дата видачы завдання __________

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

Керiвник ______________(пiдпис)

Завдання прийняв до виконання_____(пiдпис)

Приложение В

Схема алгоритма и её начертание

Схема алгоритма представляет собой совокупность вершин и связей между ними. Вершины СА (рис. В.1) имеют определенное назначение [1]. Выделяют начальную (имеет только выход) и конечную (имеет только вход) вершины, операторные вершины и вершины, отображающие ввод либо вывод данных, циклы и вычислительные процессы (имеют один вход и один выход), а также условные вершины (имеют один вход и два выхода, соответствующие логическому значению результата проверки условия). У всех перечисленных вершин возможно схождение нескольких линий связи у одного входа.

СА обязательно содержит начальную и конечную вершины, вершины ввода и вывода и операторные вершины; обычно в СА имеются также условные вершины и вершины, предназначенные для реализации цикла; в СА может входить так называемый предопределенный процесс, представляющий собой цельный программный модуль, оформленный, например, в виде подпрограммы (стандартной либо уникальной).

Как правило,связи между вершинами проводятся сверху вниз и слева направо; в условных вершинах выходы могут быть горизонтальными, либо один - горизонтальным, другой - вертикальным. Для увязки разных фрагментов одной СА, удаленных друг от друга (например, на разных листах документа), используются соединители с меткой того процесса, на который должен быть осуществлен переход из данного фрагмента СА, либо с указателем на номер вершины, следующей за данной.

Если связи между вершинами направлены сверху вниз и слева направо, то они не обозначаются стрелкой; в противном случае линии связи заканчиваются стрелкой. Начало и конец фрагмента мы будем обозначать таким образом: и .

На рис. 2 показаны характерные размеры вершин СА. Размер a выбирается произвольно из ряда 10, 15, 20 мм и т. д. с шагом 5 мм; регламентируется только отношение b/a, которое равно 1.5 (при ручном выполнении допускается значение 2).

Рис. 2. Совмещённое изображение вершин схем алгоритмов

Приложение Г

Сравнение методов сортировки массивов

Пусть 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 если же n < 20, то целесообразнее использовать простые алгоритмы.

40