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

Тема: Алгоритмизация

Происхождение слова «алгоритм» связывают с именем ученого Мухаммеда ал-Хорезми, который описал десятичную систему счисления (придуманную в Индии) и предложил правила выполнения арифметических действий с десятичными числами.

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

Таким образом, мы видим, что латинизированное имя среднеазиатского учёного было вынесено в заглавие книги, и сегодня считается, что слово «алгоритм» попало в европейские языки именно благодаря этому сочинению. Однако вопрос о его смысле длительное время вызывал ожесточённые споры. На протяжении многих веков происхождению слова давались самые разные объяснения.

Первоначально сочинения по искусству счета назывались алгоритмами. Постепенно значение слова расширялось. Ученые начинали применять его не только к сугубо вычислительным, но и к другим математическим процедурам. В 1684 году Готфрид Лейбниц в сочинении Nova Methodvs pro maximis et minimis, itemque tangentibus… впервые использовал слово «алгоритм» (Algorithmo) в еще более широком смысле: как систематический способ решения проблем дифференциального исчисления. Алгоритмы становились предметом все более пристального внимания ученых, и постепенно это понятие заняло одно из центральных мест в современной математике.

Одновременно с развитием понятия алгоритма постепенно происходила и его экспансия из чистой математики в другие сферы. И начало ей положило появление компьютеров, благодаря которому слово «алгоритм» вошло в 1985 г. во все школьные учебники информатики и обрело новую жизнь. Слово «алгоритм» в наши дни известно, вероятно, каждому. Оно уверенно шагнуло даже в разговорную речь, и сегодня мы нередко встречаем в газетах и слышим в выступлениях политиков выражения вроде «алгоритм поведения», «алгоритм успеха» или даже «алгоритм предательства». Академик Н. Н. Моисеев назвал свою книгу «Алгоритмы развития», а известный врач Н. М. Амосов — «Алгоритм здоровья» и «Алгоритмы разума». А это означает, что слово живет, обогащаясь все новыми значениями и смысловыми оттенками.

Алгоритм– это точное описание порядка действий, которые должен выполнить исполнитель для решения задачи за конечное время.

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

Человек как исполнитель часто действует неформально, по своему понимая команды, несмотря на это, ему тоже часто приходится действовать по тому или иному алгоритму.

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

Каждый формальный исполнитель обладает собственной системой команд. В алгоритмах для такого исполнителя нельзя использовать команды, которых нет в его системе команд.

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

Алгоритм решения задачи (описание метода решения задачи), должен быть составлен в соответствии со следующими правилами:

- выделяются величины, являющиеся исходными для задачи;

- процесс решения задачи разбивается на этапы, которые будут выполнены однозначно без всяких пояснений;

- указывается порядок выполнения этапов;

- указывается признак окончания процесса решения задачи;

- указывается, что является результатом решения задачи.

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

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

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

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

· Понятность – алгоритм содержит только команды, входящие в систему команд исполнителя для которого он предназначен.

· Конечность (результативность)алгоритма – это свойство алгоритма, состоящее в том, что он всегда приводит к результату через конечное число шагов (результатом может быть сообщение о том, что задача не имеет решений).

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

· Корректность – для допустимых исходных данных алгоритм должен приводить к правильному результату.