Программные системы

Алгоритмы и анализ сложности
Составитель	Жданова А.Н.
Уровень	Бакалавриат
Семестр	4
Описание курса	Курс «Алгоритмы и анализ сложности» предназначен для студентов, стремящихся овладеть базовыми знаниями в области структур данных и алгоритмов. Дисциплина помогает понять, как разрабатывать эффективные алгоритмы и оценивать их алгоритмическую сложность. В рамках курса изучаются основные фундаментальные алгоритмы, включая те, что часто применяются в IT-компаниях. Внимание уделяется как теоретическим аспектам, так и практическим навыкам, включая примеры задач, которые могут встретиться на собеседованиях при приеме на работу.
Необходимые знания	Базовые знания программирования – понимание принципов работы алгоритмов и основных структур данных. Опыт работы с математикой – знание основ теории вероятностей, дискретной математики и математической логики. Знание одного из языков программирования – умение писать код на одном из популярных языков программирования (Python, Java, C++, и т.д.).
Связь с другими дисциплинами	Математический анализ, Теория вероятностей и математическая статистика, Дискретная математика, Основы программирования
Языки программирования	По выбору студента (Python, Java, C++, и т.д.)
Темы курса	1. Определение алгоритма, эффективности программы, O-сложность алгоритмов 2. Экспоненциальное и полиномиальное время алгоритма 3. Метод «Разделяй и властвуй» 4. Сортировки 5. Среднее время операции, понятие потенциала, учетная стоимость операции 6. Список, очередь, дек 7. Простые структуры данных 8. Дополнительные структуры данных (хэш-таблицы, динамические массивы и т.д.) 9. Жадные алгоритмы 10. Динамическое программирование 11. Деревья 12. Графы 13. Алгоритмы на строках
Чему научится студент	• Уверенное владение методами оценки сложности алгоритмов и их оптимизации. • Умение разрабатывать алгоритмы, оптимальные с точки зрения времени и ресурсов. • Практика решения типичных задач, встречающихся на собеседованиях в ведущих IT-компаниях. • Понимание и применение различных структур данных и алгоритмов работы с данными.