Инструменты пользователя

Инструменты сайта


courses:algorithms_structures:cw_2026:regulation

Регламент выполнения и защиты курсовой работы по АиСД

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. Требования к отчёту

Отчёт содержит:

  1. титульный лист и лист задания с закреплённым вариантом и уровнем;
  2. аннотацию и содержание;
  3. формальную постановку, операции, ограничения и критерии выбора;
  4. сравнение альтернатив и обоснование решения;
  5. описание реализованных структур, алгоритмов, функций, инвариантов и оценок сложности;
  6. описание машинного интерфейса и, при наличии, пользовательского интерфейса визуализации;
  7. тестирование с воспроизводимыми входами и ожидаемыми ответами;
  8. исследование времени и памяти, практические и теоретические графики;
  9. демонстрацию промежуточных состояний;
  10. выводы, в том числе соответствие требованиям и ограничения реализации;
  11. использованные источники;
  12. программный код в приложении.

Приведите минимум три полных примера запуска: обычный сценарий, граничный случай, обработанную ошибку с последующей проверкой сохранности состояния (указываются ввод, весь вывод с заголовком, команда запуска и пояснение результата).

  • Оформление соответствует действующему шаблону курсовой работы и опубликованным требованиям дисциплины.
  • Отчёт предоставляется в 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 минут.

courses/algorithms_structures/cw_2026/regulation.txt · Последнее изменение: — dmitry.ivanov