Задача 1A. Лабораторная работа по алгоритму

Максимальный балл:1   Ограничение времени:1 сек
  Ограничение памяти:512 Мб

Условие

Требуется разработать и описать реализацию одного из выбранных алгоритмов. Реализация должна сопровождаться автоматическими тестами и пакетом в формате CATS. Описание должно содержать презентацию и реферат. Рекомендуется использовать систему подготовки документов TeX.

Список тем/алгоритмов

Число в скобках обозначает количество индивидуальных подтем/алгоритмов, по одному на человека.

Распределение тем

  1. Сжатие цветков
  2. Алгоритм Дийкстры с деревом Фибоначчи
  3. Алгоритм A*
  4. Укладка планарного графа
  5. Алгоритм Эдмонда-Карпа
  6. Изоморфизм деревьев
  7. Динамическая связность оффлайн
  8. Алгоритм D*
  9. Алгоритм Голдберга-Тарьяна
  10. Алгоритм Кристофидеса
  11. Арифметическое кодирование
  12. Алгоритм Лемпеля-Зива-Велча
  13. Алгоритм PPM
  14. Эффективная длинная арифметика
  15. Алгоритм управления памятью: близнецы + SLAB
  16. Дерево B/B+/B*
  17. Дерево ван Эмде Боаса
  18. Сбалансированные деревья: splay, AA, scapegoat, fusion, tango (2-3)
  19. Пространственные деревья (2-3)
  20. Алгоритм Укконена
  21. Алгоритм Форчуна
  22. Пересечение произвольных многоугольников
  23. Триангуляция произвольных многоугольников
  24. Дерево интервалов
  25. Алгоритм Балабана
  26. Выделение сообществ в социальных графах (2)
Темы, требующие дополнительного выбора/уточнения:

Формат входных данных

Отправьте ссылку на конкретный коммит в репозитории на Github, например

https://github.com/klenin/cats-main/commit/dce22c8348808959881ed7d6852c520a41e47c9a

В качестве среды разработки укажите Answer text.

В файле README укажите свои ФИО, вуз, направление подготовки, год, выбранный алгоритм, инструкции по сбору презентации и запуску автоматических тестов.


Задача 1B. Реферат

Максимальный балл:10   Ограничение времени:1 сек
  Ограничение памяти:512 Мб

Условие

Реферат по алгоритму.

Реферат должен находиться в репозитории, который отправляется на проверку в задачу A.

Реферат должен описывать выбранный студентом и утверждённый преподавателем алгоритм.

Реферат должен быть оформлен в виде документа, который пригоден для прямого чтения из браузера, например PDF. Исходный код реферата рекомендуется хранить в формате системы TeX в том же репозитории.

Реферат, как правило, должен состоять из следующих разделов (в зависимости от алгоритма возможны исключения, по согласованию с преподавателем).


Задача 1C. Презентация

Максимальный балл:10   Ограничение времени:1 сек
  Ограничение памяти:512 Мб

Условие

Презентация по алгоритму.

Презентация должна находиться в репозитории, который отправляется на проверку в задачу A.

Презентация должна описывать выбранный студентом и утверждённый преподавателем алгоритм.

Презентация должна быть оформлена в виде документа, который пригоден для прямого чтения из браузера, например PDF. Исходный код презентации рекомендуется хранить в формате системы TeX в том же репозитории.

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


Задача 1D. Программный код

Максимальный балл:10   Ограничение времени:1 сек
  Ограничение памяти:512 Мб

Условие

Программный код алгоритма.

Код должен находиться в репозитории, который отправляется на проверку в задачу A.

Код должен корректно реализовывать выбранный студентом и утверждённый преподавателем алгоритм.

Код должен быть оформлен в виде библиотеки (отдельного модуля) на выбранном языке программирования, с кратким комментарием, поясняющим API.

Язык программирования должен позволять максимально эффективную реализацию, то есть реализация алгоритма не должна быть существенно медленнее реализации на C++.

Оформление и структура кода должны подчиняться обычным критериям качества.


Задача 1E. Тесты

Максимальный балл:10   Ограничение времени:1 сек
  Ограничение памяти:512 Мб

Условие

Тесты к алгоритму должны находиться в репозитории, который отправляется на проверку в задачу A.

Тесты должны сопровождаться системой автоматического запуска, выводящей для каждого теста номер и результат проверки, а также общую статистику по всем тестам.

Тесты должны проверять как корректность, так и производительность алгоритма.

Тесты на корректность должны исчерпывающе проверять все граничные и стандартные режимы работы в режиме как чёрного, так и белого ящика. Желательно продемонстрировать покрытие кода и/или веток алгоритма тестами.

Тесты должны включать как созданные вручную, так и сгенерированные генератором.

Исходный код всех генераторов, как и код их запуска, должен быть в репозитории. Сами сгенерированные тесты, как и прочие артефакты, производимые в процессе компиляции и запуска, НЕ должны находиться в репозитории.

К исходному коду генераторов и тестирующей подсистемы предъявляются те же требования модульности и оформления, что и к коду алгоритма.

Тесты на производительность должны измерять время работы и, если необходимо, затраты памяти алгоритма.

Тесты должны включать защиту от эвристик, и, желательно, реализацию этих эвристик для демонстрации успешной защиты.

По результатам измерения должны быть составлены графики и/или таблицы, демонстрирующие, что алгоритм обладает заявленной алгоритмической сложностью и что константный множитель в оценке сложности реализации сопоставим с константой встроенного и/или тривиального алгоритма. Рекомендуется включить в явном виде аппроксимирующие формулы, полученные например с помощью электронных таблиц или статистических библиотек.

Если возможно, тесты должны сравнивать корректность и производительность со стандартными алгоритмами и структурами данных языка программирования. Если соответствующего стандартного алгоритма нет, следует привести сравнение с наивным/тривиальным алгоритмом.


Задача 1F. Пакет в CATS

Максимальный балл:10   Ограничение времени:1 сек
  Ограничение памяти:512 Мб

Условие

Пакет в CATS к алгоритму.


Задача 2D. Дивизион D

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:40  

Условие

Количество задач, решённых в дивизионе D


Задача 2E. Дивизион E

Входной файл:Стандартный вход   Ограничение времени:1 сек
Выходной файл:Стандартный выход   Ограничение памяти:512 Мб
Максимальный балл:60  

Условие

Количество задач, решённых в дивизионе E.

0.178s 0.009s 27