- •Г.С. Розаренов, в.А. Шаруда дискретная математика Учебное пособие
- •Воронеж 2008
- •Воронеж 2008
- •Введение
- •1. Множества
- •1.1. Основные понятия
- •Упражнения
- •1.2. Операции над множествами
- •Упражнения
- •1.3. Диаграммы Венна
- •Упражнения
- •1.4. Доказательства
- •Упражнения
- •1.5. Векторы, прямые произведения, проекции векторов
- •Упражнения.
- •2. Алгебра логики
- •2.1. Функции алгебры логики
- •2.2. Формулы. Реализация функций формулами
- •2.3. Эквивалентность формул. Свойства элементарных функций. Принцип двойственности
- •2.4. Разложение булевых функций по переменным. Совершенная дизъюнктивная нормальная форма
- •2.5. Полнота и замкнутость
- •2.6. Проблема минимизации булевых функций
- •Упражнения.
- •2.7. Упрощение д.Н.Ф. Тупиковые (относительно упрощения) д.Н.Ф.
- •Упражнения.
- •3. Язык логики предикатов
- •3.1. Основные понятия логики предикатов
- •3.2. Истинные формулы и эквивалентные соотношения
- •Упражнения.
- •4. Теория графов
- •4.1.Основные понятия
- •Г раф изоморфен
- •4.2. Способы задания графов
- •Матрица инцидентности (ij)
- •4.3. Операции над частями графа
- •4.4. Маршруты, пути, цепи, циклы
- •4.5. Дерево и лес
- •4.6. Сети
- •Упражнения.
- •5. Введение в теорию алгоритмов
- •5.1. Предварительные обсуждения
- •5.2. Блок-схемы алгоритмов
- •5.3. Машины Тьюринга
- •5.4. Некоторые операции над машинами Тьюринга
- •5.5. Рекурсивные функции
- •6. Автоматы
- •6.1. Определение основных понятий
- •6.2. Изоморфизм и эквивалентность автоматов
- •6.3. Сети из автоматов
- •6.4. Синхронные сети
- •6.5. Программная реализация логических функций
- •Заключение
- •394026 Воронеж, Московский просп., 14
5.2. Блок-схемы алгоритмов
Связь между шагами можно изобразить в виде графа. В рассмотренном примере это граф, изображенный на рис.5.
Такой граф, в котором вершинам соответствуют шаги, а ребрам – переходы между шагами, называют блок-схемой алгоритма. Его вершины могут быть двух видов: вершины, из которых выходит одно ребро (их называют операторами), и вершины, из которых выходят 2 ребра (их называют логическими условиями или предикатами). Кроме того, есть единственный оператор начала и единственный оператор конца, из которого не выходят ребра. Важной особенностью блок-схемы является то, что связи, которые она описывает, не зависят от того, являются ли шаги элементарными или представляют собой самостоятельные алгоритмы или блоки.
При всей наглядности языка блок-схемы, не следует переоценивать его возможности. Он достаточно груб и отражает связи лишь по управлению, а не по информации (где этому блоку брать исходные данные). Блок-схемы не содержат сведений ни о данных, ни о памяти, ни об используемом наборе элементарных шагов. В частности, если в блок-схеме нет циклов, это не значит, что нет циклов в алгоритме (они могут быть в каком-либо элементарном блоке). По существу блок-схема – удобное средство для описания детерминизма алгоритма. Условия, т.е. точки ветвления могут быть не только двоичными (да- нет; x < 5 - x 5 ), но и многозначными (x < 5; 5 x < 20; x = 20; x > 20).
В теории алгоритмов используется следующий подход: выбирается конечный набор исходных объектов, которые объявляются элементарными, и конечный набор способов построения из них новых объектов. Этот подход уже использован при обсуждении вопроса о ‘‘данных”. Уточнением понятия ‘‘данные” будем считать множества слов в конечных алфавитах. Для уточнения детерминизма используются либо блок-схемы, либо соответствующие словесные описания. Кроме того, нужно зафиксировать набор элементарных шагов и договориться об использовании памяти. После того, как это будет сделано, получится конкретная алгоритмическая модель.
Выделяются 3 основных типа универсальных алгоритмических моделей, различающихся исходными эвристическими соображениями относительно того, что такое алгоритм.
I тип связывает понятие алгоритма с наиболее традиционными понятиями математики – вычислениями и числовыми функциями. Наиболее развитая модель этого типа – рекурсивная функция;
II тип основан на представлении об алгоритме, как о некотором детерминированном устройстве, способном выполнять в каждый отдельный момент лишь весьма примитивные операции. Основной теоретической моделью этого типа является машина Тьюринга;
III тип алгоритмических моделей - это преобразование слов в произвольных алфавитах, в которых элементарными операциями являются подстановки, т.е. замены куска слова (подслова) другим словом. Примерами моделей этого типа являются канонические модели Поста и нормальные алгоритмы Маркова.
5.3. Машины Тьюринга
Основные определения:
Машина Тьюринга состоит из:
1) управляющего устройства, которое может находиться в одном из состояний, образующих конечное множество
Q={q1, q2, …, qn};
2) ленты, разбитой на ячейки в каждой из которых может быть записан один из символов конечного алфавита А={а1,…., am};
3) устройства обращения к ленте, (считывающей и пишущей головки), которое в любой момент времени обозревает ячейку ленты, в зависимости от символа в этой ячейке и состояния управляющего устройства, записывает в ячейку символ (быть может совпадающий с прежним или пустой, т.е. стирает), сдвигается на ячейку вправо или влево или остается на месте; при этом управляющее устройство переходит в новое состояние (или остается в старом). Среди состояний управляющего устройства выделены начальное состояние q1 и заключительное состояние qZ (z здесь не числовая переменная, а мнемонический знак конца). В начальном состоянии машина находится перед началом работы; попав в заключительное состояние она останавливается.
Таким образом, память машины Тьюринга – это конечное множество состояний (внутренняя память) и лента (внешняя память). Лента бесконечна в обе стороны, однако, в начальный момент времени только конечное число ячеек ленты заполнено непустыми символами, остальные ячейки – пусты, т.е. содержат пустой символ (пробел). Из характера работы следует, что в любой момент времени лишь конечное число ячеек будет заполнено непустыми символами, важна не бесконечность ленты, а ее неограниченность, т.е. возможность писать на ней сколь угодно длинные, но конечные слова. Данные машины Тьюринга – это слова в алфавите ленты; на ленте записываются и исходные данные и окончательные результаты. Элементарные шаги машины – это считывание и запись символов, сдвиг головки на ячейку вправо или влево, а так же переход управляющего устройства в следующее состояние. Детерминированность машины, т.е. последовательность ее шагов, определяется следующим образом: для любого внутреннего состояния qi и символа aj однозначно заданы:
а) следующее состояние qi
б) символ аj который нужно записать вместо аj в ту же ячейку (стирание символа – занесение пустого символа );
в) направление сдвига головки dk, обозначаемое одним из трех символов: L (влево), R (вправо), E (на месте). Это задание может описываться либо системой правил (команд), имеющих вид:
qi аj qi аj dk, (5.1)
либо таблицей, строкам которой соответствуют состояния, столбцам – входные символы, а на пересечении строки qi и столбца аj записана тройка символов qi аj dk и, наконец, блок –схемой, которую называют диаграммой перехода. В этой диаграмме, состояниям соответствуют вершины, а правилу (5.1) – ребро, ведущее из qi в q'i, на котором написано аj аj dk. Условие однозначности требует, чтобы для любого j и любого iz в системе команд (5.1) имелась одна команда, с левой частью qi аj; состояние qz в левых частях не встречается. На диаграмме переходов это выражается условием, что из любой вершины, кроме qz выходит ровно m ребер, причем на разных ребрах левые части различны; в вершине qz нет выходящих ребер.
Полное состояние машины Тьюринга, по которому однозначно определяется ее дальнейшее поведение, определяется ее внутренним состоянием, состоянием ленты (т.е. словом, записанным на ней) и положением головки на ленте. Полное состояние будем называть конфигурацией или машинным словом и обозначать тройкой символов 1qi2, где qi – текущее внутреннее состояние, 1 – слово слева от головки, 2 – слово образованное символом обозреваемым головкой и словом справа от головки, причем слева от 1 и справа от 2 нет непустых символов.
Например, конфигурация с внутренним состоянием qi , в которой на ленте записано abcde, а головка обозревает d, запишется abcqide. Стандартной начальной конфигурацией назовем конфигурацию вида q1, т.е. конфигурацию, содержащую начальное состояние, в которой головка обозревает крайний левый символ слова, написанного на ленте. Аналогично стандартной заключительной конфигурацией, называется конфигурация вида qz.
Ко всякой не заключительной конфигурации К машины Тьюринга применима ровно одна команда вида (5.1), которая переводит в конфигурацию К, это соотношение между конфигурациями обозначим К К. Если из контекста ясно, о какой машине Тьюринга идет речь, то знак Т опускают.
Если для К1 и Кn существует последовательность К1, К2,…..,Кn, такая, что К1 К2 ,….., Кn. Обозначим это К1Кn
Например, если в системе команд машины Тьюринга имеются команды:
q2 a5 q3 a4R и q2 a1L q4 a2, то
q2a5a1a2 a4q3a1a2 q4a4a2a2 и, следовательно,
q2a5a1a2q4a4a2a2.
Последовательность конфигураций К1 К2 ,….. …, Кn … однозначно определяется исходной конфигурацией К1 и полностью описывает работу машины Тьюринга, начиная с К1. Она конечна, если в ней встретится заключительная конфигурация, содержащая qz, или бесконечна в противном случае.
Пример 1. Машина с алфавитом A={1,} состояниями {q1,qz} и системой команд q11 q11R, q1 q11R из любой начальной конфигурации будет работать бесконечно, заполняя единицами ленту вправо от начальной точки.
Пример 2. Для любой машины Тьюринга, если К1 Кi Кj и Кi = Кj, последовательность К1 Кi Кj……. является бесконечной; ее отрезок Кi Кj будет повторяться (зацикливаться).
Если 1q12 1qz2 , то говорят, что машина Тьюринга перерабатывает слово 12 в слово 12 и обозначают это T(12)= 12. Для того, чтобы говорить о том, что могут делать машины Тьюринга, надо уточнить, как будет интерпретироваться их поведение и как будут представляться данные. Исходными данными машины Тьюринга считаем записанные на ленте слова в алфавите исходных данных АисхА и векторы из таких слов (словарные векторы над Аисх). Запись на ленте начальной конфигурации со словарным вектором (1,…,к) назовем правильной, если она имеет вид: 12…к (при условии Аисх), либо 12….к, где - специальный символ – разделитель, не входящий в Аисх. Для любого вектора Vисх над Аисх машина Тьюринга либо работает бесконечно, либо перерабатывает его в совокупность слов, разделенных пробелами в алфавите результатов АрезА. В ходе работы ленты могут появиться символы, не входящие в Аисх и А рез и образующие промежуточный алфавит Апр (содержащий, в частности разделитель). Таким образом:
А=АисхАпрАрез.
В простейшем случае Аисх=Арез и А=Аисх.
Пусть f- функция, отображающая множество векторов над Арез. Машина Тьюринга правильно вычисляет функцию f, если:
1. Для любых V и W, таких, что f(V)=W: q1V* qzW*, где V* и W* - правильные записи V и W.
2. Для любого V, такого, что f(V) не определена, машина Тьюринга запущенная в стандартной начальной конфигурации q1V*, работает бесконечно.
Если для f имеется машина Тьюринга, которая ее правильно вычисляет, функция f называется правильно вычислимой по Тьюрингу.
Обратно, каждой правильно вычисляющей машине Тьюринга, можно поставить в соответствие вычисляемую ею функцию. Две машины Тьюринга с одинаковым алфавитом Аисх называются эквивалентными, если они вычисляют одну и ту же функцию.
Пример 2: Если машина Тьюринга содержит команды qi aj qi ajE и qi aj qi ajdk, то заменив эти две команды одной qi aj qi ajdk, получим машину Тьюринга, эквивалентную Т. Путем таких преобразований можно в машине Тьюринга убрать все команды, содержащие Е и более того, доказывается, что:
Для любой машины Тьюринга существует эквивалентная ей машина, не содержащая Е в командах, следовательно, можно рассматривать машины, головки которых на любом шаге движутся.
Определения, связанные с вычислением функций, заданных на словарных векторах, даны с явным ‘‘запасом общности ‘‘ и имеют ввиду переработку нечисловых объектов.
Для начала рассмотрим числовые функции, отображающие N в N. Договоримся представлять натуральные числа в единичном (унарном) коде, т.е. для всех числовых функций Аисх={1} либо, Аисх={1,*} и число х представляется словом 1,…., 1=1х, состоящим из х единиц. Таким образом, числовая функция f(x1,…,xn) правильно вычислима по Тьюрингу, если есть машина Тьюринга, такая, что q11 х11 х2…1 хn qn1 y, когда f(x1,…,xn)=y, и Т работает бесконечно, начиная с q11 х11 х2…1 хn, если f(x1,…,xn) не определена.
Пример 3:
1. Сложение: Во введенном унарном представлении, сложить два числа а и b – значит, слово 1a 1b переработать в слово 1a+b, т.е. удалить разделитель и сдвинуть одно из слагаемых, скажем первое, ко второму. Это преобразование осуществляет машина T+ с четырьмя состояниями и следующей системой команд (первая команда ведена для случая, когда а=0 и исходное слово имеет вид 1b):
q1qzR
q11q2R
q21q21R
q2q31L
q11q31L
q1qzR
В этой системе команд перечислены не все сочетания состояний машины и символов ленты: опущены те, из них, которые при стандартной начальной конфигурации никогда не встречаются. Опускать ненужные команды будем и впредь, в таблицах это отмечено прочерками. Диаграмму переходов можно изобразить так:
2. Копирование (перезапись слова), т.е. переработка в . Для чисел эту задачу решает машина Ткоп, система команд которой приведена в таблице.
Таблица 19
|
1 |
|
|
0 |
q1 |
q20R |
qzR |
q1L |
q11L |
q2 |
q21R |
q3R |
q2R |
|
q3 |
q31R |
q41L |
|
|
q4 |
q41L |
|
q4L |
q10R |
С оответствующая диаграмма переходов: