- Алгоритмы сжатия. Алгоритм построения орграфа Хаффмана

Презентация "Алгоритмы сжатия. Алгоритм построения орграфа Хаффмана" по информатике – проект, доклад

Слайд 1
Слайд 2
Слайд 3
Слайд 4
Слайд 5
Слайд 6
Слайд 7
Слайд 8
Слайд 9
Слайд 10
Слайд 11
Слайд 12
Слайд 13
Слайд 14
Слайд 15

Презентацию на тему "Алгоритмы сжатия. Алгоритм построения орграфа Хаффмана" можно скачать абсолютно бесплатно на нашем сайте. Предмет проекта: Информатика. Красочные слайды и иллюстрации помогут вам заинтересовать своих одноклассников или аудиторию. Для просмотра содержимого воспользуйтесь плеером, или если вы хотите скачать доклад - нажмите на соответствующий текст под плеером. Презентация содержит 15 слайд(ов).

Слайды презентации

Алгоритм построения орграфа Хаффмана (алгоритм сжатия). Учитель информатики: Константинова Елена Ивановна Муниципальное образовательное учреждение Раменская средняя общеобразовательная школа №8
Слайд 1

Алгоритм построения орграфа Хаффмана (алгоритм сжатия)

Учитель информатики: Константинова Елена Ивановна Муниципальное образовательное учреждение Раменская средняя общеобразовательная школа №8

Давид Хаффман (1925-1999) Давид начал свою научную карьеру студентом в Массачусетсом технологическом институте (MIT), где построил свои коды в начале пятидесятых годов прошлого века.
Слайд 2

Давид Хаффман (1925-1999) Давид начал свою научную карьеру студентом в Массачусетсом технологическом институте (MIT), где построил свои коды в начале пятидесятых годов прошлого века.

Закодируем предложение «НА_ДВОРЕ_ТРАВА,_НА_ТРАВЕ_ДРОВА». Вначале нужно подсчитать количество вхождений каждого символа в тексте. Создаем первый узел
Слайд 3

Закодируем предложение «НА_ДВОРЕ_ТРАВА,_НА_ТРАВЕ_ДРОВА»

Вначале нужно подсчитать количество вхождений каждого символа в тексте.

Создаем первый узел

Создаем еще один узел
Слайд 4

Создаем еще один узел

Алгоритмы сжатия. Алгоритм построения орграфа Хаффмана Слайд: 5
Слайд 5
Алгоритмы сжатия. Алгоритм построения орграфа Хаффмана Слайд: 6
Слайд 6
Алгоритмы сжатия. Алгоритм построения орграфа Хаффмана Слайд: 7
Слайд 7
Алгоритмы сжатия. Алгоритм построения орграфа Хаффмана Слайд: 8
Слайд 8
Алгоритмы сжатия. Алгоритм построения орграфа Хаффмана Слайд: 9
Слайд 9
Чтобы определить код для каждого из символов, входящих в сообщение, мы должны пройти путь от листа дерева, соответствующего этому символу, до корня дерева, накапливая биты при перемещении по ветвям дерева. Полученная таким образом последовательность битов является кодом данного символа, записанным в
Слайд 10

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

ПОДСЧИТАЕМ, СКОЛЬКО ДВОИЧНЫХ СИМВОЛОВ ОКАЖЕТСЯ В СООБЩЕНИИ «НА_ ДВОРЕ_ ТРАВА,_ НА_ ТРАВЕ_ ДРОВА» ДЛЯ ЭТОГО НАДО НАЙТИ ПРОИЗВЕДЕНИЕ ЧИСЛА СИМВОЛОВ В КОДЕ КАЖДОЙ БУКВЫ НА КОЛИЧЕСТВО РАЗ, КОТОРОЕ ЭТА БУКВА ВСТРЕЧАЕТСЯ В СООБЩЕНИИ, А ЗАТЕМ ПОЛУЧЕННЫЕ ПРОИЗВЕДЕНИЯ СЛОЖИТЬ. ПОЛУЧАЕМ: 2*6+ 3*4+ 4*2+ 4*1+ 4
Слайд 11

ПОДСЧИТАЕМ, СКОЛЬКО ДВОИЧНЫХ СИМВОЛОВ ОКАЖЕТСЯ В СООБЩЕНИИ «НА_ ДВОРЕ_ ТРАВА,_ НА_ ТРАВЕ_ ДРОВА» ДЛЯ ЭТОГО НАДО НАЙТИ ПРОИЗВЕДЕНИЕ ЧИСЛА СИМВОЛОВ В КОДЕ КАЖДОЙ БУКВЫ НА КОЛИЧЕСТВО РАЗ, КОТОРОЕ ЭТА БУКВА ВСТРЕЧАЕТСЯ В СООБЩЕНИИ, А ЗАТЕМ ПОЛУЧЕННЫЕ ПРОИЗВЕДЕНИЯ СЛОЖИТЬ. ПОЛУЧАЕМ: 2*6+ 3*4+ 4*2+ 4*1+ 4*2+ 4*2 +3*4 +4*2 +4*2 +3*5 = 95

ПОСКОЛЬКУ В СООБЩЕНИИ ИСПОЛЬЗУЕТСЯ 10 РАЗЛИЧНЫХ СИМВОЛОВ, ДЛЯ ИХ КОДИРОВАНИЯ ТРЕБУЕТСЯ КАК МИНИМУМ ЧЕТЫРЕХБИТОВЫЕ ЦЕПОЧКИ, ПОЭТОМУ ПОСЛЕ КОДИРОВАНИЯ ДАННОГО СООБЩЕНИЯ ПОЛУЧИТСЯ ЦЕПОЧКА ОБЪЕМОМ 120 БИТ. КОЭФФИЦИЕНТ СЖАТИЯ ЭТО ОТНОШЕНИЕ ОБЪЕМА ИСХОДНОГО СООБЩЕНИЯ К ОБЪЕМУ СЖАТОГО. В НАШЕМ СЛУЧАЕ ЭТО О
Слайд 12

ПОСКОЛЬКУ В СООБЩЕНИИ ИСПОЛЬЗУЕТСЯ 10 РАЗЛИЧНЫХ СИМВОЛОВ, ДЛЯ ИХ КОДИРОВАНИЯ ТРЕБУЕТСЯ КАК МИНИМУМ ЧЕТЫРЕХБИТОВЫЕ ЦЕПОЧКИ, ПОЭТОМУ ПОСЛЕ КОДИРОВАНИЯ ДАННОГО СООБЩЕНИЯ ПОЛУЧИТСЯ ЦЕПОЧКА ОБЪЕМОМ 120 БИТ. КОЭФФИЦИЕНТ СЖАТИЯ ЭТО ОТНОШЕНИЕ ОБЪЕМА ИСХОДНОГО СООБЩЕНИЯ К ОБЪЕМУ СЖАТОГО. В НАШЕМ СЛУЧАЕ ЭТО ОТНОШЕНИЕ РАВНО 120/95 = 120/95 = 1,26 .

НА САМОМ ДЕЛЕ ДАННОЕ СООБЩЕНИЕ В ПАМЯТИ КОМПЬЮТЕРА ЗАКОДИРОВАНО С ПОМОЩЬЮ ASCII, ПОЭТОМУ НА КАЖДЫЙ СИМВОЛ ОТВЕДЕНО 8 БИТ. ТЕМ САМЫМ, ОБЪЕМ ИСХОДНОГО СООБЩЕНИЯ 240 БИТ, А КОЭФФИЦИЕНТ СЖАТИЯ СОСТАВЛЯЕТ 240/95 = 2,53. ИЗ ЭТОГО ВИДНО, КАКОЙ ВЫИГРЫШ МЫ ПОЛУЧИЛИ, ЕСЛИ ЭТО СООБЩЕНИЕ НУЖНО БЫЛО БЫ ПЕРЕДАТЬ
Слайд 13

НА САМОМ ДЕЛЕ ДАННОЕ СООБЩЕНИЕ В ПАМЯТИ КОМПЬЮТЕРА ЗАКОДИРОВАНО С ПОМОЩЬЮ ASCII, ПОЭТОМУ НА КАЖДЫЙ СИМВОЛ ОТВЕДЕНО 8 БИТ. ТЕМ САМЫМ, ОБЪЕМ ИСХОДНОГО СООБЩЕНИЯ 240 БИТ, А КОЭФФИЦИЕНТ СЖАТИЯ СОСТАВЛЯЕТ 240/95 = 2,53. ИЗ ЭТОГО ВИДНО, КАКОЙ ВЫИГРЫШ МЫ ПОЛУЧИЛИ, ЕСЛИ ЭТО СООБЩЕНИЕ НУЖНО БЫЛО БЫ ПЕРЕДАТЬ ПО КАНАЛУ СВЯЗИ ИЛИ СОХРАНИТЬ НА КАКОМ-ЛИБО НОСИТЕЛЕ.

ДЛЯ ДЕКОДИРОВНИЯ СЖАТОГО СООБЩЕНИЯ ВМЕСТЕ С НИМ ОБЫЧНО ПЕРЕСЫЛАЮТ НЕ КОДЫ ИСХОДНЫХ СИМВОЛОВ (Т.Е. ПЕРВЫЕ ДВЕ СТРОКИ), А САМ ОРГРАФ ХАФФМАНА (БЕЗ УКАЗАНИЯ ВЕСА КОРНЯ И РАЗМЕТКИ НА ДУГАХ, ИБО ОНА СТАНДАРТНА: ДУГА, ИДУЩАЯ ВЛЕВО, РАЗМЕЧАЕТСЯ -0, А ИДУЩАЯ ВПРАВО -1). НА ЭТОМ, ОКАЗЫВАЕТСЯ, ТО ЖЕ МОЖНО СЭК
Слайд 14

ДЛЯ ДЕКОДИРОВНИЯ СЖАТОГО СООБЩЕНИЯ ВМЕСТЕ С НИМ ОБЫЧНО ПЕРЕСЫЛАЮТ НЕ КОДЫ ИСХОДНЫХ СИМВОЛОВ (Т.Е. ПЕРВЫЕ ДВЕ СТРОКИ), А САМ ОРГРАФ ХАФФМАНА (БЕЗ УКАЗАНИЯ ВЕСА КОРНЯ И РАЗМЕТКИ НА ДУГАХ, ИБО ОНА СТАНДАРТНА: ДУГА, ИДУЩАЯ ВЛЕВО, РАЗМЕЧАЕТСЯ -0, А ИДУЩАЯ ВПРАВО -1). НА ЭТОМ, ОКАЗЫВАЕТСЯ, ТО ЖЕ МОЖНО СЭКОНОМИТЬ. МАТЕМАТИКИ ДОКАЗАЛИ, ЧТО СРЕДИ АЛГОРИТМОВ КОДИРУЮЩИХ КАЖДЫЙ СИМВОЛ ПО ОТДЕЛЬНОСТИ И ЦЕЛЫМ КОЛИЧЕСТВОМ БИТ АЛГОРИТМ ХАФФМАНА ОБЕСПЕЧИВАЕТ НАИЛУЧШЕЕ СЖАТИЕ.

Используемая литература: А.Г. Гейн. Математические основы информатики. Педагогический университет «Первое сентября», 2008г. http://edu.1september.ru/courses/07/008/01.pdf
Слайд 15

Используемая литература: А.Г. Гейн. Математические основы информатики. Педагогический университет «Первое сентября», 2008г.

http://edu.1september.ru/courses/07/008/01.pdf

Список похожих презентаций

Алгоритмы сжатия

Алгоритмы сжатия

Эффективность алгоритма сжатия зависит от. степени сжатия (отношение длины несжатых данных к длине соответствующих им сжатых данных); скорости сжатия ...
Алгоритмы действий

Алгоритмы действий

Алгоритмы в нашей жизни. Одну и ту же задачу можно решить разными способами, но перестановка некоторых пунктов плана может сделать его неразумным ...
Алгоритмы дорогами сказок

Алгоритмы дорогами сказок

Дойди до выхода Начало Иди 1 клетку Иди 1 клетку Иди__________ Иди__________ Иди__________ Иди__________ Иди__________ Иди__________ Конец. АЛГОРИТМ ...
Алгоритмы в нашей жизни

Алгоритмы в нашей жизни

МОУ « Тучковская средняя общеобразовательная школа № 2». Цели урока «Алгоритмы в нашей жизни»: Привить навыки составления алгоритмов. Показать способы ...
Алгоритмы Виды алгоритмов Свойства алгоритмов

Алгоритмы Виды алгоритмов Свойства алгоритмов

Содержание. Данные, величина, команды Постоянная и переменная величина Характеристика величины Понятие «алгоритм» Исполнитель алгоритма СКИ Свойства ...
Алгоритмы

Алгоритмы

СОДЕРЖАНИЕ ПРЕЗЕНТАЦИИ. История возникновения. Понятие алгоритм. Примеры алгоритмов. Исполнители алгоритмов. Что такое программа. Свойства алгоритма. ...
Алгоритмы в нашей жизни

Алгоритмы в нашей жизни

В обычной жизни. Каждый из нас, не задумываясь, использует множество различных алгоритмов. Я задумался:. Где мы с ним встречаемся? Что же такое алгоритм? ...
Алгоритмы

Алгоритмы

Понятие алгоритма Свойства алгоритмов Линейный алгоритм Циклический алгоритм Разветвляющийся алгоритм Представление алгоритма в виде блок-схемы Стадии ...
Алгоритмы симметричного шифрования

Алгоритмы симметричного шифрования

Алгоритм Blowfish. Алгоритм Blowfish Blowfish является сетью Фейштеля, у которой количество итераций равно 16. Длина блока равна 64 битам, ключ может ...
Логика высказываний. Алгоритм построения

Логика высказываний. Алгоритм построения

Таблицы истинности. Решение логических выражений принято оформлять в виде таблиц, в которых по действиям показано, какие значения принимает логическое ...
Алгоритмы

Алгоритмы

. Русский язык. Алгоритм проверки безударной гласной в корне слов. Алгоритм определения спряжения глаголов Алгоритм разбора предложения по членам. ...
Алгоритмы

Алгоритмы

Вспоминать Развивать Проверять. Нарисуй фигуру Начало 2. 2 3 4 5 2 2. Приготовь какао. возьми чашку положи ложку какао в чашку начало возьми молоко ...
Алгоритмы и типы алгоритмов

Алгоритмы и типы алгоритмов

Понятие алгоритма. Разветвляющиеся алгоритмы. Линейные алгоритмы. Словарь понятий Задание. Алгоритм - это строгоупорядоченная последовательность действий, ...
Алгоритмы с ветвлениями

Алгоритмы с ветвлениями

Цель: Сформировать понятие об алгоритме с ветвлением, закрепить умения составлять и выполнять алгоритмы. Задачи: Учебно-познавательная – научить учащихся ...
Алгоритмы на примере среды программирования «Паркетчик»

Алгоритмы на примере среды программирования «Паркетчик»

Строка меню «Паркетчик». Основные команды паркетчика. Пример:. Программа { положить(к); Шаг вправо; положить(к); Шаг вправо; положить(к); }. Команды ...
Алгоритмы и программы

Алгоритмы и программы

КОМАНДЫ ДЛЯ КОМПЬЮТЕРА. Компьютерная программа представляет собой список команд, которые указывают компьютеру , что он должен делать.Некоторые    программы ...
Алгоритмы симметричного шифрования

Алгоритмы симметричного шифрования

Криптография. Основные понятия. Рассмотрим общую схему симметричной, или традиционной, криптографии. Рис. 2.1. Общая схема симметричного шифрования. ...
Алгоритмы и программы для исполнителя Кукарача

Алгоритмы и программы для исполнителя Кукарача

Программирование — удивительный род человеческой деятельности, который сродни волшебству. Несколько заклинаний на языке посвящённых, и «твёрдый» металл ...
Алгоритмы и методы поиска событий в видео потоке

Алгоритмы и методы поиска событий в видео потоке

Цели доклада. Рассмотреть основные имеющиеся алгоритмы поиска событий Указать на их недостатки Указать направление поиска решения некоторых проблем ...
Алгоритмы и программирование

Алгоритмы и программирование

АЛГОРИТМ Линейный Циклический С ветвлением С процедурой. Программа – запись алгоритма на языке программирования для компьютера. Алфавит языка. Алфавит ...

Конспекты

Алгоритмы сжатия. Алгоритм построения орграфа Хаффмана

Алгоритмы сжатия. Алгоритм построения орграфа Хаффмана

. План-конспект занятия по информатике. Город:. . Раменское. МОУ «СОШ № 8». Учитель:. . Константинова Елена Ивановна. Класс:. . 11 «А». ...
Алгоритмы и исполнители

Алгоритмы и исполнители

Конспект урока информатики на тему: Алгоритмы и исполнители. Тип урока:. урок изучения и закрепления знаний и способов деятельности учащихся. ...
Что такое программирование. Алгоритмы работы с величинами

Что такое программирование. Алгоритмы работы с величинами

Урок №49. Тема:. Что такое программирование. Алгоритмы работы с величинами. Тип урока:. комбинированный урок. Цели:. Сформировать представление ...
Алгоритмы и исполнители

Алгоритмы и исполнители

Ковалева Юлия Валентиновна , учитель информатики. МОУ «СОШ «№ 7», Краснодарский край, ст.Тбилисская. Предметная область: информатика. Класс: 3. ...
Алгоритмы и исполнители

Алгоритмы и исполнители

. Комитет образования администрации г. Ставрополя. МБОУ лицей №16 г. Ставрополя. План-конспект урока по информатике. ...
Алгоритмы и исполнители

Алгоритмы и исполнители

Урок-игра для 9-го класса "Битик-банк". Цель: систематизация и обобщение изученного материала по теме «Алгоритмы и исполнители». Задачи:. общеобразовательные:. ...
Программирование. Алгоритмы работы с величинами. Язык программирования Паскаль. Правила записи основных операторов

Программирование. Алгоритмы работы с величинами. Язык программирования Паскаль. Правила записи основных операторов

Тема:. Программирование. Алгоритмы работы с величинами. Язык программирования Паскаль. Правила записи основных операторов. . . Результаты:. ...
Алгоритмы и алгоритмические структуры

Алгоритмы и алгоритмические структуры

Урок-путешествие «В гостях у сказки «Золушка». Тема урока: Алгоритмы и алгоритмические структуры. Цели:. . Закрепить знания учащихся об основных ...
Алгоритмы, виды алгоритмов, способы записи

Алгоритмы, виды алгоритмов, способы записи

Муниципальное бюджетное общеобразовательное учреждение. . «Угловская средняя общеобразовательная школа». Конспект урока по информатике. ...
Алгоритмы для смекалистых

Алгоритмы для смекалистых

Урок-повторение "Алгоритмы для смекалистых". для 4 класса. Автор: Парменова Ирина Сергеевна, учитель информатики ММБОУ "Коношская СОШ" п. Коноша ...

Советы как сделать хороший доклад презентации или проекта

  1. Постарайтесь вовлечь аудиторию в рассказ, настройте взаимодействие с аудиторией с помощью наводящих вопросов, игровой части, не бойтесь пошутить и искренне улыбнуться (где это уместно).
  2. Старайтесь объяснять слайд своими словами, добавлять дополнительные интересные факты, не нужно просто читать информацию со слайдов, ее аудитория может прочитать и сама.
  3. Не нужно перегружать слайды Вашего проекта текстовыми блоками, больше иллюстраций и минимум текста позволят лучше донести информацию и привлечь внимание. На слайде должна быть только ключевая информация, остальное лучше рассказать слушателям устно.
  4. Текст должен быть хорошо читаемым, иначе аудитория не сможет увидеть подаваемую информацию, будет сильно отвлекаться от рассказа, пытаясь хоть что-то разобрать, или вовсе утратит весь интерес. Для этого нужно правильно подобрать шрифт, учитывая, где и как будет происходить трансляция презентации, а также правильно подобрать сочетание фона и текста.
  5. Важно провести репетицию Вашего доклада, продумать, как Вы поздороваетесь с аудиторией, что скажете первым, как закончите презентацию. Все приходит с опытом.
  6. Правильно подберите наряд, т.к. одежда докладчика также играет большую роль в восприятии его выступления.
  7. Старайтесь говорить уверенно, плавно и связно.
  8. Старайтесь получить удовольствие от выступления, тогда Вы сможете быть более непринужденным и будете меньше волноваться.

Информация о презентации

Ваша оценка: Оцените презентацию по шкале от 1 до 5 баллов
Дата добавления:15 января 2015
Категория:Информатика
Содержит:15 слайд(ов)
Поделись с друзьями:
Скачать презентацию
Смотреть советы по подготовке презентации