Интуитивное определение алгоритма. Примеры алгоритмов

Лекция № 1. Интуитивное представление об алгоритме

Лекция № 11. Контекстно-свободные языки

[1] Степанов А.Н. Информатика: Учебник для вузов. 4-е изд. – СПб.: Питер, 2005. – С. 41.

[2] Этой теории будут посвящены следующие лекции.

[3] В теории нормальных алгорифмов пустое слово обозначается символом l.

[4] b – подслово слова a.

[5] В ряде источников, например в [], стандартным считается то положение, при котором головка «обозревает» ячейку, в которой записана первая буква слова, т.е. крайне левую ячейку.

[6] Здесь и далее в соответствии с тезисами теории алгоритмов под вычислимыми функциями подразумеваются частично рекурсивные функции. Соответственно под всюду определенными вычислимыми функциями – общерекурсивные функции.

[7] Эти программы могут, например, располагаться в порядке возрастания их длины.

[8] Если в классе А отсутствует нигде не определенная функция, то можно взять произвольную функцию из класса А, а нигде не определенную функцию из его дополнения.

[9] Не тривиальным в том плане, что класс всех вычислимых функций разбивается на два непустых подкласса функций, обладающих и не обладающих этим свойством.

1. Интуитивное определение алгоритма. Примеры алгоритмов

2. Способы записи алгоритмов

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

4. Исполнители и алгоритмы в школьной информатике

«Последовательность действий, которую необходимо выполнить для достижения цели, принято называть алгоритмом», – таково интуитивное понимание термина «алгоритм» на уровне его бытового использования.

Появление понятия «алгоритм» связывают с именем узбекского математика IX века Мухаммеда аль-Хорезми. Латинский перевод (XII век) его сочинения об арифметики начинался словами «Dixit Algorizmi» и, поскольку оно было очень популярно в Европе, то имя автора вскоре стало нарицательным. Европейские математики в средние века алгоритмом называли арифметику, основанную на позиционной системе счисления.

Мухаммед аль-Хорезми

В современных школьных и вузовских учебниках по информатике термин «алгоритм» интерпретируется различным образом.

Под алгоритмом понимается строгая, конечная система правил, инструкций для исполнителя, определяющая некоторую последовательность действий и после конечного числа шагов приводящая к достижению поставленной цели.

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

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

«Алгоритмы– это способ фиксации и передачи знаний, накопленных человечеством, это богатство культуры, науки и техники»[1].

Из глубины веков дошел до нас алгоритм Евклида нахождения наибольшего общего делителя. Вот так выглядел приведенный в его знаменитых Началах пример нахождения НОД чисел 7200 и 3132: 7200=2´3132+936 3132=3´936+324 936=2´324+288 324=1´288+36 288=8 ´36.

Евклид

За несколько веков до нашей эры греческий математик Эрастосфен предложил способ поиска простых чисел. Натуральные числа записывались от 1 до определенного числа. После чего из этого ряда вычеркивалась 1, затем все числа кратные 2 (за исключением 2); затем – кратные 3 (за исключением 3), затем все числа кратные 5 (за исключением 5) и т.д. «Записи» греки делали на натянутом папирусе, числа не вычеркивали, а выкалывали. В конце вычислений папирус напоминал решето, и потому способ получил название «решето Эратосфена.

Эратосфен

С тех пор было разработано множество различных алгоритмов, которые записываются разнообразными способами.