Раздел 1. Формальная теория вычислимости

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

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

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

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

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

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

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

Появление понятия «алгоритм» связывают с именем узбекского математика 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) и т.д. «Записи» греки делали на натянутом папирусе, числа не вычеркивали, а выкалывали. В конце вычислений папирус напоминал решето, и потому способ получил название «решето Эратосфена.

Эратосфен

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

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

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

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

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

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

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

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

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

Еще одно свойство алгоритма характеризуется термином «понятность». В соответствие с ним алгоритм должен состоять из команд, однозначно понимаемых (исполняемых) исполнителем. Иными словами, алгоритм не должен включать команды, которые не входят в систему команд исполнителя.

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

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

Идея определения алгоритма как последовательности предписаний из системы команд некоторого исполнителя, восходящая, пожалуй, к работам А.Тьюринга и Э.Поста, оказалась плодотворной не только в рамках формальной теории вычислимости¹, но и в рамках теории и методики обучения информатике. Так, в учебниках «Алгоритмика» [], [] для средней школы можно найти множество Исполнителей – и простых, и сложных. Например, Исполнитель под названием Удвоитель описывается следующим образом:

«Удвоитель – это воображаемое устройство с экраном и двумя кнопками. На экране написано число. Когда мы включаем Удвоитель, это число равно 0. На кнопках написано «прибавь 1» и «умножь на 2». При нажатии на первую клавишу число, изображенное на экране, увеличивается на 1. При нажатии на вторую клавишу число на экране удваивается» [] (см. рис. 1).

Рис. 1. Удвоитель

Несмотря на простоту Удвоителя, его можно использовать для знакомства школьников с двоичной системой счисления, с понятием эффективности программы. Получить на экране заданное число – задача простая. Но сделать это за наименьше число команд, да еще доказать, что это число наименьшее – задача сложнее.

Описание в «Алгоритмике» Директора Строительства выглядит следующим образом:

«1) Вы Директор Строительства. В вашем распоряжении несколько строительных бригад, которым вы должны давать работу.

2) Всякий кубик (блок) независимо от своего вида и размера может быть установлен одной бригадой за один день. Две бригады не могут устанавливать один и тот же блок.

3) Строительство блока может начаться только после того, как установлены все блоки, на которые он опирается» [ ].

Пример «строительного объекта» приведен на рис. 2.

	8
7
4		5
		6
3
1		2	11	12
			9	10

Рис. 2. Строительный объект для Директора Строительства

Рассматривая каждую бригаду как отдельного исполнителя, у которого всего одна команда установи <номер>, Директор Строительства может написать следующую программу строительства объекта (на рис.2) с помощью двух бригад:

	1 бригада	2 бригада
1 день	установи (1)	установи (2)
2 день	установи (3)	установи (9)
3 день	установи (4)	установи (6)
4 день	установи (5)	установи (10)
5 день	установи (7)	установи (11)
6 день	установи (8)	установи (12)

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

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

Лекция № 2. Машина Поста и нормальные алгорифмы Маркова

1. Машина Поста.

2. Нормальные алгорифмы Маркова.