Разминка для математических мозгов: взлом теста для программистов
Математики, физики, machine learning специалисты и к ним примкнувшие, нужна помощь.
Когда-то я написал статью про взлом тестов для программистов и предложил метод, которому не знаю название. Помогите мне, пожалуйста, ликвидировать этот пробел. Ну или просто разомните мозги, на мой взгляд интересная задача и красивое решение (кстати, не единственное).
Итак, сама задача. Имеется классический и самый обычный тест для программистов. Это черный ящик, который предлагает вопросы, принимает ответы и на выходе даёт числовой результат. За правильный ответ присваивается балл. Конечный результат теста - сумма баллов (или число правильных ответов). За одну серию (испытание) спрашивается m вопросов, они случайно достаются из банка с n вопросами, причем n заметно больше, чем m.
Тест можно проходить бесконечно. Все тексты вопросов и вариантов ответов неизменны и доступны к сохранению. Нужно найти такой алгоритм, чтобы подобрать правильные ответы и пройти тест с максимальным результатом за наименьшее число «подборов».
В статье (ссылка в комментарии) зачем-то было очень много матана, но суть там была очень простой.
Сначала я думал в сторону систем линейных уравнений, но потом меня осенило вот что. Если отвечать совершенно случайно, то результаты тестов очевидно имеют некоторое распределение рейтинга с явным «максимумом» - наиболее вероятным результатом. Однако, посколько мы можем «тестировать» черный ящик бесконечно долго, мы будем получать много таких серий, в которых рейтинг будет отличаться от наиболее вероятного. Произойдет это в случае, если мы случайно угадали больше или меньше обычного. Ключевая идея метода в том, чтобы учитывать только такие серии, где мы угадали, например, больше обычного. И для таких испытаний мы всем вариантам ответов, которые использовали, будем прибавлять 1. Тогда за число испытаний, всего на пару-тройку порядков выше числа вопросов, все правильные варианты ответов получат заметно выше рейтинг, чем неправильные, и для каждого вопроса можно будет сделать однозначный вывод о том, какой из ответов правильный - им просто будет ответ с максимальным рейтингом.
Вот такой нехитрый, но по-моему очень красивый метод. Если вдруг вы знаете, как такой класс решений называется - напишите, пожалуйста, в комментариях.
Математики, физики, machine learning специалисты и к ним примкнувшие, нужна помощь.
Когда-то я написал статью про взлом тестов для программистов и предложил метод, которому не знаю название. Помогите мне, пожалуйста, ликвидировать этот пробел. Ну или просто разомните мозги, на мой взгляд интересная задача и красивое решение (кстати, не единственное).
Итак, сама задача. Имеется классический и самый обычный тест для программистов. Это черный ящик, который предлагает вопросы, принимает ответы и на выходе даёт числовой результат. За правильный ответ присваивается балл. Конечный результат теста - сумма баллов (или число правильных ответов). За одну серию (испытание) спрашивается m вопросов, они случайно достаются из банка с n вопросами, причем n заметно больше, чем m.
Тест можно проходить бесконечно. Все тексты вопросов и вариантов ответов неизменны и доступны к сохранению. Нужно найти такой алгоритм, чтобы подобрать правильные ответы и пройти тест с максимальным результатом за наименьшее число «подборов».
В статье (ссылка в комментарии) зачем-то было очень много матана, но суть там была очень простой.
Сначала я думал в сторону систем линейных уравнений, но потом меня осенило вот что. Если отвечать совершенно случайно, то результаты тестов очевидно имеют некоторое распределение рейтинга с явным «максимумом» - наиболее вероятным результатом. Однако, посколько мы можем «тестировать» черный ящик бесконечно долго, мы будем получать много таких серий, в которых рейтинг будет отличаться от наиболее вероятного. Произойдет это в случае, если мы случайно угадали больше или меньше обычного. Ключевая идея метода в том, чтобы учитывать только такие серии, где мы угадали, например, больше обычного. И для таких испытаний мы всем вариантам ответов, которые использовали, будем прибавлять 1. Тогда за число испытаний, всего на пару-тройку порядков выше числа вопросов, все правильные варианты ответов получат заметно выше рейтинг, чем неправильные, и для каждого вопроса можно будет сделать однозначный вывод о том, какой из ответов правильный - им просто будет ответ с максимальным рейтингом.
Вот такой нехитрый, но по-моему очень красивый метод. Если вдруг вы знаете, как такой класс решений называется - напишите, пожалуйста, в комментариях.