Виталий Бормотов (bormvit) wrote,
Виталий Бормотов
bormvit

Прикладной вопрос

(формулирую с использованием формальной математики, но смысл должен быть понятен и нематематикам, просто так точнее)

Есть некое свойство - назовем его интересность - которое присуще некоторым натуральным числам, а некоторым нет. Мы не знаем, в чем оно заключается (может, это четность, может, последняя цифра нуль, может, оно читается одинаково слева направо и справа налево - но, скорее всего, что-то несколько более сложное).

Мы знаем следующее:
1) существует много - возможно, бесконечно много, но в любом случае достаточно много чисел (мы говорим только о натуральных: 1, 2, 3...), как обладающих этим свойством, так и нет;
2) свойство имеет какое-то достаточно простое словесное или формульное выражение, которое также можно (если оно будет известно) формализовать на любом языке программирования.

У нас есть два набора чисел, в каждом из которых их ровно 100. Все числа в первом наборе обладают интересностью, во втором - ни одно (естественно, никакое число не входит в оба набора одновременно). Для простоты предположим, что все рассматриваемые числа достаточно малы (если качественное определение вас не устраивает, скажу, что, в совокупости с п. 2 это говорит нам, что асимптотическая сложность проверки любого числа из набора на соответствие любой осмысленной гипотезе о том, что такое интересность, не превышает O(1)).

Наша задача - определить, в чем именно заключается интересность.

Задачу пытаются решить наши старые друзья Вася и Петя. Они делают это независимо друг от друга.

Вася распечатывает на листочке сотню интересных чисел, на другом - сотню неинтересных и, пристально на них глядя и анализируя, подбирает гипотезу об интересности, которая соответствовала бы всем числам первого листка и не соответстовала ни одному из второго. (Вариант рассмотрения только первого листка очевидно вопиюще ненаучен.) Спустя пару часов он находит три разные вообще, но удовлетворяющие конкретным данным множествам, гипотезы, выбирает из них самую простую и пишет в ЖЖ пост, где говорит, что, скорее всего, интересность - это вот такое-то свойство.

Петя случайным образом выбирает 70 чисел из ста в том и другом списке, стараясь даже не посмотреть на остальные дважды тридцать, и проделывает с ними ту же операцию, что и Вася; в результате он выдвигает 4 гипотезы и называет их a, b, c, d в порядке сложности, при этом a - наиболее сложная, d - самая простая. Затем он применяет эти гипотезы к оставшимся числам (30 интересным и 30 неинтересным) и узнает, что гипотезы a и d неверны, а b и c соответствуют имеющимся данным. Он выбирает гипотезу c как наиболее простую среди подходящих и пишет в ЖЖ пост, где говорит, что интересность - это, скорее всего, c.

Интуитивно - по крайней мере, мне - кажется, что подход Пети корректнее, так как не дает "подогнать" гипотезу под исходные данные, а оставляет возможность апостерирной проверки. А как вы считаете:

1) Какой подход продуктивнее? Как бы поступили вы?
2) Какой результат является более достоверным в строгом смысле слова (при условии, что исходные данные ровно таковы, как в описании задачи, ну разве что)? Можете ли вы это доказать?
3) Можно ли количественно, а не только качественно охарактеризовать различие достоверности в том или ином случае?
4) Если подход Пети действительно лучше, то в какой пропорции стоит разбивать исходные данные? 70/30? 80/20? 50/50? Почему?

И, да, задача вполне корректна - не потому, что в ней есть все исходные данные, а потому что подобная ей может возникнуть в реальности.

Также загляните сюда - оно почти о том же самом, просто в другой предметной области и другими словами :) Подробнее еще будет.
Tags: познание
Subscribe
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 16 comments