Основные этапы проектирования и анализа алгоритмов

Понятие алгоритма.Алгоритмические языки

Алгоритмом называется точное и понятное предписаниe исполнителю совершить последовательность действий, направленных на решение поставленной задачи

Искусственная система языковых средств, обладающая выразительными возможностями, достаточными для того, чтобы с ее помощью можно было задать любое принадлежащее заранее очерченному классу детерминированное общепонятное предписание, выполнение которого ведет от варьирующих в определенных пределах исходных данных к искомому результату

Свойства алгоритмов

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

2. Определенность. Каждое правило алгоритма должно быть четким, однозначным.

3. Результативность. Алгоритм должен приводить к решению за конечное число шагов.

4. Массовость. Алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными.

5. Правильность. Алгоритм правильный, если его выполнение дает правильные результаты решения поставленной задачи.

Наиболее важные задачи алгоритмизации

Наиболее важные задачи алгоритмизации.

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

Основные этапы проектирования и анализа алгоритмов

вопрос 4 Основные этапы проектирования и анализа алгоритмов.
1. Понимание задачи. Прежде чем начать проектировать алгоритм, надо полностью понять поставленную задачу.
2. Выбор составляющих решения задачи.
2а. Определение возможностей вычислительного устройства. Большинство алгоритмов предназначено для работы на компьютере, где команды выполняются последовательно друг за другом (последовательные алгоритмы). Тем не менее, существуют компьютеры способные выполнять одновременно несколько команд, для них разработаны параллельные алгоритмы.
2б. Следующий принципиальный вопрос - выбор точного или приближенного алгоритма. Выбором в пользу второго могут служить причины: невозможности точного решения (например, решение нелинейных уравнений), точные алгоритмы очень медленны (особенно при больших размерностях), приближенный алгоритм лишь часть другого алгоритма (может быть даже и точного).
2в. Выбор структуры данных. В некоторых алгоритмах не требуется, чтобы данные имели строго определенную структуру, но в большинстве случаев алгоритм предназначен для работы только со специфическими структурами. В мире объектно-ориентированного программирования структуры данных - один из важнейших элементов процесса проектирования.
2г. Метод проектирования алгоритмов. Основные подходы и принципы методов рассматриваются в теории алгоритмов.
3. Разработка алгоритмов. Разработка осуществляется согласно выбранным принципам и методам и может осуществляться на любом удобном языке: ЯП, псевдокоде, естественном языке, в виде блок-схемы и т.д. Степень детализации и выбор представления определяются удобством общения между разработчиком и программистом.
4. Оценка корректности. Необходимо доказать, что предложенный алгоритм за ограниченный промежуток времени выдает правильный результат для любых корректных данных. Это отдельная задача, т.к. доказать корректность некоторых алгоритмов невероятно сложно. Универсальным методом доказательства корректности считается метод математической индукции (многие алгоритмы итеративны). Тестирование алгоритма на большом числе примеров еще не доказывает его корректности, в то время как лишь один набор данных может доказать некорректность алгоритма. Если такое произошло, алгоритм надо видоизменить или, что более кардинально, пересмотреть ранее принятые принципы и подходы.
Для приближенных алгоритмов, как правило, доказывается их сходимость (если итерационны) и оценивается погрешность выходных данных.
5. Анализ алгоритма. После анализа корректности интересует анализ эффективности алгоритма. Различают 2 вида оценки эффективности: временная эффективность (индикатор скорости работы, часто оценивается не время, а количество простых операций) и пространственная эффективность (оценка занятой оперативной памяти). Вопросами эффективности алгоритмов также занимается теория алгоритмов.
Еще одной важной характеристикой алгоритмов является его простота. Такие алгоритмы легче понять и запрограммировать, а следовательно, в них меньше ошибок. Если что-то не устраивает (эффективность или простота), то процесс проектирования начинают снова (см. схему).
6. Реализация алгоритма. В момент кодирования алгоритма в него могут закрасться ошибки или будет обнаружена неэффективность алгоритма. Корме того, эффективный алгоритм может быть неэффективно реализован. Здесь надо знать ряд правил, например, выносить из сумм некоторое инвариантное выражение за пределы цикла; выделять общие подвыражения в циклах, заменять медленные операторы их быстрыми аналогами.
В процессе реализации алгоритма важен процесс тестирования. Это отдельная задача и вопросам тестирования посвящена отдельная литература.
Хороший алгоритм получается, как правило, в результате кропотливой циклической работы, связанной с возможными переделками.