Алгоритмы. Часть 2.

84. Создать нормальный алгоритм Маркова,

1. Распознающий Язык Дика Правильных СКОБОЧНЫХ выражений. Скобочные выражения получаются из первых 3х уникальных чисел в последовательности (если есть повтор, добавить, при 2-кратном повторе применить ТИПОВОЕ правило создание уникальной комбинации) переводом.

2. Провести операции над числами. Числа берутся в 1-ричной записи: 3=111, 7=1111111

   1. Вычесть с-d

   2. Сравнить a и с

   3. Умножить на 3

   4. Умножить (cmod3+2)*(dmod2+3)(Универсальным алгоритмом)

   5. Сложить с и d(только методом перегонки * на край)

Часть универсального умножения стоит как все остальные (что несколько зависит от получившейся сложности расчёта).

Машина Тьюринга. Теорема Кука.

85. (за 4 задачи)(Теорема Кука и одноименная презентация). Рассмотреть машину Тьюринга С языком a,b,c,dmod8(трехсимвольные цепочки). Свести к КНФ.

86. Пример задания языка, для распознавания которого готовится машина Тьюринга

Пример построения машины мы проведём для более скромного языка

87. Требуемая , гдеУказания:

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

s- состояния,

- координата,

- время

Логика назначения индексов: первым идет индекс посвящённый переменной, для - номер состояния, для- координата на ленте МТ, для- номер в алфавите,, присутствующий во всех наборах - всегда последний индекс, конкретно,

Координатные переменные

,

Переменные состояния

Алфавитные переменные для имеют средний индекс, отвечающий координате.

Пример машины Тьюринга, принимающей язык из двух слов 000 и 001:

Наиболее сложная под-коньюнкция отражает специфику машины Тьюринга

,

в том числе в тупиковых ситуациях

(тупиковая ситуация означает невыполнение Коньюнкции).

Логика этих индексов такова

Если , то для спасения ситуации переменные следующего щага должны принять те значения которые словлены правилом

т.е. машина должна перейти в состояние в момент,,

координата должна сместиться на величину :(в некотором смысле «»).

На ленте должен появиться символ :.

Остальные формулы базируются на конструкции типа

:

Например

или

- что означает одно единственное значение истины для одного и только одного из всего набора в первой скобке.

Действительно, за счет первой скобки

За счёт ,

Например, единственность координаты считывающей головки машины Тьюринга обеспечивает конъюнкция :

Например, за единственность координатной переменной в первый момент отвечает блок объединённых в под-Конъюнкцию дизъюнктов, находящихся во второй строке

.

и- аналогично,

,

- контролирует неизменность символа в отсутствии Каретки,

- переход в принимающее состояние на момент завершения работы.

Теория информации

(задания раздела теория информации не разрешается для непрофильных студентов к замещению заданий по другим предметам решается - их цена мала или они вовсе не оцениваются...)

1. Вычислить Энтропию

2. построить блочный код длин 2, 3 и (по указанию преподавателя)4. вычислить основные характеристики. насколько улучшился код по сравнению с неблочным вариантом

3. Вычислить Энтропию

4. построить блочный код длины 2

5. Вычислить Энтропию

6. Для сложной системы (заданной матрицей 3х3) по определению вычислить

прямым подсчётом

1. Энтропию

2. Энтропию

3. Энтропию

4. Энтропию

5. Энтропию

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

1. Вычислить то же для

2. Вычислить то же для

3. известно распределение Какая информация содержится в сообщении

   1. Имеет место событие

   2. Имеет место событие

4. Реализовать алгоритм Фано D=2 для распределения.

   2. Реализовать алгоритм Халфмана

5. для распределения .D=3

   1. Реализовать алгоритм Фано

   2. Реализовать алгоритм Халфмана

6. для распределения .D=2

   1. Реализовать алгоритм Фано

   2. Реализовать алгоритм Халфмана

7. Определить энтропию цепи а) и б)

8. Построить (для начала бинарный) код. Определить матожидание длины кода, сравнить данное значение с теоретическим пределом - с энтропией распределения.

Теория по "Теории информации".

Энтропия распределения

Энтропия сложной системы - совместного распределения двух величин

Условная энтропия

или

Формулы для условной вероятности

Р(АВ) = Р(А) Р= Р(В) Р

Переход от одной условной вероятности к другой можно

Р=

Доп.раздел

Вопросы по линейной алгебре

15. (0,4)Решить систему линейных уравнений методом Гаусса ,

16. (0,4 с проверкой) Методом Гаусса обратить матрицу , основываясь на этом решить две системыи, результат проверить подстановкой.

17. Посчитать определитель (объём) методом Гаусса

    1. (0,33задачи), б)(0,25 задачи)

18. Решить модель Леонтьева (найти матрицу перевода вектора конечного вектор выпуска и) с матрицей затрат и вектором конечного потребленя, найти вектор выпуска. Предполагается, что все числаabcdвзяты в стандартном представлении. Для обращения матриц использовать а) ряд, аналогичный ряду геометрической прогрессии б) стандартный метод Гаусса.

20.