Дополнительные главы дискретной математики 2017/18 — различия между версиями
Материал из Wiki - Факультет компьютерных наук
(→Материалы курса) |
(→Материалы курса) |
||
Строка 34: | Строка 34: | ||
|| Теорема об иерархии по времени. Квадратичный разрыв между временем вычисления на одноленточных и многоленточных машинах. || | || Теорема об иерархии по времени. Квадратичный разрыв между временем вычисления на одноленточных и многоленточных машинах. || | ||
[http://www.mi.ras.ru/~podolskii/files/extra_dm/cw07_dop.pdf Листок 7] | [http://www.mi.ras.ru/~podolskii/files/extra_dm/cw07_dop.pdf Листок 7] | ||
+ | |- | ||
+ | || Линейные рекуррентные соотношения с постоянными коэффициентами, однородный случай. || | ||
+ | Листка на этой неделе нет] | ||
|} | |} | ||
Версия 19:47, 15 марта 2018
Общая информация
Дедлайны
Домашнее задание 1 дедлайн: 16 марта, 23:59 AoE
Задание сдается письменно.
Из каждого дз достаточно решить две задачи.
Материалы курса
Summary | Домашнее задание |
---|---|
Сумма игр, функция Шпрага-Гранди, функция Шпрага-Гранди суммы игр. | Листок 1 |
Разрешающие деревья, сертификатная сложность, примеры. Соотношения между сертификатной сложностью и сложностью в модели разрешающих деревьев; пример квадратичного разрыва. Чувствительность и блочная чувствительность. Обзор по теме. | Листок 2 |
Чувствительность и блочная чувствительность: квадратичный разрыв. Сертификатная сложность не больше квадрата блочной чувствительности. Степень булевой функции. Степень не больше сложности в модели деревьев разрешения. Пример: степень квадратично больше сертификатной сложности. Пример: чувствительность больше степени. |
Листок 3 |
Схемная сложность функции "четность" от n переменных не меньше 3n-3. Глубина булевой схемы. Булева формула. Эквивалентность схем и формул с точки зрения глубины. Теорема о балансировке булевой формулы. Эквивалентность глубины булевой схемы и размера булевой формулы. | |
Классы функций AC^i, NC^i, иерархия. PARITY не лежит в NC^0. Сложение чисел в AC^0. PARITY не лежит в AC^0, полиномиальный метод: схемы приближаемы многочленами. | Листка на этой неделе не было |
PARITY не лежит в AC^0, полиномиальный метод: многочлены не приближают PARITY. PARITY вычисляется AC^0 схемой глубины d и размера $2^{n^{O(1/d)}}$. Теорема Роджерса о главных универсальных функциях, начало доказательства. | |
Теорема о существовании перечислимых неотделимых множеств. Перечислимое бесконечное множество номеров вычислимой функции. Теорема Роджерса об изоморфизме главных универсальных функциях. Конструкция Поста перечислимого неразрешимого множества. | |
Теорема об иерархии по времени. Квадратичный разрыв между временем вычисления на одноленточных и многоленточных машинах. | |
Линейные рекуррентные соотношения с постоянными коэффициентами, однородный случай. |
Листка на этой неделе нет] |