ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 5526
Скачиваний: 27
36
Если задано некоторое слово и нами выбрана буква, являющаяся его
обозначением (именем), то будем ставить между ними знак равенст-
ва «=». Обращаясь к нашему примеру, мы можем написать: для сло-
ва R = «система» слово P = «тема» является вхождением.
Марковской подстановкой называется операция над словами,
задаваемая с помощью пары слов (P, Q) и заключающаяся в сле-
дующем. Если задано исходное слово R, то в нем находят первое
вхождение P (если таковое имеется) и, не изменяя остальных частей
слова R, заменяют в нем это вхождение словом Q. Полученное слово
и есть результат применения марковской подстановки (P, Q) к слову
R. Если же нет первого вхождения слова P в слово R (при этом нет
вообще ни одного вхождения P в R), то считается, что марковская
подстановка неприменима к слову R.
Частными случаями марковских подстановок являются ( , Q),
(P, ) и ( , ). В первом из этих примеров P, во втором Q, а в третьем
и P, и Q являются пустыми словами. В табл. 2.6 приведены некото-
рые примеры преобразования слов с помощью марковских подста-
новок.
Таблица 2.6 – Примеры марковских подстановок
N
п/п
Преобразуемое
слово
Марковская под-
становка
Результат
1 192375923
(923,
0000)
1000075923
2
Функция
( , )
Функция
3
Паровоз
(овоз, )
Пар
4
Слово
( , )
Слово
5
Слово
(ра, да) (результата нет)
Будем рассматривать слова в некотором алфавите А. Предпо-
ложим, что символы «
→» и «→•» не являются буквами в А. Записи
P
→Q и P→•Q будем называть записями марковской подстановки (P,
Q), причем первую из них будем называть подстановкой, а вторую
– заключительной подстановкой. Эти записи будем называть
формулами, различая в них левую часть P и правую часть Q.
Записью нормального алгорифма в алфавите А называется
столбец формул, левые и правые части которых являются словами в А.
Выполнение нормального алгорифма
A
применительно к исходному
данному R, являющемуся словом в А, заключается в следующем.
37
Двигаясь по столбцу формул, ищут первую формулу, левая
часть которой входит в преобразуемое слово. Если такой формулы
не найдется, то процесс окончен. Если же она найдется, то выпол-
няют марковскую подстановку, соответствующую данной формуле.
Затем смотрят, является ли выполненная подстановка заключитель-
ной. Если да, то процесс окончен, и результат переработки слова R
посредством алгорифма
A
обозначается через
A
(R). Если нет, то
весь процесс повторяют с самого начала.
Пусть B является расширением алфавита A. Нормальный алго-
рифм в B, который слова в A, если он к ним применим, перерабатывает
в результаты, являющиеся словами в A, называется нормальным алго-
рифмом над A. В некоторых случаях построение алгорифма над A го-
раздо легче, чем построение нормального алгорифма в A.
Рассмотрим пример нормального алгорифма. Мы уже показы-
вали, как можно для функции
s(x) = x + 1
построить машину Тьюринга. В качестве алфавита A возьмем
перечень арабских цифр, то есть
A = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}.
Нормальный алгорифм будем строить не в A, а над A, добавив
к A еще две буквы: x и y. Для экономии места столбец формул на-
шего искомого нормального алгорифма запишем в виде четырех
подстолбцов:
0y
→• 1
8y
→• 9 x5 → 5x 3x → 3y
1y
→• 2
9y
→ y0 x6 → 6x 4x → 4y
2y
→• 3
y
→• 1 x7 → 7x 5x → 5y
3y
→• 4
x0
→ 0x x8 → 8x 6x → 6y
4y
→• 5
x1
→ 1x x9 → 9x 7x → 7y
5y
→• 6
x2
→ 2x 0x → 0y 8x → 8y
6y
→• 7
x3
→ 3x 1x → 1y 9x → 9y
7y
→• 8
x4
→ 4x 2x → 2y → x
Если бы этот алгорифм мы применили к исходному слову R –
пустому, то получили бы слова: x, xx, xxx, ... , т.е. бесконечный про-
цесс. Это означает, что к пустому слову данный алгорифм неприме-
38
ним.
Рассмотрим его применение к слову R = 299.
Применение алгорифма к этому слову даст промежуточные ре-
зультаты: x299 (в силу последней строки), 2x99, 29x9, 299x (в силу
строк, расположенных в конце второго и начале третьего подстолб-
цов), 299y (в силу предпоследней формулы), 29y0, 2y00 (в результа-
те двукратного применения второй формулы второго подстолбца), и
приведет к искомому результату 300 (в силу третьей формулы алго-
рифма). Итак, мы получили S(299) = 300, что и требуется.
Мы определили понятие нормального алгорифма в алфавите A
и нормального алгорифма над A. Одноместная частичная словарная
функция F (R), заданная в алфавите A, называется нормально вы-
числимой, если существует нормальный алгорифм
A
над алфави-
том A такой, что для каждого слова R в алфавите A выполнено ра-
венство F(R) =
A
(R).
В частности, алгорифм со схемой
Λ →• Λ вычисляет функцию
F(R)=R, а алгорифм со схемой
Λ → Λ вычисляет нигде не опреде-
ленную функцию.
Доказана следующая общая
Теорема. Класс нормально вычислимых частичных функций,
заданных в произвольном алфавите A, совпадает с классом всех
одноместных частично рекурсивных словарных функций в алфави-
те A.
Аналогом тезиса Черча для нормальных алгорифмов является
следующий принцип нормализации А.А. Маркова: всякий алго-
ритм в алфавите A вполне эквивалентен относительно A некото-
рому нормальному алгорифму над A.
Нормальные алгорифмы оказались удобным рабочим аппара-
том во многих исследованиях, требующих точного понятия алго-
ритма, особенно тогда, когда основные объекты рассмотрения име-
ют неарифметическую природу и допускают удобное представление
в виде слов в некоторых алфавитах.
2.5
Задачи
и
упражнения
1.
Если значения примитивно-рекурсивной, общерекурсивной или
частично рекурсивной функции изменить лишь на конечном
39
множестве точек, то будет ли новая функция снова соответствен-
но примитивно-рекурсивной или частично рекурсивной?
2.
Покажите, что примитивно-рекурсивна каждая
а) конечная совокупность чисел;
б) совокупность чисел вида a * n + b, n = 0, 1, 2, ...;
в) совокупность чисел вида a * b
n
, n = 0, 1, 2, ... .
3.
Составьте программу машины Тьюринга, складывающей любые
два натуральных числа n
1
и n
2
, представленные на ленте двумя
сериями из n
1
+ 1 и n
2
+ 1 единиц, разделенных ячейкой, в кото-
рой записан символ 0. (Результатом вычисления считается число
единиц в выражении, написанном на ленте после окончания вы-
числения.) В начальном состоянии головка считывает первый
символ 1.
4.
Составьте программу машины Тьюринга, проверяющей истин-
ность равенства x = 0.
5.
Составьте программу машины Тьюринга, сдвигающей головку
влево на следующий массив чисел.
6.
Составьте программу машины Тьюринга, уменьшающей данное
число на единицу.
7.
Используя понятие композиции машин Тьюринга и программы
машин, решающих задачи 5 и 6, постройте программу машины,
сдвигающей головку влево на следующий массив единиц, изо-
бражающий некоторое число, и уменьшающей это число на еди-
ницу.
8.
Постройте нормальные алгорифмы Маркова для вычисления
простейших числовых функций: функции - константы, функции
тождества.
40
3
ЭЛЕМЕНТЫ
КОМБИНАТОРНОГО
АНАЛИЗА
Целый ряд математических моделей процессов управления
представляет собой дискретные модели комбинаторного типа. Так,
например, комбинаторные методы используются для решения
транспортных задач, в частности задач по составлению расписаний;
для составления планов производства и реализации продукции и т.д.
Исследование таких моделей и методов их решения относится к об-
ласти комбинаторного анализа.
Что же изучают в комбинаторном анализе и какие типы задач
решают? Рассмотрим для начала несколько задач.
1.
Поступающий в ТУСУР должен сдать три экзамена при
пятибальной системе оценок. Для поступления достаточно набрать
13 баллов. Сколькими способами он может сдать экзамены (разуме-
ется, не получив ни одной двойки)?
2.
Как отыскать кратчайший путь для почтальона, обязанно-
го обслуживать заданное число населенных пунктов? Расстояние
между каждой парой пунктов известно.
3.
Сколько ферзей или других шахматных фигур достаточно,
чтобы они держали под боем все клетки шахматной доски? Сколь-
кими способами они могут быть расставлены?
4.
На сколько частей делят пространство
n
плоскостей, из
которых никакие четыре не проходят через одну и ту же точку, ни-
какие три не проходят через одну и ту же прямую и никакие две не
параллельны, а любые три плоскости имеют общую точку?
Общим во всех этих задачах является то, что в них рассмат-
риваются дискретные (составленные из отдельных, обособленных
элементов) множества. Эти множества в большинстве случаев ко-
нечны, но могут быть и бесконечными, составленными из неограни-
ченно большого числа элементов.
Задачи комбинаторного анализа можно разбить на три класса:
а) задачи о количестве решений, то есть о числе дискретных
построений, удовлетворяющих поставленным условиям, или пере-
числительные задачи;
б) задачи, решающие вопрос о существовании или несущест-
вовании конфигурации, удовлетворяющей условиям, то есть о нали-
чии или отсутствии решения;