Раздел 4. Алгоритмизация И ПРОГРАММИРОВАНИЕ
Лекция 11. ОСНОВНЫЕ ПОНЯТИЯ теории АЛГОРИТМов
1. Алгоритм и его свойства
2. Классы моделей алгоритмов
3. Понятие исполнителя алгоритма
4. Структурный подход к разработке алгоритма
5. Формы записи алгоритма
литература:
[1], стр. 187 – 212.
Алгоритм и его свойства
Понятие алгоритма
Алгоритм — это точное предписание, определяющее последовательность действий, обеспечивающую получение требуемого результата решения задачи из исходных данных за конечное число шагов.
Задача – проблема, подлежащая решению.
Название "алгоритм" произошло от латинской формы имени величайшего среднеазиатского математика Мухаммеда ибн Муса ал-Хорезми (Alhorithmi), жившего в 783—850 гг. Он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними "столбиком". В XII веке эта книга была переведена на латынь и получила широкое распространение в Европе.
Понятие алгоритма является не только одним из главных понятий математики, но одним из главных понятий современной науки. Более того, с наступлением эры информатики алгоритмы становятся одним из важнейших факторов цивилизации.
Теория алгоритмов – раздел математики, изучающий общие свойства алгоритмов. Началом систематической разработки теории алгоритмов можно считать 1936 г. Причиной развития этой теории были внутренние проблемы математики и, лишь с возникновением и развитием вычислительной техники и смежных наук, выяснилось, что в основе этих наук должна лежать теория алгоритмов. Так стало очевидным прикладное значение новой науки.
В основе формализации понятия «алгоритм» лежит идея построения алгоритмической модели. Составляющими такой модели должны быть конкретный набор элементарных шагов, способы определения следующего шага и т.д.
Свойства алгоритмов
К основным свойствам алгоритмов относятся следующие свойства:
Понятность для исполнителя — исполнитель алгоритма должен понимать, как его выполнять. Иными словами, имея алгоритм и произвольный вариант исходных данных, исполнитель должен знать, как необходимо действовать для выполнения данного алгоритма.
Дискретность (прерывность, раздельность) — алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов (этапов), исполнение которых не вызывает затруднений.
Определенность — исполнение каждого шага алгоритма должно быть четким, однозначным и не оставлять места для произвола. Благодаря этому свойству выполнение алгоритма носит механический характер и не требует никаких дополнительных указаний или сведений о решаемой задаче.
Результативность (конечность) состоит в том, что за конечное число шагов алгоритм либо должен приводит к решению задачи, либо после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения, либо неограниченно продолжаться в течение времени, отведенного для исполнения алгоритма, с выдачей промежуточных результатов.
Универсальность (массовость) означает, что алгоритм решения задачи разрабатывается в общем виде, т.е. он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. При этом исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.
2. КЛАССЫМОДЕЛЕЙ АЛГОРИТМОВ
Результатами теоретических исследований явились три основных класса математических моделей.
Первый класс моделей основан на арифметизации алгоритмов. Предполагается, что любые данные можно закодировать числами, и как следствие – всякое их преобразование становится в этом случае арифметическим вычислением, алгоритм в таких моделях есть вычисление значения некоторой функции, а его элементарные шаги – арифметические операции.
Последовательность шагов определяется несколькими способами. Первый способ – суперпозиция, т.е. подстановка функции в функцию, а второй – рекурсия, т.е. определение значения функции через «ранее» вычисленные значения этой же функции.
Функции, которые можно построить из целых чисел и арифметических операции с помощью суперпозиций и рекурсивных определений, называются рекурсивными функциями. Пример рекурсивной функции – факториал функции.
Второй класс моделей порожден следующей идеей – однозначность алгоритма и его техническое исполнение ЭВМ. Одной из таких машин явилась абстрактная машина Тьюринга. Она состоит из трех частей: ленты, головки и управляющего устройства. Лента бесконечна и разбита на ячейки. В каждой ячейке может быть записан только один символ (рис. 11.1).
 |
Рис. 11.1. Машина Тьюринга
Отсутствие символа в ячейке обозначается специальным «пустым» символом «». Головка всегда располагается над некоторой ячейкой ленты. Она может читать и писать символы, стирать их и перемещаться вдоль ленты. Число возможных символов конечно, и образует алфавит машины А=íа1, …, аmý. Головка в каждый такт работы машины находится в одном из состояний. Множество таких состояний конечно Q=íq1, …, qný и среди них выделяют начальное q и конечное q состояние.
Элементарный шаг машины Тьюринга состоит из следующих действий:
- головка считывает символ, записанный в ячейке, над которой она находится;
- считанный символ ак и текущее состояние головки qj однозначно определяют новое состояние qi, новый записываемый символ а1 и перемещение головки dp (которое может иметь значение на ячейку влево, на ячейку вправо, остаться на месте).
Устройство управления хранит и выполняет команды машины вида qj ak ® qi a1 dp.
Полное состояние машины Тьюринга называется конфигурацией и включает в себя состояние головки, ленты (слово, записанное на ней) и положение головки на ленте.
Третий класс моделей алгоритмов очень близок к предыдущему, но не оперирует конкретными машинными механизмами. Например, нормальные алгоритмы Маркова.
Для нормального алгоритма задается алфавит, над которым он работает, конечное множество допустимых подстановок и порядок их применения. Если в качестве алфавита взять алфавит русского языка, а в качестве множества постановок следующие правила замены букв
1) Я®У
2) Л®У
3) С®М
4) В®Б
5) Р®Т
6) Т®Р!
7) О®Х
8) Н®А,
то используя правила:
1) проверить возможность подстановок в порядке возрастания их номеров, и если она возможна (левая часть подстановки обнаружена в исходном слове), провести подстановку (заменив левую часть на правую);
2) если в примененной подстановке имеется символ «!», то преобразования прекращаются, а если нет, то текущее состояние становится исходным и весь процесс начинается заново;
3) если ни одна подстановка не применима, то процесс преобразования завершен;
можно обнаружить, что по заданному алгоритму исходное слово «слон» превращается в «муха» по следующей цепочке:
«слон» ® «суон» ® «муон» ® «мухн» ® «муха».
В теории алгоритмов строго доказано, что по своим возможностям преобразования нормальные алгоритмы эквивалентны машине Тьюринга и другим моделям, уточняющим понятия алгоритма.
Появление точного понятия алгоритма позволило сформулировать алгоритмически неразрешимые проблемы, т.е. задачи, для решения которых невозможно построить алгоритм.
Задача называется алгоритмически неразрешимой, если не существует машины Тьюринга (или рекурсивной функции, или нормального алгоритма Маркова), которая ее решает.
Например, неразрешимой оказалась проблема распознавания эквивалентности алгоритмов: нельзя построить алгоритм, который по любым двум алгоритмам выяснял бы, вычисляют они одну и ту же функцию или нет.
Знание основных неразрешимостей теории алгоритмов необходимо для специалиста, чтобы предостеречь его от всеобщей алгоритмизации, как знание основных законов физики предостерегает от попыток создания вечного двигателя.
3. ПОНЯТИЕ ИСПОЛНИТЕЛЯ АЛГОРИТМА
Исполнитель алгоритма – это некоторая абстрактная или реальная (техническая, биологическая или биотехническая) система, способная выполнять действия, предписываемые алгоритмом, т.е. это субъект или объект, реализующий алгоритм.
Исполнителем может быть человек, группа людей, робот, станок, компьютер и т.д.
Исполнитель не вникает в сущность, а только исполняет алгоритм, получая необходимый результат, т.е. исполнитель действует формально – формальный исполнитель.
Это важная особенность алгоритмов. Наличие алгоритма формализует процесс решения задачи. Исключает рассуждение исполнителя. Использование алгоритма дает возможность решать задачу формально, механически исполняя команды алгоритма в указанной последовательности. Целесообразность предусматриваемых алгоритмом действий обеспечивается точным анализом со стороны разработчика алгоритма.
Каждый алгоритм создается в расчете на конкретного исполнителя. Действия, которые может совершать исполнитель – допустимые действия. Их совокупность – система команд исполнителя. Алгоритм должен содержать только те действия, которые допустимы для его формального исполнителя. Объекты, над которыми исполнитель может совершать действия составляют среду формального исполнителя. (Например, в информатике универсальный формальный исполнитель – ЭВМ; среда исполнителя – числовые, символьные, логические величины и т.п.)
4. СТРУКТУРНЫЙ ПОДХОД К РАЗРАБОТКЕ АЛГОРИТМА
Для того, чтобы алгоритм выполнил свое предназначение, его необходимо строить по определенным правилам. В этом смысле нужно говорить не о свойствах алгоритма, а о правилах построения алгоритма, или о требованиях, предъявляемых к построению алгоритма.
Первое правило – при построении алгоритма, прежде всего, необходимо задать множество объектов, с которыми будет работать алгоритм. Формализованное (закодированное) представление этих объектов носит название данных. Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результате своей работы выдает данные, которые называются выходными. Таким образом, алгоритм преобразует входные данные в выходные.
Это правило позволяет сразу отделить алгоритмы от “методов” и “способов”. Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.
Второе правило – для работы алгоритма требуется память. В памяти размещаются входные данные, с которыми алгоритм начинает работать, промежуточные данные и выходные данные, которые являются результатом работы алгоритма. Память является дискретной, т.е. состоящей из отдельных ячеек. Поименованная ячейка памяти носит название переменной. В теории алгоритмов размеры памяти не ограничиваются, т. е. считается, что мы можем предоставить алгоритму любой необходимый для работы объем памяти.
Третье правило – дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Множество шагов, из которых составлен алгоритм, должно быть конечно.
Четвертое правило – детерменированность. После каждого шага необходимо указывать, какой шаг выполняется следующим, либо давать команду остановки.
Пятое правило – сходимость (результативность). Алгоритм должен завершать работу после конечного числа шагов. При этом необходимо указать, что считать результатом работы алгоритма.
Итак, алгоритм – неопределяемое понятие теории алгоритмов. Алгоритм каждому определенному набору входных данных ставит в соответствие некоторый набор выходных данных, т. е. вычисляет (реализует) функцию. При рассмотрении конкретных вопросов в теории алгоритмов всегда имеется в виду какая-то конкретная модель алгоритма.
Формы записи алгоритма
Алгоритм, как последовательность шагов или инструкций, может быть представлен в различных формах.
На практике наиболее распространены следующие формы представления алгоритмов:
· словесная (запись на естественном языке);
· псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
· графическая (изображения из графических символов);
· программная (тексты на языках программирования).
Словесная форма записи алгоритмов
Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.
Например. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Эвклида).
Алгоритм может быть следующим:
· задать два числа;
· если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма;
· определить большее из чисел;
· заменить большее из чисел разностью большего и меньшего из чисел;
· повторить алгоритм с шага 2.
Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи. Убедитесь в этом самостоятельно, определив с помощью этого алгоритма наибольший общий делитель чисел 125 и 75.
Словесный способ не получил широкого распространения из-за следующих недостатков:
· строго не формализуем;
· страдает многословностью записей;
· допускает неоднозначность толкования отдельных предписаний.
Псевдокод
Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов.
Псевдокод занимает промежуточное место между естественным и формальным языками. С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой стороны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи.
В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя.
Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде, так же, как и в формальных языках, есть служебные слова, смысл которых определен раз и навсегда. Они выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются.
Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций.