Лемма Фаркаша. Двойственные задачи линейного программирования. Матричные игры, цена игры, теорема фон Неймана. Применение теоремы о матричных играх для оценки сложности вероятностных алгоритмов.