Материал: Shporochki_MLITA

С) переходит в новое внутреннее состояние.

Таким образом, работа машины определяется системой Команд Вида

Где   — внутреннее состояние машины;   — считываемый символ;   — новое внутреннее состояние;   — новый записываемый символ; D — направление движения головки, обозначаемой одним из символов L (влево), R (вправо), Е (на месте).

Пример МТ, реализующей композицию двух МТ.

Сложение двух чисел (2 и 4)

1)q₁1 -> q₂R 4) q₃1 -> q₃1R

2) q₂ -> q₀R 5) q₃ -> q₄1L

q₁ – начальное состояние; 6) q₄1 -> q₄1L

3) q₂1 -> q₃R 7) q₄ -> q_fS

q_f – конечное состояние;

Пример МТ, реализующей ветвление.

-MT генерирующие функции

…

Пример МТ, реализующей цикл.

45. Нормальные алгоритмы Маркова: определение, примеры.

Набор преобразований текста с помощью замены или подстановок.

Алфавит А { ₁ … _I }

1. ₁ ₂ –> _i ₄

2. ₁ ₁ -> ₅ ₇

Подстановки:

1) Простые 2) Заключительные

Условие остановки:

1. Больше нет элементов, к которым возможно применить подстановку.

2. Достигнута заключительная подстановка.

Примеры:

1. А  { а … я }, подстановка: к –> м

Исходное сообщение: кукуку

Сообщение полученное: мумуму

2. А  { 0,1 }подстановка: 101 -> 010

Исходное сообщение: 1010110

Сообщение полученное: 0100110

46. Определения алгоритма по Тьюрингу, Черчу и Маркову.

Тьюринг: алгоритм – то, что может быть реализовано при помощи машины Тьюринга.

Чёрч: Задача алгоритмически разрешима, если может быть разрешена с помощью частично рекурсивной функции.

Тезис Маркова: Алгоритм – то, что может быть реализовано в терминах алфавита на каком-то сообщении (строке) с помощью подстановок.

47. Вычислительная сложность алгоритма: определение. Приведите пример алгоритма, имеющего сложность o(n5).

Вычислительная сложность — понятие, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных.

Пример О(n⁵):

Поиск обратной матрицы с помощью союзной A^*

1. detA : n раз считаем минор, т.е det для матрицы порядка (n – 1) (т.е умножить)

2. A^* нужно n² раз посчитать det для матрицы (n – 1), т.е сделать (n – 1)² умноженной и каждой det умножений на (и того n умножений):

3. n² раз умножить на

4. , т.е О(n⁵)  общий результат.

48. Детерминированная и недетерминированная мт. Классы p и np - определение, связь с мт.

МТ называется детерминированной, если каждой комбинации состояния и ленточного символа соответствует не более одного правила.

Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая МТ называется недетерминированной.

– Детерминированная МТ;

К классу P относятся алгоритмы, выполняемые не более чем за полиноминальное время, и могут быть реализованы на детерминированной МТ

К классу NP относятся алгоритмы, которые можно за полиномиальное время решить на недетерминированной МТ

47. Вычислительная сложность алгоритма: определение. Приведите пример алгоритма, имеющего сложность o(n5).

Вычислительная сложность — понятие, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных.

Объём работы обычно измеряется абстрактными понятиями времени и пространства, называемыми вычислительными ресурсами.

время - количество элементарных шагов, необходимых для решения задачи

пространство - объём памяти или места на носителе данных

В качестве примера рассмотрим две процедуры: Slow со сложностью O(N^3) и Fast со сложностью O(N^2).

procedure Slow; procedure Fast; var var i,j,k: integer; i,j: integer; begin begin for i:=1 to N do for i:=1 to N do for j:=1 to N do for j:=1 to N do for k:=1 to N do Slow; {какое-то действие} end; end; procedure Both; begin Fast; end; Если во внутренних циклах процедуры Fast происходит вызов процедуры Slow, то сложности процедур перемножаются. В данном случае сложность алгоритма составляет O(N^2 )* *O(N^3)=O(N^5).

48. Детерминированная и недетерминированная мт. Классы p и np - определение, связь с мт.

МТ называется детерминированной, если каждой комбинации состояния и ленточного символа соответствует не более одного правила.

Если существует пара «ленточный символ — состояние», для которой существует 2 и более команд, такая МТ называется недетерминированной.

К классу P относятся алгоритмы, выполняемые не более чем за полиноминальное время, и могут быть реализованы на детерминированной МТ

К классу NP относятся алгоритмы, которые можно за полиномиальное время решить на недетерминированной МТ

49. Язык, распознающая грамматика, порождающая грамматика - определения.

Язык-множество слов корректной структуры(слово-последовательность символов алфавита языка)

Распознающая грамматика-алгоритм распознающий корректность слова, поданного на вход

Порождающая грамматика- алгоритм строящий все корректные слова языка.

50-51. Иерархия Хомского. Пример КЗ-грамматики. Пример КС-грамматики.

Иерархия Хомского — классификация порождающих грамматик по типам правил вывода

-свободные грамматики

Тип: -свободные грамматики

Ограничений на правило вывода нет

Тип: - контекстно зависимые грамматики

,

Тип: - контекстно свободные грамматики

,

Тип: -автоматные(регулярные) грамматики

*леволинейные(леворекурсивные)

*праволинейные(праворекурсивные)

52-53. Конечный автомат - определение. Приведите примеры НКА и ДКА.

Конечный автомат — абстрактный автомат, число возможных внутренних состояний которого конечно.

Стартовое состояние:

Промежуточные состояния:

Конечные состояния:

Допустимая цепочка: последнее состояние

НЕ допустимая цепочка: последнее состояние или чтение не закончилось вовсе

(ДКА)Конечный автомат называют детерминированным если:

1По одному символу осуществляется переход строго в одно состояние

2 Переход по пустому символу запрещен

Недетерминированный конечный автомат (НКА) является обобщением детерминированного. 

54-56. Нечеткие множества

Нечетким множеством  на универсальном множестве   называется совокупность пар (  ) где   - степень принадлежности элемента   к нечеткому множеству  .

Степень принадлежности - это число из диапазона [0, 1]. Чем выше степень принадлежности, тем в большей мерой элемент универсального множества соответствует свойствам нечеткого множества.