09.10 Нормальные алгорифмы Маркова

Как вам такое определение?

• Алгоритм — это способ однозначного сопосталения любого набора входных данных из допустимого множества соответствующему набору выходных данных

• (то есть дискретная функция почти в строго математическом понимании) спойлер: это тоже опреациональное определение

Нормальные алгорифмы Маркова

• Алфавит

• Схема (программа), состоящая из формул подстановки над словами в заданном алфавите

• Правило выполнения подстановок

Как выполняется формула подстановки α → β?

• например, БЛ → Д на слове ВОБЛА?

• а на слове БЛАБЛАКАР?

Когда заканчивается обработка входного слова? ↦ или нет сопоставлений

Как работает «пустая» подстановка вида « → β», и в чём её опасность?

Правило выполнения подстановок первое подходящее, затем сначала

Признаки алгоритмически полного формализма у НАМ (обосновать):

• однозначность
• полнота (?)
• выполнимость
• конечность (?)

• аллегирование (обпращение к данным) данное одно

• обусловленние действия каждая подстановка

• цикл заложен в правило выполнения

Практикум

Эмулятор TODO: втянуть на uneex

• См. текст по ссылке

Особенности эмулятора:

• «->» и «=>» вместо «→» и «↦»

Сюда кидать решения

• Разбор и проход вручную примера 1 и примера 3 про сортировку (нажать (загрузить в эмулятор), пройти пошагово)

  • Верно ли утверждение: схема из примера 3 сначала заменяет все «ba» на «ab», затем — все «ca» на «ac», а затем — все «cb» на «bc», после чего символы в слове оказываются отсортированными? нет

• В произвольном слове, состоящем из букв {a, b, c}, все подряд стоящие одинаковые буквы, если их больше двух, заменить одной буквой, например, aaaabbaccccccaabbb → abbacaab

  • Подсказка: сразу это сделать не выйдет сначало надо сократить до трёх

• Разбор и проход вручную примера 2

  • Дополнительный символ
  • Упреждающий останов для пустой операции

• В алфавите {a, b, c}: заменить в слове все «c» на «a», а «a» на «c»

• В алфавите {a, b} заменить последнюю a на b

  • #a->a#
    #b->b#
    a#=>b
    a*=>b
    b#->*b
    b*->*b
    *=>
    ->#

  • Маркер конца + маркер активности

• двоичное прибавление 1

• Дан алфавит A = {a, b}, входное слово P чётной длины. Стереть правую половину слова P. Пример: babbaa → bab.
  • хинт: поставьте в начало слова два разных символа-маркера, и сделайте второй более приоритетным — он доходит до конца и удаляет последнюю букву, после чего первый маркер пропускает букву и снова заменяется на два

Д/З

1. Дан алфавит A = {a, b}. Обратить входное слово P. Пример: babbaa → aabbab.

2. Дан алфавит A = {|, −}, P = |||...||−|||...||. Входное слово P представляет собой запись некоторых чисел n и m в палочной системе счисления, разделённую знаком «−». Получить запись модуля разности n и m в палочной системе счисления. Пример: |−||| → ||.

3. Дан алфавит A = {|, *, =}, P = |||...||*|||...||=. Входное слово P содержит n палочек слева от знака * и m палочек справа. В конце стоит знак =. Дописать справа от знака = nm палочек. Пример: ||*|||= → ||*|||=||||||.