Описание:Учебный курс рассчитан на студентов магистратуры первого года обучения.
Цели курса:
Изучение эффективных математических алгоритмов, используемых в современных информационных системах. Расширение представлений студентов о методологии построения эффективных вычислительных алгоритмов в области распознавания образов. Приобретение навыков разработки вычислительных алгоритмов для решения задач распознавания изображений и видеопоследовательностей.
Основные темы курса:
1.Алгоритмическая парадигма «Разделяй и властвуй». Умножение чисел. Основная теорема о рекуррентных соотношениях. Алгоритм Штрассена умножения матриц. Сортировка слиянием. Выпуклые оболочки.
2.Медиана. Алгоритм вычисления на основе рандомизации (вероятностный алгоритм).
3.Жадные алгоритмы, минимальное покрытие графа. Алгоритм Крускала. Евклидово минимальное покрытие. Триангуляция Делоне, ЕМОД.
4.Динамическое программирование. Топологическая сортировка ориентированного ациклического графа. Наибольшая возрастающая последовательность. Расстояние редактирования, вычисление с помощью динамического программирования.
5.Быстрое преобразование Фурье. Произведение многочленов, приложение к цифровой обработке сигналов. Шаги Вычисление и Интерполяция. Формула обращения.
6.Вычислительная геометрия. Подсчет пересечений отрезков. Алгоритмическая парадигма плоского заметания. Структуры «Статус заметающей прямой» и «Очередь событий». O((N+K) log N) алгоритм для K пересечений N отрезков. Диаграмы Вороного.