Дополнительные главы дискретной математики 2
Преподаватель
Преподаватель факультатива
Первое занятие - 23 января с 13.40 до 15.00 – ауд. G002,
3 модуль с 30 января по 19 марта - c 13.40 до 15.00 - ауд. G004
4 модуль с 2 апреля по 11 июня - c 13.40 до 15.00 - ауд. G004
Текущий курс дискретной математики программы ПМИ покрывает множество больших тем. Поскольку времени в курсе ограниченно, по этим темам удается обсудить только самый необходимый минимум материала. Эту проблему как раз и планируется решить на факультативе. Для желающих студентов на факультативе будет рассказываться дополнительный (по сравнению с пилотным потоком ПМИ) материал по изучаемым в основном курсе темам. Занятия факультатива будут идти параллельно с основным курсом и во многом его продолжать.
От слушателей факультатива требуется знакомство с материалом курса, идущего параллельно дискретной математике на пилотном потоке ПМИ.
Примерная программа курса:
1. Комбинаторные игры. Теория Шпрага-Гранди.
2. Разрешающие деревья. Чувствительность и блочная чувствительность булевых функций.
3. Булевых схемы. Оценки сложности вычисления булевых функций булевыми схемами.
4. Вычислимые функции. Конструкция Поста: невычислимая функция. Сводимость по Тьюрингу и m-сводимость.
5. Машины Тьюринга. Вычисления с ограничением на время и память.
6. Коды с исправлением ошибок.
7. Выполнимость булевых формул.
8. Цепи и антицепи в упорядоченных множествах.
9. Производящие функции.
10. Комбинаторика: методы линейной алгебры, вероятностный метод, полиномиальный метод.