Л. А. ДУБРАКОВА, В. И. ИГОШИН НАЧАЛО КУРСА «ТЕОРИЯ АЛГОРИТМОВ» В ОБУЧЕНИИ БУДУЩИХ УЧИТЕЛЕЙ МАТЕМАТИКИ И ИНФОРМАТИКИ
Курс «Теория алгоритмов» входит в общеобразовательный стандарт специальности 050201 – «математика с дополнительной специальностью информатика». Он является непосредственным продолжением курса математической логики и в значительной мере опирается на него. Культура алгоритмического мышления становится в последнее время все более значимой в жизни современного человека, чему в немалой степени способствует компьютеризация, проникающая буквально во все сферы жизни. В значительной мере эта культура формируется на уроках математики под руководством учителя математики. Фундаментальной основой для формирования алгоритмической культуры самого будущего учителя математики и информатики и призван стать курс теории алгоритмов.
Курс теории алгоритмов, как и курс математической логики, не является традиционным для студентов, т. е. не имеет ретроспективы в школьном образовании. Если раньше студенты и встречались с какими-либо алгоритмами, то это были вполне конкретные алгоритмы, решающие конкретные (математические) задачи. Курс теории алгоритмов носит принципиально иной характер. Он имеет дело не с конкретными алгоритмами, а с понятием алгоритма как таковым. Излагаемую в нем теорию можно было бы назвать общей или абстрактной теорией алгоритмов. Все это вызывает у студентов определенные трудности при изучении этого курса. И это предъявляет к преподавателю дополнительные требования при изложении начала этого курса, когда студенты только входят в круг идей, проблем и методов, изучаемых данной теорией. В этой заметке намечаются некоторые штрихи к построению начала курса теории алгоритмов, которые, как нам представляется, сделают этот процесс вхождения более мягким и эффективным.
Первым вопросом, который решает общая теория алгоритмов, является вопрос о том, как сделать интуитивное понятие алгоритма объектом изучения строгой математической теории. В 30-е годы прошлого века было намечено несколько путей решения этого вопроса, на каждом из которых было выработано свое формальное понятие алгоритма.
Слово «алгоритм» происходит от имени узбекского математика Мухаммеда бен Муса Хорезми, который в IX в. н. э. разработал правила четырех арифметических действий. Совокупность этих правил в Европе стали называть «алгоризм». Впоследствии это слово переродилось в «алгоритм» и стало собирательным названием отдельных правил определенного вида.
Под алгоритмом обычно понимают точное, общепонятное описание определенной последовательности интеллектуальных операций, необходимых и достаточных для решения любой из задач, принадлежащих к некоторому классу.
Вплоть до 30-х годов XX в. понятие алгоритма оставалось интуитивно понятным, имевшим скорее методологическое, а не математическое значение. Термин «алгоритм» употреблялся в математике лишь в связи с теми или иными конкретными алгоритмами. Утверждение о существовании алгоритма для решения задач данного типа сопровождалось фактическим его описанием. Однако, в начале XX века были сформулированы алгоритмические проблемы, положительное решение которых представлялось маловероятным. Решение таких проблем потребовало привлечения новых логических средств. Ведь одно дело доказать существование разрешающего алгоритма – это можно сделать используя интуитивное понятие алгоритма. Другое дело - доказать несуществование алгоритма – для этого нужно знать точно, что такое алгоритм.
Одним из первых понятие алгоритм формализовал Алан Тьюринг. В 1936 году он построил логическую модель так называемой машины Тьюринга.
Машину Тьюринга удобно представлять в виде автоматически работающего устройства. В каждый дискретный момент времени устройство, находясь в некотором состоянии, обозревает содержимое одной ячейки протягиваемой через устройство ленты и делает шаг, заключающийся в том, что устройство переходит в новое состояние, изменяет (или оставляет без изменений) содержимое обозреваемой ячейки и переходит к обозрению следующей ячейки – справа или слева. Причем шаг осуществляется на основании предписанной команды. Совокупность всех команд представляет собой программу машины Тьюринга.
Машина Тьюринга обладает внешним алфавитом А = {a0, a1, …, an}, символы которого записываются на ленту машины, и алфавитом внутренних состояний Q = {q0, q1, …, qm}, где q1 – начальное состояние, q0 – заключительное. Работа машины определяется программой (функциональной схемой). Программа состоит из команд. Каждая команда T(i, j) (i = 1, 2, …, m; j = 0, 1, …, n) представляет собой выражение одного из следующих видов:
 ;  ;  ,
где 0 ≤ k ≤ m; 0 ≤ l ≤ n, С – машина продолжает обозревать ту же ячейку, П – машина сдвигается на клетку вправо, Л – на клетку влево.
Синтез машин Тьюринга является достаточно сложной задачей, требующей определенного уровня развития алгоритмического мышления.
Машина Тьюринга работает со словами своего внешнего алфавита. Пусть А = {0, 1} (здесь 0 – символ пустой ячейки). Полезно ввести следующие обозначения. Для натурального х обозначаем:
 ,  .
Приведем программы следующих машин Тьюринга: «левый сдвиг»  и «правый сдвиг»  . Первая из начального стандартного положения перерабатывает слово 01x0 в то же самое слово и останавливается, обозревая самую левую ячейку с нулем. Вторая машина из начального состояния, в котором обозревается левая ячейка с нулем, 01x0 перерабатывает в то же самое слово и останавливается, обозревая самую правую ячейку с нулем.
Программа машины : q10 → q20Л, q21 → q21Л, q20 → q00.
Программа машины : q10 → q20П, q21 → q21П, q20 → q00.
Программа машины Тьюринга называемой «транспозицией» и обозначаемой В, осуществляющей переход 01xq101y0  01yq001x0, выглядит так:
q10 → q20П, q21 → q21П, q20 → q30, q30 → q40Л, q41 → q50, q50 → q60Л, q61 → q61Л, q60 → q71, q40 → q70, q71 → q81Л, q81 → q90, q90 → q100П, q101 → q101П, q100 → q111, q111 → q121Л, q121 → q130, q130 → q140Л, q141 → q141Л, q140 → q151, q70 → q161, q161 → q171Л, q171 → q150, q151 → q71, q150 → q70, q80 → q180П, q181 → q181П, q180 → q00, q170 → q190П, q191 → q00.
Здесь целесообразно предложить студентам рассмотреть процедуру работы этой машины Тьюринга при следующих конкретных значениях аргументов: x = 1, y = 2; x = 2, y = 1; x = 2, y =3; x = 3, y = 2; x = 2, y = 4; x = 5, y = 3 и т. д.
Приведем программу машины Тьюринга (называемую «удвоение» и обозначаемую Г), которая осуществляет переход q101x0 q001x01x0.
Программа машины Тьюринга Г:
q10 → q2П, q21 → q2П, q20 → q3Л, q31 → q40, q40 → q5П, q50 → q61, q61 → q6П, q60 → q7П, q71 → q7П, q70 → q81, q81 → q8Л, q80 → q9Л, q91 → q9Л, q90 → q20, q30 → q0П.
Здесь также полезно предложить студентам проанализировать работу машины Тьюринга при некоторых конкретных значениях аргумента x = 2, 3, 4, 5.
Эффективным инструментом для конструирования машин Тьюринга является понятие композиции машин Тьюринга.
Пусть заданы машины Тьюринга  , имеющие общий внешний алфавит {a0, a1, …, am} и алфавиты внутренних состояний {q0, q1, …, qn} и {q0,  } соответственно. Композицией (или произведением) машины  и машины  называется новая машина  с тем же внешним алфавитом {a0, a1, …, am}, внутренним алфавитом {q0, q1, …, qn, qn+1, …, qn+t} и программой, получающейся следующим образом. Во всех командах из  , содержащих символ остановки q0, заменяем последний на qn+1. Все остальные символы в командах из остаются неизменными. В командах из символ q0 оставляем неизменным, а все остальные состояния  (i = 1, …, t) заменяем соответственно на qn+i. Совокупность всех так полученных команд образует программу машины-композиции .
Покажем на примере, как это понятие применяется для конструирования машин Тьюринга.
Пример. Построить машину Тьюринга (называемую «циклический сдвиг» и обозначаемую Ц), которая осуществляет переход 01x01yq101z0 01zq001x01y0.
Проверим, что такой перевод произойдет в результате последовательного применения (композиции) ранее построенных машин В, , В, т.е. Ц = ВВ. В самом деле, вычисляем: ВВ(01x01yq101z0) = В(В(01x01yq101z0)) = В(01x01zq01y0) = В(01xq01z01y0) = 01zq001x01y0.
Одна и та же машина Тьюринга может быть построена с помощью разных композиций машин Тьюринга.
Пример. Построим машину Тьюринга (называемую «копирование» и обозначаемую К2), которая осуществляет переход q101x01y 01x01yq001x01y.
В книге А. И. Мальцева [3] приводится следующая композиция машин Тьюринга для осуществления такого перехода:
ВВВГВВГ.
Проверим, что такой же переход произойдет в результате применения композиции машин Тьюринга В, , Г, , Ц, , Г, , В, , т.е.
К2 = ВГЦГВ. В самом деле,
ВГЦГВ (q101x01y) = ВГЦГВ(01xq01y) =
= ВГЦГ(01yq01x) = ВГЦГ(q01y01x) =
= ВГЦ(01yq01y01x) = ВГЦ(01y01yq01x) =
= ВГ(01xq01y01y) = ВГ(q01x01y01y) = В(01xq01x01y01y) =
= В(01x01xq01y01y) = 01x01yq001x01y.
Машина Тьюринга – одно из важнейших понятий в теории алгоритмов, можно даже сказать, основа этой теории. В связи с повсеместным распространением ЭВМ изучение теории машин Тьюринга стало особенно актуальным, поскольку машина Тьюринга является предтечей современных ЭВМ, а самого Алана Тьюринга даже, шутя, называют первым хакером. Особую роль изучение этой теории играет в теоретической подготовке специалистов в области программирования.
Литература
Игошин, В. И. Математическая логика и теория алгоритмов. – 2-е изд., стер. – М.: Издательский центр «Академия», 2008. – 448 с.
Игошин, В. И. Задачи и упражнения по математической логике и теории алгоритмов. – 3-е изд., стер. – М.: Издательский центр «Академия», 2007. – 304 с.
Мальцев, А. И. Алгоритмы и рекурсивные функции. – М.: Наука, 1965. – 392с.
|
