City: Saint Petersburg Novosibirsk Kazan Language: Русский English

Лекция 13. Теорема о матричных играх и принцип Яо
Introduction to Theoretical Computer Science

What: Lecture
When: Monday, 07 December 2020, 18:30–19:50
Where: Конференция в zoom, Онлайн

Description

Лемма Фаркаша. Лемма о неотрицательных комбинациях строк и столбцов матрицы. Матричные игры, смешанные стратегии. Теорема фон-Неймана. Принцип Яо: оценка сложности вероятностных алгоритмов сортировки, сложность вероятностных деревьев решений, вычисляющих \(Maj_3\).

Video

Attached files

Other materials

Текущая версия конспекта.