Введение
Мой реферат содержит информацию об определении алгоритма, а также об истории его возникновения, различные свойства и виды алгоритмов и способы их записи.
Определение алгоритма
Алгоритмом называется точное и понятное предписаниe исполнителю совершить последовательность действий, направленных на решение поставленной задачи. Слово «алгоритм» происходит от имени математика Аль Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмом понимали только правила выполнения четырех арифметических действий над числами. В дальнейшем это понятие стали использовать вообще для обозначения последовательности действий, приводящих к решению любой поставленной задачи. Говоря об алгоритме вычислительного процесса, необходимо понимать, что объектами, к которым применялся алгоритм, являются данные. Алгоритм решения вычислительной задачи представляет собой совокупность правил преобразования исходных данных в результатные.
Некоторые из математических алгоритмов известны уже несколько тысячелетий. Считается, что самым древним нетривиальным алгоритмом является способ нахождения наибольшего общего делителя двух целых чисел. Он был открыт около 2300 лет тому назад и известен как алгоритм Евклида, поскольку содержится в первых предложениях седьмой книги «Начал» этого древнего математика. (Правда есть предположение, что алгоритм Евклида лишь интерпретация алгоритма, предложенного Эвдоксом за 75 лет до этого.)
История возникновения понятия алгоритм
Поговорим и о происхождении слова «алгоритм». Известно, что в раннем Средневековье слово algorism использовали для обозначения способа арифметических вычислений на бумаге без применения счетных досок (абаков). Именно в таком значении оно вошло в некоторые европейские языки. Например, в авторитетном словаре английского языка «Webster’s New World Dictionary», изданном в 1957 году., оно снабжено пометкой «устаревшее» и объясняется как выполнение арифметических действий с помощью арабских цифр. Несмотря на то что известно, когда появился термин «алгоритм», лингвисты по-разному пытались толковать его происхождение. Одни выводили algorism из греческих «альгирос» - больной и «арифмом» - число. Правда, не понятно, почему числа «больные»? Другие склонялись к еще более экстравагантному объяснению, связывая слово с неким мифическим древним испанским правителем King Algor of Castil. Свой вариант предлагает и Энциклопедический словарь Брокгауза и Эфрона (1890 г.) В нем «алгорифм» (кстати, до революции использовалось и написание «алгори?м», через «фиту») производится от арабского слова «Аль-Горетм», т.е. корень.
Но истину удалось установить не лингвистам, а историкам математики. Они доказали, что слово происходит от имени великого среднеазиатского ученого, автора популярнейшего на протяжении многих веков учебника по математике аль – Хорезми, жившего в первой половине IX века. Он написал ряд трактатов по арифметике и алгебре, в том числе книгу "Арифметика индусскими цифрами" – о счете с помощью десяти цифр и правилах арифметических действий с числами. В латинской транскрипции его имя записывается как Abu’Abd Allah Muhammad ibn Musa al-Khwarismi и означает «Мухаммад, сын Мусы, отец Абдуллы, родом из Хорезма». Хорезм – это историческая область на территории современного Узбекистана, центром которой является город Хива.
Свойства алгоритмов
Описание основных свойств помогает углубить само понятие алгоритма. Итак, алгоритм должен обладать следующими свойствами:
Детерминированность (определенность, точность, однозначность)
Это свойство заключается в том, что при задании одних и тех же исходных данных несколько раз алгоритм будет выполняться абсолютно одинаково и всегда будет получен один и тот же результат. Свойство детерминированности проявляется также и в том, что на каждом шаге выполнения алгоритма всегда точно известно, что делать дальше, а каждое действие однозначно понятно исполнителю и не может быть истолковано неопределенно. Благодаря этому свойству выполнение алгоритма носит механический характер.
Массовость
Выражается в том, что с помощью алгоритма можно решать не одну конкретную задачу, а любую задачу из некоторого класса однотипных задач при всех допустимых значениях исходных данных.
Результативность (направленность)
Означает, что выполнение алгоритма обязательно должно привести к решению поставленной задачи, либо к сообщению о том, что при заданных исходных величинах задачу решить невозможно. Алгоритмический процесс не может обрываться безрезультатно.
Дискретность
Означает, что алгоритм состоит из последовательности отдельных шагов - элементарных действий, выполнение которых не представляет сложности. Именно благодаря этому свойству алгоритм может быть реализован на ЭВМ.
Конечность (финитность)
Заключается в том, что последовательность элементарных действий алгоритма не может быть бесконечной, неограниченной, хотя может быть очень большой (если требуется, например, большая точность вычислений).
Корректность
Означает, что если алгоритм создан для решения определенной задачи, то для всех исходных данных он должен всегда давать правильный результат и ни для каких исходных данных не будет получен неправильный результат. Если хотя бы один из полученных результатов противоречит хотя бы одному из ранее установленных и получивших признание фактов, алгоритм нельзя признать корректным
Рассмотрим пример алгоритма, на примере, кипячения воды на газовой плите.
Из определения алгоритма возникает вопрос, а все ли алгоритмы правильные? Любой ли алгоритм можно выполнить?
Вам представлено два алгоритма, как можно вскипятить чайник, один является верным алгоритмом, второй соответственно неверным!
1.Налить воду в чайник
2.Открыть кран газовой горелки
3.Поставить чайник на плиту
4.Ждать, пока вода не закипит
5.Поднести спичку к горелке
6.Зажечь спичку
7.Выключить газ
1.Налить воду в чайник
2.Поставить чайник на плиту
3.Открыть кран газовой горелки
4.Зажечь спичку
5.Поднести спичку к горелке
6.Ждать, пока вода не закипит
7.Выключить газ
Каждый из вас ставил кипятить чайник с водой, и знает алгоритм. Конечно же второй вариант является верным, а первый неверным алгоритмом.
Виды алгоритмов
Различают следующие виды алгоритмов:
4.1 Линейный.
Список команд (указаний), выполняемых последовательно друг за другом;
4.2 Разветвляющийся.
Алгоритм, содержащий хотя бы одну проверку условия, в результате которой обеспечивается переход на один из возможных вариантов решения;
4.3 Циклический.
Алгоритм, предусматривающий многократное повторение одной и той же последовательности действий. Количество повторений обусловливается исходными данными или условием задачи.
Рис. 1. Линейный алгоритм
Рис. 2. Разветвленный алгоритм.
Рис. 3. Циклический.