Дополнительные главы дискретной математики 2017/18

Материал из Wiki - Факультет компьютерных наук
Перейти к: навигация, поиск

Общая информация

Правила выставления оценок

Дедлайны

Домашнее задание 1 дедлайн: 16 марта, 23:59 AoE

Материалы курса

Summary Домашнее задание
Сумма игр, функция Шпрага-Гранди, функция Шпрага-Гранди суммы игр. Листок 1
Разрешающие деревья, сертификатная сложность, примеры. Соотношения между сертификатной сложностью и сложностью в модели разрешающих деревьев; пример квадратичного разрыва. Чувствительность и блочная чувствительность. Обзор по теме. Листок 2
Чувствительность и блочная чувствительность: квадратичный разрыв. Сертификатная сложность не больше квадрата блочной чувствительности. Степень булевой функции. Степень не больше сложности в модели деревьев разрешения. Пример: степень квадратично больше сертификатной сложности. Пример: чувствительность больше степени.