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