====== Регламент выполнения и защиты курсовой работы по АиСД ====== [[:courses:algorithms_structures:cw_2026:start|Варианты курсовых работ]] · [[:courses:algorithms_structures:cw_2026:requirements|Общие требования и интерфейс, версия 1]] ===== 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. Требования к программе и интерфейсу ===== Точный нормативный формат приведён в [[:courses:algorithms_structures:cw_2026:requirements|общих требованиях]]. Основные положения: * 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++. * Наличие обоих считается ошибкой; дополнительные служебные программы размещаются вне src. * Для основного приложения сторонние пакеты, установка зависимостей и сеть не требуются и не используются. * Ввод — stdin, результат — stdout. * Обязательных аргументов командной строки нет. * Каждый запуск независим от предыдущих. * Первая строка содержит закреплённый вариант и автора строго по шаблону общего интерфейса. Заголовок выводится один раз. * Режим 1 читает число q и ровно q строк команд с сохранением состояния между ними; режим 6 выводит справку и завершается без ожидания других данных. * Команды, форматы ответов, порядок выдачи результатов и коды ошибок должны точно соответствовать заданию. * Обработанная ошибка одной команды не меняет состояние и не препятствует следующей команде; код штатного завершения равен 0. * При штатной работе stderr пуст. * Отладочные сообщения, графики и визуализация не выводятся в проверяемый stdout. * Данные программы, включая ошибки и изменения состояния, должны обрабатываться корректно на всём допустимом диапазоне. * Превышение разрешённого количества данных тестовыми входами не требуется обрабатывать, если условие гарантирует отсутствие такого превышения. * Ссылаться на успешное выполнение только опубликованных примеров вместо реализации всего условия нельзя. ===== 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 показывают прогресс и помогают искать ошибки, но не заменяют полное прохождение. * Баллы не пересчитываются в академическую оценку по формуле. * Содержательность справки, самостоятельность реализации, соответствие закреплённому варианту и теоретические оценки дополнительно проверяются при просмотре кода и защите: автоматический тест не доказывает эти свойства. * Результат автоматической проверки подтверждает только прохождение выполненных тестов. * Он не заменяет обоснование, исследование, просмотр кода и защиту. * Даже результат 100% не означает автоматического выставления выбранной оценки. ===== 10. Состав финального PR ===== PR к защите содержит: * исходный код в src/, включая все собственные модули и Makefile для C++; * собственные тесты, входные данные и способ получения ожидаемых результатов; * исходники исследования и визуализации, исходные результаты измерений и команды построения графиков; * отчёт в PDF и DOCX; * минимум три воспроизводимых примера запуска; * Код в PR должен совпадать с проверенным кодом. * Материалы исследования и визуализации могут иметь отдельные зависимости (эти зависимости не должны становиться обязательными для запуска основного приложения). **Созданный PR считается финальной версией работы.** * После создания и до проверки преподавателем изменения не допускаются. * Нельзя закрывать корректный PR ради создания нового с исправлениями. * Предварительная проверка выполняется до этого момента. * Исправления после замечаний преподавателя допустимы только по явному указанию и не отменяют решения о допуске. ===== 11. Допуск к защите ===== Для допуска одновременно необходимы: * финальный PR, созданный до установленного срока и содержащий все обязательные материалы; * успешная предварительная проверка той же версии основного кода; * прохождение автоматических тестов не компенсирует отсутствие раздела или нарушение требований к реализации. * выполнение всех операций, ограничений и требований эффективности назначенного варианта; * самостоятельная реализация, анализ альтернатив и обоснование выбора; * описание реализации, тестирование, исследование и надлежаще оформленный отчёт. * Отсутствие обязательного материала/раздела либо его несоответствие содержательным требованиям означает **невыполнение курсовой работы**: к защите она не допускается, выставляется «Неудовлетворительно» без возможности исправить представленную финальную работу для этого допуска. * Большое количество нарушений оформления также может быть основанием признать работу невыполненной. ===== 12. Порядок защиты ===== Аналогично защитам лабораторных работ: практическая часть и беседа с преподавателем. Планируемое ограничение по времени - 45 минут.