Алгоритмы для жизни: Простые способы принимать верные решения [заметки]

1

В переводе М. Канна. – Прим. ред.

2

Жирным шрифтом выделены названия алгоритмов, которые будут описаны в книге.

3

В рамках этой стратегии существует 33 %-ная вероятность того, что мы откажем лучшему кандидату, и 16 %-ная вероятность – что мы никогда не встретим лучшего кандидата. Конкретно, есть шесть точных возможных последовательностей для трех кандидатов: 1–2–3, 1–3–2, 2–1–3, 2–3–1, 3–1–2, и 3–2–1. Если мы начнем отбор со второго претендента, то успех вероятен только в трех комбинациях из шести (2–1–3, 2–3–1, 3–1–2), соответственно в трех остальных случаях нас постигнет неудача – дважды из-за нашей излишней взыскательности (1–2–3, 1–3–2) и один раз по причине неразборчивости (3–2–1).

4

Необязательно строго 37 %. Точнее, математически оптимальная доля кандидатов, которых необходимо отсмотреть, рассчитывается по формуле 1/е (е – та же математическая константа, 2,71828…, которая появляется при расчете сложных процентов). Однако вам нет необходимости знать наизусть все 12 десятичных знаков числа е. На самом деле любое значение от 35 до 40 % максимально приближает вас к успеху.

5

Более подробно вычислительные риски теории игр рассматриваются в главе 11.

6

Краткое содержание данного фрагмента: делай ноги, пока Гиттинс хорош.

7

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

8

На самом деле процесс пузырьковой сортировки занимает ничуть не меньше времени, поскольку в среднем книги будут находиться на n/2 позиций на полке дальше от тех, где должны оказаться в итоге. Программист все равно округлит n/2 осмотра n-ного количества книг на полке до O(n2).

9

Иногда, например в боксе, применяется другой подход. Чтобы боксеру не приходилось снова выходить на ринг после недавнего нокаута (что небезопасно с медицинской точки зрения), на соревнованиях вручаются сразу две бронзовые медали.

10

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

11

Однако по неизвестным причинам фильм «Мой личный штат Айдахо» является фаворитом в штате Мэн.

12

Вы можете заставить свой компьютер показывать электронные документы такой же «стопкой». По умолчанию, система просмотра файлов выводит папки и файлы в алфавитном порядке, но принцип замещения по давности использования советует вам отказаться от этого и просматривать файлы по критерию «последний открытый», а не по имени файла. Тогда то, что вы ищете, будет почти всегда наверху списка.

13

Аллен Д. Как привести дела в порядок. Искусство продуктивности без стресса. – М.: Манн, Иванов и Фербер, 2014.

14

15

Фьоре Н. Легкий способ перестать откладывать дела на потом. – М.: Манн, Иванов и Фербер, 2013.

16

Партной Ф. Подожди! Как отложить решение до последнего момента и… победить. – М.: АСТ: Neoclassic, 2015.

17

Что примечательно, руководитель группы по управлению программным обеспечением «Марсопроходца» считал, что проблема заключается в «давлении дедлайнов» и в том, что во время разработки программного обеспечения устранение именно этой проблемы сочли низкоприоритетной задачей. Таким образом, коренная причина, по сути, стала отражением самой задачи.

18

Такой отпуск предоставляется на год преподавателям ряда университетов и колледжей в США с сохранением заработной платы.

19

Более подробно мы рассмотрим труднорешаемые задачи в главе 8.

20

На самом деле все не так плохо, как может показаться при беглом взгляде на статистику, поскольку некоторые задачи предполагают разработку расписания работы для множества устройств, а это больше напоминает управление группой подчиненных, а не просто вашим календарем.

21

Перевод М. Лозинского.

22

Здесь есть определенная ирония: когда речь идет о времени, даже осознание того, что наше появление ничего особенно не меняет, не мешает нам представлять себя в самом центре явления.

23

Это и есть самое простое проявление закона Лапласа: он предполагает, что наличие 1 или 10 % выигрышных билетов так же вероятно, как и наличие 50 или 100 %. Формула

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

шанса на то, что следующий ваш билет выиграет. Но этот результат как нельзя лучше отражает ваши шансы в лотерее, в которую вы играете, не обладая вообще никакой информацией.

24

LASSO – least absolute shrinkable and selection operator.

25

Для тех, кто обладает уверенными знаниями в математике: это сумма абсолютных значений (модулей) коэффициентов переменных.

26

Авторы вышедших в издательстве «Манн, Иванов и Фербер» книг «Rework» и «Remote».

27

Может показаться странным при условии, что O(n2) казалось таким ужасающим в контексте сортировки, называть эту формулу эффективной в данном случае. Но правда в том, что даже экспоненциальное время с маленьким числом основания, как, например, O(2n), стремительно становится катастрофически огромным при сравнении с полиномиальным временем с большим основанием, как, например, n10. Экспоненциал всегда будет превосходить полиномиал в некоторых задачах. В этом случае, если вы сортируете более нескольких десятков элементов, n10 выглядит как прогулка в парке по сравнению с 2n. После работы Кобхэма и Эдмондса эта пропасть между полиномиалами и экспоненциалами всегда служила маркером выхода за рамки области.

28

Американский игрок в гольф, предпочитавший смешивать чай со льдом и лимонад. В 1960 году он заказал такой напиток в баре, сидевшая рядом женщина тоже попросила «напиток Палмера», так название и закрепилось. – Прим. ред.

29

Интересно отметить, что некоторые из этих экспериментов дали гораздо более точный расчет величины числа π, чем можно было бы ожидать от случайного стечения обстоятельств. И это наводит на мысль, что они либо преднамеренно выбрали хорошую точку остановки, либо подделали все результаты. Например, в 1901 году итальянский математик Марио Лаццарини предположительно произвел 3408 бросков и получил π≈3,1415929 (фактическое отношение числа π к семи знакам после запятой – 3,1415927). Но, если бы количество раз, когда иголка пересекла линию, было бы достигнуто одним броском, получившееся значение было бы не столь симпатичным (3,1398 или 3,1433), что делает результаты Лаццарини подозрительными. Лаплас счел бы уместным использование правила Байеса, чтобы подтвердить, что данные результаты вряд ли были получены в ходе реального эксперимента.

30

Нет смысла проверять простые числа, которые больше квадратного корня исходного числа, потому что если множитель числа больше его квадратного корня, то по определению у него также должен быть соответствующий множитель меньше его квадратного корня (то есть вы бы его уже вычислили). Если вы ищете множители числа 100, например, то любой множитель больше 10 будет спарен с множителем меньше 10: 20 соотносится с 5, 25 с 4 и т. д.

31

Числа-близнецы – пара простых чисел, отличающихся на 2, например 5 и 7.

32

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

33

Американская компания, поставщик фильмов и сериалов на основе потокового мультимедиа. – Прим. ред.

34

На самом деле это краеугольный камень всех современных компьютеров; это была задача об остановке, которая вдохновила Тьюринга формально установить границы вычислений с помощью того, что мы теперь называем машиной Тьюринга.

35

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

36

В своей книге «Things a Computer Scientist Rarely Talks About» «отец информатики» Дональд Кнут рассказывает, как его понимание Бога соотносится с его работой в области компьютерных наук. – Прим. ред.