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

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

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

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

Существуют три основных класса арифметических моделей.

1. Предполагается, что любые данные можно закодировать числами. Всякое их преобразование является арифметическим вычислением. Алгоритмом является вычисление некоторой числовой функции. Его элементарные шаги – арифметические операции. Последовательность шагов определяется двумя способами: 1) суперпозиция – подстановка функции в функцию, 2) рекурсия – вычисление значения функции через ранее вычисленные значения этой же функции. Функции, которые можно построить из целых чисел и арифметических операций с помощью супер- позиций и рекурсий, называются рекурсивными функциями. Пример: (n+1)!=n!(n+1).

2. Чтобы алгоритм понимался однозначно, а его каждый шаг считался элементарным и выполнимым, он должен быть представлен так, чтобы его могла выполнить машина, к которой предъявляются требования простоты и универсальности. Одной из таких машин является абстрактная машина Тьюринга, состоящая из трёх частей: ленты, головки и управляющего устройства (УУ).

3. Третий класс моделей алгоритмов очень близок к предыдущему, но не оперирует конкретными машинными механизмами. Наиболее известны нормальные алгоритмы Маркова. Для нормального алгоритма задаётся алфавит, над которым он работает, конечное множество допустимых подстановок и порядок их применения.

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

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

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

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

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

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

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

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

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

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

• словесная запись алгоритмов;

• схемы алгоритмов;

• псевдокод (формальные алгоритмические языки);

• структурограммы (диаграммы Насси-Шнейдермана);

Словесная форма записи алгоритма

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

Схемы алгоритмов

Схема — это графическое представление ритма, дополненное элементами словесной записи. Каждый пункт ритма отображается на схеме некоторой геометрической фигурой — блоком (блочным символом), причем различным по типу выполняемых дек ствий блокам соответствуют различные геометрические фигуры, изображаемые по ГОСТу Графические символы на схемах соединяются линиями потока информации, которые идут сверху вниз и слева направо (стрелки на линиях могут не указываться). В других случаях применение стрелок обязательно.

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

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

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

Таблица 1

	Название символа	Символ	Отображаемая функция
1	Блок вычислений (процесс)		Вычислительное действие или последовательность вычислительных действий
2	Логический блок (решение)	Error: Reference source not found	Выбор направления выполнения алгоритма в зависимости от некоторых условий
3	Блок ввода-вывода	Error: Reference source not found	Общее название ввода или вывода данных (в зависимости от физического носителя)
			Вывод данных на печатающее устройство
4	Начало-конец	Error: Reference source not found	Начало или конец программы останов, вход или выход в подпрограммах
5	Предопределенный процесс (подпрограмма)		Вычисление по стандартной подпрограмме или подпрограмма пользователя
6	Блок модификации (заголовок цикла)		Выполнение действий, изменяющих пункты алгоритма
7	Соединитель		Указание связи между прерванными пиниями потока информации в пределах одной страницы
8	Межстраничный соединитель		Указание связи между частями схемы, расположенными на разных листах

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