Бакалавриат
2019/2020
Дополнительные главы алгоритмов и структур данных
Лучший по критерию «Полезность курса для Вашей будущей карьеры»
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Статус:
Курс по выбору (Прикладная математика и информатика)
Направление:
01.03.02. Прикладная математика и информатика
Кто читает:
Департамент информатики
Когда читается:
3-й курс, 4 модуль
Формат изучения:
без онлайн-курса
Преподаватели:
Копелиович Сергей Владимирович
Язык:
русский
Кредиты:
4
Контактные часы:
32
Программа дисциплины
Аннотация
Является дисциплиной по выбору. Данная дисциплина направлена на овладение продвинутыми алгоритмами решения различных задач. Существенное внимание уделяется вопросам, связанным с вероятностными алгоритмами и алгоритмами для NP-трудных задач. В результате освоения дисциплины студент должен: знать: - понятия, связанные NP-полнотой, - вероятностные алгоритмы для NP-трудных задач, - точные алгоритмы для NP-трудных задач, - приближённые алгоритмы для NP-трудных задач; уметь: - доказывать NP-трудность задач, - использовать сведения задач для решения других сложных задач, - доказывать корректность приближённых алгоритмов для NP-трудных задач; владеть: - методами вероятностного решения NP-трудных задач, - методами приближённого решения NP-трудных задач, - методами точного решения NP-трудных задач.
Цель освоения дисциплины
- Целями освоения дисциплины «Дополнительные главы алгоритмов и структур данных» являются формирование у студентов теоретических знаний и практических навыков в области дополнительных глав теории алгоритмов, современных структур данных и их реализации на языке программирования C++ для построения математических моделей дискретных структур и разработки программного обеспечения.
Планируемые результаты обучения
- Знает основную терминологию теории графов и вычислительной геометрии на русском и иностранном языках. Умеет проводить операции с многочленами. Знает паросочетания в произвольных графах. Владеет понятием линейное программирование: канонический вид, двойственность, Симплекс метод, sparse matrix; метод эллипсоидов.
- Знает основные алгоритмы работы с планарными графами, многочленами и множествами точек на плоскости. Умеет анализировать и применять существующие математические модели на основе теории графов для разработки алгоритмов. Использует модифицированные алгоритмы вычислительной геометрии и теории графов для реализации алгоритмов решения прикладных задач.Знает основные математические модели с планарными графами, а также математические подходы вычислительной геометрии.
Содержание учебной дисциплины
- Операции с многочленами. Паросочетания в произвольных графах. Линейное программирование
- Планарные графы. Вероятностные и приближенные алгоритмы. Вычислительная геометрия
Элементы контроля
- Курсовой проект
- Устный экзаменЭкзамен проводится на платформе Zoom. Экзамен проводится в устной форме (опрос по материалам курса). По просьбе преподавателя студент должен быть готов выполнить некоторые задания в письменном виде, после чего сфотографировать и выслать на почту преподавателю. К экзамену необходимо подключиться согласно расписанию, высланному преподавателем на корпоративные почты студентов накануне экзамена. Компьютер студента должен удовлетворять требованиям: наличие рабочей камеры и микрофона, поддержка платформы Zoom. Для участия в экзамене студент обязан: выбрать себе имя в Zoom совпадающее с его именем и фамилией, явиться на экзамен согласно точному расписанию, при ответе включить камеру и микрофон. Во время экзамена студентам запрещается выключать камеру. Ипользование конспектов или других справочных материалов допускается только с разрешения преподавателя. Кратковременным нарушением связи во время экзамена считается нарушение связи менее 5 минут. Долговременным нарушением связи во время экзамена считается нарушение 5 минут и более. При долговременном нарушении связи возможность продолжения студентом участие в экзамене определяется преподавателем. Процедура пересдачи подразумевает использование усложненных заданий
Промежуточная аттестация
- Промежуточная аттестация (4 модуль)0.5 * Курсовой проект + 0.5 * Устный экзамен
Список литературы
Рекомендуемая основная литература
- Алгоритмы и структуры данных : учебник / В.В. Белов, В.И. Чистякова. — М. :КУРС : НИЦ ИНФРА-М, 2017. — 240 с. — (Бакалавриат). - Режим доступа: http://znanium.com/catalog/product/766771
Рекомендуемая дополнительная литература
- Skiena, S. S. (2008). The Algorithm Design Manual (Vol. 2nd ed). London: Springer. Retrieved from http://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=edsebk&AN=277139