Практика

Практика

1.Код Фано-Шеннона:

1)Определить число вхождений.

2)Построить дерево по коду Фано-Шенноа. Надписать узлы дерева, учитывая что левый сын меньше правого сына.

3)Выписать код для всех символов входящих в текст.

4)Подсчитать длину закодированного кодом текста.

2.Код Хаффмана:

1)Определить число вхождений.

2)Схематически изобразить процесс выполнения алгоритма Хаффмана.

3)Построить упорядоченное дерево имеющее минимальную высоту. Выписать код Хаффмана для всех символов входящих в текст.

4)Подсчитать длину закодированного кодом текста.

На обратной стороне дан текст длинный не успел переписать, было что-то наподобие

«упопабыласобакаонеелюбилонасъелакусокмясаонееубилакопалнатабличкенаписал….» что-то в этом роде.(для фано и хаффмана).

3.Динамическое кодирование хаффмана

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

Выписать итоговое сообщение закодированное и длину кода.

Варианты которые были:

1)рококобарроко!

2)колобокловок!

3)крексфекспекс!

Из алфавита исключены ё, Й. Таким образом буквы имеют номера от 0(а) до 31(!)

А начинается А(0 0 0 0 0)

4.Динамически декодировать по Хаффману (подпункты незнаю, напишу только примеры из билетов):

1)100000000000000001111000111101111110100110101100010001111001111.

2)1000000100100001011000111010100100010011111001000001111100010011111.

(примеры возможно не верны, переписывал не я так что могут быть ошибки.

Из алфавита исключены ё, Й. Таким образом буквы имеют номера от 0(а) до 31(!)

А начинается А(0 0 0 0 0).

5.Про постройку АВЛ, Случайных БДП, Рандомизированных БДП,

1)Сбалансированные БДП(АВЛ-деревья):

Набор(20 90 30 80 40 70 10 60 50)

А)Построить последовательность АВЛ-деревьев, полученных поочередной вставкой данных из входного файла

Б)Из АВЛ-дерева, построенного по всему набору элементов, исключить последовательно элементы 90 и 50

2)Случайные БДП.

А)В файле задан набор чисел:20 70 40 10 90 60 50 80 30.Построить случайное БДП, полученное последовательной вставкой элементов из входного файла указав порядок вставки узлов.

Б)Из случайного БДП, построенного по всему набору элементов, исключить последовательно элементы 70 и 20.

В)Выполнить операцию вставки числа 55 в корень полученного БДП, отображая на рисунке преобразования и промежуточные состояния БДП.

3)Рандомизированные БДП.(Treaps).

А)Для заданного далее входного набора ключей и приоритетов {(ki, pi)}

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

Б)Из рандомизированного БДП, построенного по всему набору элементов, исключить последовательно элементы 60 и 80.

Входной набор:

{(ki, pi)}=(20;0,10), (90;0,30), (30;0,80), (80;0,70), (40;0,60), (70;0,20), (10;0,40), (60;0,90), (50;0,50).

4)Идеально сбалансированные деревья

А)Написать процедуры или функцию………,сбалансированного дерева из заданного ……..вводятся из файла.

Б)привести примеры построенного…….. заданной далее последовательности элементов.

1)10 40 30 50 100 60 90 20 70 80… 

2)100 90 80 70 60 50 40 30 20 10….

3)10 20 30 40 50 60 70 80 90 100….

Какое из этих деревьев ……..

Фотка сделана на пол листа, поэтому нихрена не понятно.

5)там ещё простые БДП были, но они строятся как случайные БДП.

6.Иерархические списки мною не наблюдались.

7.Хеширование тоже вроде не кому не попалось, хотя может оно там есть.(группа маленькая не все билеты взяли).

8.ЗК тоже не видел.

ТЕОРИЯ

Билет 19

1.Оптимальные деревья бинарного поиска

2. Анализ хеширования (повторная расстановка)

Билет 17

1. Расширенные бинарные деревья. Средняя длина внешних и внутрених путей. Среднее время посика.

2. Задача коммивояжера. Методы приблизительной оценки и их применеие

Билет 4

1. Кодирование Фано-Шеннона. Реализация алгоритма кодирования, декодирования.

2. Связь задач опитимизационной комибинаторики. Триангуляция, число вариантов скобок при перемножении матриц, структурно различные бинарные деревья

Билет 2

1.Бинарные деревья с размеченными листьями.

2.Рандомизированные пирамиды поиска.

Билет 7

1. Кодирование информации по Хаффману. Оптимальность метода.

2. Бинарные деревья поиска (БДП). Поиск элемента в БДП.

Билет 18

1.Специфика дерева, леса и бинарного дерева.

2.Рандомизированные бинарные деревья поиска.

Билет 16

1. Динамическое программирование. Задание о порядке перемножения матриц

2. Повороты в БДП.

Билет 5

1.Кодирование информации по Хаффману. Реализация алгоритмов построения дерева, кодирования и декодирования.

2.Числа Каталана. Число способов перемножения матриц. Число структурно различных бинарных деревьев.

Билет 9

1. Динамическое кодирование по Хаффману. Постановка задачи и идея алгоритма.

2. Сбалансированные (АВЛ-) деревья. Деревья Фибоначчи. Анализ худшего случая.

Билет неизвестный

1. задача коммвояжера метод ветвей и границ

2. Представление упорядоченных списков рандомизированными пирамидами поиска

Билет неизвестный

1. Бэктрекинг. Другие способы программирования, рекурсия, макрокоманды.

2. АВЛ-деревья. Операции вставки и удаления в АВЛ-дереве.

Билет неизвестный

1.Задача коммивояжера. Приближенные решения и их использование в методе ветвей и границ.

2.Расширенные бинарные деревья. Длина внутренних и внешних путей. Среднее время удачного и неудачного поиска в заданном БДП.

Билет 3

1. Префиксный код и неравенство Крафта.

2. методы поиска с использованием функции расстановки (хеширование).

Билет неизвестный

1. Динамическое кодирование по Хаффману, привести пример.

2. Хорошие деревья бинарного поиска.

Билет неизвестный.

1)Не рекурсивные процедуры обхода бинарных деревьев.

2)Среднее время поиска в бинарных деревьях.

Билет 6

1)Сложность алгоритма Хаффмана.

2) Случайные деревья бинарного поиска. Операции удаления. Поиска максимума и минимума.

P. S. вроде сдали все, даже те кто написали практику на 2,но по теории что-то было, правда они ждали очень долго. Ивановский в своем стилеJ

P. P.S. привязывать практику к билетам не стал, потому что ивановский сам её раздает, и может раздать по разному, то бишь если у меня к билету 2 было кодирование хаффмана рококобарокко!, а он может дать что-то другое но по хаффману.