Лекция прочитана 8 декабря 2018 года в Москве, в Российской государственной детской библиотеке, в рамках лектория «Просветителя» — совместного проекта «Курилки Гутенберга», премии «Просветитель» и РГДБ.
Сколько посетителей заходит на наш сайт из разных регионов России? Сколько школьников в этом году подали заявления в вузы? Сколько людей обсуждают в социальных сетях нашу партию? Сотрудники Google пишут, что в их систему хранения и обработки данных поступает свыше пяти миллионов подобных запросов в день! Регулярно встречаются запросы, предполагающие подсчет более миллиарда объектов. Несмотря на простую формулировку, при решении таких задач мы сталкиваемся с фундаментальными ограничениями компьютерной памяти. Как найти хорошее приближение, практически ничего не запоминая?
Интересно, что самые эффективные методы решения основаны на так называемых «рандомизированных алгоритмах». То есть при подсчете мы не только удовлетворяемся приближениями, но еще и полагаемся на случайность! Тем не менее, математика гарантирует качественный ответ. Сходу такой алгоритм нельзя придумать, но понять основные идеи не так уж сложно. Прослушав эту лекцию, вы научитесь считать, как компьютер... приблизительно!
