Задача: «Кибержулики» Некто придумал задачу для школьной Олимпиады по кибернетике, в которой ответом является число, принимающее при любых наборах исходных данных одно из двух значений: А или В. Автоматическая система проверки решений (тестер) проверяет каждую версию программы решения на N наборах исходных данных (тестах), выдавая для каждого набора (попытки) число правильных ответов. Команда «Кибержулики» хочет получить за задачу полный балл, пользуясь методом «тыка», т.е. не решая ее, а генерируя пробные наборы ответов.
Вопрос 1: за какое минимальное число попыток команда может наверняка дать правильные ответы на все тесты?
Вопрос 2 (обобщение): каково будет минимальное число попыток, если ответ в задаче принимает не два значения, а M значений?
(Задача иллюстрирует понятие информации, она предлагалась на Санкт-Петербургской школьной Олимпиаде по кибернетике в 2007 г.)
Реферирование статьи
Колмогоров А.Н.
Три подхода к определению понятия «количество информации»
Проблемы передачи информации. 1965. Т.1, №1. С.3–11.
PDF-файл
Реферирование статьи
Landauer R.
Information is a physical entity
Physica A, V. 263, 1999 P 63–67
(Файлы этих и многих других статей имеются у руководителя.)