Тема 7.9 Достижимость вершин в орграфе.

 

Вершина А достижима из вершины В, если существует путь от В до А.

Для ориентированного графа Г вводят матрицу достижимости, следующего вида:

где , если вершина достижима из вершины и , если не достижима.

 

Считается, что вершина достижима сама из себя, т.е. элементы главной диагонали матрицы достижимости равны 1.

Раздел 8. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ.

Тема 8.1 Определение класса финитно-поставленных задач.

 

Класс однотипных задач называется классом финитно-поставленных задач, если существует конечный алфавит А, словами которого можно закодировать условие и ответ любой задачи этого класса.

Класс финитно-поставленных задач можно свести к задаче вычисления значений некоторой функции на множестве N.

Пусть f(n) определена на N, закодируем все слова с помощью конечного алфавита А={а₁, …а_n} следующим образом: берем каждый символ и ставим ему в соответствие его порядковый номер.

, тогда если - слова, то

где р – все простые числа

При этом натуральное число является кодом, если оно делиться на все простые числа, начиная с 2 и заканчивая этим числом. Тогда если к – некоторый класс финитно-поставленных задач и существуют конечные алфавиты, словами которого можно закодировать условие и ответ, то задача сводиться к определению кода на множестве N.

Общий метод решения задач в данном случае имеет вид:

Задача → кодируем условие на N()→ вычисляем ()→ декодируем ответ.

Функция - называется кодовой.

Тема 8.2 Машины Тьюринга.

 

Будем считать, что машина Тьюринга имеет ленту (магнитную, печатную и т.д.), которая бесконечна в обе стороны и разбита на участки называемые ячейками. Имеется считывающее устройство и существует механизм, который передвигает это устройство, как вправо, так и влево. Дан конечный алфавит А, следующего вида:

, где - пустой знак

В каждую ячейку машина может печатать только один знак. Алфавит А называется внешним алфавитом машины.

Считаем, что машина может находиться в одном из конечного числа состояний: . Состояние Q – называется внутренним алфавитом машины, где - пассивное состояние машины, а все остальные состояния называются активными состояниями машины.

В каждый момент времени t считывающее устройство видит только одну ячейку и при этом на ленте конечное число знаков (не пустых символов).

Если в момент времени t машина находиться в состоянии и обозревает ячейку , то называется локальной информацией машины.

Участок между непустыми символами - называется глобальной информацией машины.

Машина делает 4 операции:

1. переход от состояния к состоянию - называется сменой состояния

2. смена обозреваемого значка: в

3. считывающее устройство передвигается на одну ячейку вправо (П)

4. считывающее устройство передвигается на одну ячейку влево (Л)

Работа машины заключается в следующей последовательности шагов:

1. смена обозреваемого значка и смена состояния: ;

2. машина меняет состояние и двигается на одну ячейку вправо: ;

3. машина меняет состояние и двигается на одну ячейку влево: ;

Выполнение этих шагов осуществляется под действием команды (приказы), которые зависят от настоящей ситуации.

Множество приказов обозначается: и называется программой машины.