Понятие алгоритма. Свойства алгоритмов. Способы представления алгоритмов.

Алгоритм – точное предписание, определяющее вычислительный процесс, ведущий от начальных данных к искомому результату. Свойства алгоритмов:

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

2.Определенность – детерминированность – свойство заключается в том, что одно и то же предписание будучи понятным разным исполнителям и после выполнения должно давать одинаковый результат

3.Понятность – исполнитель в состоянии понять и выполнить все те действия, которые предусмотрены алгоритмом

4.Массовость – алгоритм обеспечивает решение широкого круга задач одного типа

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

Способы задания алгоритма: 1. Аналитический, 2. Табличный, 3. Словесная запись, 4. Графический

Базовые алгоритмические структуры. Построение, пошаговая детализация

Схема алгоритма – наглядное графическое представление алгоритма, дополненное элементами словесной записи. Каждый пункт алгоритма отображается геометрической фигурой – блоком. Блок схемы алгоритма предусматривает выделение двух основных видов предписания: Арифметические – без ветвления; Логические – для организации ветвлений; Начало; Ввод-вывод; Соединитель; Подпрограмма; Цикл модификаций.

Базовыми строениями являются: Линейная; Ветвление; Цикл: с пост-условием, с пред-условием, с параметром.

Основные методы разработки алгоритмов

1 Этап: Постановка задачи – неформализованное содержательное описание проблемы и возможных способов действий

1. Сформулировать цель решения задач

2. Определить критерии эффективности

3. Определить исходные данные и результаты

4. Определить связь с другими задачами

5. Определить соответствие требованиям, предъявляемым к системе

2 Этап: Построение математической модели

1. Определить математические структуры, которые подходят для решения задач

2. Существуют ли решенные аналогичные задачи

3. Определить ограничения на действующие факторы

4. Произвести запись математических соотношений, которые связывают исходные данные с результатом

3 Этап: Разработка алгоритма

1. Определить порядок ввода исходных данных

2. Необходимо построить логическую последовательность процесса обработки информации

3. Определить порядок вывода результата решения задач

4. Проверка правильности алгоритма

Доказательство правильности алгоритма: во многих случаях доказательство правильности сводят к доказательству правильности программы

Общая методика проверки алгоритма:

1. Алгоритм описан в виде шагов – предполагается обоснование правомерности для каждого шага

2. Предлагается доказательство конечности алгоритма

3. Реализация алгоритма (составление программы): а) Идентификация исходных данных, подпрограмм, стандартных процедур и функций; б) Определить порядок ввода исходных данных, обработки информации, вывод результатов; в) выбрать язык программирования

4. Анализ алгоритма и его сложности: причины для анализа: а) Определение границ объема памяти (оперативной); б) Оценка времени работы; в) Сравнение с другими алгоритмами

5. Проверка программы: а) Отладка программы; б) Выполнение программы, получение результатов решения; в) Анализ и оценка полученных результатов

6. Составление документации

Основные методы разработки алгоритма:

· Метод частных целей

· Метод подъема

· Метод отрабатывания назад (от цели к началу)

· Метод эвристики (рациональное решение)

· Метод ветвей и границ

· Рекурсия