Алгоритмический инструментарий

2025/2026

Учебный год

RUS

Обучение ведется на русском языке

6

Кредиты

Кто читает:

Департамент больших данных и информационного поиска

Статус:

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

Когда читается:

1-й курс, 3, 4 модуль

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

Аннотация

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

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

• • Знать о наиболее важных алгоритмах и структурах данных и ос- новных принципах их проектирования и анализа
• • Иметь навыки реализации алгоритмов на языке C++
• • Уметь обосновывать корректность алгоритмов, проводить теоретическую и экспериментальную оценки их временной сложности
• • Уметь формализовать условие задачи, требующей алгоритмического решения, разбить задачу на подзадачи, сформулировать эффективный алгоритм решения задачи

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

• • -ознакомление студентов с основными принципами проектирования и анализа алгоритмов и структур данных;
• • -развитие навыков обоснования корректности алгоритмов, их практической реализации, теоретической и экспериментальной оценки их временной сложности

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

• Основы C++, настройка CLion
• Циклы, массивы и основы STL в С++
• Функции, рекурсия, перебор, анализ времени работы, O-, o-, Theta- нотации
• Основы ООП в C++
• Рекурсия, перебор, анализ времени работы, O-, o-, Theta- нотации
• Сортировки, бинарный поиск
• Линейные алгоритмы
• Одномерное и многомерное динамическое программирование.
• Задача о рюкзаке и ДП по подпоследовательностям.
• Линейные структуры данных. Реализация и знакомство с unit-тестированием структур на платформе Яндекс.Контест.
• Деревья поиска.
• Самобалансирующиеся Деревья Поиска.
• B-деревья. Решение задач на деревья.
• Хеш-таблицы.
• Sparse Table. Деревья Отрезков.
• Модификации ДО.
• Декартовы Деревья. Массовые операции.
• Декартовы Деревья по неявному ключу.
• Практика решения задач на структуры данных.

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

• Домашнее задание
  Выдаются после соответствующей лекции, дедлайн 2 недели. Формула оценивания - среднее арифметическое по кол-ву решённых задач.
• Контрольная работа
  После окончания изучения C++; На последней лекции 3 модуля по пройденным темам 3 модуля; На последней лекции 4 модуля по пройденным темам 4 модуля
• Квизы: Викторины
• Экзамен
  Проводятся на сессионной неделе 3 и 4 модуля.

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

• 2025/2026 4th module
  (Домашние задания-1 * 0.350 + Контрольная работа-1 * 0.1 + Контрольная работа-2 * 0.1 + Квизы-1 * 0.15 + Экзамен-1 * 0.3) * 0.5 + (Домашние задания-2 * 0.350 + Контрольная работа-3 * 0.2 + Квизы-2 * 0.15 + Экзамен-2 * 0.3) * 0.5

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

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

• Data structures and algorithm analysis in C++, Weiss, M. A., 2006
• Introduction to algorithms, Cormen, T. H., 2009

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

• Андрианов, И. А. Программирование на языке C++ : учебное пособие / И. А. Андрианов, Д. В. Кочкин, С. Ю. Ржеуцкая. — Вологда : ВоГУ, 2018. — 277 с. — ISBN 978-5-87851-765-2. — Текст : электронный // Лань : электронно-библиотечная система. — URL: https://e.lanbook.com/book/246689 (дата обращения: 00.00.0000). — Режим доступа: для авториз. пользователей.

Авторы

• Ахмедова Гюнай Интигам кызы