Алгоритмы, их свойства и способы представления

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

Этапы решения задачи на компьютере

Основы алгоритмизации задач

Настоящая тему традиционно считают главной темой теоретической информатики, вводящей студентов в обширные практические разделы алгоритмизации методов решения различных прикладных задач. В основу алгоритмизации положено фундаментальное понятие математики и информатики – алгоритм. Название «алгоритм» происходит от латинизированного воспроизведения арабского имени узбекского математика Аль-Хорезми, жившего в конце VIII–IX вв., который первым сформулировал правила, позволяющие систематически составлять и решать квадратные уравнения.

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

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

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

Третий этап - выбор метода решения. Выбор метода определяется решаемой задачей, а также возможностями компьютера (его быстродействием, объемом памяти, точностью представления чисел, наличием разработанных ранее готовых программ и т.п.). Выполнение этого этапа требует некоторого кругозора в области математического программирования.

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

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

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

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

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

Далее более подробно рассматривают этапы составления алгоритма решения задачи и выбора структуры представления данных.

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

Каждый алгоритм должен обладать следующими основными свойствами:

№	Наименование свойства алгоритма	Содержательная суть свойства
1.	Дискретность	алгоритм должен представлять процесс решения задачи как последовательность простых шагов. При этом для выполнения каждого шага алгоритма требуется некоторый конечный отрезок времени, т.е. преобразование исходных данных в результат осуществляется во времени дискретно
2.	Определенность	каждая команда алгоритма должна быть четкой, однозначной
3.	Конечность	алгоритм должен приводить к решению задачи за конечное число шагов
4.	Массовость	алгоритм решения задачи разрабатывается не для одной конкретной задачи, а целого класса однотипных задач, различающихся лишь исходными данными

Алгоритм можно зафиксировать несколькими способами, например, словесно, в виде схемы (блок-схемы), на специальном языке (алгоритмическом языке).

Для построения алгоритма требуется такая его реализация, которая была бы легка для понима­ния, проста для доказательства правильности и удобна для модифи­каций в случае изменения спецификаций функции. Основные блоки для описания алгоритма и выполняемые ими функции представлены в таблице 2.5.1.

В настоящее время самой популярной методикой следует считать структурное программирование сверху - вниз. Объяснение структурного программирования начнем с определения блок-схемы. Блок-схема — это ориентированная сеть, вершины которой могут быть одного из трех типов, представленных на рис. 2.5.1.

Таблица2.5.1.

№	Наименование Символа	Обозначение символа	Функция символа
1.	Процесс		Выполнение операции или группы операций, в результате которых изменяются значение, форма представления или расположения данных
2.	Решение		Выбор направления выполнения алгоритма или программы в зависимости от некоторых переменных условий
3.	Ввод ‑ вывод		Преобразование данных в форму пригодную для обработки (ввод) или отображения результатов (вывод)
4.	Пуск ‑ останов		Начало, конец, прерывание процесса обработки данных или выполнения программы.
5.	Соединитель		Указание связи между прерванными линиями потока, связывающими символы
6.	Цикл		Многократное повторение одного или нескольких операторов с последовательным изменением значений параметров цикла

Рис. 2.5.1 Типы вершин алгоритма

Функциональная вершина (рис. 2.5.1а) используется для представления функции

f: X ® Y. Предикатная вершина (2.5.1.б) используется для представления функции p: X®{T,F}, т.е. в зависимости от логического выражения, передающего управление по одной из двух возможных ветвей. Объединяю­щая вершина (рис.2.5.1.в) представляет передачу управления от одной из двух входящих ветвей к одной выходящей ветви.

Структурная блок-схема — это блок-схема, которая может быть выражена как композиция из четырех элементарных блок-схем, изображенных на рис. 2.5.2. Сравнительно просто доказать, что любая программа для компьютера может быть «представлена» блок-схемой. Из этого результата немедленно следует, что для разработки любого алгоритма достаточно четырех элементарных блок-схем, приведенных на рис. 2.5.2.

Когда структурная блок-схема служит как представление про­граммы, то В интерпретируется как булевское выражение, а S1 и S2 интерпретируются как программные операторы (или процедуры).

Рис. 2.5.2. Четыре элементарных блок-схемы.

Блок-схемы на рис. 2.5.2, называют структурами уп­равления программы. Схема на рис. 2.5.2а называется композицией и записывается в виде (S1; S2). Схема на рис. 2.5.2.б называется набором (или альтернативой) и записывается в виде if B then S1 e lse S2. Блок-схема на рис. 2.5.2. в и г называются циклом (или повторением) и записываются соответственно как while B do S1 и do S1 while B. Выполнение этого цикла аналогично выполнению цикла for Q do S1, где Q – определяет выражение изменения параметра цикла от начального до конечного значения.

Следует отметить, что часто употребляемый упрощенный оператор if B then S1, блок-схема которого приведена на рис. 2.5.3, представ­ляет собой частный случай оператора if-then-else.

Рис. 2.5.3. Блок –схема, реализующая оператор if B then S1.

Важная особенность заключается в том, что каждая из этих четы­рех программных структур управления имеет один вход и один вы­ход. Отсюда следует, что у любой блок-схемы, составленной из этих элементов, также будет один вход и один выход. На рис. 2.5.4 в ка­честве иллюстраций приводится несколько примеров структурных блок-схем, построенных из данных элементов; лингвистически эти блок-схемы могут быть описаны следующим образом:

а) If B then {S1;S2} else if C then S3 else S4;

б) if B then if C then {S1;S2} else while D do {S3} else {S4;S5};

а)	б)

Рис. 2.5.4. Примеры структурных блок-схем.

Необходимо обратить внимание на то, что в представленных блок-схемах совершенно отсутствует оператор goto. Строго говоря, под алгоритмизацией задач понимается процесс разработки алгоритмов с помощью структурных блок-схем.

Однако в более широком плане алгоритмизации до­пускает большее разнообразие элементарных структур управления, чем те, которые были предложены выше (т.е. те, которые изображены на рис. 2.5.2). Дело в том, что, хотя эта совокупность структур управления достаточна для построения любой программы для компьютера, само построение не обязательно ока­жется простейшим или наиболее естественным. Проиллюстрируем это на некоторых примерах.

Первый пример (рис. 2.5.5) соответствует ситуации, которая лингвистически эту блок-схему можно выразить в виде case i of {S1;S2; … Sm};

Рис. 2.5.5. Блок-схема «выбора».

что эквивалентно следующей записи:

if i=1 then S1 else

if i=2 then S2 else

……………………..

if i=m then Sm;

Вторая запись по сравнению с первой выглядит менее естественно.

Второй пример (рис. 2.5.6) соответствует ситуации, когда необ­ходимо

OUT

Рис. 2.5.6. Блок-схема цикла с постусловием.

преждевременно завершить выполнение цикла While, вводя дополнительный выход. Один из возможных лингвистиче­ских операторов для блок-схемы на рис. 2.5.6 имеет вид

while B do S1 if C then S2 else goto OUT;

Хотя более строгие формы алгоритмизации исклю­чают применение оператора goto, блок-схемы, в которых оператор goto используется достаточно аккуратно, могут сохранить свойство структурных блок-схем: один вход и один выход.

Вообще говоря, алгоритмизация определяет процесс разработки алгоритмов в терминах блок-схем, в которых используются элементарные структуры управления. Впрочем, допускаются и другие структуры «простого типа» при условии, что они обладают свойством «один вход один выход».

Как было показано выше алгоритмизация это процесс пошагового разбиения алгоритма на всё более мелкие части с целью получить такие элементы, для которых можно легко написать конкретные команды. На рис. 2.5.7 этот процесс иллюстрируется для случая блок-схемы на рис. 2.5.4б.

Рис. 2.5.7. Блок-схемы процесса алгоритмизации задачи.

Дата добавления: 2014-10-17