Департамент программной инженерии

АБB
АБB
АБB

Обычная версия сайта

Департамент программной инженерии был создан в 2014 году на базе отделения программной инженерии. В департаменте ведутся исследования по различным современным научным направлениям, в число которых входят: анализ и моделирование бизнес процессов, математическое моделирование, машинное обучение и искусственный интеллект, нечеткая логика, процессно-ориентированные информационные системы.

Мероприятия

1 октября, 09:30

Конференция "Моделирование и анализ распределенных систем (МАРС)"

9 октября, 16:00

Предварительная защита кандидатской диссертации Косова П.В.

Все мероприятия

Публикации

Книга

The Dynamic Adaptive Packet Buffering (DAPB) Algorithm for Service Mesh Performance Enhancement Based on eBPF
В печати

Hank-Debain Djambong Tenkeu, Alexandrov D.

Vol. 37. Iss. 5. Institute for System Programming of the RAS, 2025.

Статья

Evaluating Structural Complexity of Workflow Nets Modeling Asynchronous Agent Interactions

Е. Zemlyanoy, R. Nesterov.

Proceedings of the Institute for System Programming of the RAS. 2025. Vol. 37. No. 4-2. P. 47-68.

Глава в книге

Scalable Top-K Subarray Searches: Seamless and Distributed NetCDF API Interception
В печати

Habibur Rahman H., Rodriges Zalipynis R. A.

In bk.: Communications in Computer and Information Science. Springer, 2025. Ch. 1.

Препринт

Approach to Designing CV Systems for Medical Applications: Data, Architecture and AI
В печати

Ryabtsev D., Vasilyev Boris, Shershakov S.

Computer Science ::Computer Vision and Pattern Recognition. 2501.14689. arXiv, 2025

Все публикации

Кто читает:: Департамент программной инженерии

Статус:: Курс обязательный

Когда читается:: 2-й курс, 1-4 модуль

Преподаватели

Игнатов Андрей Дмитриевич

Нестеров Роман Александрович

Дополнительные материалы в LMS Задать вопрос

Аннотация

Учебный курс "Алгоритмы и структуры данных" является обязательной дисциплиной для студентов второго курса по направлению "Программная инженерия" факультета компьютерных наук НИУ ВШЭ. Основная цель курса заключается в формировании у студентов навыков анализа производительности алгоритмов, работающих с различными структурами данных, и выбора оптимальных решений для конкретных практических задач. В ходе обучения рассматриваются методы асимптотического анализа сложности как детерминированных, так и стохастических алгоритмов, изучаются алгоритмы сортировки, методы эффективного хранения и поиска данных, включая организацию хеш-таблиц и деревьев, а также графовые и строковые алгоритмы. Особое внимание уделяется различным парадигмам разработки алгоритмов, таким как жадные методы, приближенные алгоритмы и динамическое программирования. Кроме того, рассматриваются фундаментальный вопросы разрешимости и вычислимости. Лекции направлены на систематическое освоение материала, тогда как практические занятия позволяют закрепить полученные знания через решение задач и реализацию изученных алгоритмов и структур данных на языке программирования С++. Тесная взаимосвязь лекционного материала и практической работы обеспечивает глубокое и всестороннее освоение курса.

Цель освоения дисциплины

развитие навыков анализа производительности алгоритмов, работающих с различными структурами данных, и выбора оптимальных решений для конкретных практических задач разработки программ

Планируемые результаты обучения

овладеть подходами к анализу, проектированию и реализации базовых (массивы, списки, стеки, очереди) и продвинутых (хеш-таблицы, очереди с приоритетами, сбалансированные деревья поиска, графы) структур данных
получить практический опыт реализации изученных алгоритмов и структур данных на языке программирования С++
овладеть специальными подходами к разработке алгоритмов (стохастические и приближенные алгоритмы)
овладеть основными парадигмами разработки алгоритмов (жадные алгоритмы, динамическое программирование и "разделяй-и-властвуй")
овладеть подходами точного, асимптотического и амортизированного анализа сложности алгоритмов

Содержание учебной дисциплины

Неделя 1. Корректность и сложность алгоритма
Неделя 2. Линейные контейнеры
Неделя 3. Асимптотический анализ. Рекуррентное соотношение
Неделя 4. Асимптотический анализ. Дерево рекурсии
Неделя 5. Мастер-теорема для решения рекуррентных соотношений
Неделя 6-7. Стохастические алгоритмы
Неделя 8. Сортировка, основанная на сравнениях
Неделя 9. Линейная сортировка
Неделя 10. Бинарные деревья (поиска). Введение
Неделя 11. AVL-деревья и красно-черные деревья
Неделя 12. Случайные и декартовы деревья
Неделя 13. Splay-деревья
Неделя 14. Хеширование. Хеш-функции
Неделя 15. Хеш-таблицы
Неделя 16. Вероятностные структуры данных
Неделя 17. Графы. Базовые аспекты
Неделя 18. Остовное дерево графа
Неделя 19. Поиск кратчайших путей в графе
Неделя 20. Сети и потоки
Неделя 21. Паросочетания в графах
Неделя 22-23. Раскраска и укладка графа
Неделя 24. Поиск точного вхождения строки в текст
Неделя 25. Редакционные расстояния
Неделя 26. Поиск вхождения набора строк в текст
Неделя 27. Хранение и сортировка строк
Неделя 28. Кодирование и сжатие строк
Неделя 29. Жадный алгоритм и динамическое программирование
Неделя 30. Приближенные алгоритмы. Метод ветвей и границ
Неделя 31. Стохастические алгоритмы
Неделя 32. Разрешимость

Элементы контроля

НАКОП1
Формализуемая часть накопленной оценки регулярной работы в течение первого семестра
НАКОП2
Формализуемая часть накопленной оценки регулярной работы в течение второго семестра
ПР1
Регулярная работа на практических занятиях в течение первого семестра
ПР2
Регулярная работа на практических занятиях в течение второго семестра
ЭКЗАМЕН1
Устный экзамен по материалам первого семестра курса
ЭКЗАМЕН2
Устный экзамен по материалам второго семестра курса

Промежуточная аттестация

2025/2026 2nd module
0.48 * НАКОП1 + 0.17 * ПР1 + 0.35 * ЭКЗАМЕН1
2025/2026 4th module
0.45 * НАКОП2 + 0.2 * ПР2 + 0.35 * ЭКЗАМЕН2

Список литературы

Авторы

Нестеров Роман Александрович

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