- •Балтийский федеральный университет имени Иммануила Канта
- •Расчетно-графическая работа №1 Тема: «Системы счисления».
- •Теоретическая часть
- •Виды сигнала
- •Преобразования сигнала
- •Системы счисления
- •Правила перевода чисел из одной системы счисления в другую
- •Правила перевода целых чисел
- •Правила перевода правильных дробей
- •Правила выполнения простейших арифметических действий
- •Правила сложения
- •Правила вычитания
- •Правила умножения
- •Правила деления
- •Задание
- •Содержание отчета
- •Варианты задания
- •Список литературы
- •Расчетно-графическая работа №2
- •Теоретическая часть
- •Аддитивная (логарифмическая) мера (структурный подход)
- •1.2 Статистический подход к измерению информации
- •Примеры решения задач
- •Задание
- •Содержание отчета
- •Варианты задания
- •Список литературы
- •Расчетно-графическая работа №3
- •Теоретическая часть
- •Кодирование
- •Эффективное кодирование
- •Метод Шеннона-Фано
- •Метод Хаффмана
- •Примеры решения задач
- •Задание
- •Содержание отчета
- •Расчетно-графическая работа №4 Тема: «Разработка формальной грамматики Хомского».
- •1.2 Пример построения грамматики
- •1.3 Представление грамматики в виде графа
- •1.5 Классификация формальных грамматик
- •Примеры решения задач
- •Задание
- •Содержание отчета
- •Варианты задания
- •Список литературы
- •Расчетно-графическая работа №5 Тема: «Нормальные алгоритмы Маркова и машины Тьюринга».
- •Теоретическая часть
- •Нормальные алгоритмы Маркова
- •Машина Тьюринга
- •Примеры задач
- •Задание
- •Содержание отчета
- •Варианты задания
- •Список литературы
- •Расчетно-графическая работа №6 Тема: «Расчет числовых характеристик графов».
- •Теоретическая часть
- •Решение задач
- •Задание
- •Содержание отчета
- •Список литературы
- •Расчетно-графическая работа №7 Тема: «Нахождение кратчайшего остова неориентированного графа по алгоритму Дейкстра».
- •Теоретическая часть
- •Примеры решения задач
- •Задание
- •Содержание отчета
- •Список литературы
- •Расчетно-графическая работа №8 Тема: «Поиск кратчайших путей на неориентированном графе по алгоритму Флойда».
- •Теоретическая часть
- •Задание
- •Содержание отчета
- •Список литературы
- •Расчетно-графическая работа №9 Тема: «Архивирование файлов алгоритмом Зива-Лемпеля-Велча».
- •Теоретическая часть
- •Примеры решения задачи сжатия сообщений
- •Задание
- •Содержание отчета
- •Список литературы
Содержание отчета
Условие задачи в соответствии с вариантом.
Пошаговый подробный поиск кратчайших путей на неориентированном графе по алгоритму Флойда.
Проверка результатов расчетов по алгоритму Флойда.
Выводы.
Список литературы
Пономарев В.Ф. Дискретная математика для инженеров.- Калининград: ФГОУ ВПО КГТУ, 2010.- 351 с.
Расчетно-графическая работа №9 Тема: «Архивирование файлов алгоритмом Зива-Лемпеля-Велча».
Теоретическая часть
На сегодняшний день существует достаточно много способов архивации данных. Все они делятся на два больших, принципиально разных подхода: сжатие с потерями и без потерь. Под сжатием с потерями (или необратимым сжатием) предполагают такое преобразование входного массива данных, при котором выходной поток представляет, достаточно похожий и, возможно, даже не отличный от исходного по внешним характеристикам поток, однако, отличается от него объемом и составляющим содержимым. Примерами такого сжатия являются mp3 файлы и jpeg изображения.
Но данные алгоритмы не всегда удобны и эффективны. В некоторых случаях, например с текстом, сжатие с потерями абсолютно нецелесообразно, ибо текст – единое целое и исчезновение символов, пусть даже при уменьшении веса файла, недопустимо.
Для этого случая были разработаны так называемые алгоритмы сжатия информации без потерь данных.
Алгоритм Зива – Лемпеля - Велча (LZW) относится к алгоритмам сжатия без потерь.
История этого алгоритма начинается с опубликования в мае 1977 г. Дж. Зивом и А. Лемпелем статьи в журнале "Информационные теории". В последствии этот алгоритм был доработан А. Велчем, и в окончательном варианте отражен в статье "IEEE Computer" в июне 1984 . В этой статье описывались подробности алгоритма и некоторые общие проблемы, с которыми можно столкнуться при его реализации. Позже этот алгоритм получил название - LZW (Lempel - Ziv - Welch).
Алгоритм:
1. Создать словарь со всеми возможными односимвольными фразами. Принять за входную фразу w первый символ сообщения.
2. Считать очередной символ k из кодируемого сообщения. Если КОНЕЦ_СООБЩЕНИЯ, то выдать код и КОНЕЦ, иначе если фраза wk уже есть в словаре, присвоить входной фразе значение wk и перейти к п. 2, иначе выдать код w, добавить wk в словарь, присвоить входной фразе значение k и перейти к п 2.
Алгоритм LZW представляет собой алгоритм кодирования последовательностей неодинаковых символов. Возьмем для примера строку: "Объект TSortedCollection порожден от TCollection.".В данной строке слово "Collection" повторяется дважды. В этом слове 10 символов = 80 бит. Если мы заменим это слово, в выходном файле, во втором его включении, на ссылку на первое включение, то получим сжатие информации. Если рассматривать входной блок информации размером не более 64К и ограничить длину кодируемой строки в 256 символов, то, учитывая байт "флаг" получим, что строка из 80 бит, заменяется 8+16+8 = 32 бита. (1 байт – флаг, 2 байта – ссылка, 1 байт – длинна кодируемой последовательности). Если существуют повторяющиеся строки в файле, то они будут закодированы в таблицу. Очевидным преимуществом алгоритма является то, что нет необходимости включать таблицу кодировки в сжатый файл. Другой важной особенностью является то, что сжатие по алгоритму LZW является однопроходной операцией в противоположность алгоритму Хаффмана, которому требуется два прохода.
Плюс его: высокая степень сжатия.
Минус: сложность в реализации.