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

Оглавление

 

Введение

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

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

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

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

Понятие

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Список литературы

Введение

 

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

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

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

 

 

 

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

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

 

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

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

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

 

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

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

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

 

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

Понятие

 

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

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

 

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

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

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

 

Рисунок 1

 

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

 

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

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

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

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

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