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

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