Применение алгоритмов кодирования в архиваторах для обеспечения продуктивной работы в windows

1.

Алгоритмы кодирования источников,
применяемые в архиваторах
1 Монотонные коды
2 Интервальное кодирование и метод «стопка книг»

2.

1 Монотонные коды
Префиксный код множества натуральных чисел
N = {1,2,…}
мы будем называть монотонным,
если для любых i, j N, i < j,
длины соответствующих кодовых слов
li и lj
удовлетворяют неравенству li <= lj
2

3.

Унарный код
Унарный код сопоставляет числу i двоичную комбинацию вида
1i-10
пример,
унарными кодами чисел 1, 2 и 3 являются последовательности
unar(1) = 0,
unar(2) = 10
unar(3) = 110
Длина кодового слова для числа i равна
li = i
3

4.

Код Голомба
Т = 2m
Код Голомба для числа i состоит из двух частей
Первая часть – унарный код числа

Практическая работа №4

Тема: Использование алгоритмов сжатия данных

Цель: научиться работать с программами архиваторами

Средства для выполнения работы:

• информационные: теоретическая часть, лекции, раздаточный материал.

Ход работы:

1. Ознакомьтесь с теоретической частью запишите в тетрадь
2. Выполните задания практической части
3. Оформите отчет, ответьте на вопросы:

Теоретическая часть:

Характерной особенностью большинства типов данных является их избыточность. Степень избыточности данных зависит от типа данных. Например, для видеоданных степень избыточности в несколько раз больше чем для графических данных, а степень избыточности графических данных, в свою очередь, больше чем степень избыточности текстовых данных. Другим фактором, влияющим на степень избыточности является принятая система кодирования. Примером систем кодирования могут быть обычные языки общения, которые являются ни чем другим, как системами кодирования понятий и идей для высказывания мыслей. Так, установлено, что кодирование текстовых данных с помощью средств русского языка дает в среднем избыточность на 20-25% большую чем кодирование аналогичных данных средствами английского языка.

Для человека избыточность данных часто связана с качеством информации, поскольку избыточность, как правило, улучшает понятность и восприятие информации. Однако, когда речь идет о хранении и передаче информации средствами компьютерной техники, то избыточность играет отрицательную роль, поскольку она приводит к возрастанию стоимости хранения и передачи информации. Особенно актуальной эта проблема стает в случае обработки огромных объемов информации при незначительных объемах носителей данных. В связи с этим, постоянно возникает проблема уменьшения избыточности или сжатия данных. Если методы сжатия данных применяются к готовым файлам, то часто вместо термина «сжатие данных» употребляют термин «архивация данных», сжатый вариант данных называют архивом, а программные средства, которые реализуют методы сжатия называются архиваторами.

В зависимости от того, в каком объекте размещены данные, подлежащие сжатию различают:

1. Сжатие (архивация) файлов: используется для уменьшения размеров файлов при подготовке их к передаче каналами связи или к транспортированию на внешних носителях маленькой емкости;

2. Сжатие (архивация) папок: используется как средство уменьшения объема папок перед долгим хранением, например, при резервном копировании;

3. Сжатие (уплотнение) дисков: используется для повышения эффективности использования дискового просторную путем сжатия данных при записи их на носителе информации (как правило, средствами операционной системы).

Существует много практических алгоритмов сжатия данных, но все они базируются на трех теоретических способах уменьшения избыточности данных. Первый способ состоит в изменении содержимого данных, второй — в изменении структуры данных, а третий — в одновременном изменении как структуры, так и содержимого данных.

Если при сжатии данных происходит изменение их содержимого, то метод сжатия называется необратимым, то есть при восстановлении (разархивировании) данных из архива не происходит полное восстановление информации. Такие методы часто называются методами сжатия с регулированными потерями информации. Понятно, что эти методы можно применять только для таких типов данных, для которых потеря части содержимого не приводит к существенному искажению информации. К таким типам данных относятся видео- и аудиоданные, а также графические данные. Методы сжатия с регулированными потерями информации обеспечивают значительно большую степень сжатия, но их нельзя применять к текстовым данным. Примерами форматов сжатия с потерями информации могут быть:

• JPEG — для графических данных;

• MPG — для для видеоданных;

• MP3 — для аудиоданных.

Если при сжатии данных происходит только изменение структуры данных, то метод сжатия называется обратимым. В этом случае, из архива можно восстановить информацию полностью. Обратимые методы сжатия можно применять к любым типам данных, но они дают меньшую степень сжатия по сравнению с необратимыми методами сжатия. Примеры форматов сжатия без потери информации:

• GIF, TIFF — для графических данных;

• AVI — для видеоданных;

• ZIP, ARJ, RAR, CAB, LH — для произвольных типов данных.

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

• алгоритм RLE (Run Length Encoding);

• алгоритмы группы KWE(KeyWord Encoding);

• алгоритм Хаффмана.

Алгоритм RLE

В основе алгоритма RLE лежит идея выявления повторяющихся последовательностей данных и замены их более простой структурой, в которой указывается код данных и коэффициент повторения. Например, пусть задана такая последовательность данных, что подлежит сжатию:

1 1 1 1 2 2 3 4 4 4

В алгоритме RLE предлагается заменить ее следующей структурой: 1 4 2 2 3 1 4 3, где первое число каждой пары чисел — это код данных, а второе — коэффициент повторения. Если для хранения каждого элемента данных входной последовательности отводится 1 байт, то вся последовательность будет занимать 10 байт памяти, тогда как выходная последовательность (сжатый вариант) будет занимать 8 байт памяти. Коэффициент сжатия, характеризующий степень сжатия, можно вычислить по формуле:

где Vx- объем памяти, необходимый для хранения выходной (результирующей) последовательности данных, Vn- входной последовательности данных.

Чем меньше значение коэффициента сжатия, тем эффективней метод сжатия. Понятно, что алгоритм RLE будет давать лучший эффект сжатия при большей длине повторяющейся последовательности данных. В случае рассмотренного выше примера, если входная последовательность будет иметь такой вид: 1 1 1 1 1 1 3 4 4 4, то коэффициент сжатия будет равен 60%. В связи с этим большая эффективность алгоритма RLE достигается при сжатии графических данных (в особенности для однотонных изображений).

Алгоритмы группы KWE

В основе алгоритма сжатия по ключевым словам положен принцип кодирования лексических единиц группами байт фиксированной длины. Примером лексической единицы может быть обычное слово. На практике, на роль лексических единиц выбираются повторяющиеся последовательности символов, которые кодируются цепочкой символов (кодом) меньшей длины. Результат кодирования помещается в таблице, образовывая так называемый словарь.

Существует довольно много реализаций этого алгоритма, среди которых наиболее распространенными являются алгоритм Лемпеля-Зіва (алгоритм LZ) и его модификация алгоритм Лемпеля-Зіва-Велча (алгоритм LZW). Словарем в данном алгоритме является потенциально бесконечный список фраз. Алгоритм начинает работу с почти пустым словарем, который содержит только одну закодированную строку, так называемая NULL-строка. При считывании очередного символа входной последовательности данных, он прибавляется к текущей строке. Процесс продолжается до тех пор, пока текущая строка соответствует какой-нибудь фразе из словаря. Но рано или поздно текущая строка перестает соответствовать какой-нибудь фразе словаря. В момент, когда текущая строка представляет собой последнее совпадение со словарем плюс только что прочитанный символ сообщения, кодер выдает код, который состоит из индекса совпадения и следующего за ним символа, который нарушил совпадение строк. Новая фраза, состоящая из индекса совпадения и следующего за ним символа, прибавляется в словарь. В следующий раз, если эта фраза появится в сообщении, она может быть использована для построения более длинной фразы, что повышает меру сжатия информации.

Алгоритм LZW построен вокруг таблицы фраз (словаря), которая заменяет строки символов сжимаемого сообщения в коды фиксированной длины. Таблица имеет так называемое свойством опережения, то есть для каждой фразы словаря, состоящей из некоторой фразы w и символа К, фраза w тоже заносится в словарь. Если все части словаря полностью заполнены, кодирование перестает быть адаптивным (кодирование происходит исходя из уже существующих в словаре фраз).

Алгоритмы сжатия этой группы наиболее эффективны для текстовых данных больших объемов и малоэффективны для файлов маленьких размеров (за счет необходимости сохранение словаря).

Алгоритм Хаффмана

В основе алгоритма Хаффмана лежит идея кодирования битовыми группами. Сначала проводится частотный анализ входной последовательности данных, то есть устанавливается частота вхождения каждого символа, встречащегося в ней. После этого, символы сортируются по уменьшению частоты вхождения.

Основная идея состоит в следующем: чем чаще встречается символ, тем меньшим количеством бит он кодируется. Результат кодирования заносится в словарь, необходимый для декодирования. Рассмотрим простой пример, иллюстрирующий работу алгоритма Хаффмана.

Пусть задан текст, в котором бурва ‘А’ входит 10 раз, буква ‘В’ — 8 раз, ‘С’- 6 раз , ‘D’ — 5 раз, ‘Е’ и ‘F’ — по 4 раза. Тогда один из возможных вариантов кодирования по алгоритму Хаффмана приведен в таблицы 1.

Таблица 1.

Символ	Частота вхождения	Битовый код
A	10	00
B	8	01
C	6	100
D	5	101
E	4	110
F	4	111

Как видно из таблицы 1, размер входного текста до сжатия равен 37 байт, тогда как после сжатия — 93 бит, то есть около 12 байт (без учета длины словаря). Коэффициент сжатия равен 32%. Алгоритм Хаффмана универсальный, его можно применять для сжатия данных любых типов, но он малоэффективен для файлов маленьких размеров (за счет необходимости сохранение словаря).

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

Таблица 2.

Формат сжатия	Операционная система MS DOS	Операционная система Windows
Программа архивации	Программа разархивации	Программа архивации	Программа разархивации
ARJ	Arj.exe	Arj.exe	WinArj.exe	WinArj.exe
RAR	Rar.exe	Unrar.exe	WinRar.exe	WinRar.exe
ZIP	Pkzip.exe	Pkunzip.exe	WinZip.exe	WinZip.exe

Кроме того, современные архиваторы предоставляют пользователю полный спектр услуг для работы с архивами, основными из которых являются:

1. создание нового архива;

2. добавление файлов в существующий архив;

3. распаковывание файлов из архива;

4. создание самораспаковающихся архивов (self-extractor archive);

5. создание распределенных архивов фиксированного размера для носителей маленькой емкости;

6. защита архивов паролями от несанкционированного доступа;

7. просмотр содержимого файлов разных форматов без предварительного распаковывания;

8. поиск файлов и данных внутри архива;

9. проверка на вирусы в архиве к распаковыванию;

10. выбор и настройка коэффициента сжатия.

Практическая часть:

Изучить примеры форматов сжатия с потерями информации:

• JPEG — для графических данных;

• MPG — для видеоданных;

• MP3 — для аудиоданных, его конструкцию и работу.

Изучить примеры форматов сжатия без потери информации:

• алгоритм RLE (Run Length Encoding);

• алгоритмы группы KWE(KeyWord Encoding);

• алгоритм Хаффмана.

Контрольные вопросы:

1. Какие факторы влияют на степень избыточности данных?
   2. Что такое архив? Какие программные средства называются архиваторами?
   3. Почему методы сжатия, при которых происходит изменение содержимого данных, называются необратимыми?
   4. Приведите примеры форматов сжатия с потерями информации.
   5. В чем состоит преимущество обратимых методов сжатия над необратимыми? А недостаток?
   6. Которая существует зависимость между коэффициентом сжатия и эффективностью метода сжатия?
   7. В чем состоит основная идея алгоритма RLE?
   8. В чем состоит основная идея алгоритмов группы KWE?
   9. В чем состоит основная идея алгоритма Хаффмана?
   10. Какие вы знаете програми-архиваторы? Коротко охарактеризуйте их.

Требования по выполнению отчета:

1. Тема

2. Цель.

3. Выполненные задания.

4. Ответы на контрольные вопросы.

5. Вывод.

5

Другие методы кодирования

Мы
рассмотрели лишь несколько наиболее
известных алгоритмов сжатия данных,
дабы дать читателям поверхностное
представление о методах сжатия данных.
Конечно же, самих алгоритмов сжатия
разработано очень много, и их рассмотрение
не входит в задачи данной публикации.
Тем не менее при рассмотрении архиваторов
WinRAR, WinZip и 7-Zip можно встретить упоминание
о таких алгоритмах кодирования, как
PPMd, LZMA и bzip2. А потому вкратце поясним, о
чем идет речь.

Итак,
начнем с метода PPM (PPMd — это одна из
многочисленных вариаций метода PPM).

PPM
(Prediction by Partial Matching) — это алгоритм
сжатия данных без потерь, основанный
на контекстном моделировании и
предсказании (предсказание по частичному
совпадению).

Метод
PPM был предложен еще в 1984 году Клири
(Cleary) и Уиттеном (Witten) и до настоящего
времени широко используется, поскольку
является одним из наиболее эффективных
методов экономного кодирования.

В
рассмотренных нами ранее методах для
кодирования информационных сообщений
требовалось знание вероятности появления
символов. В случае если нет никакой
дополнительной информации об источнике,
определить эти вероятности можно только
путем статистического анализа его
информационной выборки. Данный принцип
лежит в основе статистических методов
экономного кодирования, к которым
относится и метод PPM.

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

Длина
контекста, применяемого при предсказании,
обычно очень ограниченна. Эта длина
обозначается N и называется порядком
контекста, или порядком модели PPM. Если
предсказание символа по контексту из
N символов не может быть произведено,
то предпринимается попытка предсказать
его с помощью контекста более низкого
порядка. Рекурсивный переход к моделям
с меньшим порядком реализуется, пока
предсказание не произойдет в одной из
моделей либо когда контекст приобретет
нулевую длину (N = 0).

Сам
алгоритм PPM лишь предсказывает значение
символа, а непосредственное сжатие
осуществляется такими алгоритмами, как
алгоритм Хаффмана или арифметическое
кодирование.

Отметим,
что алгоритм PPM имеет множество вариаций
и используется, в частности, в архиваторах
WinRAR (алгоритмы PPMd и PPMII), 7-Zip (алгоритм
PPMd) и WinZip (алгоритм PPMd).

Еще
один часто применяемый алгоритм сжатия —
это LZMA (Lempel-Ziv-Markov chain-Algorithm), который был
разработан в 2001 году и является
своеобразным вариантом алгоритма LZW. В
этом алгоритме используется метод
скользящего окна и интервального
кодирования.

Алгоритм
LZMA находит применение в архиваторах
7-Zip и WinZip.

Последний
алгоритм, о котором мы упомянем, —
это алгоритм bzip2, основанный на
преобразовании Барроуза—Уилера
(Burrows—Wheeler Transform, BWT). В алгоритме bzip2
преобразование BWT используется для
превращения последовательностей
многократно чередующихся символов в
строки одинаковых символов, а затем
применяется преобразование MTF, а в
заключение — кодирование Хаффмана.
Процесс BWT-преобразования очень прост —
он выполняется в три этапа, которые мы
рассмотрим на примере исходной
информационной последовательности
«BANAN».

На
первом этапе составляется таблица всех
циклических сдвигов входной строки. В
нашем случае из строки «BANAN» мы получим
путем циклического сдвига еще четыре
строки: «ANANB», «NANBA», «ANBAN» и «NBANA».

На
следующем этапе производится сортировка
в алфавитном порядке всех полученных
строк, включая исходную (табл.
2).
На последнем этапе мы выписываем строку,
полученную по последним символам (сверху
вниз) всех отсортированных строк. То
есть если все отсортированные строки
представить в виде матрицы, то нужная
нам строка образована последним столбцом
этой матрицы. В нашем случае получим
строку «BNNAA». Кроме того, для возможности
восстановления исходной строки по
преобразованной нам нужно запомнить
еще и номер исходной строки в отсортированном
списке строк. В нашем случае это третья
строка, поэтому результат преобразования
можно записать как BWT = («BNNAA», 3).

Важно,
что в результате BWT-преобразования все
повторяющиеся символы группируются
вместе, что очень удобно для последующего
кодирования.

Теперь
посмотрим, как сделать обратное
преобразование. Итак, мы имеем результат
преобразования в виде «BNNAA», 3.

Сначала
записываем в столбик нашу строку «BNNAA».
Затем сортируем все символы этого
столбца в алфавитном порядке. Далее,
слева от полученного столбца записываем
столбец «BNNAA» и производим сортировку
в алфавитном порядке уже всех двухсимвольных
строк. Далее дописываем к эти двум
столбцам слева опять столбец «BNNAA» и
производим сортировку в алфавитном
порядке уже всех трехсимвольных строк.
Процедуру продолжаем до тех пор, пока
строки не будут содержать по пять
символов. В отсортированной по пяти
символам матрице находим третью строку
(напомним, что номер три мы изначально
запомнили), которая и будет представлять
раскодированную последовательность
символов (табл.
3).

Как
видите, прямое и обратное BWT-преобразование
реализуется очень просто.

Итак,
мы рассмотрели наиболее важные алгоритмы
сжатия информации, которые находят
применение в современных архиваторах.
При этом мы преследовали лишь одну
цель — продемонстрировать, каким
образом можно реализовать сжатие
информации без потерь. Однако мы не
стремились к детальному рассмотрению
всех алгоритмов сжатия информации, тем
более что количество их огромно.

Ну
а теперь давайте познакомимся с тремя
наиболее популярными архиваторами,
реализующими сжатие данных без потерь
с использованием различных алгоритмов.

Тестируемые
архиваторы

WinRAR
4.2

Архиватор
WinRAR — это Windows-версия архиватора RAR.
Он предназначен для создания архивов
в форматах RAR и ZIP. Кроме того, этот
архиватор позволяет распаковывать
архивы форматов 7Z, ACE, ARJ, BZIP2, CAB, GZ, ISO, JAR,
LZH, TAR, UUE, Z.

Существует
32- и 64-разрядная версия WinRAR. В дальнейшем
мы будем рассматривать только 64-битную
версию.

WinRAR
позволяет создавать крупный архив с
дроблением его на части (тома) заданного
размера. Это очень удобно, когда необходимо
передать большой объем данных через
файлообменные серверы в Интернете,
большинство из которых обладают
ограничением по размеру одного
передаваемого файла. Кроме того, можно
использовать архивацию без сжатия,
когда множество файлов и папок объединяются
в один общий файл (архив). Данный способ
часто используется для повышения
скорости копирования, поскольку один
архивный файл будет копироваться гораздо
быстрее, чем множество отдельных файлов.

Среди
функций WinRAR также стоит выделить
возможность создания самораспаковывающихся
SFX-архивов, распаковать которые можно
без всяких архиваторов. Кроме того,
пользуясь WinRAR, можно надежно защитить
содержимое архива от свободного просмотра
и распаковки с помощью пароля.

WinRAR
также имеет встроенную командную строку,
что очень удобно при написании различных
скриптов.

При
архивации WinRAR позволяет выбрать один
из пяти вариантов сжатия (Store, Fastest, Fast,
Normal, Good, Best). Вариант Store подразумевает
отсутствие сжатия, а вариант Best —
максимальную степень сжатия, но и
максимальное время архивации.

Архиватор
WinRAR является платным.

WinZip
17

Архиватор
формата ZIP (PKZIP) был первоначально создан
для MS-DOS в 1989 году компанией PKWare и сегодня
является одним из самых распространенных.
Версия WinZip появилась в 1990-м как коммерческий
графический интерфейс для PKZIP.

В
мае 2006 года корпорация Corel объявила о
приобретении WinZip Computing.

В
конце 2012-го компания WinZip Computing (подразделение
компании Corel) представила новую
русифицированную версию приложения
WinZip 17, которая оптимизирована для
многоядерных процессоров и поддерживает
возможность использования вычислительных
мощностей графических процессоров,
встроенных в процессоры Intel Core третьего
поколения, процессоры AMD A-Series APU, а также
дискретные графические карты AMD Radeon и
NVIDIA GeForce.

Архиватор
WinZip 17 является 64-битным и позволяет
создавать архивы в форматах ZIP и ZIPX, а
также распаковывать архивы форматов
7Z, RAR, BZIP2, LHA/LZH, CAB, ISO и других (каких именно,
в документации не уточняется).

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

Естественно,
WinZip 17 позволяет создавать архив с
дроблением его на тома заданного размера.
Кроме того, можно использовать архивацию
без сжатия, когда множество файлов и
папок объединяются в один общий файл
(архив).

Кроме
того, поддерживается возможность
шифрования архива (128- и 256-битное
AES-шифрование).

При
архивации WinZip позволяет задать уровень
компрессии и алгоритм сжатия. Для формата
ZIPX можно выбрать алгоритм PPMd, LZMA или
bzip2, которые обеспечивают очень высокую
степень сжатия. Кроме того, имеется
вариант, называемый Best Method, предусматривающий
максимальную степень сжатия. При выборе
данного метода архиватор сам выбирает
оптимальный алгоритм сжатия, обеспечивающий
максимальную степень компрессии, в
зависимости от типа файла.

Также
отметим, что WinZip не имеет встроенной
командной строки, однако в случае ее
необходимости можно скачать дополнение
WinZip Command Line Support Add-On Version 3.2, которое
обеспечивает работу с командной строкой.

Архиватор
WinZip является платным.

7-Zip
9.30

В
отличие от архиваторов WinRAR и WinZip,
архиватор 7-Zip абсолютно бесплатный.
7-Zip — это программное обеспечение с
открытым кодом, при этом большая часть
исходного кода находится под лицензией
GNU LGPL.

Существует
как 32-, так и 64-битная версии этого
архиватора. Текущей версией, появившейся
в конце 2012 года, является версия 9.30.

Архиватор
7-Zip имеет удобный графический интерфейс,
но при этом поддерживает работу с
командной строкой.

Основным
форматом для архиватора 7-Zip является
собственный формат 7Z с компрессией
LZMA. Кроме того, 7-Zip позволяет производить
архивирование/разархивирование в
форматах ZIP, GZIP, BZIP2 и TAR. Также поддерживается
разархивирование форматов ARJ, CAB, CHM,
CPIO, DEB, DMG, HFS, ISO, LZH, LZMA, MSI, NSIS, RAR, RPM, UDF, WIM,
XAR и Z.

Как
утверждает производитель, архиватор
7-Zip обеспечивает степень сжатия выше,
чем RAR, за исключением мультимедийных
данных. Более того, считается, что по
степени сжатия 7-Zip уступает только
архиваторам PAQ и его GUI-модификации KGB,
которые, однако, имеют на порядок большее
время сжатия.

Для
форматов ZIP и GZIP архиватор 7-Zip предлагает
сжатие, которое на 2-10% лучше, чем
предоставляемое архиваторами PKZip и
WinZip

Программа
поддерживает работу на 64-битных
операционных системах. Интерфейс
программы переведен на множество языков,
включая русский.

Отметим,
что архиватор позволяет создавать
самораспаковывающиеся архивы для
формата 7z. Кроме того, поддерживается
шифрование AES 256-бит.

Естественно,
архиватор 7-Zip (как WinZip и WinRAR) интегрируется
в проводник Windows и доступен через
контекстное меню.

Еще
одна особенность заключается в том, что
в архиваторе 7-Zip предусмотрен плагин
для FAR Manager.

Для
своего родного формата 7z архиватор
позволяет выбрать уровень сжатия (без
сжатия, «Скоростной», «Быстрый»,
«Нормальный», «Максимальный», «Ультра»),
а также задать алгоритм сжатия (LZMA2,
LZMA, PPMd, BZip2).

Кроме
того, дополнительно можно задать размер
словаря, размер слова, размер блока и
число потоков.

Также
поддерживается создание архивов,
разбитых на тома заданного размера.

Соседние файлы в папке 1

• #
• #

ДЕПАРТАМЕНТ
ОБРАЗОВАНИЯ ГОРОДА МОСКВЫ

Государственное
бюджетное профессиональное образовательное учреждение

города
Москвы

«Политехнический
техникум № 47 имени В.Г. Федорова»

(ГБПОУ
ПТ № 47)

Контрольно
— оценочный материал

  Специальность:  09.02.02 
 Компьютерные сети (базовая подготовка)

Учебная
дисциплина:          Основы теории информации

Группа:
1КС11

Курс:       
1

Семестр: 
2

Контрольное
мероприятие: дифференцированный зачет

Преподаватель:
Дементьев А.В.

Москва
2017

СОГЛАСОВАН На заседании цикловой комиссии общепрофессиональных и профессиональных дисциплин	Разработан на основе Федерального государственного образовательного стандарта среднего профессионального образования по специальности 09.02.02 Компьютерные сети (базовая подготовка)
	Протокол № 1 от «30» августа 2017г.
	Председатель Цикловой комиссии _____________ Власова Л.А.	РСП по УМР ___________ Косенко  Ю.В.

ПОЯСНИТЕЛЬНАЯ
ЗАПИСКА

Дисциплина                  Основы
теории информации

Курс                             1

Группа       
                   1КС11

Дисциплина  Основы
теории информации  изучается на 1 курсе во 2 семестр по специальности 09.02.02
Компьютерные сети (базовая
подготовка),

максимальная
нагрузка по дисциплине 153 час., из них обязательная аудиторная
учебная нагрузка 68 час., самостоятельные работы обучающегося  51
час.

Цели
и задачи зачета – проверка освоенных знаний и умений.

Содержание
вопросов к зачету разработано для проверки знаний обучающихся 1 курса по
материалу программы данной дисциплины по темам:   

Тема Смысл энтропии Шеннона.

Тема Сжатие
информации

Тема Арифметическое
кодирование

Тема  Стандарты
шифрования данных. Криптография.

Время,
отводимое на выполнение зачета 90 минут. 

Зачет – самостоятельный труд
студента,  который способствует углублённому изучению пройденного материала.

Цель зачета:

Промежуточный контроль, измерение
уровня знаний и умений и определение степени компетентности студента;

Основные задачи зачета:

1) закрепление полученных ранее
теоретических знаний;

2) выработка навыков самостоятельной
работы;

3) выяснение подготовленности
студента к будущей практической работе.

При подготовке
к Зачету следует использовать учебные материалы только в следующем порядке:
лекционный материал, результаты практических и лабораторных работ, учебные и методические
материалы, разработанные учебным заведением, указанная преподавателем основная и
дополнительная литература и, наконец, интернет источники. Ответы на вопросы
должны быть конкретны, логичны,  соответствовать теме, содержать выводы,
обобщения и показывать собственное отношение к проблеме, где это уместно.

Требования к содержанию ответов на вопросы зачета

Основная
часть ответов на вопросы должна содержать основные определения, обоснования и
доказательства, описание методики расчёта (формулы), а также иметь ссылки на
используемые источники информации. Материал работы и ее отдельные положения
должны быть взаимосвязаны. Основная часть может также включать анализ теории
вопроса по теме Зачета. Здесь же приводятся исходные данные и значения
параметров в соответствии с вопросами Зачета. После этого излагается ход
рассуждений, описывается последовательность расчётов, приводятся промежуточные
доказательства, выводы и обоснования.

При
необходимости в конце приводится список использованных источников информации.

В
содержании ответа необходимо показать знание рекомендованной литературы по
данной теме, но при этом следует правильно пользоваться первоисточниками,
избегать чрезмерного цитирования. При использовании цитат необходимо указывать
точные ссылки на используемый источник: указание автора (авторов), название
работы, место и год издания, страницы.

Порядок выполнения зачетных заданий

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

Излагая
вопрос, каждый новый смысловой абзац необходимо начать с красной строки.
Закончить изложение вопроса следует выводом, итогом по содержанию данного
раздела.

Страницы ответа
должны иметь нумерацию (сквозную). Номер страницы ставится вверху в правом углу.
На титульном листе номер страницы не ставится. В тексте не допускается
произвольное сокращение слов, только общепринятых.

При
выполнении работы следует оставлять широкие поля для замечания преподавателя.
Не рекомендуется нарушать последовательность заданий.

По всем
возникшим вопросам студенту следует обращаться за консультацией преподавателю. Время
подготовки определяется преподавателем. Результат ответа оценивается на 2-5
баллов. В случае отрицательной оценки, студент должен ознакомиться с
замечаниями и, устранив недостатки, повторно сдать Зачет.

КРИТЕРИИ
ОЦЕНКИ УСТНОГО ОТВЕТА  СТУДЕНТА НА ЗАЧЕТЕ.

—
оценка «5» (отлично) ставится, если студент:

1)
полно излагает изученный материал по конкретному вопросу, даёт правильное
определение основных понятий;

2)
обнаруживает понимание материала, может обосновать свои суждения, применить
знания на практике, привести необходимые примеры не только по учебнику, но и
самостоятельно составленные;

3)
излагает ответ на вопросы  последовательно и правильно.

—
оценка «4» (хорошо) ставится, если студент даёт ответ,
удовлетворяющий тем же требованиям, что и для отметки «5», но
допускает 1-2 ошибки, которые сам же исправляет, и 1-2 недочёта в
последовательности и языковом оформлении излагаемого.

—
оценка «3» (удовлетворительно) ставится, если студент обнаруживает
знание и понимание основных положений данной темы, но:

1)
излагает материал неполно и допускает неточности в определении понятий или
ссылке на нормативно-правовые акты;

2)
не умеет достаточно глубоко и доказательно обосновать свои суждения и привести
свои примеры;

3)
излагает материал непоследовательно и допускает ошибки в языковом оформлении
излагаемого.

—
оценка «2» (неудовлетворительно)ставится, если студент обнаруживает
незнание большей части  содержания ответа на поставленные перед ним  вопросы.
допускает ошиб­ки в формулировке определений, искажающие их смысл, беспорядочно
и неуверенно излагает материал, что является серьёзным препятствием к успешному
овладению последующим материалом.

Перечень
вопросовк
зачету

по
учебной дисциплине «Основы теории информации»

Специальность
09.02.02 Компьютерные сети (базовая подготовка)

1.    
Семантическая
информация.

2.     Закон
аддитивности информации.

3.     Понятие
энтропии, формула Шеннона.

4.     Теория
вероятности, функция распределения, дисперсия случайной величины.

5.     Локальная
теорема Муавра — Лапласа.

6.     Простейшие
алгоритмы сжатия информации, методы Лемпела-Зива, особенности программ
архиваторов.

7.     Применение
алгоритмов кодирования в архиваторах для обеспечения продуктивной работы в 
WINDOWS.

8.     Принципы
сжатия данных, характеристики алгоритмов сжатия и их применимость, коэффициент
сжатия, допустимость потерь.

9.     Системные
требования алгоритмов, алгоритмы сжатия данных неизвестного формата.

10. Помехоустойчивое
кодирование, линейные блочные коды.

11. Адаптивное
арифметическое кодирование, полиномиальные коды.

12. Цифровое
кодирование, аналоговое кодирование, таблично-символьное кодирование, числовое
кодирование, дельта-кодирование.

13. Код (в теории
информации), классификатор,  криптография, сетевое кодирование.

14. Кодирование
Хаффмена.

15. Понятие
криптографии использование ее на практике.

16. Различные методы
криптографии, их свойства и методы шифрования.

17. Криптография с
симметричным ключом, с открытым ключом.

18. Криптоанализ,
криптографические примитивы, криптографические протоколы, управление ключами.

19. Понятие о
кодировании и декодировании информации.

20.  Основные подходы
к методам кодирования информации.

21. Практическое
применение криптографии.

22. Практическое
применение алгоритмов сжатия.

23. Понятие о
программно-аппаратных средствах защиты данных.

24. Понятие об
информационной безопасности.

25. Сравнительный
анализ методов шифрования.

26. Применение алгоритмов
кодирования на практике.