План курса

Материал из Викиконспекты
Перейти к: навигация, поиск

Цель: набрать хотя бы 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 баллов.
  • Помощь Алексею Сергушичеву с тестирующей системой — он оценивает сам.