История алгоритма

Министерство Образования  Российской Федерации 
Дальневосточный Федеральный Университет (ДВФУ) 
Школа экономики и менеджмента

Реферат: 
«История алгоритма» 
Дисциплина: Программирование.

Выполнила: ст. гр. Б1104

Иванова Ирина Ивановна.

Проверил: Тихоновская Галина Ивановна 
– преподаватель, доцент.                                                                                          

Владивосток,  2013 г. 

Оглавление

Введение 3

1. История 4

2. Понятие  алгоритма. Сущность алгоритмизации 8

3. Свойства  алгоритма 9

5. Типовые  структуры алгоритмов 13

5.1. Линейная  структура 13

5.2. Разветвляющаяся  структура 13

5.3. Циклическая  структура 13

Заключение 15

Литература 16

Введение

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

1. История

Древнегреческий ученый Эратосфен (II в. до н. э.) предложил способ получения  простых чисел (т.н. "решето Эратосфена"). В IX в. узбекский математик Мухаммад Ал-Хорезми разработал правила четырех арифметических действий над числами. В Европе эти правила стали называть алгоритмами (от латинской формы написания имени автора - Alchorismi илиAlgorithmi). Переводы арифметического трактата Ал-Хорезми с арабского содержали описание индийской позиционной системы счисления и искусства счета в этой системе (например, алгоритм сложения "столбиком"). Таким образом, сначала понятие "алгоритм" обозначало десятичную позиционную арифметику  и процедуры цифровых вычислений.

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

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

А. Сравнить первое и второе числа. Если они равны, перейти к п. Г.  Если нет, то перейти к п.Б.

Б. Если первое число меньше второго, то переставить их. Перейти к п.В.

В. Вычесть из первого числа второе и рассмотреть полученную разность как новое первое число. Перейти к п.А. 
Г. Считать первое число результатом задачи.

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

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

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

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

В начале ХХ в. алгоритм стал объектом математического изучения.

Общее понятие алгоритма  как эффективной вычислительной процедуры и примеры использования  такого понятия встречаются в  работах француза Э.Бореля (1912 г.) и  немца Г.Вейля (1921 г.). Оба они пришли к понятию вычислимой функции (термин "fonction calculable").

Одно из первых формальных определений алгоритма дал английский математик А.Тьюринг [1, 2], который в 1936 году описал схему гипотетической (абстрактной) машины и назвал алгоритмом то, что умеет делать такая машина. А если что-то не может быть сделано машиной Тьюринга, то это уже не алгоритм. Таким образом, Тьюринг формализовал правила выполнения действий при помощи описания работы некоторой конструкции. Вычислительные машины - это тоже конструкции для выполнения алгоритмов, но это реальные устройства, тогда как машина Тьюринга - это математическая модель, она является абстракцией, которая никогда не была реализована, да и вообще не может быть реализована. Польза от машины Тьюринга в том, что, говоря о воображаемой конструкции, можно доказывать существование или несуществование алгоритмов решения различных задач.

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

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

В 1954 г. советский математик А.А. Марков[1] предложил  свою алгоритмическую схему преобразования слов, назвав ее нормальным алгоритмом. Он ввел также понятие нормализации как перехода от разных способов описания алгоритмов к эквивалентным нормальным алгоритмам. Основная гипотеза теории алгоритмов в форме Маркова звучит так: "Всякий алгоритм нормализуем". Как и машина Тьюринга, алгоритмическая схема Маркова в общем случае не может быть физически реализована, т.к. она, например, допускает неограниченно большую длину слов. А вот формулировка алгоритма по Маркову: "Алгоритм - это точное предписание, которое задает вычислительный процесс, начинающийся с произвольного (но выбранного из фиксированной для данного алгоритма совокупности) исходного данного и направленный на получение полностью определяемого этим исходным данным результата" [2].

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

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

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

В настоящее время понятие "алгоритм" вышло за пределы  математики. Его стали применять  в самых различных областях, понимая  под ним точно сформулированные инструкции, назначение которых - достижение необходимого результата. 
Формирование научного понятия алгоритма, ставшее важной проблемой, не закончено и в настоящее время. Теория алгоритмов, как любая другая наука, находится в постоянном развитии. Согласно утверждению авторов [2], современная теория алгоритмов может быть разделена на две части.

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

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

2. Понятие алгоритма. Сущность алгоритмизации

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

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

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

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

3. Свойства алгоритма

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

• Детерминированность (определенность, точность, однозначность). Это свойство заключается в том, что при задании одних и тех же исходных данных несколько раз алгоритм будет выполняться абсолютно одинаково и всегда будет получен один и тот же результат. Свойство детерминированности проявляется также и в том, что на каждом шаге выполнения алгоритма всегда точно известно, что делать дальше, а каждое действие однозначно понятно исполнителю и не может быть истолковано неопределенно. Благодаря этому свойству выполнение алгоритма носит механический характер.
• Массовость - выражается в том, что с помощью алгоритма можно решать не одну конкретную задачу, а любую задачу из некоторого класса однотипных задач при всех допустимых значениях исходных данных.
• Результативность  (направленность) - означает, что выполнение алгоритма обязательно должно привести к решению поставленной задачи, либо к сообщению о том, что при заданных исходных величинах задачу решить невозможно. Алгоритмический процесс не может обрываться безрезультатно.
• Дискретность - означает, что алгоритм состоит из последовательности отдельных шагов - элементарных действий, выполнение которых не представляет сложности. Именно благодаря этому свойству алгоритм может быть реализован на ЭВМ.
• Конечность (финитность)- заключается в том, что последовательность элементарных действий алгоритма не может быть бесконечной, неограниченной, хотя может быть очень большой (если требуется, например, большая точность вычислений).
• Корректность - означает, что если алгоритм создан для решения определенной задачи, то для всех исходных данных он должен всегда давать правильный результат и ни для каких исходных данных не будет получен неправильный результат. Если хотя бы один из полученных результатов противоречит хотя бы одному из ранее установленных и получивших признание фактов, алгоритм нельзя признать корректным.

Если разработанная Вами последовательность действий не обладает хотя бы одним из перечисленных выше свойств, то она не может считаться  алгоритмом [3].

4. Правила оформления схем алгоритмов

Условные обозначения  и правила выполнения схем алгоритмов регламентируются требованиями Единой системы программной документации в соответствии с ГОСТ 19.701-90 [4].

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

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

Рис. 1.

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

Рис. 2.

Как правило, каждый символ имеет один вход и один выход. Исключение составляют символы:

• "терминатор" (у операции "начало" нет входа, у операции "конец" нет выхода),
• "решение" (один вход и несколько выходов),
• "подготовка".

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

Рис. 3

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

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

5. Типовые структуры алгоритмов

Из многообразия всевозможных алгоритмов выделяются три основных типовых  структуры:

• линейная,
• разветвляющаяся,
• циклическая.

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

5.1. Линейная структура

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

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

5.2. Разветвляющаяся структура

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

 
5.3. Циклическая структура

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

• циклы с известным заранее числом повторений (классические);
• циклы с неизвестным числом повторений (итерационные).

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

• начальное значение параметра (обозначим его    );
• конечное значение параметра (обозначим его    );
• шаг изменения параметра (обозначим его   ).

Зная эти 3 величины, можно вычислить  количество повторений цикла по формуле:          

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

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

Итерационный цикл отличается другой организацией.

Заключение

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

Литература

1. Любимский Э.З., Мартынюк В.В., Трифонов Н.П. Программирование. - М.: Наука, 1980.- 608
2. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. - М.: Наука, 1987.- 288 с. Вирт Н. Алгоритмы + структуры данных = программы. - М.: Мир, 1985.-385 с.
3. Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4
4. ГОСТ 19.701-90. Единая система программной документации. Схемы алгоритмов и программ. Условные обозначения и правила выполнения. - М.: Изд-во стандартов, 1991.- 26 с.
5. Интернет - ресурсы: http://comp5.ru/Teoria/algoritm/Alglit.php
6. Интернет - ресурсы: http://pascal.proweb.kz/