| Максимальный балл: | 1 | Ограничение времени: | 1 сек | |
| Ограничение памяти: | 512 Мб |
Требуется разработать и описать реализацию одного из выбранных алгоритмов. Реализация должна сопровождаться автоматическими тестами и пакетом в формате CATS. Описание должно содержать презентацию и реферат. Рекомендуется использовать систему подготовки документов TeX.
Число в скобках обозначает количество индивидуальных подтем/алгоритмов, по одному на человека.
Отправьте ссылку на конкретный коммит в репозитории на Github, например
https://github.com/klenin/cats-main/commit/dce22c8348808959881ed7d6852c520a41e47c9a
В качестве среды разработки укажите Answer text.
В файле README укажите свои ФИО, вуз, направление подготовки, год, выбранный алгоритм, инструкции по сбору презентации и запуску автоматических тестов.
| Максимальный балл: | 10 | Ограничение времени: | 1 сек | |
| Ограничение памяти: | 512 Мб |
Реферат по алгоритму.
Реферат должен находиться в репозитории, который отправляется на проверку в задачу A.
Реферат должен описывать выбранный студентом и утверждённый преподавателем алгоритм.
Реферат должен быть оформлен в виде документа, который пригоден для прямого чтения из браузера, например PDF. Исходный код реферата рекомендуется хранить в формате системы TeX в том же репозитории.
Реферат, как правило, должен состоять из следующих разделов (в зависимости от алгоритма возможны исключения, по согласованию с преподавателем).
| Максимальный балл: | 10 | Ограничение времени: | 1 сек | |
| Ограничение памяти: | 512 Мб |
Презентация по алгоритму.
Презентация должна находиться в репозитории, который отправляется на проверку в задачу A.
Презентация должна описывать выбранный студентом и утверждённый преподавателем алгоритм.
Презентация должна быть оформлена в виде документа, который пригоден для прямого чтения из браузера, например PDF. Исходный код презентации рекомендуется хранить в формате системы TeX в том же репозитории.
Презентация, как правило, должен состоять из следующих разделов (в зависимости от алгоритма возможны исключения, по согласованию с преподавателем).
| Максимальный балл: | 10 | Ограничение времени: | 1 сек | |
| Ограничение памяти: | 512 Мб |
Программный код алгоритма.
Код должен находиться в репозитории, который отправляется на проверку в задачу A.
Код должен корректно реализовывать выбранный студентом и утверждённый преподавателем алгоритм.
Код должен быть оформлен в виде библиотеки (отдельного модуля) на выбранном языке программирования, с кратким комментарием, поясняющим API.
Язык программирования должен позволять максимально эффективную реализацию, то есть реализация алгоритма не должна быть существенно медленнее реализации на C++.
Оформление и структура кода должны подчиняться обычным критериям качества.
| Максимальный балл: | 10 | Ограничение времени: | 1 сек | |
| Ограничение памяти: | 512 Мб |
Тесты к алгоритму должны находиться в репозитории, который отправляется на проверку в задачу A.
Тесты должны сопровождаться системой автоматического запуска, выводящей для каждого теста номер и результат проверки, а также общую статистику по всем тестам.
Тесты должны проверять как корректность, так и производительность алгоритма.
Тесты на корректность должны исчерпывающе проверять все граничные и стандартные режимы работы в режиме как чёрного, так и белого ящика. Желательно продемонстрировать покрытие кода и/или веток алгоритма тестами.
Тесты должны включать как созданные вручную, так и сгенерированные генератором.
Исходный код всех генераторов, как и код их запуска, должен быть в репозитории. Сами сгенерированные тесты, как и прочие артефакты, производимые в процессе компиляции и запуска, НЕ должны находиться в репозитории.
К исходному коду генераторов и тестирующей подсистемы предъявляются те же требования модульности и оформления, что и к коду алгоритма.
Тесты на производительность должны измерять время работы и, если необходимо, затраты памяти алгоритма.
Тесты должны включать защиту от эвристик, и, желательно, реализацию этих эвристик для демонстрации успешной защиты.
По результатам измерения должны быть составлены графики и/или таблицы, демонстрирующие, что алгоритм обладает заявленной алгоритмической сложностью и что константный множитель в оценке сложности реализации сопоставим с константой встроенного и/или тривиального алгоритма. Рекомендуется включить в явном виде аппроксимирующие формулы, полученные например с помощью электронных таблиц или статистических библиотек.
Если возможно, тесты должны сравнивать корректность и производительность со стандартными алгоритмами и структурами данных языка программирования. Если соответствующего стандартного алгоритма нет, следует привести сравнение с наивным/тривиальным алгоритмом.
| Максимальный балл: | 10 | Ограничение времени: | 1 сек | |
| Ограничение памяти: | 512 Мб |
Пакет в CATS к алгоритму.
| Максимальный балл: | 10 | Ограничение времени: | 1 сек | |
| Ограничение памяти: | 512 Мб |
Пакет в CATS к алгоритму.
| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
| Максимальный балл: | 40 |
Количество задач, решённых в дивизионе D
| Входной файл: | Стандартный вход | Ограничение времени: | 1 сек | |
| Выходной файл: | Стандартный выход | Ограничение памяти: | 512 Мб | |
| Максимальный балл: | 60 |