02.05.2017 09:42
artemshitov 15 8700 Источник
Очередные 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 на решение этих задачек. А таких было много, что не может не радовать!
Поделиться с друзьями
-->

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


  1. shpaker
    02.05.2017 13:36
    #10199812

    А в чём сакральный смысл выкладывания текста картинками?


    1. Ole
      02.05.2017 13:54
      #10199860

      Чтобы не спёрли? )


      1. poxvuibr
        02.05.2017 13:56
        #10199868
        +2

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


    1. artemshitov
      02.05.2017 14:01
      #10199886

      Стилизация: чтобы ламповая форма соответствовала содержанию. Как в еде — важен не только вкус, но и запах, и форма подачи, или в картинах, где иногда впечатление составляет не только одна картина, но и ее рама или сопроводительный материал (как, например, манифест супрематизма Малевича, относящийся к его Черному квадрату).


      1. GlukKazan
        02.05.2017 14:59
        #10200062
        +1

        Ламповая стилизация — это хорошо, но текст про Клавдию глазам читать больно.
        Почему-то он размытый.


        1. artemshitov
          02.05.2017 15:28
          #10200124
          +6

          GlukKazan, посмотрите, пожалуйста, похорошела ли теперь Клавдия? Привел картинку в соответствие с остальными по разрешению.


          1. GlukKazan
            02.05.2017 16:02
            #10200198

            Да, значительно похорошела.


    1. TheEin
      02.05.2017 20:15
      #10200556
      +1

      Буклетики именно так и выглядели. Няшный шрифт :-P


  1. novoselov
    02.05.2017 21:14
    #10200626
    +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. artemshitov
      02.05.2017 23:22
      #10200676
      +1

      1. Если представить что всегда говорит только Балмер, а Греф понимает все сразу (едва Балмер откроет рот), то максимально достижимая скорость 11 бит/сек

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

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

      Иллюстрация, как может выглядеть передача 4 бит: 0010.


      1. novoselov
        03.05.2017 00:39
        #10200730
        +1

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


        1. efremov
          03.05.2017 08:40
          #10200896
          +1

          +1
          Из условия задачи нигде не следует, что скорость передачи «0» 0.05 сек. Сказано только, что это скорость распознавания сигнала.


          1. madkite
            03.05.2017 19:01
            #10201999

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


            1. novoselov
              03.05.2017 21:06
              #10202153

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


  1. fRoStBiT
    04.05.2017 18:29
    #10203694
    -1

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