Информация и информационные процессы Практические работы Алгоритм rle

• Название: Информация и информационные процессы Практические работы Алгоритм rle
• Дата: 11.11.2020
• Размер: 162 Kb.
• Имя файла: practice11-1bu.doc
• Тип: Документы; #149583

И
11.11.2020
нформатика, 11 класс К.Ю. Поляков, Е.А. Еремин

Информация и информационные процессы

Практические работы

Алгоритм RLE

Файлы для выполнения этой работы находятся в каталоге RLE.

1. 
   Используя алгоритм RLE, закодируйте последовательность символов
   

BBBBBBACCCABBBBBB

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

Ответ:

86 42 01 41 83 43 01 41 86 42

2. 
   Раскодируйте последовательность, упакованную с помощью алгоритма RLE (приводятся шестнадцатеричные коды): 01 4D 8E 41 01 4D 8E 41₁₆. Для определения символов по их шестнадцатеричным кодом используйте таблицу ASCII. В приведённой таблице в первом столбце записана первая цифра шестнадцатеричного кода символа, а в первой строке – вторая. Например, символ «&» имеет шестнадцатеричный код 26₁₆.
   

.0

.1

.2

.3

.4

.5

.6

.7

.8

.9

.A

.B

.C

.D

.E

.F

0.

NUL

SOH

STX

ETX

EOT

ENQ

ACK

BEL

BS

TAB

LF

VT

FF

CR

SO

SI

1.

DLE

DC1

DC2

DC3

DC4

NAK

SYN

ETB

CAN

EM

SUB

ESC

FS

GS

RS

US

2.

!

"

#

$

%

&

'

(

)

*

+

,

—

.

/

3.

0

1

2

3

4

5

6

7

8

9

:

;

<

=

>

?

4.

@

A

B

C

D

E

F

G

H

I

J

K

L

M

N

O

5.

P

Q

R

S

T

U

V

W

X

Y

Z

[

\

]

^

_

6.

`

a

b

c

d

e

f

g

h

i

j

k

l

m

n

o

7.

p

q

r

s

t

u

v

w

x

y

z

{

|

}

DEL

Ответ:

MAAAAAAAAAAAAAAMAAAAAAAAAAAAAA

3. 
   Определите количество байтов в исходной и распакованной последовательности (см. предыдущее задание) и вычислите коэффициент сжатия:
   

   Сжатая последовательность	Несжатая последовательность	Коэффициент сжатия
   8 байтов	30 байтов	3,75

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

   Несжатая последовательность	Сжатая последовательность	Коэффициент сжатия
   		2
   		4
   		5

6. 
   Придумайте три последовательности, которые невозможно сжать с помощью алгоритма RLE:
   

   Несжатая последовательность	«Сжатая» последовательность	Коэффициент сжатия

7. 
   Используя программу RLE, примените RLE-сжатие к следующим файлам и найдите для каждого из них коэффициент сжатия:
   

   Файл	Размер без сжатия	Размер после сжатия	Коэффициент сжатия
   grad_vert.bmp
   grad_horz.bmp
   grad_diag.jpg

8. 
   Объясните результаты, полученные в предыдущем пункте:
   

• 
  почему не удается сжать рисунки в формате JPEG?
  

Ответ:

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

Ответ:

9. 
   Оцените максимально достижимый коэффициент сжатия с помощью рассмотренного в учебнике варианта RLE-алгоритма. В каком случае его удастся достичь?
   

Ответ:

10. 
    Оцените коэффициент сжатия с помощью RLE-алгоритма в худшем случае. Опишите этот худший случай.
    

Ответ:

Сравнение алгоритмов сжатия

Файлы для выполнения этой работы находятся в каталоге Compress.

При выполнении этой работы используются программы RLE (алгоритм сжатия RLE) и Huffman (кодирование Хаффмана и Шеннона-Фано).

1. 
   Запустите программу Huffman.exe и закодируйте строку «ЕНОТ НЕ ТОНЕТ», используя методы Шеннона-Фано и Хаффмана. Запишите результаты в таблицу:
   

	Шеннон и Фано	Хаффман
Длина основного кода
Длина кодовой таблицы (дерева)
Коэффициент сжатия (по основным кодам)
Коэффициент сжатия (с учетом дерева кодов)

Сделайте выводы.

Ответ:

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

Ответ:

2. 
   Повторите эксперимент с текстом, который записан в файле enot.txt (скопируйте этот текст в окно программы через буфер обмена).
   

	Шеннон и Фано	Хаффман
Длина основного кода
Длина кодовой таблицы (дерева)
Коэффициент сжатия (по основным кодам)
Коэффициент сжатия (с учетом дерева кодов)

Сделайте выводы.

Ответ:

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

3. 
   Используя кнопку Анализ файла в программе Huffman, определите предельный теоретический коэффициент сжатия для файла a.txt¹ при побайтном кодировании.
   

Ответ:

4. 
   С помощью программ RLE и Huffman выполните сжатие файла a.txt разными способами. Запишите результаты в таблицу:
   

	RLE	Шеннон и Фано	Хаффман
Размер сжатого файла
Коэффициент сжатия

Объясните результат, полученный с помощью алгоритма RLE.

Ответ:

5. 
   Используя кнопку Анализ файла в программе Huffman, определите предельный теоретический коэффициент сжатия для файла a.txt.huf при побайтном кодировании. Объясните результат.
   

Ответ:

6. 
   Примените несколько раз повторное сжатие этого файла с помощью алгоритма Хаффмана (новые файлы получат имена a.txt.huf2, a.txt.huf3 и т.д.) и заполните таблицу, каждый раз выполняя анализ полученного файла.
   

	Размер файла	Предельный коэффициент сжатия
a.txt
a.txt.huf
a.txt.huf2
a.txt.huf3
a.txt.huf4
a.txt.huf5
a.txt.huf6

Объясните, почему с некоторого момента при повторном сжатии файла его размер увеличивается.

Ответ:

7. 
   Выполните те же действия, используя метод Шеннона-Фано.
   

	Размер файла	Предельный коэффициент сжатия
a.txt
a.txt.shf
a.txt.shf2
a.txt.shf3
a.txt.shf4
a.txt.shf5
a.txt.shf6

Объясните, почему с некоторого момента при повторном сжатии файла его размер увеличивается.

Ответ:

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

	Размер файла	Предельный коэффициент сжатия
RLE
Хаффман
Шеннон и Фано
ZIP
RAR
7Z

Объясните результаты и сделайте выводы.

Ответ:

Использование архиватора

Файлы для выполнения этой работы находятся в каталоге Archive.

1. 
   Изучите возможности архиватора, который установлен на вашем компьютере (Ark, 7-Zip, WinRAR или др.).
   
2. 
   Откройте каталог, указанный учителем. Он должен содержать все файлы, которые используются далее.
   
3. 
   Распакуйте архив secret.zip, который упакован с паролем secretLatin. В подкаталогах, получившихся после распаковки, вы должны найти 3 файла, содержащие части высказывания на латинском языке, которое означает «договоры следует выполнять».
   
4. 
   Создайте новый текстовый файл latin.txt и запишите в него это высказывание на латыни. После этого удалите архив secret.zip.
   
5. 
   Выполните сжатие отдельно для каждого из перечисленных в таблице файлов, используя формат архива, указанный учителем. Вычислите коэффициент сжатия (для этого удобно использовать табличный процессор):
   

Имя файла	Описание	Объем до сжатия, Кб	Объем после сжатия, Кб	Коэффициент сжатия
random.dat	случайные данные	391
morning.zip	сжатый файл	244
sunset.jpg	рисунок в формате JPEG	730
prog.exe	программа для Windows	163
signal.mp3	звук в формате MP3	137
forest.wav	звук в формате WAV	609
ladoga.bmp	рисунок в формате BMP	9217
tolstoy.txt	текст	5379

Сделайте выводы о том, какие файлы обычно сжимаются лучше, а какие – хуже:

Ответ:

6. 
   Если ваш архиватор позволяет создавать самораспаковывающиеся архивы, сравните размеры обычного архива и SFX-архива для файла tolstoy.txt:
   

Имя архива	Описание	Объем до сжатия, Кб	Объем после сжатия, Кб
tolstoy.7z	обычный архив	5379
tolstoy.exe	SFX-архив	5379

Объясните, почему размеры двух архивов получились разные. После этого удалите оба созданных архива.

7. 
   Переместите рисунки в отдельный каталог Pictures, а звуковые файлы – в каталог Sounds.
   
8. 
   Упакуйте рисунки и звуки в архив Media с паролем media123.
   
9. 
   Упакуйте все остальные файлы и папки в архив Data (без пароля).
   
10. 
    Удалите все файлы, кроме архивов Media и Data, и покажите работу учителю.
    

Сжатие с потерями

Файлы для выполнения этой работы находятся в каталоге Lossy.

1. 
   Скопируйте в свою папку файл valaam.bmp.
   
2. 
   Используя растровый графический редактор (GIMP, Photoshop), сохраните несколько копий этого рисунка с разным качеством, от 0% до 100%.
   

В редакторе GIMP нужно выбрать пункт меню Файл – Экспортировать, ввести имя файла с расширением JPG (например, для файла с качеством 50% можно использовать имя valaam50.jpg) и в появившемся окне установить нужное качество:

В редакторе Photoshop нужно выбрать пункт меню Файл – Сохранить как…, далее в окне сохранения файла выбрать формат JPEG, ввести имя файла с расширением JPG (например, для файла с качеством 50% можно использовать имя valaam50.jpg) и в появившемся окне установить нужное качество (от 0 до 12):

3. 
   В табличном процессоре заполните таблицу
   

Для GIMP:

Качество, %	0	10	20	30	40	50	60	70	80	90	100
Объем файла, Кбайт

Для Photoshop:

Качество, %	0	1	2	3	4	5	6	7	8	9	10	11	12
Объем файла, Кбайт

С помощью табличного процессора постройте график по этим данным.

График:

Сделайте выводы.

Ответ:

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

Ответ:

5. 
   Скопируйте в свою папку звуковой файл bears.mp3.
   
6. 
   Используя звуковой редактор (например, Audacity), сохраните несколько копий этого звукового файла с разным качеством. Для формата Ogg Vorbis используйте качество от 0 до 10, для формата MP3 – битрейт от 8 до 128 Кбит/с.
   
7. 
   В табличном процессоре заполните таблицу
   

Для формата Ogg Vorbis:

Качество	1	2	3	4	5	6	7	8	9	10
Объем файла, Кбайт

Для формата MP3:

Битрейт, Кбит/с	8	16	32	48	64	96	128
Объем файла, Кбайт

Постройте график по этим данным.

График:

Объясните, почему получилась именно такая зависимость.

Ответ:

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

Ответ:

Системы управления

Программа ShipControl.exe, которая используется в этой работе, позволяет изучить различные законы управления движением судна. Нужно привести судно в район, обозначенный красной точкой; в этом районе находится радиомаяк, так что экипаж в любой момент может определить курс на маяк ₀ и собственный курс судна  (см. рисунок).



Судно управляется вертикальным рулём, который можно повернуть на угол от –35 до 35 относительно оси симметрии судна. Положительным будем считать такой угол поворота руля , который приводит к вращению судна по часовой стрелки (для человека, который смотрит в направлении движения судна, это будет поворот вправо). В ситуации, которая изображена на рисунке, нужно поворачивать влево, поэтому угол поворота руля должен быть отрицательным.

В работе вы попробуете привести судно в заданный район , используя четыре варианта управления судном:

• 
  ручное управление, когда вы сами изменяете угол поворота руля;
  
• 
  авторулевой, использующий релейный закон управления – переключение между двумя углами перекладки руля, положительным и отрицательным:
  

Эта запись означает следующее: «если угол  меньше, чем ₀, то повернуть руль на угол _R; если угол  больше, чем ₀, то повернуть руль на угол –_R;».

• 
  авторулевой, использующий пропорциональный закон управления (П-регулятор), при котором сигнал управления вычисляется как ошибка  = ₀ –  (разность между направлением на маяк и направлением движения судна), умноженная на некоторый коэффициент k:
  

.

• 
  авторулевой, использующий пропорционально-дифференциальный закон управления (ПД-регулятор), при котором сигнал управления учитывает не только значение ошибки , но и скорость её изменения :
  

.

Здесь k и k_d – коэффициенты регулятора, которые вам предстоит выбрать во время выполнения работы.

Главная проблема состоит в том, что судно – это инерционный объект, поэтому оно не сразу реагирует на поворот руля, а затем, когда оно начнёт поворачиваться, не так просто остановить вращение.

Уровень А.

1. 
   Запустите программу ShipControl.exe. Попробуйте вручную изменять угол поворота руля, перетаскивая мышью рукоятку манипулятора влево и вправо. Убедитесь, что датчик показывает изменение угла поворота руля.
   

2. 
   Попробуйте управлять положением руля, используя клавиши-стрелки «влево» и «вправо».
   
3. 
   Щелкните по кнопке и попытайтесь привести судно в заданный район, управляя им вручную. Если не получилось с первого раза, попробуйте снова. Сделайте не более 5 попыток. Ответьте на вопросы:
   

Удалось ли вам привести судно в заданный район:

Добавьте в отчёт скриншот вашей лучшей траектории движения:

Чему равна длина пути до заданного района (это число выводится в нижней части окна программы):

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

4. 
   Попробуйте использовать авторулевой с релейным регулятором при _R = 10:
   

Удалось ли привести судно в заданный район:

Сколько времени занял выход в заданную точку:

Добавьте в отчёт скриншот траектории движения:

5. 
   Уменьшите угол перекладки релейного регулятора до _R = 4 и повторите моделирование.
   

Сколько времени занял выход в заданную точку:

Что изменилось в поведении судна в сравнении с первым вариантом:

6. 
   Попробуйте использовать авторулевой с П-регулятором при k = 1,2:
   

Удалось ли привести судно в заданный район:

Добавьте в отчёт скриншот траектории движения:

Сколько времени занял выход в заданную точку:

7. 
   Попробуйте использовать авторулевой с ПД-регулятором при k = 1,2 и k_d = 100:
   

Удалось ли привести судно в заданный район:

Добавьте в отчёт скриншот траектории движения:

Сколько времени занял выход в заданную точку:

Чем отличается результат управления при использовании П- и ПД-регуляторов:

Какой регулятор вы бы выбрали:

Уровень B.

8. 
   Экспериментально определите с точностью до 0,1 минимальный и максимальный коэффициенты усиления П-регулятора, при которых судно достигает заданного района. Сравните работу этих регуляторов со случаем, когда k = 1,2.
   

   	kmin	k	kmax
   Значение k		1,2
   Число колебаний курса
   Время движения до точки

9. 
   Перейдите на вкладку Модель и выберите модель судна-контейнеровоза. Чем отличается эта модель от модели учебного судна?
   

Ответ:

10. 
    Попробуйте вывести судно в нужную точку на ручном управлении. Получилось ли у вас?
    

Ответ:

Как вы думаете, почему управлять контейнеровозом сложнее, чем учебным судном:

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

Ответ:

12. 
    Попробуйте вывести судно в нужную точку с помощью П-регулятора, пробуя значения коэффициентов. Получилось ли у вас? При каком значении k? Если да, вставьте в отчёт скриншот.
    

Ответ:

13. 
    Попробуйте вывести судно в нужную точку с помощью ПД-регулятора с настройками по умолчанию. Получилось ли у вас? Если да, вставьте в отчёт скриншот.
    

Ответ:

Уровень С.

14. 
    Экспериментально определите (с точностью до 10) минимальный и максимальный коэффициенты дифференциального канала k_d, при которых судно приходит в заданную точку. Сравните регуляторы с разными значениями k_d.
    

    	kd,min	k	kd, max
    Значение k		1
    Время движения до точки

15. 
    Экспериментально найдите значения коэффициента дифференциального канала k_d (с точностью до 5) при котором время выхода в заданную точку наименьшее. Потом, зафиксировав k_d, попробуйте изменять с шагом 0,1 коэффициент пропорционального канала k так, чтобы ещё улучшить результат.
    

Коэффициенты оптимального регулятора:

k = …, k_d = …

Добавьте в отчёт скриншот траектории движения:

Сколько времени занял выход в заданную точку:

1 Этот файл имеет объем 1 Мбайт и состоит из одних символов «А».

http://kpolyakov.spb.ru