Взвешивания, отгадывания, пробы: сложность алгоритмов // Александр Шень

Сколько нужно вопросов (с ответом “да” и “нет”), чтобы заведомо отгадать задуманное число от 1 до 1000? Можно ли обойтись меньшим числом вопросов? Если нет, то как это доказать? Сколько нужно взвешиваний на чашечных весах без гирь, чтобы наверняка выделить более лёгкую монету среди 1000 одинаковых на вид? С такого рода вопросов начинается наука о сложности алгоритмов, и очень скоро доходит до важных, но до сих пор не решённых задач. Шень Александр Ханиевич, кандидат физико-математических наук. Популярные лекции по математике и смежным наукам 16 февраля 2014 г., XXV Математический праздник, МГУ им. М.В. Ломоносова