Efficient Algorithms

2022/2023

Academic Year

RUS

Instruction in Russian

6

ECTS credits

Delivered at:

Department of Informatics

Course type:

Compulsory course

When:

1 year, 1, 2 module

Instructors

Деб Натх Максим

Курилкин Александр Сергеевич

Moskvin, Denis

Орешников Даниил Михайлович

Саютин Дмитрий Сергеевич

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

Аннотация

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

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

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

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

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

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

• Раздел 1. Основные понятия теории алгоритмов и структур данных
• Раздел 2. Динамическое программирование. Комбинаторные и графовые алгоритмы

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

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

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

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

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

Рекомендуемая основная литература

• Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms (3rd edition). – MIT Press, 2009. – 1292 pp.

Рекомендуемая дополнительная литература

• 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 - 18563 - https://ibooks.ru/bookshelf/18563/reading - iBOOKS

Авторы

• Кузнецов Антон Михайлович
• Спицина Кристина Станиславовна