Элементы теории алгоритмов

Алгоритм - понятие, относящееся к фундаментальным основам информатики. Оно возникло задолго до появления компьютеров и является одним из основных понятий математики.

Слово «алгоритм» произошло от имени выдающегося средневекового ученогоМухамеда ибн Муса Ал-Хорезми (IXвек н.э.), сокращенноАл-Хорезми . В латинском переводе одного из трудов Ал-Хорезми правила выполнения действий начинались словамиDIXIT ALGORIZMI (Алгоризми сказал), в других латинских переводах автор именовалсяALGORITHMUS (Алгоритмус).

У понятия «алгоритм» нет четкого, однозначногоопределения в математическом смысле. Можно дать толькоописание (пояснение) этого понятия. Для пояснения понятия«алгоритм» большое значение имеет определение понятия«исполнитель алгоритма» . Алгоритм формулируется в расчете на конкретного исполнителя.

Алгоритм - руководство к действию для исполнителя, поэтому значение слова «алгоритм» близко по смыслу к значению слов «указание» или «предписание».

Алгоритм - понятное и точноепредписание (указание ) исполнителю совершить определенную последовательность действий для достижения указанной цели или решения поставленной задачи.

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

Понятно, что сказанное не является определением в математическом смысле, а лишь отражает интуитивное понимание алгоритма (в математике нет понятия «предписание», неясно, какова должна быть точность, что такое «понятность» и т.д.).

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

Массовость.

Алгоритм имеет некоторое число входных величин - аргументов, задаваемых до начала исполнения. Цель выполнения алгоритма - получение результата (результатов), имеющего вполне определенное отношение к исходным данным. Алгоритм указывает последовательность действий по переработке исходных данных в результаты. Для алгоритма можно выбирать различные наборы входных данных из множества допустимых для этого процесса данных, т.е. можно применять алгоритм для решения целого класса задач одного типа, различающихся исходными данными. Это свойство алгоритма обычно называют массовостью . Однако существуют алгоритмы, применимые только к единственному набору данных. Можно сказать, что для каждого алгоритма существует свой класс объектов, допустимых в качестве исходных данных. Тогда свойствомассовости означает применимость алгоритма ко всем объектам этого класса.

Понятность.

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

Дискретность.

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

Конечность.

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

Определенность.

Каждый шаг алгоритма должен быть четко и недвусмысленно определен и не должен допускать произвольной трактовки исполнителем. Следовательно, алгоритм рассчитан начисто механическое исполнение . Именноопределенность алгоритма дает возможность поручить его исполнениеавтомату .

Эффективность.

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

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

Построение такого формального определения было начато с формализации объектов (операндов) алгоритма, так как в интуитивном понятии алгоритма его объекты могут иметь произвольную природу. Ими могут быть, например, числа, показания датчиков, фиксирующих параметры производственного процесса, шахматные фигуры и позиции и т.п. Однако предполагая, что алгоритм имеет дело не с самими реальными объектами, а с их изображениями, можно считать, что операнды алгоритма - слова в произвольном алфавите. Тогда получается, что алгоритм преобразует слова в произвольном алфавите в слова того же алфавита. Дальнейшая формализация понятия алгоритма связана с формализацией действий над операндами и порядка этих действий. Одна из таких формализаций была предложена в 1936 году английским математиком А.Тьюрингом, который формально описал конструкцию некоторой абстрактной машины (машины Тьюринга ) как исполнителя алгоритма и высказал основной тезис о том, что всякий алгоритм может быть реализован соответствующей машиной Тьюринга. Примерно в это же время американским математиком Э.Постом была предложена другая алгоритмическая схема -машина Поста , а в 1954 году советским математиком А.А.Марковым была разработана теория классов алгоритмов, названных имнормальными алгорифмами , и высказан основной тезис о том, что всякий алгоритм нормализуем.

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

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

Содержательная (аналитическая) теория алгоритмов стала возможной лишь благодаря фундаментальным работам математиков в области логических теорий алгоритмов. Развитие такой теории связано с дальнейшим и расширением формального понятия алгоритма, которое слишком сужено в рамках логических теорий. Формальный характер понятия позволит применять к нему математические методы исследования, а его широта должна обеспечить возможность охвата всех типов алгоритмов, с которыми приходиться иметь дело на практике.

Каждый алгоритм имеет дело с данными – входными, промежуточными и выходными.

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

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

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

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

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

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

Эффективность. Одну и ту же задачу можно решить по-разному и соответственно за разное время и с различными затратами памяти. Желательно, чтобы алгоритм состоял из минимального числа шагов и при этом решение удовлетворяло бы условию точности и требовало минимальных затрат других ресурсов.

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

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

В настоящее время можно выделить три основных типа универсальных алгоритмических моделей. Они различаются исходными посылками относительно определения понятия алгоритма.

Первый тип связывает понятие алгоритма с наиболее традиционными понятиями математики – вычислениями и числовыми функциями. Второй тип основан на представлении об алгоритме как о некотором детерминированном устройстве, способном выполнять в каждый отдельный момент лишь весьма примитивные операции. Такое представление обеспечивает однозначность алгоритма и элементарность его шагов. Кроме того, такое представление соответствует идеологии построения компьютеров. Основной теоретической моделью этого типа, созданной в 1930-х гг. английским математиком Аланом Тьюрингом, является машина Тьюринга.

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

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

Запись алгоритма на некотором языке представляет собой программу. Если программа написана на специальном алгоритмическом языке (например, на ПАСКАЛе, БЕЙСИКе или каком-нибудь другом), то говорят об исходной программе . Программа, написанная на языке, который непосредственно понимает компьютер (как правило, это двоичные коды), называется машинной, или двоичной.

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

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

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

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

Для записи алгоритмов используют самые разнообразные средства. Выбор средства определяется типом исполняемого алгоритма. Выделяют следующие основные способы записи алгоритмов:

■ вербальный – алгоритм описывается на человеческом языке;

■ символьный – алгоритм описывается с помощью набора символов;

■ графический – алгоритм описывается с помощью набора графических изображений.

Общепринятыми способами записи алгоритма являются графическая запись с помощью схем алгоритмов (блок-схем) и символьная запись с помощью какого-либо алгоритмического языка.

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

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

Начало и конец алгоритма обозначают с помощью одноименных символов (рис. 21.1).

Рис. 21.1.

Шаг алгоритма, связанный с присвоением нового значения некоторой переменной, преобразованием некоторого значения с целью получения другого значения, изображается символом "процесс" (рис. 21.2).

Рис. 21.2.

Выбор направления выполнения алгоритма в зависимости от некоторых переменных условий изображается символом "решение" (рис. 21.3).

Рис. 21.3.

Здесь Р означает предикат (условное выражение, условие). Если условие выполнено (предикат принимает значение ИСТИНА), то выполняется переход к одному шагу алгоритма, а если не выполнено, то к другому.

Имеются примитивы для операций ввода и вывода данных, а также другие графические символы. В настоящий момент они определены стандартом ГОСТ 19.701–90 (ИСО 5807–85) "Единая система программной документации. Схемы алгоритмов, программ данных и систем. Условные обозначения и правила выполнения". Всего сборник ЕСПД содержит 28 документов.

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

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

В алгоритмах линейной структуры действия выполняются последовательно одно за другим.

В алгоритмах разветвленной структуры в зависимости от выполнения или невыполнения какого-либо условия производятся различные последовательности действий. Каждая такая последовательность действий называется ветвью алгоритма.

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

В этом случае одно повторение цикла называется итерацией.

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

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

Слово «алгоритм» появилось в Средние века, когда ев­ропейцы познакомились со способами выполнения ариф­метических действий в десятичной системе счисления, описанными узбекским математиком Мухаммедом бен Муса аль-Хорезми («аль-Хорезми» - человек из города Хорезми; в настоящее время город Хива в Хорезмской об­ласти Узбекистана). Слово «алгоритм» есть результат ев­ропейского произношения слов «аль-Хорезми».

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

Дискретность - это свойство, означающее следую­щее: каждый алгоритм состоит из отдельных законченных действий, т. е. «делится на шаги».

Массовость - применимость алгоритма ко всем зада­чам рассматриваемого типа при любых исходных данных.

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

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

Существует несколько способов описания алгоритмов: словесное описание, блок-схема, алгоритмический язык и программа.

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

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

Блок-схема - описание структуры алгоритма с по­мощью геометрических фигур с линиями-связями, по­казывающими порядок выполнения отдельных инструк­ций. Этот способ имеет ряд преимуществ. Благодаря на­глядности он обеспечивает «читаемость» алгоритма и явно отображает порядок выполнения отдельных ко­манд. В блок-схеме каждой формальной конструкции со­ответствует определенная геометрическая фигура или связанная линиями совокупность фигур. К основным гео­метрическим фигурам, используемым для построения блок-схем, относятся следующие.

Блоки, характеризующие нача­ло и конец алгоритма:

Блок, отображающий процесс {оператор), предназначенный для описания отдельных действий:

Блок, описывающий цикл с пара­метром:

Блок ввода/вывода с произвольного носителя информации:

Описание алгоритма в словесной форме или в виде блок-схемы допускает некоторый произвол при изображении команд. Вместе с тем оно позволяет человеку легко понять суть дела и исполнить алгоритм.

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

нп - начало цикла; кп_ - конец цикла; для - цикл с параметром; если - условие; то - результат выполнения условия; иначе - результат невыполнения условия; всё - конец условия; пока - условие цикла.

Рассмотрим примеры блок-схем трех основных видов ал­горитмов: линейного, разветвляющегося и циклического. Линейным называется алгоритм, в котором все этапы решения задачи выполняются строго последовательно.

Блок-схема линейного алгоритма нахождения перимет­ра прямоугольного треугольника Р при известных длинах его катетов a, b изображена на рис. 5.1.

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

Различают неполное (если-то) и полное (если-то-иначе) виды ветвления.

Неполное ветвление предполагает нали­чие оператора только на одной ветви (то; Да; Истина), на другой ветви оператор отсутст­вует и управление сразу переходит к точке слияния

Полное ветвление позволяет организовывать две вет­ви в алгоритме (то или иначе; Да илиНет; Истина или Ложь), каждая из которых ведет к общей точке их слия­ния (рис. 5.26).

Циклическим, или просто циклом, называют такой алгоритм, в котором получение результата обеспечива­ется многократным выполнением одних и тех же опера­ций. Группа повторяющихся операций называется телом цикла.

Широкое применение получили три типа циклов: цикл с параметром, цикл с предусловием и цикл с постуслови­ем.

Цикл с параметром используется в тех случаях, когда известна величина k, т. е. количество элементов или ша­гов цикла.

Количество шагов цикла с предусловием заранее не определено. В нем сначала проверяется выпол­нение условия. Если оно Истинно (Да), то исполняется тело цикла, после чего вновь проверяется условие. Ука­занные действия проверяются до тех пор, пока условие не примет значение Ложно (Нет).

Цикл с постусловием отличается от цик­ла с предусловием расположением условия и тем, что тело цикла всегда будет выполнено хотя бы один раз. Тело это­го цикла будет выполняться, пока условие Ложно (Нет).

Для повышения производительности и качества рабо­ты каждый язык программирования имеет структуриро­ванный тип данных - массив.

Массивом называется упорядоченная совокупность однотипных величин, имеющих общее имя, элементы ко­торой различаются порядковыми номерами, именуемыми индексами.