Дискретная математика. Лекция дискретная математика. Программа это набор команд
![]()
|
Теории основы кодирования Префиксный код построен таким образом, что никакой код целиком не является началом другого кода 1.Алгоритм Фано Суть: Первый шаг: упорядочиваем коды по убыванию вероятности (снижению частоты встречаемости символов) Второй шаг: делим все коды на две группы максимально близкие по суммарной вероятности (частоте) первой группе присваиваем префикс ноль второй один Третий шаг: повторяем этот процесс далее пока можно делить ![]() 2.Алгоритм Хаффмана Первый шаг: упорядочиваем коды по убыванию вероятности (снижению частоты встречаемости символов) Второй шаг: складываем значения с наименьшими частотами(вероятностями) и опять сортируем, продолжаем этот процесс пока можем складывать. Двигаясь в обратном порядке, строим код ставим соответствия верхнему слагаемому ноль нижнему один ![]() ![]() Код Хэмминга ![]() ![]() Основы теории алгоритмов Машина Тьюринга Это абстрактная машина состоящая из бесконечной в обе стороны ленты поделенная на ячейки и головки просматривающие эти ячейки и находящимся в определенном состоянии. Алфавит символы на ленте … команда машины строится по принципу ![]() Если просматривается символ ![]() Программа это набор команд Состояние на ленте вида а1 а2 а3 Есть символ 0. А0 обычно считающийся пустым ![]() Тезис Тьюринга или основная теория основы алгоритмов Для нахождения значения функции заданной в некотором алфавите тогда и только тогда существует какой ни будь алгоритм, когда эта функция вычислима по Тьюрингу. Нормальные алгоритмы Маркова это еще одна модель Марковской подстановкой называется подстановка вида Которая работает след образ в некотором слове ищется первое вхождение под слово П которое заменяется на под слово ку заключительная подстановка п следует точка ку После заключительной подстановки работа завершается символом лямбда обозначается пустой символ ![]() ![]() ![]() ![]() ![]() |