Источник: РПД Б1.О.30 «Структуры и алгоритмы обработки данных» (актуализировано 2026) и ФОС дисциплины, МТУСИ, кафедра «Программная инженерия». Настоящий Markdown-документ воспроизводит содержание первого семестра курса (4-й учебный семестр, разделы 1–4). Полная РПД охватывает два семестра (7 ЗЕТ / 252 ч); материалы второго семестра (разделы 5–7, экзамен) добавляются модулями M5–M7.
| Параметр | Значение |
|---|---|
| Название дисциплины | «Структуры и алгоритмы обработки данных» |
| Индекс по учебному плану | Б1.О.30, обязательная часть |
| Уровень высшего образования | Бакалавриат |
| Направление подготовки | 09.03.04 «Программная инженерия» |
| Направленность (профиль) | «ТОП-ИТ: Разработка и сопровождение программного обеспечения» |
| Курс / семестр | 2 курс, 4 учебный семестр (первый семестр курса) |
| Форма обучения | Очная |
| Трудоёмкость семестра | 108 часов (дисциплина в целом — 7 ЗЕТ / 252 ч) |
| Виды занятий семестра | Лекции — 16 ч; лабораторные работы — 32 ч; СР — 59 ч; ИКР — 1 ч |
| Форма промежуточной аттестации | Зачёт |
| Разработчик РПД | и.о. заведующего кафедрой ПИ, к.т.н. М.С. Мосева |
| Основание | Учебный план, утверждённый Учёным советом 02.10.2025, протокол № 2; ФГОС ВО 09.03.04 (приказ Минобрнауки РФ от 19.09.2017 № 920) |
Цель: изучение фундаментальных принципов организации и эффективного управления данными, базовых структур данных и алгоритмов их обработки (на примере языков Python, C/C++, Java), развитие навыков анализа сложности алгоритмов и выбора оптимальных структур данных для решения практических задач программирования.
Особое внимание уделяется формированию навыков критической проверки и верификации программных решений, полученных с использованием технологий искусственного интеллекта: анализа корректности и оценки вычислительной сложности сгенерированных реализаций, их проверки на репрезентативных наборах тестов и обоснованного вывода о применимости (методика — ai-verification.md).
- Пререквизиты: «Введение в информационные технологии», «Информационные технологии и программирование».
- Постреквизиты: «Технологии и инструменты систем управления данными», «Проектный практикум», «Функциональное программирование», «Высоконагруженные приложения», курсовое проектирование, ВКР.
| Компетенция | Индикатор | Результаты (сокращённо) |
|---|---|---|
| ОПК-6 (ППК-Р1) — разработка алгоритмов и программ, пригодных для практического использования | ОПК-6.1 (ППК-Р1.1) | Формализация и алгоритмизация задач; инварианты и репрезентативные тесты; статический анализ |
| ОПК-6.2 (ППК-Р1.4) | Разработка кода (Python/C/C++/Java); среды PyCharm/VS Code; профилирование и отладка | |
| ОПК-6.3 (ППК-Р1.5) | Оформление кода по стандартам; black, pylint, clang-format; CI-проверки стиля | |
| ОПК-6.4 (ППК-Р1.6) | Система управления версиями; ветвление, слияние, регламент коммитов; CI/CD | |
| ОПК-7 — применение основных концепций, принципов, теорий и фактов информатики | ОПК-7.1 | Модели вычислений, классы сложности, методы оценки алгоритмов; амортизированный анализ |
| ОПК-7.2 | Метрики производительности (CPU, память, I/O); Big-O и эмпирическое профилирование; бенчмаркинг реализаций |
| Раздел | Всего, ч | Л | ЛР | СР и пр. | Контроль раздела |
|---|---|---|---|---|---|
| Раздел 1. Введение и базовые структуры | 27 | 4 | 8 | 15 | Тест № 1 |
| Раздел 2. Алгоритмы сортировки | 27 | 4 | 8 | 15 | Тест № 2, ДЗ 1 |
| Раздел 3. Деревья и иерархические структуры | 27 | 2 | 4 | 21 | Тест № 3, ДЗ 2 |
| Раздел 4. Алгоритмы поиска и хеш-таблицы | 27 | 6 | 12 | 9 | Тест № 4, ДЗ 3–4 |
| Итого за семестр | 108 | 16 | 32 | 60 | Зачёт |
Привязка тестов и ДЗ к разделам — методическая рекомендация настоящего репозитория; РПД фиксирует объёмы часов и порядок тем. Баланс СР по разделам в РПД равномерный (15 ч на раздел + подготовка к зачёту).
| Элемент | Содержание | Форма | а.ч. | Индикаторы |
|---|---|---|---|---|
| Лекция 1 | Введение и алгоритмическая сложность; худший/средний/лучший случаи; анализ рекуррентных соотношений | Л | 2 | ОПК-6.1, ОПК-7.1 |
| ЛР 1 | Анализ временной сложности элементарных алгоритмов | ЛР | 4 | ОПК-6.1, ОПК-7.2, ОПК-6.3, ОПК-6.4 |
| Лекция 2 | Рекурсия, «разделяй и властвуй», амортизированный анализ; динамический массив, связные списки, стек и дек | Л | 2 | ОПК-6.1, ОПК-7.2 |
| ЛР 2 | Рекурсивные функции, динамический массив, стек и дек | ЛР | 4 | ОПК-6.1, ОПК-7.2, ОПК-6.3, ОПК-6.4 |
| Лекция 3 | Базовые алгоритмы сортировки; быстрая сортировка (QuickSort) | Л | 2 | ОПК-6.1, ОПК-7.2 |
| ЛР 3 | Экспериментальное сравнение простых сортировок; QuickSort с рандомизацией опорного элемента | ЛР | 4 | ОПК-6.1, ОПК-7.2, ОПК-6.3, ОПК-6.4 |
| Лекция 4 | Сортировка слиянием и внешние сортировки; линейно-временные и кучные сортировки | Л | 2 | ОПК-6.1, ОПК-7.2 |
| ЛР 4 | MergeSort, Counting, Radix и HeapSort: оценка производительности | ЛР | 4 | ОПК-6.1, ОПК-7.2, ОПК-6.3, ОПК-6.4 |
| Лекция 5 | Бинарное дерево поиска, AVL-деревья | Л | 2 | ОПК-6.1, ОПК-6.2, ОПК-7.1 |
| ЛР 5 | Построение BST и реализация обходов; вставка и удаление элементов | ЛР | 4 | ОПК-6.1, ОПК-7.2, ОПК-6.3, ОПК-6.4 |
| Лекция 6 | Поиск в линейных структурах | Л | 2 | ОПК-6.1, ОПК-6.2, ОПК-7.2 |
| ЛР 6 | Линейный, бинарный и интерполяционный поиск: сравнение | ЛР | 4 | ОПК-6.1, ОПК-7.2, ОПК-6.3, ОПК-6.4 |
| Лекция 7 | Поиск подстрок | Л | 2 | ОПК-6.1, ОПК-7.2 |
| ЛР 7 | Сравнительный анализ КМП, Рабина–Карпа и Бойера–Мура | ЛР | 4 | ОПК-6.1, ОПК-7.2, ОПК-6.3, ОПК-6.4 |
| Лекция 8 | Хеш-таблицы: хеш-функции, цепочечное разрешение коллизий, открытая адресация | Л | 2 | ОПК-6.1, ОПК-6.2, ОПК-7.2 |
| ЛР 8 | Хеш-таблица с отдельным цепочечным хешированием | ЛР | 4 | ОПК-6.1, ОПК-7.2, ОПК-6.3, ОПК-6.4 |
| ДЗ 1 | Верификация ИИ-сгенерированной сортировки | СР | — | ОПК-6.1, ОПК-6.2, ОПК-7.2 |
| ДЗ 2 | Эксперимент: высота BST и деградация операций | СР | — | ОПК-6.1, ОПК-7.1, ОПК-7.2 |
| ДЗ 3 | Кейс ГК «Астра»: аномалии в журналах событий ОС | СР | — | ОПК-6.1, ОПК-6.2, ОПК-7.1, ОПК-7.2 |
| ДЗ 4 | Кейс hh.ru: семантический подбор по эмбеддингам | СР | — | ОПК-6.1, ОПК-6.2, ОПК-7.1, ОПК-7.2 |
Перечень контрольных вопросов семестра (по разделам 1–4) — в resources/problem-banks/.
Применяется балльно-рейтинговая система (БРС), максимум 100 баллов; автомат при наборе более 70 баллов. Структура баллов, согласование шкал и критерии рубрик — в README.md и methodical-guidelines/teachers-assessment/.
Лабораторные работы выполняются в компьютерном классе; занятия по материалам кейсов индустриальных партнёров могут проводиться в интерактивной форме, включая кейс-чемпионат (см. Cases/). Применение технологий ИИ допускается как вспомогательный инструмент с обязательной верификацией результатов (ai-verification.md).
- Основная и дополнительная литература —
resources/textbooks/. - Программное обеспечение —
resources/software/. - Банки тестов и вопросов —
resources/test-banks/. - Банки задач —
resources/problem-banks/. - Наборы данных —
resources/datasets/. - Промпты и правила работы с БЯМ —
resources/llm-prompts/.
Учебные аудитории для лекций и лабораторных работ с мультимедийным оборудованием и компьютерной техникой; помещения для самостоятельной работы с доступом к ЭИОС МТУСИ.
- Обучающимся —
methodical-guidelines/students/. - Преподавателям —
methodical-guidelines/teachers-assessment/,methodical-guidelines/teachers-resources/.