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