Магистратура
2023/2024
Эффективные алгоритмы
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Лучший по критерию «Новизна полученных знаний»
Статус:
Курс обязательный (Вычислительная биология и биоинформатика)
Направление:
01.04.02. Прикладная математика и информатика
Кто читает:
Департамент информатики
Когда читается:
1-й курс, 1, 2 модуль
Формат изучения:
без онлайн-курса
Охват аудитории:
для своего кампуса
Преподаватели:
Зубаков Алексей Васильевич,
Кузнецов Антон Михайлович,
Москвин Денис Николаевич,
Тимофеева Мария Александровна
Прогр. обучения:
Вычислительная биология и биоинформатика
Язык:
русский
Кредиты:
6
Контактные часы:
56
Программа дисциплины
Аннотация
В курсе рассматриваются основные подходы к анализу и проектированию алгоритмов и структур данных. Среди тем, изучаемых в курсе, — асимптотическая оценка сложности алгоритма в худшем случае, эффективные алгоритмы сортировки и выбора порядковых статистик, структуры данных (двоичные деревья поиска, кучи, хеш-таблицы), способы проектирования алгоритмов (разделяй и властвуй, динамическое программирование, жадная стратегия), основные алгоритмы на графах (кратчайшие пути, топологическая сортировка, компоненты связности, минимальные остовные деревья).
Цель освоения дисциплины
- Формирование у студентов теоретических знаний и практических навыков в области теории алгоритмов, современных структур данных и их реализации на языке программирования C++ для построения математических моделей дискретных структур и разработки программного обеспечения
Планируемые результаты обучения
- Владеет основными понятиями динамисечкого программирования. Владеет понятиями кобинаторики и подмножеств. Знает основные алгоритмы и структуры данных, применяемые для различных задач.
- Знает основные способы модификации базовых алгоритмов, применяемые для различных задач.
- Знает основые понятия теории алгоритмов и структур данных
- Использует базовые алгоритмы и подходы и модифицирует их, исходя из специфики решаемой задачи.
- Подбирает оптимальный алгоритм для конкретной практической задачи, анализирует его эффективность.
- Формализует и описывает алгоритм решения поставленных практических задач. Математически корректно и адекватно записывает алгоритмы, наиболее корректно описывающие дискретные объекты прикладной задачи.
- Знает методы оценки сложности алгоритмов в среднем и в худшем случаях, базовые и продвинутые абстрактные структуры данных, постановки основных задач, основные классы алгоритмов.
- Умеет оценивать сложность алгоритмов в среднем и в худшем случаях, выделять из практических задач их алгоритмическую составляющую, реализовывать изученные алгоритмы и структуры данных на процедурных языках программирования, выбирать оптимальные алгоритмы и структуры данных, в зависимости от конкретных ограничений на решение задачи, применять приближённые алгоритмы в тех случаях, когда эффективное точное решение невозможно.
- Имеет навыки оценки сложности алгоритмов в среднем и в худшем случаях, реализации алгоритмов и структур данных на процедурных языках программирования.
Содержание учебной дисциплины
- Раздел 1. Основные понятия теории алгоритмов и структур данных
- Раздел 2. Динамическое программирование. Комбинаторные и графовые алгоритмы
- Раздел 3. Элементы теории сложности алгоритмов. Кратчайшие пути. Жадные алгоритмы
- Раздел 4. Деревья поиска, деревья отрезков и другие аналогичные структуры
- Раздел 5. Алгоритмы на графах. Потоки в орграфах. Строки
- Раздел 6. Игры на графах. Быстрое преобразование Фурье. Линейная алгебра
Элементы контроля
- ЭкзаменПисьменный экзамен проводится в форме ответов на вопросы экзаменационного билета. Экзаменационный билет содержит два вопроса из перечня вопросов к экзамену. На подготовку ответа выделяется 2,5 часа.
- Домашнее задание №2Домашнее задание №2 выдается студентам в одном варианте и состоит из 6 задач. Каждой задаче присвоен свой балл. Срок выполнения домашнего задания - 2 недели. Форма представления обучающимися домашнего задания - представленные в письменном виде решения задач.
- КоллоквиумКоллоквиум проводится в форме ответов на вопросы билета. Билет содержит два вопроса из перечня вопросов кколлоквиуму. На подготовку ответа выделяется 2,5 часа.
- Домашнее задание №1Домашнее задание №1 выдается студентам в одном варианте и состоит из 6 задач. Каждой задаче присвоен свой балл. Срок выполнения домашнего задания - 2 недели. Форма представления обучающимися домашнего задания - представленные в письменном виде решения задач.
Промежуточная аттестация
- 2023/2024 учебный год 2 модульРезультирующая оценка по дисциплине рассчитывается следующим образом: Орез = (Оит1 + Оит2) / 2, где Оит1 = 0,59*Од/з1 + 0,41*Окол (оценка за первый модуль) Оит2 = 0,59*Од/з2 + 0,41*Оэкз (оценка за второй модуль)
Список литературы
Рекомендуемая основная литература
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms (3rd edition). – MIT Press, 2009. – 1292 pp.
- Алгоритмы и структуры данных: Учебник / Белов В.В., Чистякова В.И. - М.:КУРС, НИЦ ИНФРА-М, 2016. - 240 с.: 60x90 1/16. - (Бакалавриат) (Переплёт 7БЦ) ISBN 978-5-906818-25-6 - Режим доступа: http://znanium.com/catalog/product/551224
Рекомендуемая дополнительная литература
- 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
- Структуры и алгоритмы обработки данных: обьектно ориентированный подход и реализация на С++ - 5-94157-506-8 - Кубенский А. - 2010 - Санкт-Петербург: БХВ-Петербург - https://ibooks.ru/bookshelf/18563 - 18563 - iBOOKS