План курса

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

Как можно набрать баллы:

Конспекты

• Кураторство — 30 баллов.
  • Кураторы конспектов — Андрей Комаров, Артем Васильев и Андрей Шулаев.
• Конспект — 25 баллов.
  • Конспекты и их распределение.
  • Нужно выбрать алгоритм, который был или не был рассказан и согласовать.

Презентации

• Кураторство — 30 баллов.
  • Кураторы презентаций — Вика Волочай и Андрей Рыбак.
  • От кураторов нужен простой пример в beamer, от которого можно было бы отталкиваться.
  • Кураторы должны следить, чтобы все презентации были оформлены в едином стиле и без ошибок.
• Презентация — 25 баллов.
  • Презентация должна представлять из себя не полную копию конспекта, а удобное сопровождение лекции, содержащее какие-то основные формулировки, примеры, хорошие, информативные картинки, и тому подобное.
  • Презентация должна быть сделана в beamer и, для удобства, лежать в каком-нибудь хостинге репозиториев (github/bitbucket и т.п.)

Задачи

• Список задач.
  • Задачи делятся на простые (от 10 до 17 баллов включительно), сложные (от 18 до 29 баллов включительно) и прочие. Задачи, которые стоят 30 и больше — необязательны, но также пойдут в счет сложных в случае решения. За решенную в срок задачу ставится соответствующий балл, после дедлайна баллы начинают убывать.
  • После того, как вы выбрали задачи, которые хотите решать, надо отметиться в форме. Одну задачу одновременно может взять не более 6 человек. Одновременно можно взять одну простую и одну сложную задачу.
  • Задача должна быть решена лучше опеределенной минимальной производительности (будет выбрана позже).
  • После того, как задача сдана, можно запросить code review и также получить за него дополнительные баллы.
  • Можно использовать библиотеки GMP и boost::interval.

Формула для расчета баллов за сданную задачу:

[math] B = M \cdot C_{delay} + \frac{M}{2} \cdot C_{performance} + \frac{M}{4} \cdot C_{quality} [/math], где

[math] M [/math] — заявленный в таблице балл за задачу,

[math] C_{delay} [/math] — коэффициент за опоздание в сдаче задачи (от 1 до 0.5),

[math] C_{performance} [/math] — коэффициент за производительность (от 0 до 1),

[math] C_{quality} [/math] — коэффициент за качество кода (от 0 до 1).

[math] C_{delay} = \begin{cases} 1,& T \le T_{deadline}\\ \max(\frac{1}{2}, 1 - \frac{1}{60} \cdot (T - T_{deadline})),& T \gt T_{deadline} \end{cases} [/math], где

[math] T [/math] — текущий номер дня,

[math] T_{deadline} [/math] — день дедлайна.

Проще говоря, если вы сдаете задачу до дедлайна, вы получаете за нее полный балл. После дедлайна баллы за задачу убывают линейно в течение месяца до [math] \frac{M}{2} [/math]. Дальше убывание баллов прекращается.

[math] C_{performance} = 1 - 2^{1 - \frac{t_{min}}{t}} [/math], где

[math] t [/math] — время работы вашей программмы,

[math] t_{min} [/math] — минимальная производительность.

Таким образом, с минимальной производительностью коэффициент будет равен нулю, если вы решили в два раза быстрее, он равен 0.5, если в 10 раз — то почти 1.

Коэффициент [math] C_{quality} [/math] — выставляется непосредственно проверяющим качество кода.

• Офомление условия в tex — 3 балла.
  • Тикеты на условия и чекеры — тут.
  • За условия и соответсвие их чекерам отвечает Андрей Козлов.
  • Задача должна быть оформлена в виде скомпилированного в TeX файла с условием, описанием формата входных и выходных данных.
• За чекер к задаче — число баллов, указанное в таблице
  • Чекер может работать неоптимально, но должен быть абсолютно корректным.
  • Можно пользоваться любыми внешними библиотеками (например, CGAL).
  • Также автор чекера генерирует некоторый набор тестов (хотя бы рандомных).

Экзамен

• За экзамен можно получить до 20 баллов.
  • Экзамен будет состоять из теоретической части и реализации задач вычислительной геометрии.

Прочее

• Написание tutorial'а — 25 баллов. В tutorial должно быть освещено:
  • Как собирать проект.
  • Показать сложности в реализации задач.
  • Пример задачи с решением, в которой все тонкости и сложные случаи рассматриваются со ссылкой на конспект.
• Viewer для отладки алгоритмов вычгеома + документация и простой пример — 100 баллов. Требования:
  • Viewer должен быть написан на Qt + OpenGL.
  • Ошибки ловятся с помощью boost/exception, в примерах должен быть продемонстрирован этот способ отладки.
  • Документация и простые примеры работы с ним.
  • Реализовать тривиальный набор примитивов (точки, вектора, отрезки, полигоны и т.д.)
  • Поддержка в рабочем состоянии.
  • Баллы получит лучший вьюер, возможно, остальные тоже получат в зависимости от их качества.
• Разобраться с CORE/Leda — в случае успеха — 100 баллов, в случае фейла — 15.
  • Продемонстрировать что с помощью этих библиотек можно реализовать точные предикаты, принимающие на вход данные, полученные разными путями.
• Кодогенератор для предикатов — 100 баллов.
• Помощь Алексею Сергушичеву с тестирующей системой — он оценивает сам.