О нетривиальном соблазнении тестировщицы Клавдии: задачки из буклета GridGain c JBreak и JPoint

    Очередные Java-конференции JBreak и JPoint прошли на «ура». Здешние доклады всегда имеют резонанс, но многим запомнилось и кое-что ещё.

    Буклет GridGain. Задачки про Грефа и Балмера, белорусского программиста с ведром картошки и, конечно, нетривиальное соблазнение тестировщицы Клавдии продолжают публиковать на различных ресурсах на радость автору, и многие уже даже не знают, каков их источник.


    Рассказываем. Задачки были специально сочинены главным архитектором core-команды GridGain Сергеем Владыкиным и после решены всеми остальными её участниками.

    Мы знаем, что у большинства посетителей конференций, основную сложность вызвала задача №1. Не расстраивайтесь, так же было и среди сотрудников GridGain! Но, справедливости ради, надо отметить, что на московском JPoint нашлось 3 человека, которые решили правильно все 4 задачки и передали свои результаты нам.

    Страна! Знай своих героев! Это:

    • Алексей Остриков
    • Анна Гусенцова
    • Иван Смольянинов

    Сегодня мы публикуем решения задачек: для тех, кто хорошо их помнит, и для тех, кто видит их впервые. Развлекайтесь!



    Решение
    Как нам кажется, основное затруднение у участников вызвали два, на первый взгляд, противоречащих друг другу утверждения: с одной стороны, Герман Оскарович и Стив договорились передавать байты по очереди, с другой — они могут говорить и слушать одновременно. Тонкость в том, что если каждый из участников может отличить слово от тишины за 0.05 секунды, то последний бит в байте можно различить за 0.05 секунды (даже если это было слово, кодирующее “1”) и начать передавать очередной байт уже в другую сторону. Поэтому время передачи первых семи бит в байте зависит от значения байта, а последний бит всегда можно передать за 0.05 секунды.

    Далее остается только подсчитать среднее время передачи одного байта в каждую сторону. Так как значения битов “1” и “0” равновероятны, то время передачи одного байта в одну сторону составляет

    ${1\over2}({1\over7}+{1\over20})\times7+{1\over20}$


    секунд, время передачи одного байта в другую сторону составляет

    ${1\over2}({1\over11}+{1\over20})\times7+{1\over20}$


    секунд. Общее время передачи двух байт в обе стороны составляет

    ${1\over2}({1\over7}+{1\over11}+{1\over10})\times7+{1\over10}$


    секунд, и, соответственно, пропускная способность в битах составляет

    ${16\over{1\over2}({1\over7}+{1\over11}+{1\over10})\times7+{1\over10}}\approx12.62 \text{ бит/сек.}$



    Также стоит отметить, что проводить аналогичные вычисления с частотами некорректно, так как усреднение частот нарушает предположение о равномерном распределении “1” и “0” в битах.




    Решение
    Понятно, что в передаче шприца участвуют оба наркомана, поэтому параллельно могут быть выполнены только первый и третий шаги, а время этого параллельного выполнения будет равным максимальному из T1 и T3, при этом при передаче шприца ни первый, ни второй наркоман не могут выполнять других действий, то есть передача шприца будет выполняться последовательно с другими шагами. Поэтому ответ:

    $\max(T1,T3)+T2$






    Решение
    В этой задаче нам требуется оптимизировать среднее количество картошки, попадающее в ведро за единицу времени, которое равно произведению количества картошки, собранной за эту единицу времени на вероятность того, что эта картошка попадет в ведро. Если x — расстояние программиста от ведра, то среднее количество картошки вычисляется по формуле

    $V(x)=(0.5+x)(1-0.25x)=-0.25x^{2}+0.875x+0.5$


    Квадратичная функция достигает своего экстремума (в данном случае — максимума) в точке

    $$display$$-{b\over2a}={0.875\over2\times0.25}=1.75$$display$$





    Решение
    Иннокентий повстречается на сеновале с Кондратием в том случае, если за 90 минут тестирования Клавдия не воспроизведет баг, а при контрольном прогоне тестов QA-lead его все же обнаружит. При этом понятно, что каждое из испытаний независимо от другого, поэтому конечная вероятность будет равна произведению вероятностей каждого из событий. Так как пикап-лайн выводится в конце прогона тестов, то нас интересует только количество полных прогонов тестов за 90 минут, что равно

    $\text{floor}({90\over17})=5$


    Вероятность того, что баг не воспроизведется за 5 прогонов тестов составляет

    $(1-0.11)^{5}$


    а значит вероятность того, что после 5 успешных прогонов тестов баг воспроизведется на контрольном прогоне, равна

    $(1-0.11)^{5}\times0.11=0.0614$



    P.S. Спасибо за старания всем тем, кто нашел время на конференциях JPoint и JBreak на решение этих задачек. А таких было много, что не может не радовать!
    GridGain
    100,00
    Компания
    Поделиться публикацией

    Комментарии 15

      0
      А в чём сакральный смысл выкладывания текста картинками?
        0
        Чтобы не спёрли? )
          +2

          Может, чтобы сохранить первоначальное ламповое оформление?

          0
          Стилизация: чтобы ламповая форма соответствовала содержанию. Как в еде — важен не только вкус, но и запах, и форма подачи, или в картинах, где иногда впечатление составляет не только одна картина, но и ее рама или сопроводительный материал (как, например, манифест супрематизма Малевича, относящийся к его Черному квадрату).
            +1
            Ламповая стилизация — это хорошо, но текст про Клавдию глазам читать больно.
            Почему-то он размытый.
              +6
              GlukKazan, посмотрите, пожалуйста, похорошела ли теперь Клавдия? Привел картинку в соответствие с остальными по разрешению.
                0
                Да, значительно похорошела.
            +1
            Буклетики именно так и выглядели. Няшный шрифт :-P
            +2
            В первой задаче проблема не в деталях, а в общей формулировке.
            Не понятно как вы превысили скорость света Балмера?
            1. Если представить что всегда говорит только Балмер, а Греф понимает все сразу (едва Балмер откроет рот), то максимально достижимая скорость 11 бит/сек
            2. Из условия следует что Балмер произносит слово приблизительно за 0.091 сек, но уже через 0.05 сек Греф понимает что это слово или молчание (где-то как раз после произнесения «Devel...»). В итоге Балмер произносит 7 слов за 7*1/11 сек, и еще 0.05 сек нужно Грефу чтобы понять смысл 8 слова и начать свою речь.
            3. Аналогично Греф тратит 7*1/7 сек на свои 7 слов и 8 слово Балмер понимает за 0.05 сек
            4. 16 бит передается за (7/11+1/20)+(7/7+1/20) секунд или 191/110 сек, в среднем получается ~9.214 бит/сек (или 1760/191)
            Лучше всего тут бы подошла простая визуализация передачи сообщений по времени, что-то не так там с логикой.
              +1
              1. Если представить что всегда говорит только Балмер, а Греф понимает все сразу (едва Балмер откроет рот), то максимально достижимая скорость 11 бит/сек

              Из задачи предполагается, что теоретическая разрешающая способность системы — 0.05 сек., но при этом сигнал может посылаться только непрерывным потоком в 1/11 сек. либо 1/7 сек. Соответственно, объем передаваемой информации по данному условию зависит от того, что передается: «0»-и передаются быстрее «1»-иц, поскольку единицы нам нужно ждать дольше, чем мы теоретически могли бы, передавайся они со скоростью эквивалентной нашей разрешающей способности.

              Соответственно, максимально достижимая скорость — если передаются только «нули» — 1 / 0.05 = 20 бит / сек. Минимальная, когда всегда передаются «единицы»: бит / сек. Реальная скорость зависит от распределения передаваемых бит, задача была — найти эту скорость для равномерного распределения.

              Иллюстрация, как может выглядеть передача 4 бит: 0010.
                +1
                Спасибо, «теоретическая разрешающая способность системы — 0.05 сек» вот это вообще не очевидно, в задаче говорится про разрешающую способность приемника, но не передатчика. Из условия я бы предположил, что скорость передатчика фиксирована (11 слов в секунду): хочу говорю, хочу не говорю.
                  +1
                  +1
                  Из условия задачи нигде не следует, что скорость передачи «0» 0.05 сек. Сказано только, что это скорость распознавания сигнала.
                    0

                    Вполне может быть не "1" за 0.05 сек, а "0" за длительность произнесения слова. Это зависит от кодирования и непринципиально, т.к. биты по условию равновероятны. Просто так сложилось, что обычно тишину кодируют как "0".
                    В условии не сказано как передается информация, но очевидно, что оптимальным будет в случае передачи тишины не ждать дольше 0.05 сек.

                      0
                      Загвоздка не в том что принято за «0», а что за «1», а в том что длительность тишины передатчика «задана» неявно.
                      0.05 сек это характеристика приемника, откуда об этом должен знать передатчик? Это что система с обратной связью?
                      Собеседник же не кивает когда принял сообщение.
              –1

              «Выложим на следующей неделе» — говорили они…
              Чёт поздно, ребят

              Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

              Самое читаемое