Дискретная математика

Подготовка к экзамену

Посещаемость

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

Письмо нужно послать на адрес iposov+dm@gmail.com, тема не важна. Внутри письма укажите построчно следующие данные

группа
фамилия имя
ряд … (считая от меня)
место … (считая по людям слева направо)
решение задачи (не обязательно. Можно в нескольких строчках)

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

Текущую посещаемость и другие результаты можно проверить по ссылке: Посещаемость и результаты

Конспекты

Текущий набор конспектов

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

Я не ожидаю, что кто-то напишет все лекции, вполне достаточно будет для одного человека сделать одну, две, три штуки за семестр.

Важно, чтобы вы набирали лекции именно в LaTeX. Вот немного материалов по нему:

Сайт Overleaf позволяет работать в LaTeX онлайн, без установки его на компьютере.
MikTeX - это дистрибутив TeX, именно его надо установить на Windows, чтобы писать на LaTeX. Для других OS устанавливайте дистрирубтив texlive.
Учебник: Липский. Набор и верстка в системе LaTeX
Сайт overleaf, указанный выше, содержит очень хорошие материалы по LaTeX, но они на английском.

При написании конспекта уделите внимание содержанию. Не нужно настраивать параметры страницы, шрифты, другие глобальные параметры. Просто напишите текст и все необходимые формулы.

Дополнение

Убедитесь, что ваш файл компилируется без предупреждений. Некоторые незначительные ошибки TeX исправляет автоматически, выводя предупреждения, но вы все равно разберитесь, как писать правильно.
Современный способ добавления изображений в LaTeX документ - это SVG картинки, их можно создавать в бесплатной программе Inkscape. Делайте картинки, если не можете добавить графику средствами самого LaTeX.

Программирование

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

Набор минимальных требований и рекомендаций к программе.

Программа должна уметь запускаться “из командной строки” и самостоятельно завершаться после создания генератора. Это значит, что должна быть возможность запустить вашу программу, подождать, когда она закончит работу, и сразу получить результат. Если вы пишете на c/c++/pascal, это простейшая форма программы, которую можно создать. Скорее всего, такая программа в вашей среде разработки будет называться “консольной” программой.

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

Если вы пишете на javascript, изучите nodejs, чтобы ваша программа могла запускаться без браузера. Если вы пишете на php, разберитесь, как в нем можно запускать программы в режиме скрипитов, без веб сервера.
Программа должна получать на вход число-инициализатор генератора случайных чисел (seed или randseed по-английски). При запуске генератора несколько раз с одним и тем же значением seed должен получаться одинаковый результат генерации. В стандартной библиотеке вашего языка должна быть возможность инициализировать генератор случайных чисел.

Значение randseed должно быть 64 битным беззнаковым целым, т.е. числом от -2⁶³ до 2⁶³-1.

У программы могут быть и другие параметры, влияющие на процесс генерации, например, уровень сложности задачи, форма ответа, но это на ваше усмотрение.
Программа получает параметры, т.е. значение randseed, через аргументы командной строки. Или через стандартный ввод (клавиатуру). Или, через файлы - перечислено от наиболее рекомендуемого к менее рекомендуемому варианту. Вы можете придумать и другие способы, но помните, что программа должна запускаться автоматически, поэтому, например, не подходит вариант, что кому-то нужно ввести данные в окошко.
В результате работы программы необходимо сгенерировать два текста: текст условия и текст ответа. Например, условие “Чему равно произведение 6 и 9?” И ответ “42”. Если в условии и ответе есть формулы, оформляйте их в формате LaTeX. Это не так сложно, как кажется. Вот ссылка с простейшими примерами формул, и вот ссылка тестировать, как выглядят тексты с формулами, которые создаёт ваш генератор.

Выдавать результат программа может на стандартный вывод (т.е. в консоль), или в файлы. Возможны другие варианты, но помните, что результат работы программы будет собираться автоматически.
Вы можете добавить к программе оконный интерфейс, веб интерфейс, но это дополнительные, необязательные возможности.
Программу нужно передать в виде архива, в котором содержатся следующие файлы и информация:
- исходные коды программы. Постарайтесь передать минимально необходимые коды без лишних файлов, например, настроек вашей среды разработки.
- описание, как компилировать программу
- бинарные, т.е. скомпилированные и готовые к запуску файлы. Но только если они нужны, например, они не нужны для интерпретируемых языков типа python, javascript.
- описание, как запускать программу, как передавать параметры, как получать ответ. Какие есть режимы запуска кроме основного.
- примеры результатов работы программы
- хотя бы краткое описание самого генератора, как он работает, и как решать генерируемые им задачи.
Почтовые сервисы могут не пропускать бинарные файлы, в этом случае будьте готовы передать файлы через файлообменник или облака.
Помните, что программы будут запускаться не на вашем компьютере, а на чужом, и, вероятно, на linux. Старайтесь делать программу максимально независимой от среды. Самая частая проблема - использовать абсолютные пути к файлам в коде программы. Например, c:\windows\a.txt. Для максимальной переносимости лучше вообще не пользоваться файлами, получайте параметры через командную строку или стандартный ввод, и выдавайте результат через стандартный вывод.

Пример генератора на C++.

Пример генератора на Python (пока не готов)

Перед началом работы напишите мне письмо для выбора задачи. Вы можете либо сами предложить задачу, либо спросить меня. Примеры задач (кратко):

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