Цели и задачи дисциплины
Целью дисциплины является обучение студентов оценке эффективности алгоритмов и структур данных. Задачи дисциплины:
- изучить этапы решения алгоритмических задач, методы оценки и доказательства эффективности алгоритма;
- научиться выбирать эффективные структуры данных для решения задач;
- изучить основные методы решения, научиться применять их на практике.
Краткое содержание дисциплины
Этапы решения алгоритмической задачи. Типы задач. Основы анализа эффективности алгоритмов и структур данных. Асимптотические обозначения. Инварианты. Методы грубой силы. Метод декомпозиции. Метод уменьшения размера задачи. Метод преобразования. Пространственно-временной компромисс. Динамическое программирование. Жадные методы. Доказательства нижних границ. Р, NP и NP-полные задачи. Приближенные алгоритмы для NP-сложных задач. Метод ветвей и границ.
Компетенции обучающегося, формируемые в результате освоения дисциплины
ОПК-2
Способен применять методы математического и алгоритмического моделирования, современный математический аппарат в научно-исследовательской и опытно-конструкторской деятельности