Точные оценки на сложность. Лекция 11
Таймкоды
- Задача о пересекающем наборе и поиск подсолнуха
- Лемма о частом элементе и подсолнухе
- Инвариант о частоте элементов в множествах дерева
- Индукция: сколько множеств может появиться и исчезнуть
- Ограничение на число добавлений лепестков на пути
- Оценка числа листьев дерева и итоговая граница
- Перенос на SAT и связь с нижними оценками для схем
- Схемы ограниченной глубины и модульные вентили
- План: расщепление переменных и симметрическая схема
- Функция f(S) и быстрая свёртка по подмножествам
Таймкоды созданы автоматически по субтитрам. Будем благодарны за сообщения об ошибках.
АвторИван Михайлин
Лекции курса
16- Точные оценки на сложность. Лекция 1
- Точные оценки на сложность. Лекция 2
- Точные оценки на сложность. Лекция 3
- Точные оценки на сложность. Лекция 4
- Точные оценки на сложность. Лекция 5
- Точные оценки на сложность. Лекция 6
- Точные оценки на сложность. Лекция 7
- Точные оценки на сложность. Лекция 8
- Точные оценки на сложность. Лекция 9
- Точные оценки на сложность. Лекция 10
- Точные оценки на сложность. Лекция 11▶ Вы тут
- Точные оценки на сложность. Лекция 12
Онлайн-курсы по математике
3
Математика для поступающих в 8 класс
Курс поможет ученикам 6−7 классов подготовиться к поступлению в физико-математическую школу. Вы научитесь решать задания из вступительных работ Президентского ФМЛ № 239, ФТЛ им. П. Л. Капицы, школы № 179, лицея «Вторая школа» и ФМШ № 2007.
Бесплатный

Математика: от баллов к знаниям
Если вы абитуриент или студент нематематических специальностей и хотите не завалить сессию, наш курс для вас.
Бесплатный

Алгебра 7 класс
Бесплатные уроки по алгебре для 7 класса, записанные в студии Президентского ФМЛ № 239 для проекта Российская Электронная Школа.
Бесплатный
