Оцените презентацию от 1 до 5 баллов!
Тип файла:
ppt / pptx (powerpoint)
Всего слайдов:
15 слайдов
Для класса:
1,2,3,4,5,6,7,8,9,10,11
Размер файла:
166.27 kB
Просмотров:
57
Скачиваний:
0
Автор:
неизвестен
Слайды и текст к этой презентации:
№1 слайд![Алгоритм построения орграфа](/documents_2/e108ec3c7ef931cea1b09f8b68acee0e/img0.jpg)
Содержание слайда: Алгоритм построения орграфа Хаффмана
(алгоритм сжатия)
Учитель информатики:
Константинова Елена Ивановна
Муниципальное образовательное учреждение Раменская средняя общеобразовательная школа №8
№2 слайд![Давид Хаффман - Давид начал](/documents_2/e108ec3c7ef931cea1b09f8b68acee0e/img1.jpg)
Содержание слайда: Давид Хаффман (1925-1999)
Давид начал свою научную карьеру студентом в Массачусетсом технологическом институте (MIT), где построил свои коды в начале пятидесятых годов прошлого века.
№3 слайд![Закодируем предложение НА](/documents_2/e108ec3c7ef931cea1b09f8b68acee0e/img2.jpg)
Содержание слайда: Закодируем предложение
«НА_ДВОРЕ_ТРАВА,_НА_ТРАВЕ_ДРОВА»
№4 слайд![](/documents_2/e108ec3c7ef931cea1b09f8b68acee0e/img3.jpg)
№5 слайд![](/documents_2/e108ec3c7ef931cea1b09f8b68acee0e/img4.jpg)
№6 слайд![](/documents_2/e108ec3c7ef931cea1b09f8b68acee0e/img5.jpg)
№7 слайд![](/documents_2/e108ec3c7ef931cea1b09f8b68acee0e/img6.jpg)
№8 слайд![](/documents_2/e108ec3c7ef931cea1b09f8b68acee0e/img7.jpg)
№9 слайд![](/documents_2/e108ec3c7ef931cea1b09f8b68acee0e/img8.jpg)
№10 слайд![Чтобы определить код для](/documents_2/e108ec3c7ef931cea1b09f8b68acee0e/img9.jpg)
Содержание слайда: Чтобы определить код для каждого из символов, входящих в сообщение, мы должны пройти путь от листа дерева, соответствующего этому символу, до корня дерева, накапливая биты при перемещении по ветвям дерева. Полученная таким образом последовательность битов является кодом данного символа, записанным в обратном порядке.
№11 слайд![ПОДСЧИТАЕМ, СКОЛЬКО ДВОИЧНЫХ](/documents_2/e108ec3c7ef931cea1b09f8b68acee0e/img10.jpg)
Содержание слайда: ПОДСЧИТАЕМ, СКОЛЬКО ДВОИЧНЫХ СИМВОЛОВ ОКАЖЕТСЯ В СООБЩЕНИИ
«НА_ ДВОРЕ_ ТРАВА,_ НА_ ТРАВЕ_ ДРОВА»
ДЛЯ ЭТОГО НАДО НАЙТИ ПРОИЗВЕДЕНИЕ ЧИСЛА СИМВОЛОВ В КОДЕ КАЖДОЙ БУКВЫ НА КОЛИЧЕСТВО РАЗ, КОТОРОЕ ЭТА БУКВА ВСТРЕЧАЕТСЯ В СООБЩЕНИИ, А ЗАТЕМ ПОЛУЧЕННЫЕ ПРОИЗВЕДЕНИЯ СЛОЖИТЬ. ПОЛУЧАЕМ:
2*6+ 3*4+ 4*2+ 4*1+ 4*2+ 4*2 +3*4 +4*2 +4*2 +3*5 = 95
№12 слайд![ПОСКОЛЬКУ В СООБЩЕНИИ](/documents_2/e108ec3c7ef931cea1b09f8b68acee0e/img11.jpg)
Содержание слайда: ПОСКОЛЬКУ В СООБЩЕНИИ ИСПОЛЬЗУЕТСЯ 10 РАЗЛИЧНЫХ СИМВОЛОВ, ДЛЯ ИХ КОДИРОВАНИЯ ТРЕБУЕТСЯ КАК МИНИМУМ ЧЕТЫРЕХБИТОВЫЕ ЦЕПОЧКИ, ПОЭТОМУ ПОСЛЕ КОДИРОВАНИЯ ДАННОГО СООБЩЕНИЯ ПОЛУЧИТСЯ ЦЕПОЧКА ОБЪЕМОМ 120 БИТ.
КОЭФФИЦИЕНТ СЖАТИЯ ЭТО ОТНОШЕНИЕ ОБЪЕМА ИСХОДНОГО СООБЩЕНИЯ К ОБЪЕМУ СЖАТОГО. В НАШЕМ СЛУЧАЕ ЭТО ОТНОШЕНИЕ РАВНО 120/95 = 120/95 = 1,26 .
№13 слайд![НА САМОМ ДЕЛЕ ДАННОЕ](/documents_2/e108ec3c7ef931cea1b09f8b68acee0e/img12.jpg)
Содержание слайда: НА САМОМ ДЕЛЕ ДАННОЕ СООБЩЕНИЕ В ПАМЯТИ КОМПЬЮТЕРА ЗАКОДИРОВАНО С ПОМОЩЬЮ ASCII, ПОЭТОМУ НА КАЖДЫЙ СИМВОЛ ОТВЕДЕНО 8 БИТ.
ТЕМ САМЫМ, ОБЪЕМ ИСХОДНОГО СООБЩЕНИЯ 240 БИТ, А КОЭФФИЦИЕНТ СЖАТИЯ СОСТАВЛЯЕТ 240/95 = 2,53.
ИЗ ЭТОГО ВИДНО, КАКОЙ ВЫИГРЫШ МЫ ПОЛУЧИЛИ, ЕСЛИ ЭТО СООБЩЕНИЕ НУЖНО БЫЛО БЫ ПЕРЕДАТЬ ПО КАНАЛУ СВЯЗИ ИЛИ СОХРАНИТЬ НА КАКОМ-ЛИБО НОСИТЕЛЕ.
№14 слайд![ДЛЯ ДЕКОДИРОВНИЯ СЖАТОГО](/documents_2/e108ec3c7ef931cea1b09f8b68acee0e/img13.jpg)
Содержание слайда: ДЛЯ ДЕКОДИРОВНИЯ СЖАТОГО СООБЩЕНИЯ ВМЕСТЕ С НИМ ОБЫЧНО ПЕРЕСЫЛАЮТ НЕ КОДЫ ИСХОДНЫХ СИМВОЛОВ (Т.Е. ПЕРВЫЕ ДВЕ СТРОКИ), А САМ ОРГРАФ ХАФФМАНА (БЕЗ УКАЗАНИЯ ВЕСА КОРНЯ И РАЗМЕТКИ НА ДУГАХ, ИБО ОНА СТАНДАРТНА: ДУГА, ИДУЩАЯ ВЛЕВО, РАЗМЕЧАЕТСЯ -0, А ИДУЩАЯ ВПРАВО -1).
НА ЭТОМ, ОКАЗЫВАЕТСЯ, ТО ЖЕ МОЖНО СЭКОНОМИТЬ.
МАТЕМАТИКИ ДОКАЗАЛИ, ЧТО СРЕДИ АЛГОРИТМОВ КОДИРУЮЩИХ КАЖДЫЙ СИМВОЛ ПО ОТДЕЛЬНОСТИ И ЦЕЛЫМ КОЛИЧЕСТВОМ БИТ АЛГОРИТМ ХАФФМАНА ОБЕСПЕЧИВАЕТ НАИЛУЧШЕЕ СЖАТИЕ.
№15 слайд![Используемая литература А.Г.](/documents_2/e108ec3c7ef931cea1b09f8b68acee0e/img14.jpg)
Содержание слайда: Используемая литература:
А.Г. Гейн. Математические основы информатики.
Педагогический университет «Первое сентября», 2008г.