09.15 Элементы теории алгоритмов

Семинар

TODO многовато!

:)) Понятие применимости алгоритма. К чему применим алгоритм?

:)) Понятия области применимости и порождаемого множества (TODO как оно называется на на лекциях?)

:)) Пример алгоритма в алфавите {a, b}, применимого ко всем словам.

:)) Пример алгоритма в алфавите {a, b}, применимого не ко всем словам, только к некоторым.

:)) Понятие эквивалентности алгоритмов как совпадения их ОП и отображения ОМ на ПМ

:)) Пример двух неэквивалентных НАМ-схем

:)) Пример двух эквивалентных НАМ-схем, актуальные (работающие) правила которых отличаются

Запись алгоритма. Введём три дополнительных символа — «знак замены», «знак финальной замены» и «знак разделителя».

Алгоритм называется самоприменимым, если он применим к собственной записи.

:)) Самоприменим ли этот алгоритм? А если переставить местами правила?

:)) Формулировка и принцип доказательства теоремы о неразрешимости проблемы останова (от противного с помощью композиции и самоприменимости)

Практикум

:)) Понятие композиции алгоритмов терминах применимости.

:)) Области применимости и порождаемые множества для P, Q и P(Q)

Композиция двух машин Тьюринга P и Q

Композиция двух машин Тьюринга P и Q

  1. переименовать состояния (например, в Q);
  2. объединить таблицы;
  3. все заключительные состояния P заменить на начальное состояние Q.

Пирмер:

Ветвление двух машин Тьюринга P и Q

Машина P обрабатывает входное слово таким образом, что часть переходов в заключительное состояние (назовём «истина»-переходами) соответствуют ситуации, когда входное слово отвечает некоторому условию, а оставшиеся («ложь»-переходы) — когда не отвечает. Такая машина называется проверкой условия. Входное слово при этом не изменяется.

Если ∃ машина Q, предназначенная для обработки «истина»-переходов

  1. переименовать состояния (например, в Q);
  2. объединить таблицы;
  3. «истина»-переходы в P заменить на переход в начальное состояние Q

Это частный случай множественного ветвления, когда есть N классов переходов и N манимш-обработчиков Пример:

Цикл машины Тьюринга P

Если машина работает аналогичнo проверке условия, но изменяет входное слово, это шаг цикла.

  1. Некоторые переходы на конечное состояние в машине P заменяются на другое состояние qц этой машины. Состояние qц называется входом в цикл.

При этом можно выделить четыре секции цикла:

  1. Инициализация: группа (возможно, пустая) состояний, начиная с q0 , которые больше не не будут достигнуты после перехода в qц

  2. Проверка условия: группа состояний внутри цикла, вычисляющая необходимость циклического перехода (или, наоборот, выхода из цикла — тогда циклический переход будет в конце)

  3. Тело цикла: группа состояний внутри цикла, выполняющая действия, ради которых был задуман цикл

  4. Изменение: группа состояний внутри цикла, изменяющая слово там, где его будет проверять проверка условия

:)) Зачем нужны секции 0 и 3?

Пример:

Д/З

  1. Определить область применимости следующего НАМ относительно алфавита {a,b,c}: 
    a→c
b→a
cc→
c→c
  2. Из следующей схемы НАМ вычеркнуть как можно больше правил так, чтобы получившийся алгоритм был эквивалентен исходному относительно алфавита {a,b} 
    aba → aab
ba → ab
abab → aabb
ab →
  3. Составить программу для МТ, эквивалентную следующему НАМ 
    *aa->b*
*b->b*
*=>
->*
  4. Составить (методом композиции) программу для МТ, которая для данного нечётного натурального двоичного числа n на ленте записывает двоичное число m=(n+1)/2.
  5. Составить (методом цикла) программу для МТ, на алфавите {1,0,+}, которая для любой записи на ленте вида n+m, где т и n — натуральные числа в двоичной системе счисления, записывает на ленту их сумму — двоичное число.
    • Подсказка: эта довольно обширная программа собирается из программы прибавления 1, вычитания 1 и цикла.

LecturesCMC/AL/Prac/04_AlgorithmTreory (последним исправлял пользователь FrBrGeorge 2026-09-15 11:36:44)