Комбинаторные объекты

Это дополнительное задание для студентов первого курса 2017–2018 учебного года мат-меха СПбГУ — групп 17.Б01-мм и 17.Б02-мм.

При изучении математики мы часто сталкиваемся с комбинаторными объектами. Например, это могут быть перестановки, подмножества заданного множества, слова Дика, разбиения на слагаемые, разбиения множества на подмножества. При работе с такими объектами возникают типичные задачи: записать объект, посчитать количество объектов заданного размера, показать все объекты в каком-то удобном порядке, перебрать их в этом порядке, или даже научиться быстро по номеру в этом порядке узнавать объект и наоборот.

В этом задании мы систематизируем знания о различных комбинаторных объектах и решения типичных задач для них. В процессе решения мы будем использовать язык C++ (в частности, классы и наследование), онлайн-энциклопедию целочисленных последовательностей OEIS, а также систему контроля версий Git и онлайн-платформу GitHub.

Можно посмотреть слайды по решению подобных задач для комбинаторных объектов, а также мини-инструкцию по использованию Git и GitHub в похожем случае.

Задание

Каждый студент может выполнить следующие части задания:

1. Выбрать интересный комбинаторный объект и способ его записи, для которого задание ещё не выполнено.

   • Формальные критерии: объект должен иметь размер — целое число n — и записываться как последовательность из n целых чисел. Если интересный вам объект обычно записывается иначе, попробуйте найти другой подходящий способ записи. Например, правильные скобочные последовательности в чистом виде не подходят, так как состоят из скобок, но их можно записывать как слова Дика, состоящие из цифр 0 и 1. Разбиения числа n на слагаемые обычно записываются как последовательности слагаемых и имеют разную длину, но разбиение можно записать и в виде n чисел — например, указав, какому по счёту слагаемому принадлежит каждая из n единичек суммы.

   • Примерный критерий интересности объекта: наличие последовательности «количество таких объектов размера n» в On-Line Encyclopedia of Integer Sequences, http://oeis.org/. Например, для перестановок это факториалы, http://oeis.org/A000142, для скобочных последовательностей это числа Каталана, http://oeis.org/A000108, а для подмножеств заданного множества это степени двойки, http://oeis.org/A000079. Если вы не уверены, что ваш объект интересный — обсудите это с преподавателем, прежде чем выполнять задание.

2. Завести аккаунт на сайте https://github.com и скопировать (fork) себе репозиторий задания: https://github.com/spbsu-student-projects/combinatorial-objects. Там есть общий класс для всех подходящих комбинаторных объектов, который называется CombinatorialObject: в этот момент, вероятно, стоит изучить его описание и реализацию. Есть также пример выполненного задания для строк Фибоначчи, а также, возможно, другие выполненные задания.

3. В своей копии завести каталог для выбранного комбинаторного объекта, написав его название маленькими английскими буквами и знаками подчёркивания. Далее мы для примера будем рассматривать выдуманный объект «макаронный монстр», так что каталог будет называться spaghetti_monster. Там следует завести несколько файлов:

   • Файл spaghetti_monster.h, в котором будет описан класс SpaghettiMonster — наследник класса CombinatorialObject.

   • Файл spaghetti_monster.cpp, который будет содержать реализацию класса SpaghettiMonster.

   • Файл readme.markdown, где будет написано несколько предложений о выбранном комбинаторном объекте и реализованных функциях.

   • Служебный файл runner.cpp для запуска вашего решения, в котором по сравнению с примером поменяются только автор, строка #include и название класса.

   • Служебный файл Makefile для сборки вашего решения, в котором по сравнению с примером поменяется только имя объекта в первой строке.

   • Возможно, вам удобно будет завести дополнительные служебные файлы, например, файлы проекта для Visual Studio, CodeBlocks или другой среды программирования, которой вы пользуетесь.

4. Реализовать в своём классе следующие функции:

   • total (n): посчитать количество объектов размера n.

   • generate_all (n): показать все объекты размера n в лексикографическом порядке.

   • is_valid (v): проверить корректность объекта v.

   • number_by_object (v): среди всех объектов такого же размера, как заданный корректный объект v, найти номер объекта v в лексикографическом порядке, считая с нуля.

   • object_by_number (n, k): среди всех объектов размера n найти k-й объект в лексикографическом порядке, считая с нуля.

   • prev (v): сделать из корректного объекта v предыдущий объект такого же размера в лексикографическом порядке, если он существует, и при этом вернуть результат — существует ли он.

   • next (v): сделать из корректного объекта v следующий объект такого же размера в лексикографическом порядке, если он существует, и при этом вернуть результат — существует ли он.

5. Описать комбинаторный объект и решение в файле readme.markdown.

   • Нужно указать название комбинаторного объекта и дать ему краткое описание.

   • Обязательно нужно указать автора решения.

   • Далее следует указать ссылку на последовательность «количество таких объектов размера n» в OEIS, а после неё — ссылки на статьи об объекте на сайте http://mathworld.wolfram.com, в Википедии и на аналогичных ресурсах.

   • После этого для каждой реализованной функции следует указать асимптотическое время работы в терминах n или ответа. Если используется предподсчёт или ленивые вычисления, это также следует указать вместе с асимптотикой в терминах максимального используемого n. Наконец, если функция имеет лучшую амортизированную асимптотику — это особенно актуально для функций prev и next — это тоже следует отметить.

6. Предложить выполненное задание на проверку. Для этого нужно создать Pull Request к исходному репозиторию, а после этого реагировать на комментарии к нему — вполне возможно, потребуется что-то доделать или переделать.

7. Исправить, улучшить или дополнить части других решений или общего кода. Для этого тоже следует действовать по схеме «fork — modify — pull request».

Сборка и запуск

Для самостоятельной проверки можно собрать и запустить получившуюся программу. Это делается при помощи инструмента make. Кроме того, можно настроить сборку другим инструментом. Программа состоит из трёх .cpp-файлов и двух .h-файлов: в нашем примере это spaghetti_monster.cpp, runner.cpp и spaghetti_monster.h, написанные студентом, а также общие файлы combinatorial_object.cpp и combinatorial_object.h из каталога ../combinatorial_object.

После запуска можно ввести команду help, чтобы получить список доступных команд.

Система оценки

Всё взаимодействие, связанное с оценкой, осуществляется через интерфейс GitHub. Вопросы также можно задать в issues. Все pull request-ы проверяются в порядке их создания.

За выполнение частей задания начисляются баллы. Всего можно получить от 0 до 30 баллов. Основная часть баллов распределяется по реализации указанных функций. За каждый из подпунктов ниже начисляется один балл:

• Описание объекта:

  • правильное описание и ссылки

• total (n):

  • правильная работа и описание
  • вычисление за полиномиальное время
  • «оптимальное» вычисление
  • крайние случаи: результат INT64_MAX, если n отрицательно или количество объектов не помещается в тип int64_t

• generate_all (n):

  • правильная работа и описание
  • «оптимальное» вычисление
  • крайние случаи: результат пуст, если n отрицательно

• is_valid (v):

  • правильная работа и описание
  • вычисление за полиномиальное время
  • «оптимальное» вычисление

• number_by_object (v):

  • правильная работа и описание
  • вычисление за полиномиальное время
  • «оптимальное» вычисление
  • крайние случаи: результат INT64_MAX, если номер не помещается в тип int64_t

• object_by_number (n, k):

  • правильная работа и описание
  • вычисление за полиномиальное время
  • «оптимальное» вычисление
  • крайние случаи: результат пуст, если номер k некорректен

• prev (v):

  • правильная работа и описание
  • вычисление за полиномиальное время
  • «оптимальное» вычисление
  • крайние случаи: переход к последнему объекту после первого

• next (v):

  • правильная работа и описание
  • вычисление за полиномиальное время
  • «оптимальное» вычисление
  • крайние случаи: переход к первому объекту после последнего

Несколько замечаний:

• По каждому пункту окончательное решение о начислении баллов или необходимости доработки принимает преподаватель.

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

• В пунктах выше «оптимальное» вычисление обычно означает, что алгоритма с лучшей асимптотикой не существует, или же его существование не очевидно для участников и преподавателя.

• Код и текст должны быть грамотно составлены, удобны для чтения и написаны в едином стиле. Стиль при этом может отличаться от стиля примера. Код должен компилироваться без ошибок и предупреждений.

Как можно посчитать, по описанным выше правилам можно получить от 8 до 27 баллов. Кроме этого, для комбинаторных объектов, которые реализовал кто-то другой, можно выполнять следующие типы дополнительных заданий:

• Добавить для объекта и его записи альтернативное описание (в файле readme.markdown, после ссылок, но до асимптотик). Например, существуют целые книги, перечисляющие объекты, связанные с числами Каталана. Этот пункт также поможет получить балл в случае, если объект, аналогичный придуманному вами, уже реализован кем-то другим, но ваше описание отличается от указанного.

• Найти и исправить ошибку в любой функции. При этом следует указать, как воспроизвести ошибку в предыдущей версии этой функции (до того, как она была исправлена).

• Ускорить любую функцию, которая работала за экспоненциальное время, до полиномиального времени.

• Улучшить асимптотику любой функции до «оптимальной». Также учитывается улучшение амортизированного времени работы.

• Правильно рассмотреть крайние случаи в любой функции, где они не были рассмотрены.

• Как-то улучшить общий код или другую общую часть задания. Для этого стоит заглянуть в issues и либо взяться там за какое-то одобренное улучшение, оставив комментарий об этом, либо добавить информацию о своём предложении, а потом взяться за него, если оно будет одобрено.

Каждый из типов заданий выше приносит один балл в момент первого выполнения. Дальнейшее выполнение заданий аналогичного типа на баллы не влияет. Исключение — последний пункт об общих улучшениях, который можно выполнять несколько раз и каждый раз получать один балл. Наконец, общая сумма баллов за все выполненные основные и дополнительные задания не может превысить 30.

Чтобы всем было что исправлять и улучшать, решение для слов Линдона уже написано в качестве примера, но асимптотику почти всех функций можно улучшить.

Выполнение частей задания отмечается преподавателем в файле score.txt в том же каталоге. Если какая-то часть не выполнена, отметка напротив неё пуста, и, значит, эту часть можно улучшить.

Изменения в правилах

Вряд ли в правилах удалось с первого раза учесть все тонкие моменты. Если что-то в них непонятно или кажется противоречивым, напишите об этом в issues. Правила могут поменяться, если возникнет такая необходимость.