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

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

 

 

 

 

 

 

 

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

 

 

 

 

Выполнила: ст. гр. Б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. Свойства алгоритма

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

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