Дополнительные главы дискретной математики 2017/18 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
(→Материалы курса) |
|||
| Строка 19: | Строка 19: | ||
|- | |- | ||
|| Чувствительность и блочная чувствительность: квадратичный разрыв. Сертификатная сложность не больше квадрата блочной чувствительности. Степень булевой функции. Степень не больше сложности в модели деревьев разрешения. Пример: степень квадратично больше сертификатной сложности. Пример: чувствительность больше степени. || | || Чувствительность и блочная чувствительность: квадратичный разрыв. Сертификатная сложность не больше квадрата блочной чувствительности. Степень булевой функции. Степень не больше сложности в модели деревьев разрешения. Пример: степень квадратично больше сертификатной сложности. Пример: чувствительность больше степени. || | ||
| − | [http://www.mi.ras.ru/~podolskii/files/extra_dm/cw03_dop.pdf Листок 3] | + | [http://www.mi.ras.ru/~podolskii/files/extra_dm/cw03_dop.pdf Листок 3] <br> <span style="color:red">Updated: 05.02.18</span> |
|} | |} | ||
Версия 10:06, 5 февраля 2018
Общая информация
Дедлайны
Домашнее задание 1 дедлайн: 16 марта, 23:59 AoE
Задание сдается письменно.
Из каждого дз достаточно решить две задачи.
Материалы курса
| Summary | Домашнее задание |
|---|---|
| Сумма игр, функция Шпрага-Гранди, функция Шпрага-Гранди суммы игр. | Листок 1 |
| Разрешающие деревья, сертификатная сложность, примеры. Соотношения между сертификатной сложностью и сложностью в модели разрешающих деревьев; пример квадратичного разрыва. Чувствительность и блочная чувствительность. Обзор по теме. | Листок 2 |
| Чувствительность и блочная чувствительность: квадратичный разрыв. Сертификатная сложность не больше квадрата блочной чувствительности. Степень булевой функции. Степень не больше сложности в модели деревьев разрешения. Пример: степень квадратично больше сертификатной сложности. Пример: чувствительность больше степени. |
Листок 3 |
