Кратко об алгоритмах
Посмотрим определение алгоритма в одном из учебников: [1, c 8]:
Алгоритм - точное предписание, которое задает вычислительный процесс, начинающийся с произвольного исходного данного (из некоторой совокупности возможных для данного алгоритма исходных данных) и направленный на получение полностью определяемого этим исходным данным результата.
Алгоритм можно записать разными способами:
- графически - на языке блок-схем,
( можете скачать
ГОСТ 19_701-90 ЕСПД - СХЕМЫ АЛГОРИТМОВ, ПРОГРАММ, ДАННЫХ И СИСТЕМ.
УСЛОВНЫЕ ОБОЗНАЧЕНИЯ И ПРАВИЛА ВЫПОЛНЕНИЯ),
- при помощи графов.
- Наконец, при помощи специальных языков, которые называются АЛГОРИТМИЧЕСКИМИ (Pascal, Basic и т д - их очень много).
Принято считать, что вначале алгоритм записывается на языке блок-схем, затем - переписывается на алгоритмическом языке. Далее программа компилируется, то есть преобразуется в программу на машинном языке. Однако несложные программы опытному программисту проще написать сразу, например, на Паскале или Делфи, минуя стадию блок-схем. Но существуют стандарты оформления документации, согласно которым блок-схема все же необходима.
Примечание: в старые (но не добрые) времена, когда программы выполнялись на ЭВМ в пакетном режиме и исправление (редактирование) текста программ было возможно 1 раз в сутки, тщательность разработки алгоритма была более необходима, чем сейчас, когда программист надеется выявить ошибки в процессе наладки (к тому же, находить ошибки - дело увлекательное (для тех, кто умеет)).
В настоящее время существуют средства автоматизации разработки программ, позволяющие строить модель задачи и затем создающие программу, соответствующую этой модели. Познакомиться с алгоритмами более подробно можно в [1, часть 1], где изложены следующие вопросы:
- Введение в теорию алгоритмов: Свойства алгоритмов, понятие об исполнителе алгоритма, точное понятие алгоритма (машина Тьюринга), понятие об алгоритмической неразрешимости, методы разработки алгоритма.
- Рекурсивные алгоритмы: вычислимые функции, рекурсия и математическая индукция, реализация механизма рекурсии, рекурсия и итерация.
- Рекурсивные данные: рекурсивно определенные типы данных, линейные списки, деревья, графы.
- Анализ сложности алгоритмов: понятие сложности а., основные методы и приемы анализа сложности , сложность операций с бинарными деревьями, оптимизация алгоритмов.
- Классы сложности задач: разрешимые и неразрешимые задачи, сложность задачи, пограничная полоса - класс NP, if NP <> P then NP:= P U NPC U NPI.
- Сортировка и поиск: Сортировка массивов, сортировка последовательных файлов, поиск; хеширование.
- Формальные языки: принципы построения, классификация, описание синтаксиса яз. с помощью металингвистических формул и синтаксических диаграмм.
- Дискретность -
алгоритм состоит из конечного числа шагов, причем любые два последовательных шага разделены при исполнении некоторым отрезком времени. - Элементарность шагов.
Например, для численных алгоритмов элементарными шагами могут быть: сложение, вычитание, умножение, деление, сравнение двух 32-разрядных чисел, пересылка числа из одного места памяти в другое и т п. - Определенность (детерминированность)
означает, что для каждого шага результаты выполнения шага зависят только от исходных данных этого шага. оответственно и алгоритм в целом по окончании работы исполнителя выдает результат, однозначно определяемый исходными данными алгоритма. - Конечность
- для получения результата нужно выполнить конечное число шагов, т. е. исполнитель в некоторый момент времени останавливается. Требуемое число шагов обычно зависит от входных данных алгоритма. - Массовость
- входные данные могут выбираться из некоторого множества значений, то есть алгоритм решает некоторый тип задач при различных исходных данных, например, квадратное уравнение a*x^2 + b*x + c = 0 при различных значениях коэффициентов a,b,c.
Авторы: Алексеев Е.Р., Чеснокова О.В., Кучер Т.В. Формат - .pdf 4,6Mb Сайты автора: ww.teacher.dn-ua.com и www.teacher.ucoz.net
Этот самоучитель можно скачать и здесь (4Mb, Lazarus-uchebnik.rar).
Продолжение (Выводы)
