Задания и методические рекомендации по их выполнению
Задание №1 Сжатие информации
а) Используя таблицы, выполнить сжатие своих инициалов:
- студенты с чётной последней цифрой - делением по модулю два;
- студенты с нечётной последней цифрой – делением по правилам двоичной логики.
Например: Длинношеев Василий Олегович
– ДВО – 100001001000001010001110.
б) Из своих ФИО выбрать одно слово с максимальным количеством совпадающих букв и сжать методом побуквенного сдвига или решить задачу.
Например: Длинношеев Василий Олегович – Длинношеев.
Задача
1 2 3 4 5 6 7
1 2 3 4 5 8 6
2 1 3 4 5 2 4
2 1 3 4 5 2 9
4 2 9 4 5 2 9
4 2 9 4 5 2 9
4 2 9 4 5 2 9
5 2 9 4 5 2 1
Таблица 1. Правила выполнения арифметических действий над двоичными числами.
Таблица двоичного сложения |
Таблица двоичного вычитания |
Таблица двоичного умножения |
0+0=0 0+1=1 1+0=1 1+1=10 |
0-0=0 1-0=1 1-1=0 10-1=1 |
0 |
0=0
0
1=0
1
0=0
1
1=1
При сложении двоичных чисел в каждом разряде производится сложение цифр слагаемых и переноса из соседнего младшего разряда, если он имеется. При этом необходимо учитывать, что 1+1 дают нуль в данном разряде и единицу переноса в следующий.
Т
аблица
2. Десятичные, шестнадцатеричные и
двоичные ASCII – коды.
Таблица 3. Правила сложения по модулю 2.
a |
b |
|
a |
b |
c |
|
0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
|
|
|
0 |
0 |
1 |
1 |
|
|
|
1 |
0 |
1 |
0 |
|
|
|
0 |
1 |
1 |
0 |
|
|
|
1 |
1 |
1 |
1 |
2.1.1 Методические рекомендации и примеры
Сжатие информации представляет собой операцию, в результате которой данному коду или сообщению ставится в соответствие более короткий код или сообщение.
Сжатие информации ставит целью - ускорение и удешевление процессов механизированной обработки, хранения и поиска информации, экономии памяти ЭВМ. При сжатии следует стремиться к минимальной неоднозначности сжатых кодов при максимальной простоте алгоритма сжатия. Рассмотрим наиболее характерные методы сжатия информации.
Сжатие информации делением кода на части, меньше некоторой заданной величины А, заключается в том, что исходный код делится на части, полученные части кода складываются между собой, либо по правилам двоичной арифметики, либо по модулю 2. Например, исходный код 101011010110 при А=4.
0 1 1 0 1 1 1 0 1 сжатый код двоичной логикой |
0 1 1 0 0 0 0 1 сжатый код по модулю 2 |
Сжатие информации с побуквенным сдвигом.
Очень часто обрабатываемая информация бывает представлена в виде набора однородных массивов, в которых элементы столбцов или строк массивов расположены в нарастающем порядке. Длина строки известна. Если считать старшими разряды, расположенные левее данного элемента, а младшими – расположенные правее, то можно заметить, что во многих случаях строки матриц отличаются друг от друга в младших разрядах. Если при записи каждого последующего элементы массива отбрасывать все повторяющиеся в предыдущем элементы, например в строке стоящие подряд элементы старших разрядов, то массивы могут быть сокращены от 2 до 10 и более разрядов.
Для учета выброшенных разрядов вводится знак раздела, который позволяет отделить элементы в свернутом массиве. В случае полного повторения строк записывается соответствующее количество раз р. При развертывании вместо знака р восстанавливаются все пропущенные разряды, которые были до элемента, стоящего непосредственно за р в сжатом тексте.
Для примера рассмотрим следующий массив:
9 5 7 0 1 2 4
9 5 7 0 1 2 5
9 5 7 0 3 8 6
9 5 7 0 3 9 0
1 2 3 4 5 6 7
1 2 3 4 5 9 1
1 2 3 4 5 9 3
Свернутый массив будет иметь вид:
5 7 0 1 2 4
р 5 р 3 8 6 р
9 0 1 2 3 4 5
6 7 р 9 1 р 3