Содержание
Регламент выполнения и защиты курсовой работы по АиСД
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++.
- Наличие обоих считается ошибкой; дополнительные служебные программы размещаются вне 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 минут.
