Регламент выполнения и защиты курсовой работы по АиСД
1. Назначение и состав задания
Курсовая работа выполняется индивидуально на Python или C++.
Цель работы — самостоятельно выбрать, реализовать, обосновать и исследовать способ хранения и обработки данных для заданного набора операций.
Предусмотрены три уровня: «Удовлетворительно» (3), «Хорошо» (4), «Отлично» (5).
Полный номер варианта имеет вид L.N, где L — уровень, N — номер от 1 до 15.
Варианты разных уровней являются самостоятельными заданиями.
Вариант и уровень закрепляются после заполнения формы выбора сложности курсовой и распределения вариантов.
Максимальная оценка ограничивается закреплённым уровнем.
Изменять вариант после закрепления можно только по согласованию с преподавателем до создания финального PR и защиты.
Обязательны одновременно:
все операции, правила, ограничения данных и требования эффективности страницы назначенного варианта;
общий интерфейс версии 1, правила сборки, запуска и обработки ошибок;
требования настоящего регламента к обоснованию, реализации, тестированию, исследованию, отчёту и защите.
Предметные особенности и специальные диапазоны определяются на странице варианта, общий формат — страницей интерфейса.
2. Выбор и самостоятельная реализация решения
Конкретные структуры данных и алгоритмы условием не назначаются.
Студент самостоятельно выбирает решение, которое реализует все операции и удовлетворяет требованиям эффективности.
Можно сочетать несколько собственных структур, если это обосновано.
Все предметные структуры и алгоритмы реализуются самостоятельно.
Готовые контейнеры, реализующие операции задания, и готовые алгоритмы их обработки запрещены.
Разрешены базовые типы, строки, собственные классы, стандартный ввод/вывод и разбор токенов.
Python list и C++ std::vector разрешены только как индексируемое хранилище: выделение длины/ёмкости, чтение и запись по индексу, получение длины.
Управление логическим размером, перенос элементов, поиск, сортировка и предметные операции реализуются самостоятельно.
Готовые append/pop/insert/remove/sort, срезы и поиск через in для выполнения этих операций запрещены.
Это разрешение не означает, что готовое поведение контейнера можно использовать как решение задания.
В независимых эталонах тестов и обработке результатов исследования готовые контейнеры разрешены.
Проверяемое приложение, измерения и визуализация используют одну и ту же собственную реализацию
3. Требования к программе и интерфейсу
Точный нормативный формат приведён в общих требованиях. Основные положения:
Python: src/main.py и собственные модули, запуск из src командой python3 main.py; Python 3.12 в объявленной среде проверки.
C++: C++17, сборка командой make из src/Makefile создаёт исполняемый файл cw; запуск из src командой ./cw.
В src должен быть ровно один вход: main.py для Python либо Makefile для C++.
Для основного приложения сторонние пакеты, установка зависимостей и сеть не требуются и не используются.
Ввод — stdin, результат — stdout.
Первая строка содержит закреплённый вариант и автора строго по шаблону общего интерфейса. Заголовок выводится один раз.
Режим 1 читает число q и ровно q строк команд с сохранением состояния между ними; режим 6 выводит справку и завершается без ожидания других данных.
Команды, форматы ответов, порядок выдачи результатов и коды ошибок должны точно соответствовать заданию.
При штатной работе stderr пуст.
Данные программы, включая ошибки и изменения состояния, должны обрабатываться корректно на всём допустимом диапазоне.
Превышение разрешённого количества данных тестовыми входами не требуется обрабатывать, если условие гарантирует отсутствие такого превышения.
Ссылаться на успешное выполнение только опубликованных примеров вместо реализации всего условия нельзя.
4. Обоснование выбора
Обоснование должно показывать связь между операциями задачи, характеристиками данных, критериями оптимальности и выбранной реализацией.
4.1. Формализация задачи
Укажите:
явный нумерованный список всех операций, включая чтение, изменения, ошибки и специальные действия варианта;
типы полей и ключей, правила равенства, уникальности и порядка результатов;
ограничения размеров и динамику данных: рост, удаление, изменения, сохранение истории или версий, если они предусмотрены;
относительную частоту каждой операции: из условия, если она задана; иначе сформулируйте допущение и обоснуйте его. Допускается равномерная нагрузка, если она явно описана.
4.2. Сравнение альтернатив
Сравните выбранное решение как минимум с двумя применимыми альтернативами: для каждой рассмотрите все операции, оценки времени и памяти, соответствие ограничениям, особенности реализации и условия ухудшения поведения (недостаточно назвать варианты без анализа или сравнить только одну удобную операцию).
Явно перечислите критерии выбора: время операций, предсказуемость, стоимость изменения данных, упорядоченной выдачи, памяти и других существенных для задачи свойств. Если отдельные структуры не покрывают все операции эффективно, рассмотрите возможность их сочетания и цену согласования данных.
Завершите сравнением преимуществ и недостатков именно в условиях своего варианта: ожидаемую или амортизированную сложность нельзя выдавать за гарантию худшего случая, если условие допускает несколько видов гарантий, укажите, какой из них обеспечивает реализация и при каких предпосылках.
5. Тестирование
Подготовьте собственные воспроизводимые тесты всех операций, а не только копии примеров задания. Проверяемые случаи должны включать:
начальное и пустое состояние, один элемент, повторения и совпадающие ключи, если применимо;
добавление, изменение, удаление и повторное добавление;
граничные значения, пустые выборки и равенство критериев упорядочения;
ошибочные команды и последующие запросы, подтверждающие неизменность состояния;
длинные смешанные последовательности и большие объёмы данных с учётом ограничений ответа;
специальные свойства варианта: восстановление состояния, отношения объектов, версии, зависимости, истечение и другие предусмотренные операции.
Для каждого теста должны быть доступны входные данные и ожидаемый результат либо независимая модель его получения (для случайных тестов сохраняются seed и способ генерации).
Необработанное исключение или ненулевой код не является корректной реализацией сообщения об ошибке.
6. Исследование времени и памяти
Исследование охватывает все реализованные операции и алгоритмы, а также особенности их совместной работы. Для каждой операции приведите:
теоретические оценки времени и памяти, обозначения параметров и обоснование;
лучший, средний и худший случаи, если различие применимо, и способ формирования данных для этих случаев;
практические измерения и графики в сопоставлении с теоретической зависимостью;
объяснение совпадений и расхождений теории и эксперимента.
Если случаи совпадают или понятие среднего случая требует особой вероятностной модели, это нужно явно пояснить, для амортизированных оценок исследуйте последовательность операций, а не только отдельную наиболее дорогую операцию.
Используйте не менее пяти возрастающих размеров для масштабируемых операций, повторяйте измерения, укажите число повторов, медиану и разброс.
Измерение ядра реализации проводится отдельно от генерации входа, разбора stdin, вывода и построения графиков, дешёвые операции допускается измерять пакетами, полное время приложения можно исследовать дополнительно. Средства диагностики не должны незаметно искажать сравниваемые измерения.
Покажите, что расход памяти соответствует требованиям варианта, включая вспомогательные сведения, историю и временные данные там, где они используются.
Объясните, какие данные сохраняются после удаления, отмены, переключения или повторной записи.
Масштаб теоретической кривой на графике поясняется; она не выдаётся за измеренные данные.
Для операций постоянной сложности допустимо исследование зависимости от числа повторов или другого осмысленного параметра с объяснением выбора.
7. Визуализация и демонстрация
Подготовьте наглядное представление выбранной организации данных и промежуточных состояний хотя бы для одного нетривиального сценария.
Допустимы текстовая схема, автоматически формируемое изображение или отдельное средство визуализации. Обязательное создание графического интерфейса не требуется.
Визуализация должна позволять объяснить, где хранятся данные, какие отношения и служебные сведения поддерживаются и как они меняются при операции.
Графики быстродействия не заменяют демонстрацию состояния.
Программа визуализации использует тот же код предметной реализации и не вмешивается в машинный интерфейс.
8. Требования к отчёту
Отчёт содержит:
титульный лист и лист задания с закреплённым вариантом и уровнем;
аннотацию и содержание;
формальную постановку, операции, ограничения и критерии выбора;
сравнение альтернатив и обоснование решения;
описание реализованных структур, алгоритмов, функций, инвариантов и оценок сложности;
описание машинного интерфейса и, при наличии, пользовательского интерфейса визуализации;
тестирование с воспроизводимыми входами и ожидаемыми ответами;
исследование времени и памяти, практические и теоретические графики;
демонстрацию промежуточных состояний;
выводы, в том числе соответствие требованиям и ограничения реализации;
использованные источники;
программный код в приложении.
Приведите минимум три полных примера запуска: обычный сценарий, граничный случай, обработанную ошибку с последующей проверкой сохранности состояния (указываются ввод, весь вывод с заголовком, команда запуска и пояснение результата).
Оформление соответствует действующему шаблону курсовой работы и опубликованным требованиям дисциплины.
Отчёт предоставляется в PDF и DOCX.
Титульный лист, лист задания, программный код, анализ, описание реализации и исследование являются обязательными содержательными разделами и обязательны для защиты и получения оценки.
9. Предварительная автоматическая проверка
До создания финального PR выполните предварительную проверку в объявленном модуле АиСД для своего варианта и уровня.
Для отправки используется текстовый diff-патч с исходным кодом в src/.
Элемент курса принимает все варианты и оба языка:
Настройки вопроса не назначают студенту номер.
После применения патча должны получаться предусмотренные общим интерфейсом точки входа и файлы сборки.
Патч формируется из той же зафиксированной версии кода, которая будет представлена в PR.
В отправляемый код не включаются бинарные файлы, виртуальное окружение, скачанные зависимости и результаты экспериментов.
Патч должен создавать все необходимые файлы в src/ после применения к пустому каталогу решения; обычного diff только последних изменений недостаточно.
Пути назначения имеют вид b/src/main.py, b/src/main.cpp, b/src/Makefile и аналогичные для собственных модулей.
Для успешной проверки необходимо выполнить все обязательные проверки сборки/запуска, интерфейса, результатов операций, ошибок и предусмотренных нагрузок.
Пропуск обязательных тестов или неполное выполнение проверки не считаются успешным прохождением.
Автоматическая проверка выдаёт долю балла от 0 до 1:
| Блок | Максимальная доля | Начисление |
| Подготовка и справка | 0.1 | Сборка/подготовка и успешный запуск режима 6 с корректным заголовком и непустой справкой. |
| Базовый интерфейс | 0.3 | Пропорционально доле пройденных функциональных сценариев: протокол, операции, ошибки и граничные случаи. |
| Общая нагрузка | 0.2 | Целиком за все сценарии общего блока, если верны ответы и соблюдён суммарный бюджет. |
| Целевые операции | 0.4 | По одной трети блока за каждый из трёх размеров, если верны ответы и соблюдён предел запуска. |
Нагрузочные баллы начисляются только после полного функционального этапа.
Пределы времени различаются по группе вариантов и языку; таблица и границы измеряемого времени опубликованы в общих требованиях.
Доля округляется до двух знаков; если хотя бы один обязательный этап не пройден, результат не выше 0.99.
Ошибка подготовки даёт 0.
Рост времени между размерами служит диагностикой и не оценивается отдельным автоматическим порогом.
Успешная предварительная проверка для допуска — 1.0 при завершении всего обязательного набора.
Частичные 0.1–0.99 показывают прогресс и помогают искать ошибки, но не заменяют полное прохождение.
Баллы не пересчитываются в академическую оценку по формуле.
Содержательность справки, самостоятельность реализации, соответствие закреплённому варианту и теоретические оценки дополнительно проверяются при просмотре кода и защите: автоматический тест не доказывает эти свойства.
10. Состав финального PR
PR к защите содержит:
исходный код в src/, включая все собственные модули и Makefile для C++;
собственные тесты, входные данные и способ получения ожидаемых результатов;
исходники исследования и визуализации, исходные результаты измерений и команды построения графиков;
отчёт в PDF и DOCX;
минимум три воспроизводимых примера запуска;
Код в PR должен совпадать с проверенным кодом.
Материалы исследования и визуализации могут иметь отдельные зависимости (эти зависимости не должны становиться обязательными для запуска основного приложения).
Созданный PR считается финальной версией работы.
После создания и до проверки преподавателем изменения не допускаются.
Нельзя закрывать корректный PR ради создания нового с исправлениями.
Предварительная проверка выполняется до этого момента.
Исправления после замечаний преподавателя допустимы только по явному указанию и не отменяют решения о допуске.
11. Допуск к защите
Для допуска одновременно необходимы:
финальный PR, созданный до установленного срока и содержащий все обязательные материалы;
успешная предварительная проверка той же версии основного кода;
выполнение всех операций, ограничений и требований эффективности назначенного варианта;
самостоятельная реализация, анализ альтернатив и обоснование выбора;
описание реализации, тестирование, исследование и надлежаще оформленный отчёт.
12. Порядок защиты
Аналогично защитам лабораторных работ: практическая часть и беседа с преподавателем.
Планируемое ограничение по времени - 45 минут.