Алгоритмы и структуры данных

Цели и задачи дисциплины

Целью дисциплины является обучение студентов оценке эффективности алгоритмов и структур данных. Задачи дисциплины: - изучить этапы решения алгоритмических задач, методы оценки и доказательства эффективности алгоритма; - научиться выбирать эффективные структуры данных для решения задач; - изучить основные методы решения, научиться применять их на практике.

Краткое содержание дисциплины

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

Компетенции обучающегося, формируемые в результате освоения дисциплины

Выпускник должен обладать:

ОПК-2 Способен применять методы математического и алгоритмического моделирования, современный математический аппарат в научно-исследовательской и опытно-конструкторской деятельности