====== Общие требования к курсовым работам АиСД: интерфейс ======
[[:courses:algorithms_structures:cw_2026:start|К вариантам курсовых работ]] · [[:courses:algorithms_structures:cw_2026:regulation|Регламент выполнения и защиты]]
===== Выполнение и обоснование =====
* Реализуйте все операции своего варианта.
* Структуры хранения данных и алгоритмы их обработки выберите самостоятельно.
* В отчёте перечислите операции, характеристики и объём данных, частоты операций и критерии оптимальности.
* Сравните выбранное решение как минимум с двумя применимыми альтернативами, обоснуйте выбор, оцените время всех операций и расход памяти. Различайте гарантированные, ожидаемые и амортизированные оценки.
* Требования на данной странице, а также требования описанные в варианте и регламенте обязательны; примеры показывают отдельные случаи, а не заменяют полное условие.
* Необходимые структуры и алгоритмы реализуются самостоятельно.
* Готовые контейнеры, выполняющие предметные операции задания, и готовые реализации алгоритмов обработки **использовать нельзя**.
* Разрешены базовые типы, строки, собственные классы и ввод/вывод.
* Python list и C++ std::vector разрешены только как индексируемое хранилище: выделение длины/ёмкости, чтение и запись по индексу, получение длины.
* Расширение с переносом содержимого, поиск, сортировку и другие предметные операции реализуйте самостоятельно.
* Готовые append/pop/insert/remove/sort, срезы и поиск через in для этой цели **запрещены**.
* Разбор входных строк стандартными средствами разрешён.
* В независимых тестах и обработке результатов экспериментов готовые контейнеры допустимы.
* Эксперименты и визуализация должны использовать ту же реализацию, что основное приложение.
* Исследуйте все операции на возрастающих объёмах и характерных случаях входа, зафиксируйте seed, среду, число повторов, медиану и разброс.
* Визуализация данных и промежуточных состояний выполняется отдельно от проверяемого stdout.
===== Языки, состав и запуск =====
* Python 3.12 (версия среды проверки): входной файл ''src/main.py'', запуск из src командой ''python3 main.py''. Собственные соседние модули разрешены. Сторонние пакеты не требуются и не используются.
* C++17: в ''src/Makefile'' команда ''make'' собирает исполняемый файл ''cw''; запуск из src командой ''./cw''. Количество собственных исходных файлов не ограничено. Сторонние библиотеки не используются.
* Программа читает stdin и пишет stdout, обязательных аргументов командной строки нет. Каждый запуск независим от предыдущих.
* Среда проверки: Python 3.12.3, C++17, Linux. Время нагрузки ограничено отдельно для группы вариантов и языка по таблице ниже; на процесс программы отводится 512 МБ адресного пространства, общий stdout/stderr ограничен 1 МБ
* Флаги C++17 и оптимизации задайте в Makefile; эталонная конфигурация — -std=c++17 -O2 без санитайзера.
* Границы данных и оценки сложности обязательны независимо от этих лимитов.
===== Обязательная первая строка =====
При любом запуске первой строкой stdout, до других сообщений, выводится:
Course work for option G.N, created by Name Surname.
Замените G.N на назначенный уровень и номер (например, 4.12), Name и Surname — на собственные имя и фамилию латиницей. Каждая часть имени должна соответствовать [A-Za-z][A-Za-z0-9_]*. Номер записывается без ведущих нулей: G — 3, 4 или 5, N — от 1 до 15. Пробелы и пунктуация должны совпадать с шаблоном; точка и перевод строки обязательны. Заголовок одинаков во всех запусках, включая справку и ошибочный ввод, и выводится один раз за запуск. Ivan Ivanov в примерах — условный автор.
===== Режим работы и строки команд =====
Первая строка stdin содержит одно целое число — режим:
* ''6'' — сразу вывести непустую справку о командах своего варианта и завершиться. Читать q или ждать текст после 6 нельзя. Формулировки справки студент выбирает сам; они должны описывать синтаксис и назначение всех команд.
* ''1'' — в следующей строке прочитать одно число q от 0 до 100000, затем ровно q строк предметных команд. Ответить на каждую команду, сохраняя общее состояние между ними, после чего завершиться.
Иной корректно записанный целый режим, включая зарезервированные 8 и 9, даёт ''Error: COMMAND'' и завершение. Пустой stdin, неверный формат строки режима или q, отсутствующая строка q либо q вне диапазона дают ''Error: INPUT'' и завершение. При q=0 выводится только заголовок. Две пустые строки не являются признаком конца сценария. Данные после q команд не входят в допустимый вход и не тестируются.
Каждая команда целиком занимает одну строку. Разделители — один или несколько ASCII-пробелов или табуляций; такие разделители в начале и конце строки допустимы. Регистр команд учитывается. Вход может иметь переводы строк LF или CRLF. Последняя непустая строка может завершаться EOF без перевода строки.
===== Формат значений =====
* Общий строковый токен: от 1 до 64 символов из ''A-Z'', ''a-z'', ''0-9'', ''_'' и ''-''. Пробелы внутри токена и кавычки не поддерживаются. Слова text/value не означают строку произвольной длины: это тоже один токен. Специальные форматы путей и имён задаются в вариантах.
* Целое число имеет вид ''-?[0-9]+'': знак плюс, экспонента и десятичная точка запрещены. Ведущие нули и -0 разрешены. Число корректного формата вне допустимого диапазона даёт RANGE, а не INPUT. В режиме/q действует отдельное правило INPUT, описанное выше.
* Если в варианте не указано иначе, диапазон числового значения от -1000000000 до 1000000000. Числовой id — от 1 до 1000000000. Числа в ответах печатаются без ведущих нулей и без плюса; ноль печатается как 0.
* Строки сравниваются лексикографически по ASCII с учётом регистра. Числа сравниваются численно. Для составных записей поля сравниваются слева направо, если вариант задаёт такой порядок.
* Одновременно хранится не более 100000 предметных записей, если в варианте не задан иной предел. Вход гарантированно не требует превысить предел количества записей, отношений и суммарного объёма данных; отдельный код ошибки переполнения таких пределов не требуется.
* Правильный полный вывод одного сценария автоматической проверки, включая заголовок, не превышает 1 МиБ в UTF-8. Это ограничение проверочных входов, а не разрешение обрезать правильный ответ.
* Вычисления сумм, расстояний и сроков должны корректно работать в знаковом 64-битном диапазоне. Входные сценарии гарантируют, что все промежуточные значения и запрашиваемые результаты в него помещаются; это отдельная гарантия допустимости сценария.
* Для сложности используйте n — текущее число записей, L — максимальную длину обрабатываемого строкового поля; дополнительные обозначения задаются в варианте.
* Обозначения в синтаксисе команд — места для значений, а не буквальный текст ввода, например:
* GET i означает GET 0 для i=0.
* Многоточие означает последовательность аргументов, которая раскрывается согласно условию.
* В ITEMS k буква k — фактическое число следующих строк;
* аналогично трактуются m/r в ответах.
* Оценки памяти и времени для пустого состояния допускают постоянные накладные расходы O(1).
* Выделенное хранилище после удалений может сохранять ёмкость до наибольшего достигнутого размера.
* Если требуется память O(n), это O(N+1), где N — наибольший достигнутый размер в сценарии
* зависимость от числа всех когда-либо выполненных команд вместо N не допускается, если явно не требуется хранение истории.
===== Ответы =====
Каждый ответ заканчивается переводом строки LF. Используйте ровно один пробел между полями, без пробелов в конце, без пустых строк и приглашений. stderr при штатной работе пуст.
^ Вид ответа ^ Значение ^
| ''OK'' | Операция успешно выполнена. |
| ''VALUE ...'' | Одно значение или одна запись с полями в порядке из условия. |
| ''NONE'' | Обычный результат отсутствия, если он предусмотрен данной командой. |
| ''ITEMS k'' | После этой строки идут ровно k строк записей указанного формата. Для пустой выборки выводится только ITEMS 0. |
| ''Error: CODE'' | Обработанная ошибка с одним из кодов ниже; это полный текст ответа, дополнительных пояснений нет. |
===== Ошибки и их порядок =====
^ Код ^ Значение ^
| ''COMMAND'' | Неизвестная команда или неподдерживаемый режим. |
| ''INPUT'' | Неверное число аргументов или лексический формат, пустая строка предметной команды, преждевременный конец ввода. |
| ''RANGE'' | Неверный числовой диапазон или границы/индексы. |
| ''NOT_FOUND'' | Отсутствует обязательный объект. |
| ''EXISTS'' | Нарушается уникальность существующего объекта. |
| ''EMPTY'' | Нет данных для извлечения либо отмены. |
| ''STATE'' | Недопустимое состояние или нарушение предпосылки операции. |
Проверяйте ошибки в порядке:
- Имя команды: неизвестное непустое имя даёт COMMAND независимо от остальных аргументов.
- Число аргументов и их лексический формат: INPUT. Для строк с числом элементов n/d сначала проверяется формат и диапазон этого размера, затем число остальных аргументов.
- Статические диапазоны чисел: RANGE.
- Наличие требуемой инициализации: STATE.
- Индексы и границы, зависящие от текущего размера: RANGE.
- Существование обязательных объектов слева направо: NOT_FOUND; затем уникальность: EXISTS; затем прочие ограничения: STATE. Особенности прохода по путям явно заданы в соответствующих вариантах.
Если режим и q уже прочитаны, ошибка одной команды не меняет ни предметное состояние, ни время, ни порядок использования, ни историю отмены.
* После ошибочной команды исполняется следующая строка команды.
* Пустая строка считается одной ошибочной командой.
* Если EOF наступил до очередной строки из q, выведите один Error: INPUT и завершите работу (не печатайте ошибки за все оставшиеся строки).
* После обработанной ошибки программа завершается с кодом 0. Необработанное исключение и ненулевой код завершения не являются корректной обработкой ошибки.
===== Справка: пример =====
Ввод:
6
Один из допустимых ответов для варианта 3.1:
Course work for option 3.1, created by Ivan Ivanov.
INIT c - clear history and set capacity
ADD text - append an event
RESIZE c - change capacity
GET i - read an event
LIST - print stored events
Справка не должна ожидать дополнительного ввода. Примеры предметных команд с полными входом и выходом приведены на странице каждого варианта.
===== Лимиты нагрузочных блоков =====
* Общий блок содержит два смешанных сценария с параметром размера 2048 и 18000.
* Размер не равен числу команд q: один сценарий выполняет несколько операций над данными.
* Блок оценивается целиком по суммарному времени (без учёта компиляции).
* Целевой блок содержит три независимых запуска на указанных размерах.
* Для каждого размера действуют свой предел времени и одинаковая доля баллов
* Размер не равен числу команд.
Критерии предварительного прохождения и доли баллов приведены в разделе 9 регламента.
Для допуска необходимо полное прохождение, а не произвольный положительный балл.
^ Варианты ^ Язык ^ Общий блок, с ^ Целевая операция ^ Размеры ^ Пределы размеров, с ^
| 3.1, 3.6, 3.7 | Python | 1 | ADD | 8192, 16384, 32768 | 0.45, 0.65, 1 |
| 3.1, 3.6, 3.7 | C++ | 0.5 | ADD | 8192, 16384, 32768 | 0.25, 0.3, 0.5 |
| 3.2, 3.8, 3.9 | Python | 1.35 | PEEK | 8192, 16384, 32768 | 0.6, 0.9, 1.5 |
| 3.2, 3.8, 3.9 | C++ | 0.5 | PEEK | 8192, 16384, 32768 | 0.3, 0.4, 0.65 |
| 3.3, 3.10, 3.11 | Python | 1.8 | GET | 8192, 16384, 32768 | 0.65, 1.1, 1.95 |
| 3.3, 3.10, 3.11 | C++ | 0.75 | GET | 8192, 16384, 32768 | 0.3, 0.5, 0.85 |
| 3.4, 3.12, 3.13 | Python | 1.8 | GET | 8192, 16384, 32768 | 0.9, 1.6, 2.95 |
| 3.4, 3.12, 3.13 | C++ | 0.85 | GET | 8192, 16384, 32768 | 0.45, 0.7, 1.35 |
| 3.5, 3.14, 3.15 | Python | 3.45 | DOMAIN | 8192, 16384, 32768 | 0.8, 1.4, 2.55 |
| 3.5, 3.14, 3.15 | C++ | 1.15 | DOMAIN | 8192, 16384, 32768 | 0.35, 0.5, 0.9 |
| 4.1, 4.6, 4.7 | Python | 1.8 | LOWER | 8192, 16384, 32768 | 0.6, 0.95, 1.65 |
| 4.1, 4.6, 4.7 | C++ | 0.75 | LOWER | 8192, 16384, 32768 | 0.25, 0.45, 0.7 |
| 4.2, 4.8, 4.9 | Python | 2.8 | COUNT | 8192, 16384, 32768 | 0.55, 0.8, 1.55 |
| 4.2, 4.8, 4.9 | C++ | 0.85 | COUNT | 8192, 16384, 32768 | 0.25, 0.35, 0.6 |
| 4.3, 4.10, 4.11 | Python | 1.8 | RANK | 8192, 16384, 32768 | 0.65, 1.05, 2 |
| 4.3, 4.10, 4.11 | C++ | 0.7 | RANK | 8192, 16384, 32768 | 0.3, 0.35, 0.6 |
| 4.4, 4.12, 4.13 | Python | 1.3 | ADD + SUM | 8192, 16384, 32768 | 0.5, 0.7, 1.1 |
| 4.4, 4.12, 4.13 | C++ | 0.7 | ADD + SUM | 8192, 16384, 32768 | 0.25, 0.35, 0.6 |
| 4.5, 4.14, 4.15 | Python | 1.15 | DIST | 2048, 4096, 8192 | 0.45, 0.5, 0.6 |
| 4.5, 4.14, 4.15 | C++ | 0.5 | DIST | 2048, 4096, 8192 | 0.15, 0.2, 0.2 |
| 5.1, 5.6, 5.7 | Python | 1.85 | GET | 8192, 16384, 32768 | 0.75, 1.35, 2.55 |
| 5.1, 5.6, 5.7 | C++ | 0.9 | GET | 8192, 16384, 32768 | 0.35, 0.65, 1 |
| 5.2, 5.8, 5.9 | Python | 1.85 | COMMIT | 4096, 8192, 16384 | 0.65, 1.1, 1.95 |
| 5.2, 5.8, 5.9 | C++ | 1.1 | COMMIT | 4096, 8192, 16384 | 0.35, 0.6, 1.1 |
| 5.3, 5.10, 5.11 | Python | 3.05 | BACKLINKS | 4096, 8192, 16384 | 0.7, 1.2, 2.3 |
| 5.3, 5.10, 5.11 | C++ | 1 | BACKLINKS | 4096, 8192, 16384 | 0.3, 0.4, 0.7 |
| 5.4, 5.12, 5.13 | Python | 3.4 | NEXT | 8192, 16384, 32768 | 1.2, 2.2, 4.35 |
| 5.4, 5.12, 5.13 | C++ | 0.9 | NEXT | 8192, 16384, 32768 | 0.35, 0.55, 0.95 |
| 5.5, 5.14, 5.15 | Python | 2.4 | TICK | 8192, 16384, 32768 | 0.85, 1.45, 2.8 |
| 5.5, 5.14, 5.15 | C++ | 0.85 | TICK | 8192, 16384, 32768 | 0.35, 0.55, 1 |
Успешная нагрузка подтверждает ресурсные ограничения только на выполненных входах; требования к сложности и самостоятельной реализации остаются обязательными.