Эффективные алгоритмы

2024/2025

Статус: Маго-лего

Кто читает: Департамент информатики

Охват аудитории: для своего кампуса

Преподаватели: Козлова Дарья Дмитриевна, Копелиович Сергей Владимирович, Ткаченко Данил Михайлович

Язык: русский

Кредиты: 6

Контактные часы: 56

Полная версия программы учебной дисциплины

Аннотация

В курсе рассматриваются основные подходы к анализу и проектированию алгоритмов и структур данных. Среди тем, изучаемых в курсе, — асимптотическая оценка сложности алгоритма в худшем случае, эффективные алгоритмы сортировки и выбора порядковых статистик, структуры данных (двоичные деревья поиска, кучи, хеш-таблицы), способы проектирования алгоритмов (разделяй и властвуй, динамическое программирование, жадная стратегия), основные алгоритмы на графах (кратчайшие пути, топологическая сортировка, компоненты связности, минимальные остовные деревья).

Цель освоения дисциплины

Формирование у студентов теоретических знаний и практических навыков в области теории алгоритмов, современных структур данных и их реализации на языке программирования C++ для построения математических моделей дискретных структур и разработки программного обеспечения

Планируемые результаты обучения

Владеет основными понятиями динамисечкого программирования. Владеет понятиями кобинаторики и подмножеств. Знает основные алгоритмы и структуры данных, применяемые для различных задач.
Знает основные способы модификации базовых алгоритмов, применяемые для различных задач.
Знает основые понятия теории алгоритмов и структур данных
Использует базовые алгоритмы и подходы и модифицирует их, исходя из специфики решаемой задачи.
Подбирает оптимальный алгоритм для конкретной практической задачи, анализирует его эффективность.
Формализует и описывает алгоритм решения поставленных практических задач. Математически корректно и адекватно записывает алгоритмы, наиболее корректно описывающие дискретные объекты прикладной задачи.
Знает методы оценки сложности алгоритмов в среднем и в худшем случаях, базовые и продвинутые абстрактные структуры данных, постановки основных задач, основные классы алгоритмов.
Умеет оценивать сложность алгоритмов в среднем и в худшем случаях, выделять из практических задач их алгоритмическую составляющую, реализовывать изученные алгоритмы и структуры данных на процедурных языках программирования, выбирать оптимальные алгоритмы и структуры данных, в зависимости от конкретных ограничений на решение задачи, применять приближённые алгоритмы в тех случаях, когда эффективное точное решение невозможно.
Имеет навыки оценки сложности алгоритмов в среднем и в худшем случаях, реализации алгоритмов и структур данных на процедурных языках программирования.

Содержание учебной дисциплины

Раздел 1. Основные понятия теории алгоритмов и структур данных
Раздел 2. Динамическое программирование. Комбинаторные и графовые алгоритмы
Раздел 3. Элементы теории сложности алгоритмов. Кратчайшие пути. Жадные алгоритмы
Раздел 4. Деревья поиска, деревья отрезков и другие аналогичные структуры
Раздел 5. Алгоритмы на графах. Потоки в орграфах. Строки
Раздел 6. Игры на графах. Быстрое преобразование Фурье. Линейная алгебра

Элементы контроля

Экзамен
Письменный экзамен проводится в форме ответов на вопросы экзаменационного билета. Экзаменационный билет содержит два вопроса из перечня вопросов к экзамену. На подготовку ответа выделяется 2,5 часа.
Домашнее задание №2
Домашнее задание №2 выдается студентам в одном варианте и состоит из 6 задач. Каждой задаче присвоен свой балл. Срок выполнения домашнего задания - 2 недели. Форма представления обучающимися домашнего задания - представленные в письменном виде решения задач.
Коллоквиум
Коллоквиум проводится в форме ответов на вопросы билета. Билет содержит два вопроса из перечня вопросов кколлоквиуму. На подготовку ответа выделяется 2,5 часа.
Домашнее задание №1
Домашнее задание №1 выдается студентам в одном варианте и состоит из 6 задач. Каждой задаче присвоен свой балл. Срок выполнения домашнего задания - 2 недели. Форма представления обучающимися домашнего задания - представленные в письменном виде решения задач.

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

2024/2025 2nd module
Результирующая оценка по дисциплине рассчитывается следующим образом: Орез = (Оит1 + Оит2) / 2, где Оит1 = 0,59*Од/з1 + 0,41*Окол (оценка за первый модуль) Оит2 = 0,59*Од/з2 + 0,41*Оэкз (оценка за второй модуль)

Список литературы

Авторы

Кузнецов Антон Михайлович
Юдаева Оксана Юрьевна

Программа дисциплины