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

О.Н. Паулин

 

 

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

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

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

 

 

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

 

 

Одесса ОГПУ 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, то целесообразнее использовать простые алгоритмы.

В В Е Д Е Н И Е

 

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

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

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

 

СОДЕРЖАНИЕ И ПОРЯДОК ВЫПОЛНЕНИЯ

КУРСОВОЙ РАБОТЫ

 

Общие положения

 

Курсовая работа состоит из пояснительной записки (25-30 с. рукописного текста) и графических материалов (один-два листа чертёжной бумаги формата А1). Пояснительная записка и графические материалы должны быть выполнены в соответствии с требованиями ГСТУ и ЕСПД [1-3].

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

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

2. Построение машины Тьюринга,

а также заключение и список литературы.

Пояснительная записка начинается титульным листом (прил.А). В аннотации приводятся цель и краткое содержание курсовой работы с указанием заданных алгоритма и операции, выполняемой машиной Тьюринга, а также выводы относительно особенностей, эффективности, возможности и области применения полученных алгоритмов. Задание на разработку приводится подробно на отдельном бланке (прил. Б). Раздел "Содержание" оформляется обычным образом [1] с перечислением конкретных разделов, подразделов и пунктов с указанием их начального номера страницы.

В разделе "Введение" должно быть отражено следующее:

· актуальность темы;

· что такое алгоритм, его назначение, виды алгоритмов;

· структуры данных и их представление в памяти ЭВМ;

· эффективность алгоритмов и методы её достижения;

· машина Тьюринга как модель вычислительного процесса;

· краткое содержание курсовой работы.

Раздел "Разработка эффективных алгоритмов" в пояснительной записке должен содержать такие подразделы (для примера - алгоритма покрытия; аналогично - для алгоритмов на графах и сортировки):

1.1. Задача о покрытии

 

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

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

 

Приложение В

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

Алгоритмы выбираются из следующих списков.

Алгоритмы покрытия:

A1 - по методу "минимальный столбец - максимальная строка";

A2 - построение одного кратчайшего покрытия;

A3 - построение одного минимального покрытия;

A4 - граничный перебор по вогнутому множеству;

*А5 - построение циклического остатка;

*A6 - разложение по столбцу;

*A7 - по методу ветвей и границ.

Алгоритмы на графах:

B1 - нахождение кратчайшего пути;

B2 - алгоритм Дейкстры нахождения кратчайшего пути;

B3 - нахождение длиннейшего пути;

B4 - построение минимального остова;

B5 - построение системы независимых циклов;

B6 - нахождение компонент связности;

*B7 - кратчайшая раскраска;

*B8 - определение максимального потока в сети;

*B9 - определение минимального потока в сети.

Алгоритмы сортировки:

C1 - сортировка бинарными включениями;

C2 - шейкер-сортировка;

C3 - сортировка Шелла;

*C4 - пирамидальная сортировка;

*C5 - быстрая сортировка.

Приложение Б

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

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

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

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

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

 

З а в д а н н я

 

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

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

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

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

2. Вихідн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.Основна схема алгоритму та схеми

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

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

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

 

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

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

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

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

 

Приложение А

 

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

 

 

М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

 

Примечания:

1. АлгоритмыА6 и А7 строятся, считая, что циклический остаток уже есть.

2. Простые алгоритмы описаны в [4], более сложные - в [5,6].

Задания по построению машины Тьюринга выбираются из следующего списка.

МТ1. Сравнение двух отмеченных символом "*" чисел a и b в последовательности. В качестве результата справа от этой последовательности должен стоять знак отношения: ">", "<" либо "="; числа при этом должны быть сохранены.

МТ2. Сложение двух отмеченных символом "*" чисел a и b в последовательности. Справа от неё должна находиться сумма.

МТ3. Определение остатка от деления числа a на 3.

МТ4. Определение середины последовательности чисел. Если количество чисел чётное, то поставить один символ "*" в середине последовательности вместо пустой ячейки; если же количество чисел нечётное, то "окаймить" символом "*" центральное число.

МТ5. Пересылка отмеченного символом "*" числа на место первого слева, остальные числа сдвигаются.

МТ6. Пересылка отмеченного символом "*" числа на место за последним справа, остальные сдвигаются.

МТ7. Копирование системы чисел (x₁, x₂..., x_n). Должно получиться: (x₁, x₂,.., x_n, x₁, x₂,...,x_n).

МТ8. Обмен двух отмеченных символом "*" чисел a и b в последовательности.

МТ9. Разметка чисел в последовательности с шагом 3. Это значит, что необходимо вместо пустого символа поставить символ "*" после каждого третьего числа.

*МТ10. Разметка чисел в последовательности с шагом k, заданным на ленте на месте самого левого числа. Необходимо символ "*" поставить вместо пустого символа после каждого k -го числа.

*МТ11. Определение середины последовательности чисел и обмен рядом стоящих у середины чисел местами. Принять, что количество чисел - чётное. Отметить середину последовательности символом ²*².

*МТ12. Сравнение двух трехразрядных чисел (3 десятичных разряда в каждом). Начальная конфигурация на ленте:

11 v 11...1*11...1*11...1 v 11...1*11...1*11...1 00....

а b

здесь a и b - числа, которые необходимо сравнить; v - указатель на числа; * - разделитель между разрядами для трехразрядных чисел. В результате справа от последовательности чисел должны стоять знаки отношения: ">", "<" либо "=".

*МТ13. Вычислить выражение: 2(a + b)- c.

*МТ14. Вычислить выражение: 2 a + b -3 c.

*МТ15. Вычислить выражение: a -3 b -2 c.

Примечания:

1.Числа a, b, c,... расположены на ленте в порядке перечисления.

2. Начальное расположение головки задаётся руководителем курсовой работы (по умолчанию - стандартное).

 

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

Рекомендации к разд. 1. В подразд. 1.1 рассматриваются 2 пункта: "Постановка задачи" и "Математическое описание задачи и методов её решения". Подразд. 1.2 содержит 3 пункта: "Словесное описание алгоритма", "Структуры данных" и "Техническое описание схемы алгоритма". Содержание п. 1.2.1 ясно из названия. В п. 1.2.2 описывается выбор структур данных (т.е. представление в памяти ЭВМ исходных, промежуточных и конечных данных) и его обоснование. Отметим, что выбор подходящих структур данных осуществляется параллельно с составлением схемы алгоритма (СА). В п. 1.2.3 приводятся основная СА и СА предопределённых процессов и функций, а также их описания с указанием передаваемых параметров и их значений. СА составляют достаточно подробными для того, чтобы по ним можно было понять работу алгоритма; в то же время СА не должна дублировать программу. В подразд. 1.3 необходимо пошагово описать работу алгоритма, используя контрольный(е) пример(ы) (задаются таблицы из [4] для алгоритмов покрытия и на графах, а также количество чисел - для алгоритмов сортировки). В п. 1.4 необходимо провести анализ эффективности заданного алгоритма и продумать возможность повысить её за счёт разделения задачи на подзадачи и балансировки данных, использования рекурсии либо итераций, а также метода динамического программирования.

 

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

 

1. ГСТУ 3008-95. Документация. Отчёты в сфере науки и техники. Структура и правила оформления. - Киев: Изд-во стандартов, 1995. – 38 с.

2. Единая система программной документации / Схемы алгоритмов, программ, данных и систем. Условные обозначения и правила выполнения. ГОСТ 19.701-90. – М.: Госкомитет СССР по управлению качеством продукции и стандартизации, 1990. –25 с.

3. Методические указания к курсовому и дипломному проектированию для студентов специальности 7.080403: Организация и выполнение курсовых и дипломных работ / Сост. В.И. Давыдов, А.Б. Кунгурцев. – Одесса: ОГПУ, 1994. – 18 с.

4. Методические указания и задачи к практическим занятиям по курсу "Теория алгоритмов и вычислительных процессов" для студентов специальности 7.080403 и 7.091501: Часть 1 / О.Н. Паулин, В.М. Рувинская, Е.С. Осадчук – Одесса: ОГПУ, 1996. – 54 с.

5. Гудман С., Хидетниеми С. Введение в разработку и анализ алго-ритмов. -М.: Мир, 1981.- 368 с.

6. Вирт Н. Алгоритмы + структуры данных = программы.- М.: Мир, 1985. - 406 с.

 

 

 

...	...	...
qi	0 R qj	1 R qi
...	...	...
qj	0 R qj	x x x
...	...	...

 

Рис. 2.9. Пример ухода головки в бесконечность

 

Если происходит уход головки “в бесконечность” в сторону левого края ленты, то через некоторое время головка достигнет этого края, но, как говорилось ранее, программист не может отслеживать этот факт, он может только видеть аварийное завершение работы МТ.

...	...	...
qi	0 S qj	x x x
...	...	...
qj	1 R qt	1 R qj
...	...	...
qt	x x x	x x x
...	...	...

Рассмотренная на рис. 2.10 ситуация не приводит к аварийной работе МТ, но ее тоже нужно избегать, так как она влечёт за собой лишние действия МТ и неоправданное увеличение ФС. В данном случае состояние q_j является избыточным, и его можно убрать.

 

Рис. 2.10. Пример особого случая

 

Рассмотренные примеры не охватывают всего многообразия поведения МТ, однако достаточны для выполнения заданий по данному разделу.

 

Примечание. Для алгоритмов сортировки необходимо подсчитать количество пересылок элементов массива и их сравнений для трёх примеров массивов, состоящих из заданного числа элементов:

а) отсортированный;

б) отсортированный в обратном порядке;

в) отсортированный случайным образом.

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

Рекомендации к разд. 2. В подразд. 2.1 должны быть представлены следующие пункты: "Постановка задачи", "Идея решения задачи", "Словесное описание алгоритма решения", "Используемые символы на ленте" (в результате анализа словесного описания алгоритма определяется множество используемых символов, требуемых для реализации алгоритма заданной операции; иногда для решения задачи бывает проще использовать дополнительные символы, но желательно использовать как можно меньшее их количество). В подразд. 2.2 должны быть представлены два пункта, "Схема алгоритма" и "Функциональная схема". В первом пункте необходимо привести схему алгоритма, построенную в соответствии с его словесным описанием, и описать работу машины Тьюринга (МТ). Во втором пункте необходимо проанализировать СА с целью определения состояний и переходов МТ, реализующей этот алгоритм; построить программу работы машины (её функциональную схему - ФС), которая выполняет заданную операцию над указанными числами в некоторой последовательности (желательно решить задачу, используя как можно меньше внутренних состояний машины Тьюринга, т.е. меньше строк в ФС); нарисовать граф состояний МТ (для заданного фрагмента СА). В подразд. 2.3 необходимо рассмотреть пример (выбирается самостоятельно), показывающий работу машины для конкретной начальной конфигурации на ленте, расписав по тактам последующие конфигурации (в случае цикла допустимо ограничиться начальным и конечным тактами); пример должен охватывать все ветви алгоритма. Далее этот пример анализируется с целью выявления аварийных ситуаций. В заключение определяется длительность (в тактах) процесса выполнения заданной операции.

 

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

 

Пример 2.1.

Постановка задачи. Необходимо ввести таблицу покрытий, а также номера строк таблицы. Алгоритм должен определить, являются ли эти строки покрытием.

Таблица 2.6

Т	Q	Ситуация на ленте
	q1	... 0 1 1 1 0 0 0 0 0...
1-3	q1	... 1 110 0...
	q2	... 1 1 0...
	q3	... 0 0 0...
	q4	... 0 0 0...
	q5	... 0 0 1...
	q6	... 1 0 0...
	q7	... 1 1 1...
10, 11	q3	... 0 10 1...
12, 13	q4	... 0 10 0...
14, 15	q5	... 1 01 1...
16, 17	q6	... 1 01 0...
	q7	... 0 1 1...
	q3	... 0 1 1...
...	...	...
	!	... 0 1 1 1 0 1 1 1 0...

 

 

Описание схемы алгоритма функции. Функция POKR(D, kol, A, n) определяет, являются ли строки матрицы А, номера которых заданы в списке D, покрытием. Здесь kol - количество элементов в массиве D, n - количество столбцов матрицы A. Функция возвращает 1, если заданные строки матрицы A образуют покрытие, 0 - в противном случае.

Алгоритм работает следующим образом. При вызове в основном алгоритме функции POKR(D, kol, A, n) в неё передаются параметры D, kol, A, n; затем организуется внешний цикл (блоки 2-8) прохода по всем столбцам матрицы A и внутренний цикл (блоки 3-6) расчёта суммы S по i -му столбцу для заданных строк, проверяемых на покрытие. В качестве признака отсутствия покрытия используется значение суммы S=0, поскольку если в некотором столбце на всех позициях, соответствующих рассматриваемым строкам, будут нули, то этого достаточно, чтобы констатировать отсутствие покрытия (в этом случае можно не проверять остальные столбцы). Вычисление S производится в блоке 5 для выбранной из массива D (блок 4) строки с номером k. В блоке 7 проверяется условие S=0 и в зависимости от его значения принимается решение о том, какое значение функции возвращается в основной алгоритм (блоки 9 и 10), где они присваиваются переменной usl. Отметим, что если цикл прохода по столбцам полностью завершился, значит, ни одна сумма по столбцам не равна 0, что означает, что заданные строки являются решением задачи о покрытии.

Контрольные примеры решения задачи с помощью алгоритма.

Пусть задача о покрытии задана матрицей (табл.2.1). Требуется определить

а) являются ли строки А1, А3 решением задачи о покрытии;

б) являются ли строки А1, А3, А4 решением задачи о покрытии.

 

Пошаговое решение:

а) i=1, S=2;

i=2, S=0; выход из функции POKR, возвращается 0, выдаётся сообщение «нет».

б) i =1, S=2;

i =2, S=1;

i =3, S=2;

i= 4, S=1;

i =5, S=2;

выход из функции POKR, возвращается 1, выдаётся сообщение «да».

Степень детализации как проходимых алгоритмом ветвей, так и значений переменных, должна быть достаточной для понимания и проверки правильности алгоритма. Так, в нашем случае было опущено слежение за переменной внутреннего цикла по j и сам цикл, так как. это достаточно очевидно.

 

Построение машины Тьюринга

Таблица 2.3

Такт	Состояние	Ситуация на ленте
	q1	... 0 1 1 1 0 0...
	q1	... 0 1 1 1 0 0...
	q1	... 0 1 1 1 0 0...
	q1	... 0 1 1 1 0 0...
	q2	... 0 1 1 1 1 0...
	q2	... 0 1 1 1 1 0...
	q2	... 0 1 1 1 1 0...
	q2	... 0 1 1 1 1 0...
	q2	... 0 1 1 1 1 0...
	!	... 0 1 1 1 1 0...

Пример 2.3.

Постановка задачи. Синтезировать МТ, выполняющую копирование числа у_исх = а (крайнее правое в последовательности чисел). Результатом работы МТ должна быть конкатенация вида y_рез=a. 0. a. Сохранить исходное число. После завершения работы МТ головка должна быть установлена в начале исходного числа.

Идея решения. Поочередно копировать каждую “1” из исходного числа на ленту после числа а, последовательно формируя результирующую последовательность ”1”. Копируемую ”1” отмечать, инвертируя её значение. Промежуточные результаты удобно представить конкатенацией вида y_пром=a´.0.a´´.0.a´´´, где a´.0.a´´ - ”расщеплённое” меткой ”0” число a; a´´´ - часть копии числа a. При переходе к обработке следующей “1” из исходного числа а пометку снимать, выполняя обратное инвертирование.

По окончании работы МТ лента может выглядеть так:

!... 0 1 11011110110111111100..., или так:!... 0 1 11111100...,

В первом случае сохранены исходные данные.

Пустые ячейки ленты правее исходной последовательности чисел (n₁, n₂,..., n_m) могут быть использованы для размещения промежуточных результатов вычисления заданной функции у. Однако нужно помнить, что лента слева ограничена, поэтому возможно достижение левого конца ленты при записи информации на ленту. Программно такая ситуация не определяется, происходит аварийный останов МТ. Поэтому для записи промежуточных вычислений предпочтительнее использовать ячейки, расположенные правее заданной последовательности чисел.

 

Примеры построения машин Тьюринга

 

Рассмотрим примеры синтеза МТ для различных числовых функций.

Решение поставленной задачи должно быть описано в соответствии с рекомендациями по данному разделу.

Пример 2.2. Постановка задачи: синтезировать МТ, вычисляющую функцию y = n +1 (операция инкремента). Сохранение исходного числа n не требуется.

Идея решения в данном случае проста: необходимо переместить головку к концу заданного числа и следующий за ним символ (а это - 0, открывающий потенциально бесконечный ряд пустых ячеек) заменить на единицу.

Словесное описание алгоритма: головка автомата движется вправо вдоль последовательности единиц, пока не встретит пустую ячейку. В эту ячейку записывается “1”, и головка движется влево вдоль единиц результата (числа у), пока не встретит пустую ячейку. Обнаружив её, головка сдвигается вправо на одну ячейку, и МТ останавливается (головка обозревает крайнюю слева единицу результата у).

 

 

Здесь же проводится анализ словесного описания алгоритма с целью определения выполняемых операций и их последовательности, а также требуемых символов на ленте.

В данном примере МТ выполняет две макрооперации - прохождение группы единиц вправо и затем прохождение группы единиц влево. Множество используемых символов: Х={0,1}; дополнительные символы не требуются.

Схема алгоритма. Введем следующие обозначения.

Для команд перемещения головки:

· R(L) - сдвинуть вправо (влево) на одну ячейку;

· GR x_i (x_j) (GL x_i (x_j)) - двигаться вправо (влево), пропуская группу символов x_i Î Х, пока не встретится ячейка с символом x_î Î Х (после выполнения команды головка находится напротив ячейки, содержащей символ x_î); например, GR1(0) - двигаться вправо до пустой ячейки, пропуская группу единиц.

Для команд, оперирующих с содержимым текущей ячейки:

· z=x_i - проверка наличия символа x_î Î Х в текущей ячейке;

· z x_i - записать в текущую ячейку символ x_î Î Х;

· INV - замена “1”(“0”) на “0”(“1”).

Схема алгоритма операции инкремента представлена на рис 2.3.

Анализ схемы алгоритма

В алгоритме имеются две операции выбора:

1. V_a: если на ленте z =1, то выполняется операция R, иначе выполняется операция инвертирования (замена “0” на “1”);

2. V_b: если на ленте z =1, то выполняется операция L, иначе выполняется операция R; в обоих случаях символ в ячейке не изменяется.

Операции V_a и V_b выполняются последовательно; после выполнения команды, соответствующей истинной ветви операции V_a, происходит переход на повторное выполнение операции V_а, а после выполнения команд ложной ветви – безусловный переход на V_b. После выполнения команд истинной ветви операции V_b происходит возврат на эту же операцию V_b, а после команд ложной ветви завершается работа алгоритма.

 

 

 

Итак, каждой операции выбора можно сопоставить свою строку в ФС:

V_a ® q₁: 1 S q₂; 1 R q₁

V_b ® q₂: 0 R!; 1 L q₂

Первая команда в строке соответствует символу “0” в текущей ячейке, вторая - символу “1”. Таким образом, ФС машины М1, реализующей функцию y=n +1, принимает следующий вид - (см. табл. 2.2).

Заметим, что допускается не проставлять в клетке ФС символы q_i, x_j, инициирующих и формирующих команду МТ, в случае их совпадения с символами, именующими клетку, а также символ S, если головка не передвигается.

О.Н. Паулин

 

 

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

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

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

 

 

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

 

 

Одесса ОГПУ 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, то целесообразнее использовать простые алгоритмы.

В В Е Д Е Н И Е

 

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

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

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

 

СОДЕРЖАНИЕ И ПОРЯДОК ВЫПОЛНЕНИЯ

КУРСОВОЙ РАБОТЫ

 

Общие положения

 

Курсовая работа состоит из пояснительной записки (25-30 с. рукописного текста) и графических материалов (один-два листа чертёжной бумаги формата А1). Пояснительная записка и графические материалы должны быть выполнены в соответствии с требованиями ГСТУ и ЕСПД [1-3].

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

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

2. Построение машины Тьюринга,

а также заключение и список литературы.

Пояснительная записка начинается титульным листом (прил.А). В аннотации приводятся цель и краткое содержание курсовой работы с указанием заданных алгоритма и операции, выполняемой машиной Тьюринга, а также выводы относительно особенностей, эффективности, возможности и области применения полученных алгоритмов. Задание на разработку приводится подробно на отдельном бланке (прил. Б). Раздел "Содержание" оформляется обычным образом [1] с перечислением конкретных разделов, подразделов и пунктов с указанием их начального номера страницы.

В разделе "Введение" должно быть отражено следующее:

· актуальность темы;

· что такое алгоритм, его назначение, виды алгоритмов;

· структуры данных и их представление в памяти ЭВМ;

· эффективность алгоритмов и методы её достижения;

· машина Тьюринга как модель вычислительного процесса;

· краткое содержание курсовой работы.

Раздел "Разработка эффективных алгоритмов" в пояснительной записке должен содержать такие подразделы (для примера - алгоритма покрытия; аналогично - для алгоритмов на гр