School of Software Engineering

Regular version of the site

Article

Statistical testing of segment homogeneity in classification of piecewise-regular objects

International Journal of Applied Mathematics and Computer Science. 2015. Vol. 25. No. 4. P. 915-925.

Article

Reconstruction of a word from a finite set of its subwords under the unit shift hypothesis. I. Reconstruction without for bidden words1

Smetanin Y., Ulyanov M.

Cybernetics and Systems Analysis. 2015. Vol. 50. No. 1. P. 148-156.

Article

VTMine Framework as Applied to Process Mining Modeling

Sergey Andreevich Shershakov.

International Journal of Computer and Communication Engineering. 2015. Vol. 4. No. 3. P. 166-179.

All publications

Delivered by:: School of Software Engineering

Type:: Compulsory course

When:: 2 year, 1-4 module

Instructors

Ignatov, Andrei

Nesterov, Roman

Дополнительные материалы в 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

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

Авторы

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

Algorithms and Data Structures

Instructors

Программа дисциплины

Аннотация

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

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

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

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

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

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

Рекомендуемая основная литература

Рекомендуемая дополнительная литература

Авторы