rpd000002491 (1006606), страница 3
Текст из файла (страница 3)
Тип лекции: Информационная лекция
Форма организации: Лекция, мастер-класс
Описание: B-деревья. Вставка элемента в B-дерево. Удаление элемента из B-дерева.
1.1.4. Дерево ключей(АЗ: 6, СРС: 8)
Тип лекции: Информационная лекция
Форма организации: Лекция, мастер-класс
Описание: Дерево PATRICIA. Вставка нового элемента в дерево PATRICIA. Удаление элемента из дерева PATRICIA.
1.1.5. Поиск образца в строке.(АЗ: 6, СРС: 8)
Тип лекции: Информационная лекция
Форма организации: Лекция, мастер-класс
Описание: Основной алгоритм предварительной обработки образца. Использование Z-блоков для поиска образца в строке. Алгоритм Кнута-Мориса-Пратта. Алгоритм Ахо-Корасик. Алгоритм Бойера-Мура.Алгоритм Апостолико-Джанкарло.
1.1.6. Суффиксные деревья(АЗ: 6, СРС: 8)
Тип лекции: Информационная лекция
Форма организации: Лекция, мастер-класс
Описание: Наивный алгоритм построения суффиксного дерева. Неявные суффиксные деревья. Алгоритм Укконена. Приложения суффиксных деревьев. Сжатие дерева. Бинарный поиск образца в суффиксном массиве. Обратный поиск.
2.1.1. Длинная арифметика.(АЗ: 4, СРС: 2)
Тип лекции: Информационная лекция
Форма организации: Лекция, мастер-класс
Описание: Классические алгоритмы сложения, вычитания, умножения и возведения в степень длинных чисел. Классический алгоритм деления длинных чисел. Алгоритм умножения Тоома-Кука. Алгоритм деления с использованием быстрого умножения.
2.1.2. Модульная арифметика(АЗ: 2, СРС: 2)
Тип лекции: Информационная лекция
Форма организации: Лекция, мастер-класс
Описание: Китайская теорема об остатках. Оценка скорости выполнения умножения.
2.1.3. Полиномы(АЗ: 6, СРС: 2)
Тип лекции: Информационная лекция
Форма организации: Лекция, мастер-класс
Описание: Операции над полиномами. Дискретное преобразование Фурье. Алгоритм быстрого преобразования Фурье.
2.1.4. Динамическое программирование.(АЗ: 6, СРС: 2)
Тип лекции: Информационная лекция
Форма организации: Лекция, мастер-класс
Описание: Перекрытие подзадач, построение оптимального решения. Применение динамического программирования для решения задачи о расписании работы конвейера, о перемножении цепочки матриц. Оптимальные деревья поиска. Задача о максимальном совпадении двух строк и поиске самой длинной общей подпоследовательности. Расстояние Левен-штейна.
2.1.5. Жадные алгоритмы(АЗ: 6, СРС: 2)
Тип лекции: Информационная лекция
Форма организации: Лекция, мастер-класс
Описание: Свойство жадного выбора и элементы жадной стратегии. Решение задачи о выборе процессов. Понятие о префиксных кодах, коды Хаффмана, их построение. Корректность алгоритма Хаффмана. Матроиды. Задача о расписании. Поиск максимальной возрастающей подпоследовательности. Сведение задачи о возрастающей подпоследовательности к задаче о максимальной совпадающей подпоследовательности.
2.1.6. Теория информации(АЗ: 6, СРС: 2)
Тип лекции: Информационная лекция
Форма организации: Лекция, мастер-класс
Описание: Наивный байесовский классификатор. Понятие энтропии, её свойства. Количество информации. Энтропия источника. Канал передачи данных, его пропускная способность в идеальных условиях и при наличии шума. Оптимальное кодирование, код Шеннона-Фано. Теоремы Шеннона. Коды Хэмминга.
2.1.7. Сжатие текстов(АЗ: 6, СРС: 2)
Тип лекции: Информационная лекция
Форма организации: Лекция, мастер-класс
Описание: Адаптивные модели. Проблема символов с нулевой частотой. Коды Хаффмана. Арифметическое кодирование. Символьные модели сжатия текстов. Словарные методы сжатия. Использование суффиксных деревьев для сжатия данных по аналогии со словарным методом Зива-Лемпеля.
-
Практические занятия
-
Лабораторные работы
1.1.1. Сортировка за линейное время(АЗ: 8, СРС: 18)
Форма организации: Лабораторная работа
1.1.2. Поиск образца в строках(АЗ: 8, СРС: 18)
Форма организации: Лабораторная работа
1.1.3. Построение словаря с использованием деревьев различного вида (сбалансированные, B-деревья, цифровой поиск, PATRICIA)(АЗ: 8, СРС: 18)
Форма организации: Лабораторная работа
1.1.4. Поиск кратчайших путей в графе, построение остовного дерева.(АЗ: 8, СРС: 19)
Форма организации: Лабораторная работа
2.1.1. Реализация алгоритмов работы с длинными числами: сложение, вычитание, умножение, деление.(АЗ: 8, СРС: 4)
Форма организации: Лабораторная работа
2.1.2. Связь битовых и арифметических операций.(АЗ: 8, СРС: 4)
Форма организации: Лабораторная работа
2.1.3. Динамическое программирование.(АЗ: 8, СРС: 4)
Форма организации: Лабораторная работа
2.1.4. Построение классификатора данных с самообучением (Байесовский, метод Фишера). Оценка количества ложных срабатываний.(АЗ: 8, СРС: 4)
Форма организации: Лабораторная работа
-
Типовые задания
Приложение 3
к рабочей программе дисциплины
«Дискретный анализ »
Прикрепленные файлы
Версия: AAAAAAQvW4k Код: 000002491
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
