Дополнительные главы дискретной математики 2017/18 — различия между версиями

Версия 20:56, 31 января 2018

Домашнее задание 1 дедлайн: TBA

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

@@ Строка 15: / Строка 15: @@
 |-
   || Разрешающие деревья, сертификатная сложность, примеры. Соотношения между сертификатной сложностью и сложностью в модели разрешающих деревьев; пример квадратичного разрыва. Чувствительность и блочная чувствительность. [https://homepages.cwi.nl/~rdewolf/publ/qc/dectree.pdf Обзор по теме].  ||  [http://www.mi.ras.ru/~podolskii/files/extra_dm/cw02_dop.pdf Листок 2]
+|-
+ || Чувствительность и блочная чувствительность: квадратичный разрыв. Сертификатная сложность не больше квадрата блочной чувствительности. Степень булевой функции. Степень не больше сложности в модели деревьев разрешения. Пример: степень квадратично больше сертификатной сложности. Пример: чувствительность больше степени. ||
 |}