rpd000002491 (010400 (01.03.02).Б1 Информатика), страница 2

Тематика:

Трудоемкость(СРС): 19

Прикрепленные файлы:

Типовые варианты:

-Разработка и реализация развитой поисковой системы.

-Разработка программ сжатия и распаковки данных.

-Разработка программ помехоустойчивого кодирования.

1. Рубежный контроль

1. Промежуточная аттестация

1. экзамен (3 семестр)

Прикрепленные файлы:

Вопросы для подготовки к экзамену/зачету:

1.Недостижимость линейной оценки времени для алгоритмов сортировок, основанных на сравнениях элементов.

2.Сортировка за линейное время. Метод сортировки посдчётом, поразрядная сортировка

3.Сортировка за линейное время. Карманная сортировка

4.Деревья поиска. Идеально сбалансированные деревья. АВЛ-деревья. Вставка нового узла в АВЛ-дерево.

5.Деревья поиска. Идеально сбалансированные деревья. АВЛ-деревья. Удаление узла из АВЛ-дерева.

6.Деревья поиска. Идеально сбалансированные деревья. Красно-черные деревья. Вставка нового узла в красно-черное дерево.

7.Деревья поиска. Идеально сбалансированные деревья. Красно-черные деревья. Удаление узла из красно-черного дерева.

8.Сильноветвящиеся деревья, B-деревья. Вставка элемента в B-дерево.

9.Сильноветвящиеся деревья, B-деревья. Удаление элемента из B-дерева.

10.Дерево ключей. Дерево PATRICIA. Вставка нового элемента в дерево PATRICIA.

11.Дерево ключей. Дерево PATRICIA. Удаление элемента из дерева PATRICIA.

12.Поиск образца в строке. Основной алгоритм предварительной обработки образца. Использование Z-блоков для поиска образца в строке.

13.Алгоритм Кнута-Мориса-Пратта. Построение функций sp и sp' на основе Z-блоков. Вариант алгоритма Кнута-Мориса-Пратта реального времени.

14.Алгоритм Кнута-Мориса-Пратта. Построение функций sp и sp' «классическим» способом.

15.Множественный поиск образцов в строке. Алгоритм Ахо-Корасик.

16.Построение связей неудач для дерева ключей. Поиск в строке образца с метасимволами («джокерами»).

17.Алгоритм Бойера-Мура. Правило плохого символа, расширенное правило плохого символа. Сильное и слабое правило хорошего суффикса. Предварительная обработка образца с использованием Z-блоков. Реализация алгоритма Бойера-Мура.

18.Алгоритм Апостолико-Джанкарло с линейной оценкой времени.

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

20.Суффиксные деревья. Неявные суффиксные деревья. Построение суффиксного дерева за линейное время, общее описание алгоритма Укконена.

21.Суффиксные деревья. Алгоритм Укконена. Суффиксные связи и их построение.

22.Суффиксные деревья. Алгоритм Укконена. Использование суффиксных связей для достижения оценки O(n2), алгоритм отдельного продолжения.

23.Суффиксные деревья. Алгоритм Укконена. Детали реализации, важные для линейности алгоритма. Подробное описание одной фазы с учётом деталей реализации.

24.Обобщенное суффиксное дерево для набора строк. Трудности использования суффиксных деревьев для алфавитов большой размерности.

25.Суффиксные деревья. Приложения суффиксных деревьев: поиск образца в строке, множественный поиск образцов в строке.

26.Суффиксные деревья. Приложения суффиксных деревьев: Решение задачи о наибольшей общей подстроке для двух строк; для большого количества строк; линеариазация циклической строки.

27.Суффиксные деревья. Приложения суффиксных деревьев: статистика совпадений, решение с её помощью задачи о поиске образца в строке и задачи о наибольшей общей подстроке двух строк.

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

29.Суффиксные массивы. Бинарный поиск образца в суффиксном массиве. Использование свойств суффиксного массива для уменьшения количества сравнений символов при бинарном поиске.

30.Суффиксные массивы. Преобразование Барроуза-Уилера. Обратный поиск.

31.Суффиксные массивы. Обратный поиск. Эффективная реализация обратного поиска: вейвлетные деревья и вычисление rankb(B,i) за константное время.

32.Суффиксные деревья. Обобщение алгоритма Бойера-Мура для решения задачи о множественном поиске образцов.

2. экзамен (4 семестр)

Прикрепленные файлы:

Вопросы для подготовки к экзамену/зачету:

1.Длинная арифметика. Классические алгоритмы сложения, вычитания, умножения и возведения в степень длинных чисел.

2.Длинная арифметика. Классический алгоритм деления длинных чисел.

3.Модулярная арифметика. Китайская теорема об остатках. Оценка скорости выполнения умножения.

4.Длинная арифметика. Алгоритм умножения Тоома-Кука. Алгоритм деления с использованием быстрого умножения.

5.Полиномы, коэффициентное и интерполяционное представление полиномов. Операции над полиномами. Дискретное преобразование Фурье.

6.Алгоритм быстрого преобразования Фурье. Прямое и обратное БПФ. Использование БПФ для перемножения полиномов.

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

8.Динамическое программирование. Перекрытие подзадач, построение оптимального решения. Применение динамического программирования для решения задачи о перемножении цепочки матриц.

9.Динамическое программирование. Перекрытие подзадач, построение оптимального решения. Оптимальные деревья поиска.

10.Динамическое программирование. Перекрытие подзадач, построение оптимального решения. Задача о максимальном совпадении двух строк и поиске самой длинной общей подпоследовательности. Расстояние Левен-штейна.

11.Жадные алгоритмы, связь с динамическим программированием. Свойство жадного выбора и элементы жадной стратегии. Решение задачи о выборе процессов.

12.Жадные алгоритмы. Свойство жадного выбора и элементы жадной стратегии. Понятие о префиксных кодах, коды Хаффмана, их построение. Корректность алгоритма Хаффмана.

13.Теоретические основы жадных алгоритмов. Матроиды. Жадные алгоритмы для взвешенного матроида.

14.Матроиды. Задача о расписании.

15.Жадные алгоритмы. Поиск максимальной возрастающей подпоследовательности.

16.Жадные алгоритмы. Сведение задачи о возрастающей подпоследовательности к задаче о максимальной совпадающей подпоследовательности. Максимальная совпадающая подпоследовательность более чем для двух строк.

17.Базовые понятия теории вероятностей. Наивный байесовский классификатор.

18.Теория информации. Понятие энтропии, её свойства. Количество информации. Энтропия источника.

19.Теория информации. Канал передачи данных, его пропускная способность в идеальных условиях и при наличии шума. Оптимальное кодирование, код Шеннона-Фано. Теоремы Шеннона. Коды Хэмминга.

20.Сжатие текстов, модели текста. Адаптивные модели. Проблема символов с нулевой частотой.

21.Коды Хаффмана. Неоднозначность кодов Хаффмана. Адаптивные коды Хаффмана.

22.Канонические коды Хаффмана. Эффективное кодирование и декодирование с использованием канонических кодов Хаффмана.

23.Канонические коды Хаффмана. Быстрое вычисление длин кодов Хаффмана.

24.Арифметическое кодирование, реализация.

25.Быстрое вычисление сумм частот символов при их частом изменении. Дерево Фенвика и операции над ним.

26.Символьные модели сжатия текстов. Предсказание по частичному совпадению, различные варианты метода.

27.Символьные модели сжатия текстов. Преобразование Барроуза-Уиллера. Использование преобразования Барроуза-Уиллера для сжатия текстов, связь с суффиксными деревьями. Кодирование методом Move-To-Front.

28.Символьные модели сжатия текстов. Динамическое Марковское сжатие, детали реализации. Использование слов в качестве символов для символьных моделей.

29.Словарные методы сжатия. Алгоритм LZ77, детали реализации. Использование LZ77 в программе gzip.

30.Словарные методы сжатия. Алгоритмы LZ78, LZW. Детали реализации.

31.Суффиксные деревья. Использование суффиксных деревьев для сжатия данных по аналогии со словарным методом Зива-Лемпеля.

1. УЧЕБНО-МЕТОДИЧЕСКОЕ И ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

а)основная литература:

1. Романовский И.В. Дискретный анализ: Учебное пособие для студентов, специализирующихся по прикладной математике и информатике. – СПб.: Невский диалект; БХВ-Петербург, 2004.

2. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. Основание информатики. – М.: Мир, 1998.

3. Кормэн Т.Х., Лейзерсон Ч.И., Ривест Р.Л., Штайн К. Алгоритмы: построение и анализ, 2-е издание. : Пер. с англ. –М.: Издательский дом «Вильямс», 2005. –1296 с.: ил. (ISBN 5-8459-0857-4 (рус.)).

4. Кнут Д. Искусство программирования. В 3-х томах. –М: Вильямс, 2007 г. –720 с. (ISBN 5-8459-0080-8, 0-201-89683-4).

5. Липский В. Комбинаторика для программистов. Пер. с польск. –М.: Мир,1988. –212 с.

6. Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы, матроиды, алгоритмы. –Ижевск, 2001.

7. Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. –СПб: Невский диалект; БХВ-Петербург, 2003. –656 с., ил. (ISBN: 5-94157-321-9).

8. Лорин Г. Сортировка и системы сортировки. Пер. с англ. –М.: Финансы и статистика, 1983. 384 с.

б)дополнительная литература:

в)программное обеспечение, Интернет-ресурсы, электронные библиотечные системы:

1. МАТЕРИАЛЬНО-ТЕХНИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДИСЦИПЛИНЫ

Преподавателю для демонстрации сопровождающих материалов во время проведения лекций потребуется следующее оборудование:

• Ноутбук.

• Проектор.

Студентам, для выполнения лабораторных работ, потребуется по одному персональному компьютеру или терминалу сервера,

работающего под управлением операционной системы семейства Unix. Должна быть установлена система программирования GCC

или аналогичная.

Приложение 1
к рабочей программе дисциплины
«Дискретный анализ »

Аннотация рабочей программы

Дисциплина Дискретный анализ является частью Математического и естественно-научный цикл дисциплин подготовки студентов по направлению подготовки Прикладная математика и информатика. Дисциплина реализуется на 8 факультете «Московского авиационного института (национального исследовательского университета)» кафедрой (кафедрами) 806.

Дисциплина нацелена на формирование следующих компетенций: ПК-2 ,ПК-3 ,ПК-5 ,ПК-8 ,ПК-9 ,ДПК-16.

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

Преподавание дисциплины предусматривает следующие формы организации учебного процесса: Лекция, мастер-класс, Лабораторная работа.

Программой дисциплины предусмотрены следующие виды контроля: промежуточная аттестация в форме экзамен (3 семестр) ,экзамен (4 семестр).

Общая трудоемкость освоения дисциплины составляет 10 зачетных единиц, 360 часов. Программой дисциплины предусмотрены лекционные (72 часов), практические (0 часов), лабораторные (64 часов) занятия и (170 часов) самостоятельной работы студента. Дисциплина «Дискретный анализ» является частью цикла дисциплин по информационным технологиям подготовки студентов

по направлению 010400 профиля «Информатика»(каф. 806). Дисциплина реализуется на факультете «Прикладная математика и физика»

Московского авиационного института кафедрой 806 «Вычислительная математика и программирование».

Приложение 2
к рабочей программе дисциплины
«Дискретный анализ »

Cодержание учебных занятий

1. Лекции

1.1.1. Сортировка за линейное время(АЗ: 6, СРС: 8)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Недостижимость линейной оценки времени для алгоритмов сортировок, основанных на сравнениях элементов. Метод сортировки посдчётом, поразрядная сортировка. Карманная сортировка.

1.1.2. Деревья поиска.(АЗ: 6, СРС: 8)

Тип лекции: Информационная лекция

Форма организации: Лекция, мастер-класс

Описание: Идеально сбалансированные деревья. АВЛ-деревья. Вставка нового узла в АВЛ-дерево. Удаление узла из АВЛ-дерева. Красно-черные деревья. Вставка нового узла в красно-черное дерево. Удаление узла из красно-черного дерева.

1.1.3. Сильноветвящиеся деревья(АЗ: 6, СРС: 8)