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

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