Лекции по теории алгоритмов. Лекция Интуитивное представление об алгоритме Интуитивное определение алгоритма. Примеры алгоритмов
 Скачать 2.84 Mb.
|
|
Раздел 1. ФОРМАЛЬНАЯ ТЕОРИЯ ВЫЧИСЛИМОСТИ Лекция № 1. Интуитивное представление об алгоритме 1. Интуитивное определение алгоритма. Примеры алгоритмов 2. Способы записи алгоритмов 3. Свойства алгоритмов 4. Исполнители и алгоритмы в школьной информатике 1. Интуитивное определение алгоритма. Примеры алгоритмов «Последовательность действий, которую необходимо выполнить для достижения цели, принято называть алгоритмом», – таково интуитивное понимание термина «алгоритм» на уровне его бытового использования.
В современных школьных и вузовских учебниках по информатике термин «алгоритм» интерпретируется различным образом.
При таком широком подходе к интерпретации термина «алгоритм», алгоритмами называют: кулинарные рецепты, нотную запись мелодии, чертеж детали и т.д. В этом контексте обоснованным выглядит и утверждение:
С тех пор было разработано множество различных алгоритмов, которые записываются разнообразными способами. 2. Способы записи алгоритмов В учебниках информатики выделяют разные способы записи алгоритмов. В частности, алгоритм можно записать на обычном (естественном языке) – в этом случае говорят о словесном способе задания алгоритма. Нотную запись музыкальной мелодии допустимо рассматривать в качестве способа задания алгоритма ее исполнения (на языке музыки). На языке математики с помощью формул записываются алгоритмы вычисления различных математических величин и т. д. Выделяя графические способы задания алгоритма, упоминают о чертежах, регламентирующих процесс строительства зданий и производства деталей и т.п. При таком понимании под графический способ задания алгоритма попадает и маршрут геологической партии, нанесенный на карту, и блок-схема алгоритма. В качестве особого способа задания алгоритмов рассматриваются компьютерные программы, кодирующие алгоритмы на формальных языках программирования. При всех различиях в записи алгоритмов, при всем разнообразии исполнителей и задач, решаемых ими, алгоритм не отождествляется с любой последовательностью действий того или иного исполнителя. Даже на интуитивном уровне подразумевается, что последовательность действий, именуемая алгоритмом, должна обладать вполне определенными свойствами, позволяющими отличать алгоритм, от «не алгоритма». 3. Свойства алгоритмов В общем случае полагается, что алгоритм должен обладать важнейшим качеством (свойством) – исполнение алгоритма в одних и тех же условиях различными исполнителями (людьми или устройствами) должно приводить к одинаковым результатам. Это свойство в разных источниках называется по-разному: одназначностью, определенностью. Тот факт, что алгоритм – суть набора отдельных команд, допускающих пошаговое исполнение, характеризуется таким свойством, как дискретность. Принципиальная достижимость результата, заключающаяся в том, что при точном исполнении команд (предписаний) алгоритма процесс должен прекратится за конечное число шагов, приводя к заданному результату, фиксируется таким свойством алгоритма, как результативность. Еще одно свойство алгоритма характеризуется термином «понятность». В соответствие с ним алгоритм должен состоять из команд, однозначно понимаемых (исполняемых) исполнителем. Иными словами, алгоритм не должен включать команды, которые не входят в систему команд исполнителя. Такого рода требования предопределяют возможность формального исполнения алгоритма, не предполагающего от исполнителя осмысленности выполняемых действий, а также действий, не предусмотренных алгоритмом. 4. Исполнители и алгоритмы в школьной информатике Идея определения алгоритма как последовательности предписаний из системы команд некоторого исполнителя, восходящая, пожалуй, к работам А.Тьюринга и Э.Поста, оказалась плодотворной не только в рамках формальной теории вычислимости1, но и в рамках теории и методики обучения информатике. Так, в учебниках «Алгоритмика» [], [] для средней школы можно найти множество Исполнителей – и простых, и сложных. Например, Исполнитель под названием Удвоитель описывается следующим образом: «Удвоитель – это воображаемое устройство с экраном и двумя кнопками. На экране написано число. Когда мы включаем Удвоитель, это число равно 0. На кнопках написано «прибавь 1» и «умножь на 2». При нажатии на первую клавишу число, изображенное на экране, увеличивается на 1. При нажатии на вторую клавишу число на экране удваивается» [] (см. рис. 1).  Рис. 1. Удвоитель Несмотря на простоту Удвоителя, его можно использовать для знакомства школьников с двоичной системой счисления, с понятием эффективности программы. Получить на экране заданное число – задача простая. Но сделать это за наименьше число команд, да еще доказать, что это число наименьшее – задача сложнее. Описание в «Алгоритмике» Директора Строительства выглядит следующим образом: «1) Вы Директор Строительства. В вашем распоряжении несколько строительных бригад, которым вы должны давать работу. 2) Всякий кубик (блок) независимо от своего вида и размера может быть установлен одной бригадой за один день. Две бригады не могут устанавливать один и тот же блок. 3) Строительство блока может начаться только после того, как установлены все блоки, на которые он опирается» [ ]. Пример «строительного объекта» приведен на рис. 2.
Рис. 2. Строительный объект для Директора Строительства Рассматривая каждую бригаду как отдельного исполнителя, у которого всего одна команда установи <номер>, Директор Строительства может написать следующую программу строительства объекта (на рис.2) с помощью двух бригад:
Как представляется, решение подобных задач – неплохая пропедевтика параллельного программирования. Впрочем, Исполнителей в школьной информатике много, что свидетельствует об их высоком дидактическом потенциале. Но мы ограничимся только приведенными примерами, поскольку далее в центре нашего внимания будут более сложные математические объекты. Лекция № 2. Машина Поста и нормальные алгорифмы Маркова 1. Машина Поста. 2. Нормальные алгорифмы Маркова. 1. Машина Поста
Имеется воображаемый Исполнитель – каретка, передвигающаяся вдоль бесконечной ленты разбитой на секции. Секция может быть пустой, или же в ней может находиться метка (рис. 3).
– каретка метка метка Рис. 3. Машина Поста По командам каретка может передвигаться на одну секцию влево или вправо, ставить или стирать метку в секции, напротив которой она находится. Работает машина Поста по программе, представляющей собой последовательность пронумерованных команд. Их всего 6. Записываются эти команды так.
Для выполнения любой программы необходимо задать так называемое начальное состояние ленты, обязательно указав положение каретки. Пример 2.1.1. Пусть начальное состояние имеет вид:
Пусть также дана программа машины Поста:
В результате выполнения этой программы при заданном начальном состоянии лента примет вид:
Заметим, что начальное состояние можно рассматривать как запись на ленте двух чисел 4 и 3 в унарной системе счисления. Соответственно, результат программы представляет собой запись в унарной системе счисления числа 7. В этом контексте правомерной выглядит гипотеза о том, что приведенная программа – программа сложения натуральных чисел, записанных в унарной системе счисления. Как и всякая гипотеза, она требует проверки. Относительно любых программ машины Поста полагается, что: 1) команды в программе нумеруются с 1 и записываются по порядку; 2) для каждой ссылки, имеющейся в командах программы, в программе найдется номер команды равный указанной ссылке. Если в ходе выполнения программы машина доходит до выполнения невыполнимой команды (печати метки в непустой секции, стирания метки в пустой секции), то считается, что работа программы приводит к безрезультатной остановке. Результативной остановкой принято считать остановку работы программы по команде стоп. В том случае, когда работа машины не приводит к безрезультатной или результативной остановке, говорят, что процесс работы машины Поста происходит бесконечно. При этом различные программы при одном и том же начальном состоянии могут приводить к результативной остановке, безрезультатной остановке, безостановочной работе машины. Точно также, при различных исходных состояниях результат одной и той же программы может быть различным. Пример 2.1.2.
Определение 2.1.1. Функция f: Nk→ N (k=1, 2,..) называется вычислимой на машине Поста, если существует программа pмашины Поста, вычисляющая функцию f(x1, x2, … xk), то есть обладающая следующими свойствами: а) если f(x1, x2, … xk)=y, то результатом работы программы pпри заданном наборе данных <x1, x2, … xk>, будетзаписанное на ленте число y; б) если значение f(x1, x2, … xk) не определено, то применение программы pне приводит к результативной остановке. Простейшими вычислимыми по Посту функциями являются f(x)=0, f(x)=1. В то же время справедлива следующая теорема. Теорема 2.1.1. Существует числовая всюду определенная функция, которая не вычислима на машине Поста. Доказательство. Количество программ машины Поста, длина которых фиксирована, конечно. Выписывая подряд (в любом порядке) все программы дины 1, затем длины 2 и т.д. можно получить последовательность p0, p1, p2, … pn, … всех программ машины Поста. Иными словами, множество программ машины Поста не более чем счетно. Определим функцию f(n): N→ Nследующим образом: f(n)=0, если применение программы pnк числу nне приводит к результативной остановке или результат не есть запись натурального числа; f(n)=k+1, если применение программы pnк числу nдает результат, являющийся записью числа k. Докажем, что так всюду определенная функция f(n) не вычислима на машине Поста. Доказательство проведем от противного. Пусть существует программа машины Поста ps, вычисляющая функцию f(n). Тогда возможно два случая. 1. Применение программы psк числу sприводит к результативной остановке и в результате на ленте оказывается запись натурального числа k. В этом случае по определению функции f(n) f(s)=k+1 и, так как k+1k, то psне вычисляет f(n) и налицо противоречие с нашим предположением. 2. Применение программы psк числу sприводит к безрезультатной остановке или результат не является записью натурального числа. В этом случае противоречие с нашим предположением очевидно, поскольку функция определена f(n) всюду. Теорема доказана. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
а)
б)
в)