close

Вход

Забыли?

вход по аккаунту

?

674.Алгоритмы Машины Тьюринга проверка истинности булевых функций эффективная реализация множеств на компьютере Рублев В С

код для вставкиСкачать
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
Ярославский государственный университет им. П. Г. Демидова
Кафедра теоретической информатики
В. С. Рублев
Алгоритмы.
Машины Тьюринга,
проверка истинности
булевых функций,
эффективная реализация
множеств на компьютере
(индивидуальная работа № 10 по дисциплине
«Основы дискретной математики»)
Методические указания
Рекомендовано
Научно-методическим советом университета
для студентов, обучающихся по специальности
Информационные технологии
Ярославль 2010
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
УДК 519.2
ББК В127я73
Р82
Рекомендовано
Редакционно-издательским советом университета
в качестве учебного издания. План 2009/10 года
Рецензент
кафедра теоретической информатики Ярославского государственного
университета им. П. Г. Демидова
Р82
Рублев, В. С. Алгоритмы. Машины Тьюринга, проверка истинности булевых функций, эффективная реализация
множеств на компьютере: метод. указания / В. С. Рублев;
Яросл. гос. ун-т им. П. Г. Демидова. – Ярославль: ЯрГУ,
2010. – 44 с.
Методические указания содержат варианты индивидуальных заданий по теме “Алгоритмы”, а также необходимый материал для ее самостоятельного изучения и выполнения индивидуальных заданий. Для качественного усвоения курса в
издании даны подробные определения, примеры, иллюстрации и обоснования.
Предназначены для студентов, обучающихся по специальности 010400.62 Информационные технологии (дисциплина
“Основы дискретной математики”, блок ОП), очной формы
обучения.
УДК 519.2
ББК В174я73
c Ярославский
°
государственный
университет
им. П. Г. Демидова,
2010
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Содержание
1 Проблема определения алгоритма
2 Машины Тьюринга
2.1 Описание машины Тьюринга . . . . . . . . . . . . . . .
2.2 Тезис Тьюринга . . . . . . . . . . . . . . . . . . . . . . .
3 Реализация множеств и булевых функций
на компьютере
3.1 Эффективность алгоритмической реализации множеств
3.2 Описание класса IntSet целочисленных неотрицательных множеств . . . . . . . . . . . . . . . . . . . . . . . .
3.3 Реализация методов класса IntSet . . . . . . . . . . . .
3.4 Пример программы проверки утверждения
для множеств . . . . . . . . . . . . . . . . . . . . . . . .
3.5 Программная реализация булевых функций
на языке C ++ . . . . . . . . . . . . . . . . . . . . . . . .
4 Задание 10
4.1 Общее задание . . . . . . . . . . . . . . . . . . . . . . .
4.2 Пример задачи 1 и ее решения . . . . . . . . . . . . . .
1
3
8
8
13
18
18
21
26
32
34
38
38
39
Проблема определения алгоритма
Дискретное преобразование одного дискретного множества в другое может быть выражено графом и, в частности, сетью из функциональных элементов. Но в этих случаях дискретные множества фиксированы: с их изменением необходимо изменять и граф. Другим способом выражения дискретного преобразования является алгоритм.
Под алгоритмом решения задачи принято понимать описание вычислительного процесса, приводящего к ее решению. Этот термин обязан имени арабского математика начала IX века Мухамеда бен Мусы
по прозвищу ал-Хорезми (из Хорезма), который в своем трактате «Хисаб ал-джебр вал-мукабала» в словесной форме дал правила решения
алгебраических уравнений 1-й и 2-й степени1 .
1
Термин алгебра происходит от второго слова в названии трактата.
3
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
С этих пор алгоритм описывается как последовательность вычислительных шагов, каждый из которых определяет элементарные действия над исходными данными задачи и промежуточными величинами, вводимыми в описание алгоритма, а также определяет, какой шаг
будет выполняться следующим. Такое определение алгоритма принято называть неформальным. До начала XX века казалось, что такого
определения вполне достаточно. Но в 1900 году на математическом
конгрессе в Париже великий немецкий математик Давид Гильберт в
своем докладе о будущем развитии математики определил ряд проблем, которые XIX век оставил XX веку (эти 23 проблемы получили
название проблем Гильберта). Некоторые из них формулировались
как проблемы разработки алгоритмов. Например, десятая проблема
Гильберта заключалась в разработке алгоритма решения диофантовых уравнений (алгебраические уравнения или системы уравнений с
рациональными коэффициентами, решения которых ищутся в рациональных числах). Долгое время многие из этих проблем не поддавались решению, и к началу 30-х годов XX века возникло сомнение в
том, можно ли построить алгоритм для их решения. Но получение математического доказательства невозможности построения алгоритма
решения некоторой проблемы требует формализации понятия «алгоритм». Чтобы разобраться в трудностях формализации понятия «алгоритм», прежде всего рассмотрим свойства этого понятия, которые
справедливы для указанного неформального определения и должны
обязательно быть приняты во внимание при формальном определении.
В первую очередь следует отметить, что каждый алгоритм является способом решения некоторой потенциально бесконечной совокупности задач. Действительно, если рассматривать конечную совокупность задач, то, перенумеровав задачи, получив каким-либо образом
(не обязательно алгоритмическим) решение каждой из них и перенумеровав эти решения, можно построить способ, который каждой задаче из этой совокупности по ее номеру определяет решение с тем же
номером. Такой способ выбора решения не следует понимать как алгоритм. Бесконечная совокупность задач, для которой определяется
алгоритм, характеризуется выбором исходных данных каждой ее за4
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
дачи из некоторого бесконечного набора данных. Отмеченное первое
свойство назовем массовостью алгоритма.
Второе свойство понятия «алгоритм» характеризует его как совокупность отдельных шагов и называется дискретностью алгоритма.
Каждый шаг алгоритма связан с входными данными шага, которыми являются как исходные данные алгоритма, так и выходные данные предыдущих выполненных шагов. Каждый шаг алгоритма связан
также с выходными данными шага, которые однозначно образуются
из его входных данных элементарным действием. Это характеризует
третье и четвертое свойства алгоритма как детерминированность и
элементарность шагов алгоритма.
Результатом выполнения шага алгоритма являются не только выходные данные шага, но и номер следующего выполняемого шага. Во
многих случаях следующим при выполнении является шаг, номер которого на 1 больше, чем номер выполняемого шага. Но в некоторых
случаях единственное действие алгоритма – определение следующего шага для выполнения. Это пятое свойство алгоритма называется
направленностью алгоритма.
Число шагов алгоритма при его выполнении должно быть конечным, что составляет его шестое свойство – конечность числа шагов2 .
Это не означает, что при выполнении алгоритма каждый шаг должен выполняться только 1 раз. Некоторые шаги могут выполняться
лишь при выполнении условия, которое проверяется на предыдущем
шаге. Это дополнительное свойство называется ветвлением алгоритма. Некоторые шаги алгоритма могут выполняться многократно, если следующим выполняемым шагом становится один из предыдущих
шагов. Такое дополнительное свойство называется цикличностью алгоритма. Среди шагов алгоритма обязательно должен быть шаг, прекращающий выполнение алгоритма. Выходные данные этого шага и
являются результатом выполнения алгоритма. Если исходные данные
алгоритма таковы, что при его выполнении никогда не выполняется
шаг, прекращающий вычисления, то говорят, что алгоритм зациклился на этих исходных данных и что алгоритм недопустим для этих
исходных данных (некорректные данные) 3 .
2
3
Это свойство иногда называют результативностью алгоритма.
Корректный алгоритм должен отвергать некорректные данные.
5
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Рассмотрим в качестве примера описание схемы Горнера вычисления значения полинома y = a0 · xn + a1 · xn−1 + ... + an−1 · x + an .
Исходными данными в этом алгоритме являются степень полинома
n, вектор коэффициентов {a0 , a1 , ..., an−1 , an } и значение аргумента x.
Описание алгоритма дается следующей последовательностью шагов:
1. Положить y = a0 , k = 1.
2. Если k > n, перейти к шагу 4.
3. Положить y = y · x + ak , k = k + 1; перейти к шагу 2.
4. Закончить вычисления с результатом y.
Массовость этого алгоритма демонстрируется его применением к любому полиному и любому аргументу из бесконечной совокупности полиномов и значений аргументов. Дискретность и конечность обеспечиваются выделением 4 шагов алгоритма. Элементарность шагов алгоритма следует из простоты вычислений каждого шага. Направленность обеспечивается указанием следующего шага по умолчанию (для
шага 1 и для шага 2, если не выполнено условие), либо указанием следующего шага (для шага 3 и для шага 2, если выполнено условие)
либо указанием прекращения вычислений (шаг 4). Дополнительное
свойство ветвления алгоритма использовано на шаге 2, а свойство
цикличности алгоритма использовано в организации цикла шагов 2
и 3.
С процессом выполнения алгоритма связано понятие конфигурации
выполнения. Конфигурация описывается номером шага при выполнении алгоритма, значением всех исходных данных и всех промежуточных величин алгоритма и результата, записанных в определенном порядке. Так, для вышеописанного примера определим конфигурацию
как следующую совокупность данных:
< N, x, n, a0 , a1 , ..., an , k, y >,
где N – номер шага. Перед выполнением алгоритма N = 0. В результате вычисления каждого шага конфигурация изменяется. Выполнению алгоритма соответствует последовательность конфигураций. Например, для вычисления значения y = 52 − 2 · 5 + 1 следующая после6
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
довательность конфигураций описывает выполнение алгоритма:
< 0, 5, 2, 1, −2, 1, ?, ? >
< 1, 5, 2, 1, −2, 1, 1, 1 >
< 2, 5, 2, 1, −2, 1, 1, 1 >
< 3, 5, 2, 1, −2, 1, 2, 3 >
< 2, 5, 2, 1, −2, 1, 2, 3 >
< 3, 5, 2, 1, −2, 1, 3, 16 >
< 2, 5, 2, 1, −2, 1, 3, 16 >
< 4, 5, 2, 1, −2, 1, 3, 16 > .
Подводя итог анализу свойств алгоритма, мы можем уточнить его
определение:
Алгоритм есть описание вычислительного процесса решения задачи, обладающее свойствами массовости, дискретности, детерминированности, направленности, конечности
и элементарности.
С информационной точки зрения алгоритм есть средство переработки информации. Для каждого набора входной информации, который
является корректными исходными данными для алгоритма, он (алгоритм) однозначно определяет выходную информацию. Эта функциональная связь наборов входной информации с наборами выходной информации позволяет нам рассматривать алгоритм как частичную функцию, которую мы будем называть интуитивно вычислимой
функцией. Основной вопрос теории алгоритмов можно сформулировать следующим образом: является ли любая заданная функция интуитивно вычислимой, т. е. для любой ли функции можно построить
алгоритм, который осуществляет вычисление значения этой функции? Этот вопрос эквивалентен следующему: если произвольная задача предполагает однозначное решение для своих исходных данных,
то всегда ли существует алгоритм решения этой задачи? Для ответа на этот вопрос необходимо знать точно, что такое алгоритм.
7
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Поэтому прежде всего нужно заняться формализацией понятия «алгоритм».
Проанализируем возможность формализации алгоритма, при которой сохраняются свойства неформального определения. Не вызывает
трудностей формализация исходных данных и промежуточных величин алгоритма. Свойства дискретности, направленности и конечности
числа шагов алгоритма обеспечиваются последовательной декомпозицией алгоритма, нумерацией его шагов и определением следующего
выполняемого шага, что также можно формализовать. Но требование
элементарности шага алгоритма вызывает трудность. Не ясно, какие
действия следует считать элементарными. Если зафиксировать формально действия, которые мы считаем элементарными, то возникает
опасность, не сузили ли мы такой формализацией возможность описывать любые алгоритмы. В этом состоит основная проблема формализации понятия «алгоритм».
Начиная с 30-х годов XX в. было разработано много подходов формализации понятия «алгоритм», такие как частично-рекурсивные функции (С. К. Клини, К. Гёдель, А. Чёрч), машины Тьюринга (А. М. Тьюринг), нормальные алгоритмы Маркова (А. А. Марков), алгоритмы
Поста (Э. Л. Пост), лямбда-исчисления (А. Чёрч). Каждый из подходов по-своему определял элементарность шага алгоритма, но замечателен тот факт, что все эти определения оказались эквивалентными, т. е. описывающими одну и ту же совокупность объектов, называемых алгоритмами. Однако формализация, называемая машинами
Тьюринга, чаще всего используется в теоретических построениях.
2
2.1
Машины Тьюринга
Описание машины Тьюринга
В 1936 г. английский математик Алан Тьюринг описал схему абстрактной машины и предложил назвать алгоритмом то, что умеет
делать эта машина. Машины Тьюринга – это не реальные вычислительные машины, а способ описания алгоритма, при помощи которого формализуется понятие алгоритма и его можно исследовать.
8
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
От реальных машин они отличаются бесконечной памятью. Устройство этих машин намеренно выбрано «бедным», лишь бы оно было
универсальным и позволяло доказывать, что для определенных задач не существует такой машины (т. е. нельзя построить алгоритм).
Реальные вычислительные машины (компьютеры), наоборот, должны
быть богатыми по устройству и уметь хорошо (эффективно) решать
задачи.
В основе описания устройства машины Тьюринга (МТ) лежат три
ее составные части:
1. Память в виде бесконечной в обе стороны ленты, разделенной
на ячейки, в каждую из которых может быть записана либо одна из букв внешнего алфавита {a1 , a2 , ..., ak }, либо пустой символ (будем для единообразия обозначать его греческой буквой
Λ и добавим его к алфавиту как символ a0 ). Внешний алфавит
A = {a0 , a1 , ..., ak } может быть своим для каждой МТ, но всегда
конечным. На любом шаге работы МТ только конечный участок
ленты может содержать буквы внешнего алфавита.
2. Автомат, состоящий из устройства управления и считывающей головки, который на каждом шаге работы МТ передвигается
вдоль ленты памяти на 1 ячейку влево, вправо или остается на
месте. Движение автомата будем обозначать элементами множества движений D = {L, R, N }.
3. Считывающая головка, которая на любом шаге работы МТ обозревает какую-либо ячейку памяти.
4. Устройство управления, которое на каждом шаге работы МТ
может находиться в одном из конечного числа своих состояний,
множество {q1 , q2 , ..., qn } которых называется внутренним алфавитом.
Работа МТ может быть описана следующим образом:
1. В начальный момент работы МТ лента памяти находится в начальном состоянии (конечное непустое слово на ленте называется
входным словом), автомат находится в начальном состоянии q1 и
считывающая головка обозревает самый левый непустой символ
входного слова.
9
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2. На каждом шаге работы МТ головка считывает символ ai ∈ A
из обозреваемой ячейки и в зависимости от него и от состояния
qj ∈ Q устройства управления автомат:
a) записывает в обозреваемую ячейку символ ai0 ∈ A (может, и
не изменяет его),
b) изменяет состояние устройства управления на qj 0 ∈ Q (может,
и не изменяет его),
c) осуществляет движение в направлении d ∈ D (может, остается на месте).
3. Если в результате предыдущих шагов автомат переходит в такое
состояние, при котором:
a) состояние автомата не изменяется,
b) символ в обозреваемой ячейке не изменяется,
c) движение автомата вдоль ленты памяти не происходит,
то машина переходит в заключительное состояние останова. Для
упрощения мы такое состояние обозначим через q0 и переход к
нему будем обозначать как переход к состоянию q0 . Это состояние мы также включим в множество состояний Q = {q0 , q1 , ..., qn }.
Слово, которое получается при переходе МТ к состоянию останова, будем называть выходным словом.
Действия автомата на каждом шаге работы МТ могут быть описаны
тремя функциями:
ai0 = a(ai , qj ), возвращающая значение записываемого символа ai0 ,
если в состоянии qj был прочитан символ ai ;
qj 0 = q(ai , qj ), возвращающая состояние qj 0 , в которое переходит МТ
после того, как в состоянии qj был прочитан символ ai ;
d = d(ai , qj ), возвращающая направление движения d после того,
как в состоянии qj был прочитан символ ai .
Все 3 функции должны быть определены на множестве A×(Q−{q0 }).
Табличное задание этих функций называется функциональной схемой
10
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
МТ. В этой прямоугольной таблице (см. рис. 1) размера n × k на пересечении j-й строки (j = 1, n), отвечающей состоянию qj , и i-го столбца
0
(i = 0, k), отвечающего символу ai , находится тройка ai0 , qj 0 , d , определяющая изменение символа в обозреваемой ячейке, изменение состояния МТ и движение МТ на шаге работы МТ.
Λ a1 ...
q1
...
qj
...
qn
ai
... ak
... ... ...
...
... ...
ai0 qj 0 d
... ... ...
...
... ...
Рис. 1
С каждым шагом работы МТ свяжем конфигурацию МТ, которая
состоит из последовательности символов слова, записанного на ленте
МТ перед выполнением шага, и состояния МТ, записанного перед обозреваемым символом на этом шаге. Например, конфигурация abq2 aba
означает, что в момент выполнения шага на ленте находится слово
ababa, МТ обозревает второй символ a и находится в состоянии q2 , а
конфигурация ababaq3 означает, что на ленте находится такое же слово, но МТ в состоянии q3 обозревает пустой символ справа от слова
на ленте.
МТ называется применимой к входному слову, если, начав работу
в начальном состоянии, она через конечное число шагов перейдет в
состояние останова, и неприменимой, если при ее работе она не переходит в состояние останова ни за какое конечное число шагов. МТ
может быть неприменима ни к одному слову. Например, МТ, определенная функциональной таблицей на рис. 2, все время движется вдоль
ленты вправо, ничего не меняя.
q1
Λ
0
1
Λ q1 R 0 q1 R 1 q1 R
Рис. 2
МТ может быть применима к любому слову. Например, МТ, заданная
функциональной таблицей на рис. 3, стирает все символы входного
11
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
слова и останавливается.
q1
Λ
0
1
Λ q0 N Λ q1 R Λ q1 R
Рис. 3
В дальнейших примерах мы для большей наглядности не будем в
клетке таблицы определять
– заменяемый символ, если он не меняется,
– новое состояние, если оно не меняется,
– движение, если оно не происходит.
Введем также столбец для комментариев действий МТ в том или ином
состоянии. Рассмотрим в качестве примера разработку МТ, которая
увеличивает произвольное десятичное число на 1. Неформальный пошаговый алгоритм можно определить следующим образом:
1. Определить последнюю цифру числа (для этого двигаться вправо до пустого символа и, перейдя к следующему состоянию, вернуться
к предыдущей цифре).
2. Увеличить цифру (последнюю) на 1, если она меньше (не равна)
9, и закончить работу МТ; если же цифра равна 9, то заменить ее 0
и перейти к увеличению предыдущей цифры (единица переноса), для
чего повторить действия этого шага.
Функциональная таблица МТ представлена на рис. 4.
q1
q2
Λ
0
1 ... 8
9
q2 L R
R ... R
R поиск последней цифры
1 q0 1 q0 2 q0 ... 9 q0 0 L увеличение на 1 и перенос
Рис. 4
Каждая МТ на множестве входных слов задает частичную функцию f , которая любому применимому входному слову P ставит в соответствие выходное слово f (P ). Эта функция называется вычислимой по Тьюрингу. Ясно, что каждая вычислимая по Тьюрингу функция является интуитивно вычислимой, т. е. каждая МТ определяет
алгоритм. Но, может быть, существуют алгоритмы, для которых построение МТ невозможно? В следующем разделе мы исследуем возможности МТ и покажем, что не видно ограничений для описания
12
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
алгоритмов при помощи аппарата МТ.
2.2
Тезис Тьюринга
Рассмотрим пример МТ, которая для входного слова, образованного любым натуральным числом палочек, стирает самую правую палочку. Функциональная таблица этой МТ представлена на рис. 5.
q1
q2
Λ
|
q2 L R
q0 Λ q0
поиск последней палочки
стирание палочки и останов
Рис. 5
Теперь постараемся объединить две последние МТ в одну, которая
подсчитывает число палочек во входном слове. Для этого можно число
считаемых палочек располагать левее самой левой палочки входного
слова и соединить 2 алгоритма стирания правой палочки и увеличения
левого числа (палочек) на 1 следующим образом:
1. Выполняем 1-й алгоритм стирания правой палочки, но не останавливаемся, а переходим к следующему шагу.
2. Ищем самую последнюю цифру числа (если ее нет, то 1-й пустой
символ справа) и увеличиваем число на 1 при помощи 2-го алгоритма.
На этом не останавливаемся, а переходим к следующему шагу.
3. Ищем палочку справа от числа и, если ее нет, заканчиваем работу; иначе переходим к шагу 1.
На рис. 6 представлена функциональная таблица МТ подсчета палочек.
q1
q2
q3
q4
Λ
0
q2 L
R
q0
q0
1 q4 R 1 q4 R
q0
R
...
8
9
|
...
R
R
R
...
q0
q0 Λ q3 L
... 9 q4 R 0 L
L
...
R
R
q1 R
к последней палоч.
стир.пал.или стоп
к посл.циф.и ув.чис.
нет палоч. – стоп
Рис. 6
Для проверки алгоритма построенной МТ нужно задать достаточный
набор тестов и проверить на нем выполнение алгоритма. Например,
13
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
работу построенной МТ подсчета палочек демонстрирует следующий
пример:
q1 ||| → |q1 || → ... → |||q1 → ||q2 |→ |q3 | → q3 || →1|q4 | → 1||q1 → 1|q2 | →
1q3 | → q3 1| → 2q4 | → 2|q1 → 2q2 | → q3 2 → 3q4 → 3q0
Указанный пример построения МТ показывает, что из уже имеющихся МТ можно построить новые МТ, соединяя их различным образом. Так, в примере применено последовательное соединение МТ,
стирающей палочку и увеличивающей число на 1, которое затем повторяется в цикле. Неформальное пошаговое определение алгоритма
показывает 4 способа соединения алгоритмов:
1. Последовательное соединение, или суперпозиция, когда
за выполнением шагов первого алгоритма следует выполнение
шагов второго алгоритма и входной информацией для второго
алгоритма служит выходная информация первого алгоритма.
2. Композиция, когда 2 алгоритма параллельно и независимо выполняют работу над входной информацией и результатом их работы является выходная информация обоих алгоритмов.
3. Ветвление, когда в зависимости от выполнения условия для
входной информации, проверяемого первым алгоритмом, выполняется или не выполняется второй алгоритм.
4. Цикл, когда при проверке первым алгоритмом выполнения условия для входной информации соединения алгоритмов или выходной информации предыдущего выполнения второго алгоритма
этот второй алгоритм снова выполняется в цикле или происходит
выход из цикла с выходной информацией второго алгоритма.
Мы покажем, что МТ также можно соединить подобным образом,
приведя лишь идеи построения таких соединений.
Суперпозиция МТ. Пусть M1 и M2 – две машины Тьюринга,
вычисляющие функции f1 (P ) и f2 (P ). Тогда можно построить машину Тьюринга M = M2 (M1 ), вычисляющую суперпозицию функций
f2 (f1 (P )). Она определена тогда и только тогда, когда определены
f1 (P ) и f2 на множестве значений f1 (P ).
14
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Доказательство. Не ограничивая общность рассуждений, можно считать, что M1 заканчивает работу, когда ее головка позиционирует самый левый символ выходного слова, так как в противном случае можно заменить эту МТ на эквивалентную (вычисляющую ту же функцию), удовлетворяющую этому требованию. Сделать это можно, добавив в конце работы переход к дополнительному состоянию, в котором
отыскивается пустой символ слева от левого непустого символа выходного слова и производится сдвиг вправо с остановкой.
Пусть M1 имеет множество состояний {q0 , q1 , ..., qn1 }, а M2 имеет множество состояний {q0 , q1 , ..., qn2 }. Для построения суперпозиции
M:
1) переименуем состояния M2 , заменяя q1 на qn1 +1 ,..., qn2 на qn1 +n2 ;
2) напишем вторую функциональную таблицу под первой;
3) изменим значения тех ячеек первой функциональной таблицы,
в которых осуществляется переход к заключительному состоянию q0 ,
изменив этот переход на переход к начальному состоянию второй таблицы qn1 +1 .
В результате мы получим требующуюся машину M .
Композиция МТ. Пусть M1 и M2 – две машины Тьюринга, вычисляющие функции f1 (P ) и f2 (P ). Тогда можно построить машину
Тьюринга M = M1 ∗ M2 , которая выполняет работу обеих МТ и вычисляет функцию f (P ) = f1 (P ) ∗ f2 (P ), где символ * не встречается
в алфавите M1 и M2 (f (P ) не определена, если не определены f1 (P )
или f2 (P )).
Доказательство. Рассмотрим следующую идею образования M :
1) построим МТ M3 , которая копирует входное слово P в виде P ∗P ;
2) напишем таблицу M2 под таблицей M1 ;
3) изменим действия M1 на пустом правом символе на такие же
действия на символе *;
4) изменим переход к заключительному состоянию M1 на переход
к начальному состоянию M2 с движением влево от символа *;
5) изменим действия M2 на пустом левом символе на такие же действия на символе *.
Описанная идея некорректна в пункте 3, если действия M1 связаны
с одним из следующих:
15
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1) с заменой пустого символа на некоторый непустой (при этом
исчезнет символ *, разделяющий левую часть слова, обрабатываемую
M1 , и правую часть слова, обрабатываемую M2 , и соединение станет
неверным);
2) со стиранием символа слева от пустого (замена на символ * приведет к тому, что обе части слова для обработки M1 и M2 будут разделены более чем одним символом *).
Для того чтобы исправить некорректность в первом случае, введем
для каждого состояния qj МТ M1 , где этот случай имеет место, МТ
r
Mjc
с множеством состояний {qj1 , . . . , qjm , qj0 } (qj1 – начальное, а qj0
– конечное состояния), которая сдвигает вправо на 1 ячейку правую
часть слова, начинающуюся с символа *, записывая в освободившуюся ячейку символ λ (который не встречается в алфавите МТ M1
и M2 ), и останавливается, позиционируя этот символ. Пусть теперь
функциональная таблица МТ M1 в состоянии qj при чтении пустого
символа справа определяется тройкой (ai , qj 0 , d). В преобразованной
M1 эта тройка в строке qj и столбце, отвечающем символу *, замеr
ним на (λ, qj1 , N ), где qj1 – начальное состояние МТ Mjc
. Добавим в
функциональную таблицу M1 строку qj0 , отвечающую конечному соr
стоянию МТ Mjc
, и для дополнительно введенного столбца символа λ
этой строки определим тройку (ai , qj 0 , d). Тогда действия, отвечающие
пункту 3 в этом случае, станут корректны.
Для того чтобы исправить некорректность пункта 3 во втором случае (стирание символа слева от символа *, заменившего пустой символ), введем для каждой пары (j, i), где qj – состояние, в котором
r
стирается символ ai , МТ Mjid
с множеством состояний {q1ji , . . . , q0ji }
(q1ji – начальное, а q0ji – конечное состояния), которая сдвигает часть
слова справа от символа * вместе с ним на 1 ячейку влево, стирая
символ слева. Пусть теперь в некотором состоянии M1 при чтении
пустого символа переходит в состояние qj , сдвигая головку влево, и
в состоянии qj стирает символ ai , сдвигая после этого головку в направлении dji и переходя в состояние qji . В преобразованной МТ M1
тройку (Λ, qji , dji ) заменим на (λ, q1ji , R), где λ – символ, не встречаюr
щийся в алфавите МТ M1 и M2 , который МТ Mjid
заменит на символ
*. Добавим в функциональную таблицу M1 строку q0ji , отвечающую
r
конечному состоянию МТ Mjid
, и для столбца символа * этой строки
16
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
определим тройку (∗, qji , dji ). Тогда действия, отвечающие пункту 3
во втором случае, также станут корректными.
Так же, как для пункта 3 конструирования МТ M , требуются изменения, связанные с действиями МТ M2 при выполнении пункта 5.
Для этого аналогичным образом для каждого состояния qj МТ M2 ,
l
где необходимо добавлять символ слева, вводится МТ Mjc
, которая
сдвигает влево на 1 ячейку левую часть слова, заканчивающуюся символом *, записывается в освободившуюся ячейку символ λ и производятся аналогичные изменения функциональной таблицы МТ M2 .
Аналогичным образом для каждой пары (j, i), где qj – состояние M2 ,
l
в котором стирается символ ai , строится МТ Mjid
, которая сдвигает
часть слова справа от удаляемого символа на 1 ячейку влево, стирая
этот символ. Соответствующие изменения функциональной таблицы
МТ M2 приводят к корректным действиям при выполнении пункта 5.
В результате мы получим машину M , которая сначала перерабатывает в f1 (P ) первую копию слова P , а затем перерабатывает в f2 (P )
вторую копию слова P , что и требовалось.
Ветвление МТ. Пусть M1 и M2 – две машины Тьюринга, вычисляющие функции f1 (P ) и f2 (P ), причем множеством значений
функции f1 (P ) является множество {F, T } (F – ложь, T – истина).
Тогда можно построить машину Тьюринга M = M1 →M2 , которая
перерабатывает слово P в f2 (P ), если f1 (P ) = T , и оставляет входное слово без изменений, если f1 (P ) = F .
Доказательство. Машину M можно реализовать следующим образом:
1) построим композицию M1 ∗ M2 ;
2) изменим в этой композиции переход от работы машины M1 к
работе машины M2 так, что если после работы M1 образуется слово
F ∗ P , то M1 стирает символы F ∗ и переходит к заключительному
состоянию; а если после работы M1 образуется слово T ∗ P , то M1
стирает символы T ∗ и переходит к начальному состоянию M2 и продолжает работу, перерабатывая слово P в слово f2 (P ).
Цикл МТ. Пусть M1 и M2 – две машины Тьюринга, вычисляющие функции f1 (P ) и f2 (P ), причем множеством значений функции
f1 (P ) является множество {F, T } (F – ложь, T – истина). Тогда
17
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
можно построить машину Тьюринга M = M1 ◦M2 , которая выполняет следующую последовательность действий:
- вычисляет f1 (P ), и если f1 (P ) = T , то вычисляет новое значение P := f2 (P ), а если f1 (P ) = F , то переходит к заключительному
состоянию c выходным словом P (возможно новое значение);
- повторяет действия предыдущего пункта до тех пор, пока для
очередного значения слова P не будет выполнено f1 (P ) = F .
Доказательство. Машину M можно реализовать следующим образом:
1) образуем ветвление машин M1 →M2 ;
2) изменим заключительное состояние M2 , заменив его переходом
к копированию получившегося слова f2 (P ) и добавив после этого переход к начальному состоянию M1 .
В результате мы получим машину, которая реализует цикл МТ.
Описанные операции над машинами Тьюринга показывают, что
можно строить все более сложные МТ. Поскольку можно реализовать
арифметические и логические операции, то возникает уверенность в
том, что любая интуитивно вычислимая функция является вычислимой по Тьюрингу. Именно в этом и состоит тезис Тьюринга. Его
не следует рассматривать как некоторое утверждение, требующее доказательства, а следует понимать как определение алгоритма. Для
того чтобы убедиться в корректности такого уточнения понятия «алгоритм», мы рассмотрим другие уточнения этого понятия и вопрос об
эквивалентности уточнений.
3
3.1
Реализация множеств и булевых функций
на компьютере
Эффективность алгоритмической реализации множеств
Под реализацией множеств на компьютере будем понимать представление множеств и операций над ними.
При реализации множеств на компьютере могут быть выбраны различные структуры для их описания: например, массивы, списки и др.
18
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
В зависимости от выбора способа реализации может быть достигнута
различная эффективность:
1) по расходуемому для реализации объему памяти;
2) по сложности реализации основных операций над множествами;
3) по наглядности введенной реализации операций над множествами.
Рассмотрим сначала наиболее очевидную реализацию с помощью
массивов, при которой каждый элемент множества является элементом массива. Пусть максимальный объем памяти для записи элемента множества равен m. Тогда объем памяти, потребный для записи
n-элементного множества, равен произведению n · m. Для описания
нескольких подмножеств одного множества, чтобы не повторять названия элементов, можно их закодировать целыми числами от 0 до
n − 1. Тогда список названий элементов можно будет представить
другим массивом, индексы элементов которого равны введенным целочисленным кодам. При этом объем памяти на массив каждого подмножества сократится до 2n или n байтов в зависимости от значения
n – при значении, не превосходящем 256, – n байтов, а при большем
значении (но не превосходящем 216 ) – 2n байтов.
Оценим теперь сложность процедур основных операций над множествами при их реализации массивами. Для операции объединения подмножеств A и B множества U размера n необходимо в худшем случае
n2 операций, так как каждый элемент одного подмножества необходимо проверять на принадлежность другому подмножеству, что требует
порядка n операций. Аналогично пересечение множеств требует порядка n2 операций. То же самое относится к операциям дополнения
множества и разности множеств.
Перейдем теперь к наглядности операций над множествами. Реализация операций процедурами не является наглядной. Например, пусть
объединение множеств A ∪ B реализовано функцией union(A, B), пересечение A∩B – intersection(A, B), разность A\B – dif f erence(A, B),
а дополнение множества A – complement(A). Тогда формула для множества (A \ B) ∩ C ∪ D будет выглядеть как вызов функции
union(intersection(dif f erence(A, B), C), complement(D)).
Такой функциональный подход не является наглядным. Желательно,
19
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
чтобы можно было записывать формулы для множеств. Но общепринятых обозначений операций для множеств на клавиатуре компьютера нет. Поэтому желательно:
1) операцию объединения множеств A ∪ B обозначить знаком + как
A + B,
2) операцию пересечения множеств A ∩ B обозначить знаком * как
A ∗ B,
3) операцию разности множеств A \ B обозначить знаком – как
A − B,
4) операцию дополнения множества A обозначить знаком ∼ как
∼ A.
Тогда вышеуказанную формулу можно было бы представить в наглядном виде:
(A − B) ∗ C+ ∼ D.
Для того чтобы это можно было сделать, нужно ввести тип для
множеств. В современных языках программирования, и в частности
C ++ , это можно сделать при помощи конструкции класса объектноориентированного программирования. Каждый класс определяет новый тип данных, т. е. задает структуру данных переменных этого
типа и методы работы с его переменными как процедуры и функции
для этого типа.
Но прежде, чем создавать класс для множеств, мы продолжим обсуждение эффективности реализации множеств. Каждое подмножество некоторого n-элементного множества можно определить характеристической строкой из n нулей и единиц, каждая позиция которой
определяет наличие (1) или отсутствие (0) элемента множества в этом
подмножестве. Например, строка ’1001000010’ определяет подмножество, которое содержит элементы с номерами 0, 3, 8 10-элементного
множества. Универсальное множество задается строкой из единиц, а
пустое множество – из нулей. В реализации такая характеристическая
строка задается строкой битов (двоичных разрядов, принимающих
значения 0 или 1). При этом, во-первых, происходит экономия памяти:
вместо 10 байтов на каждое подмножество требуется d10/8e = 2 байта
20
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
(целая часть сверху от 10/8), т. е. объем памяти при этой реализации
уменьшается примерно в 8 раз.
Во-вторых, для выполнения основных операций объединения, пересечения или дополнения множеств требуется произвести соотвественно операцию поразрядного логического сложения, поразрядного логического умножения или дополнения (инвертирования кода) над соответствующими строками битов. При этом сложность такой операции
имеет порядок n (n/8 операций над байтами), а не n2 , а, учитывая, что
операции поразрядного логического сложения, умножения и дополнения являются самыми быстрыми операциями на компьютере, такая
реализация множеств при помощи строк битов становится особенно
эффективной.
3.2
Описание класса IntSet целочисленных неотрицательных множеств
Описание каждого класса в C ++ имеет следующий синтаксис:
class <имя класса>
{
<приватный раздел описания>
public:
<общий раздел описания>
};
Имя класса есть название нового типа. В приватном разделе описания
помещаются скрытые от пользователя этого класса части описания.
Как правило, здесь находится объявление данных типа класса и вспомогательных процедур и функций класса, которые не должны быть
видимы. В общем разделе описания, как правило, находятся объявления методов класса: процедур и функций, которые работают с типом
данных этого класса. Эти и только эти процедуры и функции могут
обращаться к данным типа класса. Кроме того, в общий раздел описания класса могут помещаться объявление типов исключений, связанных с нарушением целостности данных типа класса. Таким образом
данные, методы и типы исключений класса, т. е. все что связано с
этим типом данных, инкапсулированы в класс.
#ifndef INTSET_H(
21
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
#define INTSET_H
class IntSet
//класс цел.неотр.мн-ств
{
int size;
//кол.байт.стр.бит.множ.
char* x;
//указ.стр.бит.множества
public :
IntSet (int m);
//констр.множ.разм. m
IntSet (const IntSet&);
//инициализатор
IntSet& operator=(const IntSet& a); //оп-р присваивания
class SetLimit{};
//тип искл.огр.разм.мнж.
void insert(int t);
//включ. t в множество
bool member(int t);
//явл.ли t элем.множ.?
void print();
//вывод множества
int M axElem() {return size ∗ 8 − 1; } //макс.знач.для элемент.
IntSet operator+ (const IntSet a);
//объединение множеств
IntSet operator* (const IntSet a);
//пересечение множеств
IntSet operator ∼ ();
//дополнение множества
IntSet operator– (const IntSet a);
//разность множеств
bool operator== (const IntSet a);
//равны ли множества?
void InputSet(char∗);
//ввод элем.множества
};
#endif);
Перед описанием класса и после него идут макросы условной компиляции #ifndef и #endif. Они необходимы, чтобы при модульной
организации программы (если таковая имеет место) текст описания
класса не был включен макросом
#include “IntSet.h”
в программу более 1 раза (если это произойдет, то компилятор выдаст
ошибку, связанную с повторным описанием). Макросы выполняются
перед компиляцией кода, и если при выполнении первого макроса
#ifndef INTSET_H
будет обнаружено, что имя INTSET_H еще не определено, то условная компиляция исходного текста описания класса IntSet будет иметь
место и перед ней макросом
#define INTSET_H
будет определено это имя. При повторной попытке включить для ком22
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
пиляции это текст в программу она будет проигнорирована макросами
условной компиляции.
В описании класса IntSet, которое приведено выше, в приватном
разделе находится описание данных класса, которое состоит из поля
size, определяющего количество байтов строки битов множества, и
поля указателя char∗ на строку битов, который определяется как указатель на строку символов (для каждого символа отводится 1 байт).
Среди методов общего раздела следует выделить 2 особых метода:
конструктор и деструктор. Конструктор имеет названием имя класса, не имеет возвращаемого значения и может иметь параметры, количество и тип которых указываются, как обычно, в круглых скобках.
Вызов конструктора производится неявно при выполнении описания
переменных типа класса.
Например, для класса IntSet вызов конструктора в использующей
класс программе осуществляется при выполнении описания:
IntSet X(10);
При этом создается экземпляр класса с именем X, представляющий
собой пустое множество, для 10-разрядной строки битов которого выделяется память в 2 байта (в поле size этого экземпляра записывается
значение 2, выделяется память размером в 2 байта, адрес этой памяти
записывается в поле указателя char∗, а сама память инициализируется нулями – это и есть пустое множество).
Параметры необходимы, чтобы инициализировать поля данных экземпляра класса. Если конструктор не содержит параметры1 , то он
называется конструктором по умолчанию. В некоторых реализациях
C ++ , если в описании класса конструктор не указан, определяется по
умолчанию такой конструктор, который создает экземпляр класса, но
не инициализирует поля данных этого экземпляра, что плохо.
В описании класса допускается определять несколько конструкторов, но они должны различаться количеством или типом параметров.
В примере описания класса IntSet приведены 2 конструктора: первый имеет параметр типа int для инициализации поля size, а второй
– типа ссылки на другой уже имеющийся экземпляр этого же класса.
Он вызывается указанием инициализации при описании переменной
1
В данном примере это невозможно, так как необходимо определить размер выделяемой
памяти для строки бит
23
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
типа класса. Например, при описании
IntSet Y = X;
создается экземпляр класса Y , поля данных которого инициализируются полями данных экземпляра X. Такой конструктор называется инициализатором. Попытка вызвать оба конструктора, например,
описанием
IntSet Y(10)=X;
является ошибкой.
Другой особый метод деструктор имеет имя, состоящее также из
имени класса, перед которым находится символ ∼. Например, в описании класса деструктор мог быть указан как метод:
IntSet ∼ IntSet(); .
Выполнение деструктора
Z. ∼ IntSet(); приводит к удалению экземпляра класса Z и освобождению памяти, занятой этим экземпляром. Чаще всего, как и в
примере описания ниже класса IntSet, деструктор не указывается явным образом в описании класса. Его указание совершенно необходимо
в том случае, когда нужно сделать освобождение выделенной для экземпляра динамической памяти, которая не может быть освобождена
иным образом.
Все другие методы класса имеют тип возвращаемого значения: void
для процедур и любой другой для функций.
Ввод элементов множества осуществляет метод InputSet, параметром которого является имя экземпляра множества для организации
диалога при вводе элементов. Добавление каждого введенного неотрицательного целочисленного элемента производится методом insert.
При выполнении последнего проверяется допустимость добавляемого целочисленного элемента (не должен превосходить максимального
значения отведенного для множества) и при недопустимости такого
значения вызвавший добавление элемента метод InputSet вызывает
обработчик исключения типа SetLimit, класс которого объявлен в
данном классе как пустой. Для сообщения обработчиком возникшей
исключительной ситуации используется функция M axElem, возвращающая максимально возможное значение элемента для данного множества.
Вывод множества осуществляет метод print. При этом выводится
24
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
заключенная в фигурные скобки последовательность элементов множества, разделенных пробелами.
Отношение принадлежности элемента множеству осуществляет функция member, возвращающая истинностное значение true или false.
Отметим, что вызов любого метода для объявленного экземпляра
класса имеет синтаксис:
<имя экземпляра>.<имя метода> (<список арг-ов метода>); .
В список аргументов метода не входит сам объект – экземпляр метода, так как его имя указывается перед именем метода. Поэтому для
множества X ввод его элементов осуществляется вызовом:
X.InputSet(”X”); ,
а вывод этого множества – вызовом:
X.print(); .
Для операций объединения, пересечения, разности и дополнения
множеств предназначены методы-функции с именами:
operator+, operator*, operator–, operator∼.
Это ведет к перегрузке операций +, *, –, ∼, а потому для каждой операции можно использовать фукциональный стиль или формульный.
Например, объединение множеств X и Y можно записать в функциональном стиле X.operator+(Y ) или в формульном X +Y , что гораздо
наглядней.
Эти функции возвращают значение типа IntSet, каковым и должно быть полученное операцией множество. Заметим, что при перегрузке указанных операций для множеств сохраняется естественный
приоритет этих операций, т. е. наиболее приоритетной является операция дополнения, затем идет операция пересечения, и, наконец, наимение приоритетными являются операции объединения и разности
множеств. Это соответствует общепринятым приоритетам операций
для множеств и позволяет записывать формулы с меньшим количеством скобок.
Сравнение множеств (на равенство) также является перегруженной функцией операции operator==, но возвращает булево истинностное значение. Это позволяет писать условие наглядно. Например,
if (X == Y ) . . . .
Перегруженная операция присваивания при помощи метода-функ25
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ции operator= возвращает значение ссылки на тип IntSet, чтобы
можно было осуществлять множественное присваивание. Например,
оператор A = B = X + Y ; осуществит присваивание множествам
A и B значения объединения множеств X и Y . По этой же причине
параметр этой операции присваивания также должен быть ссылкой
на множество.
3.3
Реализация методов класса IntSet
Обычно описание класса помещается в отдельный модуль, имеющий именем название класса и расширение h (заголовочный). В начале модуля реализации методов, который также имеет именем название
класса, а расширение cpp, помещается директива включения заголовочного модуля в кавычках и, если требуется ввод/вывод данных,
помещается директива включения заголовочного файла стандартного
потока ввода/вывода (в уголковых скобках). В модуле реализации в
заголовке каждого метода перед его именем идет имя класса с двойным двоеточием. Делается это по той причине, что модуль может содержать реализацию методов, совпадающих по имени для различных
классов. Даже если этого нет, такое уточнение обязано быть сделано.
Для эффективного исполнения методов класса требуется тщательный отбор операторов, реализующих программу каждого метода. Поясним выбор программных конструкций в некоторых случаях.
Реализация конструктора IntSet (int m) имеет первым оператором определение (size) количества байтов строки битов сдвигом на 3
разряда вправо (деление на 8) параметра m. Требуется увеличить size
на 1, если есть остаток от деления m на 8 (выделение остатка в трех
последних разрядах m производится побитовым умножением m на 7
— код 00. . . 0111). Затем оператором new выделяется динамическая
память в m байтов и адрес этой памяти заносится в поле x указателя
строки битов. Наконец, для обнуления строки битов (при выделении
динамической памяти она не чистится) заносится нулевой код, какой
дается символом 0 \00 .
#include <iostream.h>
#include “intset.h”
26
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
IntSet :: IntSet (int m)
{
size = m >> 3;
if (m&7) size++;
x = new char[size];
for (int i = 0; i < size; i++)
x[i] =0 \00 ;
}
IntSet :: IntSet (const IntSet& a)
{
x = new char[size = a.size];
for (int i = 0; i < size; i + +)
x[i] = a.x[i];
}
IntSet& IntSet :: operator= (const IntSet& a)
{
if (this! = &a)
{
this− >∼ IntSet();
x = new char[size = a.size];
for (int i = 0; i < size; i + +)
x[i] = a.x[i];
}
return *this;
}
IntSet
{
IntSet :: operator+ (const IntSet a)
for (int i = 0; i < size; i + +)
a.x[i] | = x[i];
return a;
}
27
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
IntSet IntSet :: operator* (const IntSet a)
{
for (int i = 0; i < size; i + +)
a.x[i] &= x[i];
return a;
}
IntSet IntSet :: operator ∼ ()
{
IntSet a = *this;
for (int i = 0; i < size; i + +)
a.x[i] = ∼ x[i];
return a;
}
IntSet IntSet :: operator– (const IntSet a)
{
for (int i = 0; i < size; i + +)
a.x[i] = x[i] & ∼ a.x[i];
return a;
}
bool
{
IntSet :: operator== (const IntSet a)
for (int i = 0; i < size; i + +)
if (a.x[i] != x[i])
return false;
return true;
}
bool
{
IntSet :: member(int t)
int byte = t >> 3;
char bit = (char)1 << (t & 7);
return x[byte] & bit;
}
28
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
void
{
IntSet :: print()
cout << ”{”;
for (int i = 0; i < size; i + +)
{
char bit = 1;
for (int j = 0; j < 8; j + +)
{
if (x[i] & bit)
cout << 8 ∗ i + j <<0 0 ;
bit <<= 1;
}
}
cout <<0 }0 ;
}
void
{
IntSet :: InputSet(char* N ameSet)
int e;
while(true)
{
cout << endl;
cout << ”Введите элемент (для конца введите -1) ”;
cout << N ameSet;
cout << ” = ”;
cin >> e;
if (e < 0) break;
try {insert(e); }
catch (IntSet :: SetLimit)
{cout << endl;
cout << ”Значение элемента больше допустим.”;
cout << M axElem();
}
}
}
29
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
void IntSet :: insert (int t)
{
if (t > 8 ∗ size − 1) throw SetLimit();
int byte = t >> 3;
char bit = (char)1 << (t & 7);
x[byte] |= bit;
}
Реализация инициализатора IntSet (const IntSet& a) связана с
перенесением данных из параметра a в новый экземпляр класса. Для
этого первым оператором выделяется динамическая память строки
битов с указателем на нее в поле x, а перед этим переносится размер строки битов в поле size. Второй оператор переносит данные из
строки битов зкземпляра a в создаваемый экземпляр.
Реализация оператора присваивания operator= (const IntSet& a)
должна сначала проверить, не происходит ли ненужное (ошибочное)
присваивание вида X = X; . Для этого используется указатель this на
текущий экземпляр класса (в левой части оператора присваивания).
Если его значение не совпадает с указателем &a на присваиваемое значение, то перед присваиванием данных экземпляру (которое подобно
действиям инициализации) необходимо удалить старые данные этого
экземпляра, так как они могут содержать другой размер строки битов.
С этой целью используется вызов деструктора this− >∼ IntSet(); ,
который удаляет текущий экземпляр класса.
При реализации операции operator+ (const IntSet a) объединения множеств используется тот факт, что второй объект-множество a
объявлен константным. Он не может быть изменен, и потому изменяется копия этого объекта, которая образуется при передаче параметра
по значению. Операция a.x[i] | = x[i]; производит логическое сложение каждого байта строки символов этой копии с соответствующим
байтом текущего экземпляра класса. После этого возвращается значение полученной копии объекта, что и требуется.
Аналогична реализация оператора operator* (const IntSet a) пересечения множеств за исключением того, что производится операция
логического умножения a.x[i] & = x[i]; .
Реализация оператора operator– (const IntSet a) разности множеств также аналогична за исключением того, что производится опе30
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
рация логического умножения a.x[i] & =∼ x[i]; .
При реализации дополнения оператором operator ∼ (); объявляется объект a, который инициализируется текущим объектом. Затем
каждый байт его строки битов заменяется на дополнение соответствующего байта текущего объекта и значение объекта a возвращается.
При реализации функции member(int t) определяется номер байта byte делением параметра t на 8 (сдвигом на 3 разряда вправо) и
кодом bit из нулей и единиц сдвигом единицы (кода 00000001) влево
на число разрядов, равных остатку от деления t на 8 (выделение последних 3 разрядов t). Значение бита в байте строки битов с номером
byte для текущего объекта, который соответствует единице в байте
bit, определяет принадлежность (1) или непринадлежность (0) элемента с номером t множеству текущего объекта, что и возвращается
выражением x[byte] & bit.
При реализации метода print () вывода множества номер t каждого
элемента разложен на его координаты i и j строки битов (i – номер
байта в строке и j – номер бита в этом байте) так, что t = 8 · i + j.
Переменная bit – это байт, в котором единица соответствует номеру
j, и потому элемент t принадлежит множеству т. и т. т., когда код
x[byte] & bit отличен от нулевого.
При реализации метода insert (int t) вставки элемента t в множество проверяется допустимость такого элемента, и если он недопустим,
то выполняется вызов исключения throw SetLimit();. При допустимости элемента его номер раскладывается, как и в методе member, на
номер байта byte и положения бита в этом байте bit, после чего добавляется в байт строки битов с этим номером оператором x[byte] |= bit; .
Реализация метода InputSet(char* N ameSet) ввода множества
связана с вводом в любом порядке в цикле элементов множества до
тех пор, пока не будет введено отрицательное значение, и попыткой
добавить этот элемент в множество. Эта попытка выполняется конструкцией try {insert(e); }. Если при этом возникнет исключительная
ситуация (превышение предела для элементов множества), то будет
вызван обработчик этого исключения catch (IntSet :: SetLimit), который выдаст на экран сообщение:
“Значение элемента больше допустим. <знач.макс.элем.>”.
31
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
3.4
Пример программы проверки утверждения
для множеств
Для следующего утверждения для множеств (методические указания «Множества»)
X1 ∩ X2 ∩ X3 = ∅ и X1 ∪ X2 ∪ X3 = U ↔ (X2 \ X3 ) ∪ (X1 \ X2 ) = X1 ∪ X 3
разработать программу проверки этого утверждения с помощью тестов для множеств из целочисленных неотрицательных элементов.
Как и в тех методических указаниях, введем обозначения A = (X2 \
X3 ) ∪ (X1 \ X2 ); B = X1 ∪ X 3 . Также введем обозначения C = X1 ∩
X2 ∩ X3 и D = X1 ∪ X2 ∪ X3 . Тогда в этих обозначениях утверждение
для множеств запишется следующим образом:
C = ∅ ∧ D = U ↔ A = B.
Учитывая, что тесты в методических указаниях «Множества» приведены для множеств из натуральных чисел, а не из целых неотрицательных чисел, изменим их.
Тесты
1) Выполнение условий X1 = {0, 1, 2, 3, 4}; X2 = {1, 2, 5, 6, 7};
X3 = {3, 6, 7, 8}
U = X1 ∪ X2 ∪ X3 = {0, 1, 2, 3, 4, 5, 6, 7, 8}
X1 ∩ X2 ∩ X3 = ∅
A = {0, 1, 2, 3, 4, 5}; B = {0, 1, 2, 3, 4, 5}
A=B
2) Невыполнение первого условия
X1 = {0, 1, 2, 3, 4}; X2 = {1, 2, 5, 6, 7};
U = X1 ∪ X2 ∪ X3 = {0, 1, 2, 3, 4, 6, 7, 8}
X1 ∩ X2 ∩ X3 = {2}
A = {0, 1, 3, 4, 5}; B = {0, 1, 2, 3, 4, 5}
A⊂B
X3 = {2, 3, 6, 7, 8}
3) Невыполнение второго условия
X1 = {0, 1, 2, 3, 4}; X2 = {2, 3, 6, 7, 8}; X3 = {4, 7, 8}
U = {0, . . . , 8} 6= X1 ∪ X2 ∪ X3 = {0, 1, 2, 3, 4, 6, 7, 8}
X1 ∩ X2 ∩ X3 = ∅
A = {0, 1, 2, 3, 4, 6}; B = {0, . . . , 6}
A⊂B
32
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
В программе, приведенной ниже, используются директивы включения потока ввода/вывода и класса IntSet.
#include <iostream.h>
#include “intset.h”
int main ()
{
int sz;
//буфер размера множества
int e;
//буфер элемента множества
cout << ”Введите размер универсального множества U = ”;
cin >> sz;
IntSet O(sz), U = O;
//пустое и универс.множ.
IntSet X1(sz), X2(sz), X3(sz); //исход.множества X1, X2, X3
/ ∗ ∗ ∗ ввод элементов множеств ∗ ∗ ∗ /
X1.InputSet (”X1”);
X2.InputSet (”X2”);
X3.InputSet (”X3”);
/ ∗ ∗ ∗ Образование множеств утверждения ∗ ∗ ∗ /
IntSet A=(X2–X3)+(X1–X2), B=X1+˜ X3 ,
C = X1 ∗ X2 ∗ X3, D = X1 + X2 + X3;
/ ∗ ∗ ∗ вывод множеств ∗ ∗ ∗ /
cout << endl << ”Универс.множ. U = ”;
U.print();
cout << endl << ”X1 = ”;
X1.print();
cout << endl << ”X2 = ”;
X2.print();
cout << endl << ”X3 = ”;
X3.print();
cout << endl << ”A = (X2 − X3) + (X1 − X2) = ”;
A.print();
cout << endl << ”B=X1+˜ X2=”;
B.print();
33
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
cout << endl << ”C = X1 ∗ X2 ∗ X3 = ”;
C.print();
cout << endl << ”D = X1 + X2 + X3 = ”;
D.print();
/ ∗ ∗ ∗ проверка утверждения ∗ ∗ ∗ /
cout << endl;
if (C == O && D == U && A == B)
cout << endl << ”A=B истинно, т.к. C=O и D=U ”;
else
{ cout << endl << ”A=B ложно, т.к. ”;
if ( !(C == O) ) cout << endl << ”C не пусто”;
else
cout << endl << ”D не равно U ”;
}
cout << endl << endl << ”Нажмите кл. 0 и Enter ”;
cin >> e;
return 0;
}
Последние 3 строки программы необходимы для задержки завершения программы, чтобы просмотреть результаты выполнения теста.
Тестирование программы показывает полное совпадение результатов программы с ожидаемыми результатами тестов.
3.5
Программная реализация булевых функций
на языке C ++
Программная реализация булевых функций позволяет автоматизировать с помощью компьютера процесс вычисления любых булевых
выражений и проверку утверждений для множеств, которая сводится к проверке тождественной истинности соответствующих булевых
функций.
В языке C ++ булевы переменные описываются типом bool, который имеет 2 значения: true и false, а также набор логических опера34
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
ций для переменных и значений этого типа:
1. Операция отрицания обозначается символом ! перед логическим
выражением.
2. Операция конъюнкции обозначается символами && между двумя логическими выражениями.
3. Операция дизъюнкции обозначается символами || между двумя
логическими выражениями.
4. Операция импликации обозначается символами <= между двумя логическими выражениями.
5. Операция эквиваленции обозначается символами == между двумя логическими выражениями.
Приоритет отрицания ! в C ++ является наивысшим. Но следует учесть,
что конъюнкция && и дизъюнкция || в C ++ имеют одинаковый приоритет. Поэтому в некоторых случаях необходимо поставить дополнительные скобки. И хотя приоритет этих операций выше, чем для
импликации <= и эквиваленции ==, но приоритет двух последних
операций в C ++ также одинаков, что может потребовать употребления дополнительных скобок.
Для иллюстрации рассмотрим утверждение примера 1-й задачи задания 1:
X1 ∩X2 ∩X3 = ∅ и X1 ∪X2 ∪X3 = U ↔ (X2 \X3 )∪(X1 \X2 ) = X1 ∪X 3 .
Для него в задании 4 была получена булева функция:
F ≡ (y1 ∧ y2 ∧ y3 ∧ (y1 ∨ y2 ∨ y3 ) ↔ (y2 ∧ y3 ∨ y1 ∧ y2 ↔ y1 ∨ y3 )),
проверка тождественной истинности которой приводит к обоснованию
утверждения для множеств.
Для программной реализации на C ++ мы опишем булеву функцию
F , которая имеет 3 булевых параметра y1, y2, y3, соответствующие
аргументам y1 , y2 , y3 , и возвращает логическое значение выражения,
получающегося из выражения функции заменой ее аргументов на параметры и заменой логических операций на соответствующие операции языка C ++ . Получим следующее описание функции F на языке
C ++ :
35
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
bool
{
F
(bool y1, bool y2, bool y3)
return ( !(y1 && y2 && y3) && (y1 || y2 || y3) ) ==
( (y2 && !y3) || (y1 && !y2) == ( y1 || !y3 )
);
}
Главная программа проверки тождественной истинности функции
F должна произвести вычисления значения функции для каждого
набора значений аргументов. Поскольку у нас имеются 3 аргумента
функции, то можно перебрать все наборы значений аргументов, организовав 3 вложенных цикла. При этом вычисленное значение функции – логическое, и нам надо его использовать для сообщения, которое
выводится на экран.
void
{
int
bool
for
main ()
x1, x2, x3;
//arguments variable
F val = true;
//functions value
( x1 = 0; F val && x1 < 2; x1 + + )
for ( x2 = 0; F val && x2 < 2; x2 + + )
for ( x3 = 0; F val && x3 < 2; x3 + + )
{ F val = F ( x1, x2, x3 );
if (!F val)
{ cout << ”Statement is false for arguments x1=”;
cout << x1 << ”, x2=” << x2 << ”, x3=”;
cout << x3 << endl;
break; }
}
if
(F val) cout << ”Statement is true” << endl;
cout << ”Press 0 and Enter”;
cin >> x1;
}
В случае ошибки в утверждении (и соответственно ложного значения
функции) нам надо вывести сообщение об этом и прекратить дальнейшее выполнение циклов. Для этого заведем логическую переменную,
которой будем присваивать значение функции и которую используем
36
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
для управления циклами. Программа главной функции будет выглядеть следующим образом:
Перед текстами функций F и main следует написать директиву
включения стандартного потока ввода/вывода:
#include <iostream.h>
Если число аргументов проверяемой булевой функции заранее неизвестно, то таким образом написать вложенные циклы не удастся. Эту
проблему можно решить за счет цикла перебора всех наборов булевых
аргументов функции. Покажем, как это сделать на примере булевой
функции от n переменных. Пусть Y = (y1 , y2 , . . . , yn ) – массив булевых
переменных, передаваемых булевой функции в качестве аргументов.
В нашем примере мы могли бы изменить описание булевой функции
F следующим образом:
bool
{
F
(bool y[ ], int n)
return ( !(y[1] && y[2] && y[3]) && (y[1] || y[2] || y[3]) ) ==
( (y[2] && !y[3]) || (y[1] && !y[2]) == ( y[1] || !y[3] )
);
}
В программе проверки утверждения, приведенной ниже, необходимо вычислить значение булевой функции для каждого из 2n наборов
значений аргументов булевой функции. Заметим, что если каждый
из этих наборов нулей и единиц выписать подряд то он представит
некоторый n-разрядный двоичный код числа из диапазона от 0 до
2n − 1. Все же наборы, выписанные в лексикографическом порядке,
представляют собой все двоичные n-разрядные числа от 0 до 2n − 1.
Теперь в создаваемой программе достаточно вычислить константу
c = 2n , а затем в цикле по k от 0 до c по каждому числу k формировать набор аргументов булевой функции и вычислять для него значение булевой функции. В остальном программа подобна приведенной
ранее.
37
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
void
{
int
cin
longint
int
bool
main ()
n, k, m;
<< n;
c = 1; c <<= n; // c = 2n
x[n];
// array of arguments variable
F val = true;
// functions value
for ( k = m = 0; k < c; m = + + k )
{ for ( i = n − 1; i >= 0; i − − )
{ x[i] = m&1; m >>= 1; };
F val = F ( x, n );
if (!F val)
{ cout << ”Statement is false for arguments: x=”;
for (m = 0; m < n; m + +)
cout << x[m] << ’,’ << endl;
break; }
}
if (F val) cout << ”Statement is true” << endl;
cout << ”Press 0 and Enter”;
cin >> x1;
}
4
Задание 10
4.1
Общее задание
1. Для функции 2-й задачи задания 9 построить машину Тьюринга
(МТ):
a) проанализировать функцию задания и построить полный набор
тестов;
b) разработать неформальное пошаговое описание алгоритма функции задания;
c) построить функциональную таблицу МТ;
d) прокрутить каждый тест на разработанной МТ, подписывая состояние МТ под рассматриваемым символом строки.
38
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
2. Для задачи 1 задания 1 написать программную проверку ее числовыми тестами, полученными при выполнении этого задания (результатом выполнения задачи является текст программы и файл исходного модуля программы с именем, обозначенным фамилией студента с инициалами).
3. Написать на языке C ++ программу проверки тождественной истинности булевой функции, построенной в 1-й задаче задания 4 (для
проверки утверждения 1-й задачи задания 1) и показать ее выполнение на компьютере (результатом выполнения задачи является текст
программы и файл исходного модуля программы с именем, обозначенным фамилией студента с инициалами).
4.2
Пример задачи 1 и ее решения
Разработать МТ 8-разрядного сумматора неотрицательных целых чисел с разрядом переноса
Решение.
A. Анализ функции задания показывает, что исходными данными
являются 2 8-разрядных целых неотрицательных числа, а результатом вычисления (выполнения функции) – 8-разрядная сумма чисел и
значение разряда переноса. Исходные числа можно разделить символом * и таким же образом разделить разряд переноса и сумму чисел.
Примерами входной строки МТ и строки соответствующего результата для нее являются:
00000101 ∗ 00001110 → 0 ∗ 00010011 (5 + 14 = 19)
00000101 ∗ 11111101 → 1 ∗ 00000010 (5 + 253 = 258 = 256 + 2)
Анализ этих примеров показывает, что подобные тесты потребуют
очень длинного выполнения. Поэтому при разработке алгоритма будем ориентироваться на исходные данные с любым количеством разрядов (в частности, 8-разрядные), а тесты составим для 2-разрядных
чисел, что, с одной стороны, отразит достаточную общность примеров, а, с другой стороны, выполнение тестов окажется короче.
Так как набор тестов должен быть полон (проверять все ветви алгоритма и иметь как данные, являющиеся крайними случаями, так и
данные общего случая), то в тесты включим следующий набор:
39
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
1. 00 ∗ 00 → 0 ∗ 00
(оба числа наименьшие – крайний случай)
2. 11 ∗ 11 → 1 ∗ 10
(оба числа наибольшие – крайний случай)
3. 10 ∗ 01 → 0 ∗ 11
случай)
(сумма допустимая, без переноса – общий
4. 10 ∗ 10 → 1 ∗ 00
(сумма с переносом – общий случай)
B. Для разработки алгоритма сложения выберем способ, при котором первое число (назовем его a) уменьшается на 1, а второе (b)
увеличивается на 1, и это повторяется до тех пор, пока первое число
не станет равным 0. Этот способ по трудоемкости не является лучшим,
но является довольно простым, что достаточно для нашей цели.
Требуется учесть представление данных в МТ и начальное состояние и положение считывающей головки МТ – в начальном состоянии
q1 под 1-м символом. В конечном состоянии q0 также головка должна
находиться под 1-м символом. Еще одна особенность, которую следует учесть, – это возникновение переполнения – такую особенность
мы будем отмечать временной заменой символа * на какой-либо другой символ, отличный от уже имеющихся (например, на символ +).
С каждым шагом алгоритма свяжем состояние МТ, соответствующее
этому шагу.
1. Поиск символа *, разделяющего числа. Если нет, то ничего не
надо складывать – переход к останову с поиском левого символа
строки. Если есть, то проверка a = 0.
2. Проверка a = 0 (перед символом * или +, разделяющего числа,
находятся одни нули). Если имеет место, то переход к стиранию
нулей до одного из символов: * или +. Если же нет, то подготовка
к уменьшению a на 1.
3. Стирание нулей до одного из символов * или +. Дальнейшие действия зависят от этого символа: если *, то добавить перед * символ 0 (нет переполнения); если символ +, то заменить на * и
добавить перед ней 1.
4. Подготовка к уменьшению a на 1 – поиск младшего разряда a.
40
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
5. Уменьшение a на 1. Переход к поиску младшего разряда b.
6. Поиск младшего разряда b (перед пустым символом, после b).
Переход к увеличению b на 1.
7. Увеличение b на 1. Если возникнет ситуация переполнения (потребуется увеличить на 1 значение, где стоит не 0 или 1, а символ
*), то замена его на символ +.
8. Поиск символа * или +. Переход к проверке a = 0 (шаг 2).
9. На шаге 3 прочитан символ *. Добавляем 0 перед * и останов.
10. На шаге 3 прочитан символ +. Заменяем его на * и добавляем 1
перед ним, после чего останов.
11. Поиск левого символа в исходной строке и останов.
На шаге 1 переход либо к шагу 11 (прочитан пустой символ), либо к
шагу 2 (прочитан символ *).
На шаге 2 переход либо к шагу 3 (прочитан пустой символ), либо к
шагу 4 (прочитан символ 1).
В остальных случаях шаг, который не заканчивается остановом, заканчивается переходом к следующему шагу.
C. Функциональная таблица МТ:
Q\A λ
∗
q1 q11 L q2 L
q2
q3 R
q3
q9 L
q4
q5 L
q5
q6
q7 L q6 R
q7
+q2 L
q8
q2 L
q9
0q0
q10
1q0
q11 q0 R
0
q1 R
q2 L
λq3 R
q4 R
1q5 L
q6 R
1q8 L
q8 L
1
q1 R
q4 R
0q6 R
q6 R
0q7 L
q8 L
q11 L q11 L
+
Комментарий
поиск *
проверка a = 0
∗q10 L стирание нулей до * или +
q5 L поиск мл.разряда a
уменьшение а на 1
q6 R поиск мл.разряда b
увеличение b на 1
q2 L поиск символа * или +
на шаге 3 прочитан *
на шаге 3 прочитан символ +
поиск левого символа
41
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
D. Тестирование.
Тест 1.
00 ∗ 00 → 00 ∗ 00 → 00 ∗ 00 → 00 ∗ 00 → 00 ∗ 00 → 00 ∗ 00 → 00 ∗ 00 →
q1
q1
q1
q2
q2
q2
q3
→ 0 ∗ 00 → ∗00 → ∗00 → 0 ∗ 00
q3
q3
q9
q0
Тест 2.
11 ∗ 11 → 11 ∗ 11 → 11 ∗ 11 → 11 ∗ 11 → 11 ∗ 11 → 11 ∗ 11 → 10 ∗ 11 →
q1
q1
q1
q2
q4
q5
q6
· · · → 10 ∗ 11 → 10 ∗ 11 → 10 ∗ 10 → 10 ∗ 00 → 10 + 00 → 10 + 00 →
q6
q7
q7
q7
q2
q2
→ 10+00 → 10+00 → 10+00 → 11+00 → 01+00 → · · · → 01+00 →
q4
q4
q5
q5
q6
q6
→ 01 + 00 → 01 + 01 → 01 + 01 → 01 + 01 → 01 + 01 → 01 + 01 →
q7
q8
q8
q2
q4
q5
→ 00+01 → · · · → 00+01 → 00+01 → 00+00 → 00+10 → 00+10 →
q6
q6
q7
q7
q8
q2
→ 00 + 10 → 00 + 10 → 00 + 10 → 0 + 10 → +10 → ∗10 → 1 ∗ 10
q2
q2
q3
q3
q3
q10
q0
Тест 3.
10 ∗ 01 → 10 ∗ 01 → 10 ∗ 01 → 10 ∗ 01 → 10 ∗ 01 → 10 ∗ 01 → 10 ∗ 01 →
q1
q1
q1
q2
q2
q4
q4
→ 10 ∗ 01 → 11 ∗ 01 → 01 ∗ 01 → · · · → 01 ∗ 01 → 01 ∗ 01 → 01 ∗ 00 →
q5
q5
q6
q6
q7
q7
→ 01 ∗ 10 → 01 ∗ 10 → 01 ∗ 10 → 01 ∗ 10 → 00 ∗ 10 → · · · → 00 ∗ 10 →
q8
q2
q4
q5
q6
q6
42
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
→ 00∗10 → 00∗11 → 00∗11 → 00∗11 → 00∗11 → 00∗11 → 00∗11 →
q7
q8
q8
q2
q2
q2
q3
→ 0 ∗ 11 → ∗11 → ∗11 → 0 ∗ 11
q3
q3
q9
q0
Тест 4.
10 ∗ 10 → 10 ∗ 10 → 10 ∗ 10 → 10 ∗ 10 → 10 ∗ 10 → 10 ∗ 10 → 10 ∗ 10 →
q1
q1
q1
q2
q2
q4
q4
→ 10 ∗ 10 → 11 ∗ 10 → 01 ∗ 10 → . . . 01 ∗ 10 → 01 ∗ 10 → 01 ∗ 11 →
q5
q5
q6
q6
q7
q8
→ 01 ∗ 11 → 01 ∗ 11 → 01 ∗ 11 → 01 ∗ 11 → 00 ∗ 11 → · · · → 00 ∗ 11 →
q8
q2
q4
q5
q6
q6
→ 00 ∗ 11 → 00 ∗ 10 → 00 ∗ 00 → 00 + 00 → 00 + 00 → 00 + 00 →
q7
q7
q7
q2
q2
q2
→ 00 + 00 → 0 + 00 → +00 → ∗00 → 1 ∗ 00
q3
q3
q3
q10
q0
Примеры решения задач 2 и 3 задания приведены в разделах 3.4 и
3.5.
43
Copyright ОАО «ЦКБ «БИБКОМ» & ООО «Aгентство Kнига-Cервис»
Учебное издание
Рублев Вадим Сергеевич
АЛГОРИТМЫ.
Машины Тьюринга,
проверка истинности булевых функций,
эффективная реализация множеств на компьютере
(индивидуальная работа № 10 по дисциплине
«Основы дискретной математики»)
Методические указания
Редактор, корректор И. В. Бунакова
Верстка В. С. Рублев
Подписано в печать 11.02.2010 г. Формат 60×84/16.
Усл. печ. л. 2,56. Уч.-изд. л. 2,1. Тираж 80 экз. Заказ
Оригинал-макет подготовлен
в редакционно-издательском отделе
Ярославского государственного университета им. П. Г. Демидова.
Отпечатано на ризографе.
Ярославский государственный университет им. П. Г. Демидова
150000, Ярославль, ул. Советская, 14.
1/--страниц
Пожаловаться на содержимое документа