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

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

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

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

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

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

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

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

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

Массовость.

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

Понятность.

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

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

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

Конечность.

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

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

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

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

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

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

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

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

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

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

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

В этой статье мы разберем основные понятия алгоритма.

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

Алгоритм - понятие, появившиеся в XII веке. Само слово "алгоритм" происходит от латинской интерпретации имени известного математика среднего востока Мухаммеда аль Хорезми, который написал книгу "Об индийском счете". В этой книге описано, как правильно записывать натуральные числа, используя арабские цифры, и приведено описание алгоритма действий столбиком над такими числами.

В XII веке книга "Об индийском счете" была переведена на латинский язык, тогда-то и появилось данное определение.

Взаимодействие алгоритма с человеком и машиной

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

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

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

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

Что такое алгоритм?

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

Какой из способов будет использован, зависит от нескольких факторов: от сложности задачи, от того, насколько нужно детализировать процесс решения задачи и т. д.

Графический вариант построения алгоритма

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

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

Также блок-схемы изображаются в соответствии с ГОСТ-19701-90 и ГОСТ-19.003-80.
Графические фигуры, применяемые в алгоритме, делятся на:

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

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

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

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

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

Как правильно построить алгоритм?

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

Общая методика по записи включает в себя следующие пункты:

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

У каждого алгоритма должны быть четко обозначены начало и конец.

У алгоритмов должны быть четко и ясно описаны все данные, как входные, так и выходные.

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

• Имя схемы.
• Данные.
• Начало.
• Команды.
• Конец.

Правильное построение схемы существенно облегчит вычисление алгоритмов.

Геометрические фигуры, отвечающие за разные действия в алгоритме

Горизонтально расположенный овал - начало и конец (знак завершения).

Горизонтально расположенный прямоугольник — вычисление или другие действия (знак процесса).

Горизонтально расположенный параллелограмм — ввод или вывод (знак данных).

Горизонтально расположенный ромб — проверка условия (знак решения).

Вытянутый, горизонтально расположенный шестиугольник — модификация (знак подготовки).

Модели алгоритмов представлены ниже на рисунке.

Формульно-словестный вариант построения алгоритма.

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

Понятие алгоритма в информатике

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

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

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

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

Вывод

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

ПОНЯТИЕ АЛГОРИТМА. СВОЙСТВА АЛГОРИТМА. ВИДЫ АЛГОРИТМОВ. СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ

Алгоритмом называется точное и понятное предписаниe исполнителю совершить последовательность действий, направленных на решение поставленной задачи. Слово «алгоритм» происходит от имени математика Аль Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмом понимали только правила выполнения четырех арифметических действий над числами. В дальнейшем это понятие стали использовать вообще для обозначения последовательности действий, приводящих к решению любой поставленной задачи. Говоря об алгоритме вычислительного процесса, необходимо понимать, что объектами, к которым применялся алгоритм, являются данные. Алгоритм решения вычислительной задачи представляет собой совокупность правил преобразования исходных данных в результатные.

Основными свойствами алгоритма являются:

1. детерминированность (определенность). Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;
2. результативность. Указывает на наличие таких исходных данных, для которых реализуемый по заданному алгоритму вычислительный процесс должен через конечное число шагов остановиться и выдать искомый результат;
3. массовость. Это свойство предполагает, что алгоритм должен быть пригоден для решения всех задач данного типа;
4. дискретность. Означает расчлененность определяемого алгоритмом вычислительного процесса на отдельные этапы, возможность выполнения которых исполнителем (компьютером) не вызывает сомнений.

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

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

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

При всем многообразии алгоритмов решения задач в них можно выделить три основных вида вычислительных процессов:

• линейный;
• ветвящийся;
• циклический.

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

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

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

ПОНЯТИЕ АЛГОРИТМА. СВОЙСТВА АЛГОРИТМА. ВИДЫ АЛГОРИТМОВ. СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ

Алгоритмом называется точное и понятное предписаниe исполнителю совершить последовательность действий, направленных на решение поставленной задачи. Слово «алгоритм» происходит от имени математика Аль Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмом понимали только правила выполнения четырех арифметических действий над числами. В дальнейшем это понятие стали использовать вообще для обозначения последовательности действий, приводящих к решению любой поставленной задачи. Говоря об алгоритме вычислительного процесса, необходимо понимать, что объектами, к которым применялся алгоритм, являются данные. Алгоритм решения вычислительной задачи представляет собой совокупность правил преобразования исходных данных в результатные.

Основными свойствами алгоритма являются:

1. детерминированность (определенность). Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;
2. результативность. Указывает на наличие таких исходных данных, для которых реализуемый по заданному алгоритму вычислительный процесс должен через конечное число шагов остановиться и выдать искомый результат;
3. массовость. Это свойство предполагает, что алгоритм должен быть пригоден для решения всех задач данного типа;
4. дискретность. Означает расчлененность определяемого алгоритмом вычислительного процесса на отдельные этапы, возможность выполнения которых исполнителем (компьютером) не вызывает сомнений.

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

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

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

При всем многообразии алгоритмов решения задач в них можно выделить три основных вида вычислительных процессов:

• линейный;
• ветвящийся;
• циклический.

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

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

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

Для составления программы, предназначенной для решения на ЭВМ какой-либо задачи, требуется составление алгоритма ее решения.

Алгоритм - это точное предписание, которое определяет процесс, ведущий от исходных данных к требуемому конечному результату. Алгоритмами, например, являются правила сложения, умножения, решения алгебраических уравнений, умножения матриц и т.п. Слово алгоритм происходит отalgoritmi , являющегося латинской транслитерацией арабского имени хорезмийского математика IX века аль-Хорезми . Благодаря латинскому переводу трактатааль-Хорезми европейцы в XII веке познакомились с позиционной системой счисления, и в средневековой Европе алгоритмом называлась десятичная позиционная система счисления и правила счета в ней.

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

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

результативностью;

определенностью;

массовостью.

Результативность означает возможность получения результата после выполнения конечного количества операций.

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

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

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

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

правило начала;

правило непосредственной переработки информации (описание последовательности действий);

правило окончания;

правило извлечения результатов.

Алгоритм всегда рассчитан на конкретного исполнителя. В нашем случае таким исполнителем является ЭВМ. Для обеспечения возможности реализации на ЭВМ алгоритм должен быть описан на языке, понятном компьютеру, то есть на языке программирования.

Таким образом, можно дать следующее определение программы.

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

Способы описания алгоритмов

К основным способам описания алгоритмов можно отнести следующие:

словесно-формульный;

структурный или блок-схемный;

с помощью граф-схем;

с помощью сетей Петри.

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

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

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

у = 2а – (х+6).

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

1. Ввести значения а их.

2. Сложить х и 6.

3. Умножить a на 2.

4. Вычесть из 2а сумму (х+6).

5. Вывести у как результат вычисления выражения.

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

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

Оформление программ должно соответствовать определенным требованиям. В настоящее время действует единая система программной документации (ЕСПД), которая устанавливает правила разработки, оформления программ и программной документации. В ЕСПД определены и правила оформления блок-схем алгоритмов (ГОСТ 10.002-80 ЕСПД, ГОСТ 10.003-80 ЕСПД).

Операции обработки данных и носители информации изображаются на схеме соответствующими блоками. Большая часть блоков по построению условно вписана в прямоугольник со сторонамиа и b. Минимальное значениеа = 10 мм , увеличениеа производится на число, кратное5 мм . Размерb=1,5a . Для от дельных блоков допускается соотношение междуа и b, равное 1:2. В пределах одной схемы рекомендуется изображать блоки одинаковых размеров. Все блоки нумеруются. Виды и назначение основных блоков приведены в табл. 1.

Таблица 1. Условные обозначения блоков схем алгоритмов