История формирования понятия «алгоритм». Известнейшие алгоритмы в истории математики

Федеральное агентство по образованию Тюменский государственный университет Институт математики и компьютерных наук РЕФЕРАТ История формирования понятия «алгоритм». Известнейшие алгоритмы в истории математики Студент: Бешкильцева Д.С.

Руководитель: доцент, к.т.н.

Охотников Евгений Сергеевич Тюмень — 2015

• Введение
• 1. Происхождение слова «алгоритм»
• 1.1 Версии происхождения слова «алгоритм»
• 1.2 Основная версия
• 2. Современное понятие алгоритма
• 2.1 Понятие
• 2.2 Свойства алгоритмов
• 2.3 Виды алгоритмов
• 2.4 Требования, предъявляемые к алгоритму
• 3. Алгоритмы в математике
• 3.1 Алгоритм Евклида
• 3.2 Решето Эратосфена
• 3.3 Алгоритм при решении уравнений
• 3.3.1 Алгоритм нахождения неизвестного слагаемого
• 3.3.2 Алгоритм нахождения неизвестного уменьшаемого
• 3.3.3 Алгоритм нахождения неизвестного вычитаемого
• 3.3.4 Алгоритм нахождения неизвестного множителя
• 3.3.5 Алгоритм нахождения неизвестного делимого
• 3.3.6 Алгоритм нахождения неизвестного делителя
• 3.4 Алгоритмические действия с положительными и отрицательными числами
• 3.4.1 Алгоритм сложения двух отрицательных чисел
• 3.4.2 Алгоритм сложения чисел с разными знаками
• 3.4.3 Алгоритм умножения чисел с разными знаками
• 3.4.4 Алгоритм деления отрицательного числа на отрицательное число
• 3.4.5 Алгоритм деления чисел с разными знаками
• Заключение
• Список литературы

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

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

И откуда же произошло это фундаментальное понятие «алгоритм»? Я сделала попытку разобраться в этом, проследив образование современного понятия алгоритм, а также рассмотрела самые известные алгоритмы в математике.

1. Происхождение слова «алгоритм»

1.1 Версии происхождения слова «алгоритм»

Было множество версий происхождения слова «алгоритм». Одной из них была версия о греческом начале этого слова. Некоторые ученые выводили algorism из греческих algiros (больной) и arithmos (число). Но это объяснение не давало понять, почему числа именно «больные». Или же лингвистам казалось, что люди, имеющие несчастье заниматься вычислениями, больны? В энциклопедическом словаре Брокгауза и Ефрона можно было найти своё объяснение. В нём алгорифм (кстати, до революции использовалось написание алгори? м, через фиту) производится «от арабского слова Аль-Горетм, то есть корень». Конечно, эти объяснения убедительными трудно назвать.

Но, греческая версия происхождения этого слова была не единственной. Мифический АлГор (Algor) именовался то королём Кастилии (Rex quodam Castelliae), то индийским королём, то арабским мудрецом (philosophus Algus nomine Arabicus), то египетским божеством. Соответственно АлГорРитм — это ритм (порядок) бога Гора (АлГора).

1.2 Основная версия

Но многие ученые приходят к выводу, что понятие «алгоритм» пошло из Индии. Слово «алгоритм» произошло от имени великого среднеазиатского учёного Мухаммеда аль-Хорезми, который жил в первой половине IX века (приблизительные даты его жизни 780−850 года).

Около 825 года аль-Хорезми написал сочинение, где впервые описал придуманную в Индии позиционную десятичную систему счисления. Оригинал книги, к сожалению, не сохранился, и ее оригинально название неизвестно. Аль-Хорезми сформулировал правила вычислений в новой системе и, возможно, впервые использовал цифру 0, чтобы обозначать пропущенную позицию в записи числа (её индийское название арабы перевели как as-sifr или просто sifr, отсюда такие слова, как цифра и шифр). Примерно в тоже время индийские числа начали использовать и другие арабские учёные. В первой половине XII века книга аль-Хорезми в латинском переводе проникла в Европу.

Переводчик, имя которого до нас не дошло, дал ей название «Algoritmi de numero Indorum» («Индийское искусство счёта, сочинение аль-Хорезми»). Следовательно, мы видим, что латинизированное имя аль-Хорезми было вынесено в заглавие книги, и сейчас нет никаких сомнений, что слово «алгоритм» попало в европейские языки непосредственно благодаря данному сочинению. Однако вопрос о его смысле длительное время вызывал ожесточённые споры. На протяжении множества веков происхождению слова давали самые различные объяснения.

2. Современное понятие алгоритма

2.1 Понятие

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

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

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

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

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

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

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

Такая трактовка понятия «алгоритм» является не совсем полной и не совсем точной.

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

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

2.3 Виды алгоритмов

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

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

Механические алгоритмы, или иначе детерминированные, жесткие (например, алгоритм работы машины, двигателя и т. п.);

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

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

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

Линейный алгоритм — набор команд (указаний), выполняемых последовательно, друг за другом.

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

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

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

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

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

Рисунок 1

2.4 Требования, предъявляемые к алгоритму

Первое требование — при построении алгоритма, прежде всего, нужно задать множество объектов, с которыми будет работать алгоритм. Формализованное (т.е. закодированное) представление этих объектов носит название данных. Алгоритм начинает работать с некоторым набором данных, название которых входные, и в результате этой работы выдает данные, название которых выходные. В итоге, алгоритм преобразует входные данные в выходные. Это правило дает возможность сразу отделить алгоритмы от «методов» и «способов». Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.

Второе требование — для работы алгоритма необходима память. В ней размещаются входные данные, с которыми алгоритм начинает работать, промежуточные данные и выходные данные, которые являются результатом работы алгоритма. Память является дискретной, т. е. состоящей из отдельных ячеек. Поименованная ячейка памяти носит название переменной. В теории алгоритмов размеры памяти не ограничиваются, т. е. считается, что мы можем предоставить алгоритму любой необходимый для работы объем памяти. В школьной «теории алгоритмов» эти два правила не рассматриваются. В то же время практическая работа с алгоритмами (программирование) начинается именно с реализации этих правил. В языках программирования распределение памяти осуществляется декларативными операторами (операторами описания переменных). В языке Бейсик не все переменные описываются, обычно описываются только массивы. Но все равно при запуске программы транслятор языка анализирует все идентификаторы в тексте программы и отводит память под соответствующие переменные.

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

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

математический алгоритм число уравнение

3. Алгоритмы в математике

3.1 Алгоритм Евклида

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

Описание алгоритма нахождения НОД делением:

1. Большее число делим на меньшее

2. Если делится без остатка, то меньшее число и есть НОД (следует выйти из цикла). Если есть остаток, то большее число заменяем на остаток от деления.

3. Переходим к пункту 1.

Найти НОД для 40 и 15.

40/15 = 2 (остаток 10)

15/10 = 1 (остаток 5)

10/5 = 2 (остаток 0). Конец: НОД — это делитель. НОД (40, 15) = 5

Описание алгоритма нахождения НОД вычитанием:

1. Из большего числа вычитаем меньшее

2. Если получается 0, то значит, что числа равны друг другу и являются НОД (следует выйти из цикла)

3. Если результат вычитания не равен 0, то большее число заменяем на результат вычитания

4. Переходим к пункту 1

Пример:

Найти НОД для 40 и 15.

40 — 15 = 25

25 — 15 = 10

15 — 10 = 5

10 — 5 = 5

5 — 5 = 0 Конец: НОД — это уменьшаемое или вычитаемое. НОД (40, 15) = 5

3.2 Решето Эратосфена

Решето Эратосфена — это алгоритм нахождения простых чисел до заданного числа n. При исполнения данного алгоритма постепенно отсеиваются составные числа, кратные простым, начиная с числа 2.

Описание алгоритма:

1. Нужно выписать подряд все целые числа от двух до n (2, 3, 4, …, n)

2. Пусть переменная p изначально равна двум — первому простому числу

3. Нужно зачеркнуть в списке числа от 2p до n считая шагами по p (это будут числа кратные p: 2p, 3p, 4p, …)

4. Найти первое незачеркнутое число в списке, большее, чем p, и присвоить значению переменной p это число

5. Повторять шаги 3 и 4, пока это возможно Рисунок 2

3.3 Алгоритм при решении уравнений

3.3.1 Алгоритм нахождения неизвестного слагаемого

Для того чтобы вычислить неизвестное слагаемое, необходимо из суммы вычесть известное слагаемое

3.3.2 Алгоритм нахождения неизвестного уменьшаемого

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

3.3.3 Алгоритм нахождения неизвестного вычитаемого

Для того чтобы вычислить неизвестное вычитаемое, необходимо из уменьшаемого вычесть разность

3.3.4 Алгоритм нахождения неизвестного множителя

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

3.3.5 Алгоритм нахождения неизвестного делимого

Для того чтобы вычислить неизвестное делимое, необходимо частное умножить на делитель

3.3.6 Алгоритм нахождения неизвестного делителя

Для того чтобы вычислить неизвестный делитель, необходимо делимое разделить на частное

3.4 Алгоритмические действия с положительными и отрицательными числами

3.4.1 Алгоритм сложения двух отрицательных чисел

1. Определить, являются ли слагаемые отрицательными числами

2. Сложить модули слагаемых

3. Поставить перед полученной суммой знак «минус»

3.4.2 Алгоритм сложения чисел с разными знаками

1. Определить модуль какого из чисел больше

2. Вычесть из большего модуля меньший

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

3.4.3 Алгоритм умножения чисел с разными знаками

1. Определить, являются ли умножаемое и множитель отрицательными числами.

2. Перемножить модули этих чисел

3. Поставить перед полученным произведение знак «минус»

3.4.4 Алгоритм деления отрицательного числа на отрицательное число

1. Определить, являются ли делимое и делитель отрицательными

2. Разделить модуль делимого на модуль делителя

3.4.5 Алгоритм деления чисел с разными знаками

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

2. Разделить модуль делимого на модуль делителя

3. Поставить перед полученным числом знак «минус»

Заключение

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

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

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

1. (2013). Получено из Алгоритмы, методы, исходники — сайт по алгоритмам и методам программирования.

2. (2014). Получено из Дискретная математика: Алгоритмы — список алгоритмов.

3. В., Ш. В. (б.д.). Слово «алгоритм»: происхождение и развитие. Журнал «Потенциал».

4. И., И.В. (2008). Математическая логика и теория алгоритмов. — 2-е изд., стер. — М.: ИЦ «Академия».

5. Кнут, Д. (2006). Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс».

6. Кормен, Т.Х. (2014). Алгоритмы: вводный курс = Algorithms Unlocked. — М.: «Вильямс».

7. Томас Х. Кормен, Ч.И. (2013). Алгоритмы: построение и анализ, 3-е издание = Introduction to Algorithms, Third Edition. — М.:"Вильямс",.