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

 

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

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

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

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

 

1.2. Построение алгоритма покрытия

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

1.4. Эффективность алгоритма

В разд. 2 пояснительной записки к курсовой работе, посвященной построению машины Тьюринга, должны быть подразделы:

2.1. Решение задачи на машине Тьюринга

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

2.3. Выявление аварийных ситуаций

В разделе "Заключение" должно быть отмечено:

· соответствие полученных результатов заданию на разработку;

· особенности построения алгоритма и машины Тьюринга;

· числовые данные, характеризующие результаты курсовой работы;

· выводы об эффективности разработанных алгоритмов;

· предложения по совершенствованию алгоритмов.

В разделе "Список литературы" приводятся только те источники, которые были использованы Вами при разработке (на них должны быть ссылки в тексте!). Отметим, что конспект лекций не является источником надёжных сведений. Список должен оформляться по ГСТУ [1].

Рекомендуется каждый раздел начинать с новой страницы. Нумеруются разделы арабскими числами; разделы "Аннотация", "Задание на разработку", "Содержание", "Введение", "Заключение" и "Список литературы" не нумеруются. Нумерация листов начинается с титульного листа (номер не ставится!), далее идёт сквозная нумерация. Листы нумеруются вверху, следующей строкой располагается шифр работы [3], (и то, и другое - посередине), а затем идёт текст.

На графических листах представляются схемы алгоритмов (см. прил. Б), основная и её модули; функциональная схема и схема алгоритма работы, а также граф состояний машины Тьюринга. Схемы алгоритмов выполняются в соответствии с [2]. Лист должен иметь свою основную надпись (штамп).

Пояснительная записка и графические листы должны быть сброшюрованы.

 

Защита курсовой работы осуществляется перед комиссией, которая назначается заведующим кафедрой. Перед защитой (не менее чем за 3 дня) работа должна быть сдана на проверку своему руководителю. Защита состоит в докладе (5 мин), в котором студент излагает задание, способы и особенности решения задач построения алгоритма (включая используемые структуры данных) и машины Тьюринга, в характеристике результатов решения, а также в ответах на вопросы комиссии по всей области, относящейся к курсовой работе.

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

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

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

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 необходимо рассмотреть пример (выбирается самостоятельно), показывающий работу машины для конкретной начальной конфигурации на ленте, расписав по тактам последующие конфигурации (в случае цикла допустимо ограничиться начальным и конечным тактами); пример должен охватывать все ветви алгоритма. Далее этот пример анализируется с целью выявления аварийных ситуаций. В заключение определяется длительность (в тактах) процесса выполнения заданной операции.

 

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