Основы разработки и анализа алгоритмов

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

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

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

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

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

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

ПК-3 Способен ориентироваться в современных алгоритмах компьютерной математики; обладать способностями к эффективному применению и реализации математически сложных алгоритмов в современных программных комплексах