Проектирование эффективных алгоритмов

Общая информация о дисциплине

Цели изучения дисциплины
Изложить классификацию алгоритмических задач и алгоритмов, основанную на их сложности. Ознакомить студентов с типичными методами разработки эффективных алгоритмов и с эффективными алгоритмами решения задач из важнейших разделов дискретной математики и программирования. В частности, рассмотреть алгоритмы сортировки и поиска информации, алгоритмы для работы с множествами, алгоритмы для задач теории графов, базовые алгоритмы вычислительной геометрии, алгоритмы умножения матриц, алгоритмы для поиска образцов в строках. Развить у студентов умение оценивать сложность готовых алгоритмов и задач и конструировать собственные эффективные алгоритмы. Дать представление о типичных NP-полных задачах, для которых неизвестны эффективные алгоритмы и о подходах к их решению.
Предварительные знания и навыки, требуемые для изучения дисциплины
Для изучения дисциплины требуются предварительные знание в объеме курсов "Дискретной математики" и "Информатики".
Получаемые знания и навыки
Знание классификации алгоритмических проблем и алгоритмов по их вычислительной сложности, умение и навыки в оценке сложности задач и алгоритмов. Знание типичных приемов и методов разработки эффективных алгоритмов и умение применять их для решения алгоритмических задач. Знание эффективных алгоритмов решения типичных конкретных задач из различных разделов дискретной математики и программирования и умение вычленять эти задачи в практических ситуациях. Знание типичных NP-полных проблем и подходов к построению приближенных и эвристических алгоритмов их решения.