Ознакомительная версия. Доступно 19 страниц из 91
И все же жить по заветам компьютерной науки не так уж и плохо. Ведь, в отличие от большинства советов, ее мудрость имеет обоснования.
Разработка алгоритмов для компьютеров изначально была предметом исследования на стыке двух дисциплин – математики и инженерии. Составление алгоритмов для людей тоже не лежит в плоскости какой-либо одной науки. Сегодня разработка алгоритмов опирается не только на достижения информатики, математики и инженерии, но и на такие смежные научные области, как статистика и операционные исследования.
Проводя параллель между алгоритмами для техники и алгоритмами для людей, нам также следует обратиться к научным ресурсам когнитивистики, математики, экономики и других наук. Авторы этой книги хорошо знакомы с междисциплинарными исследованиями в этих отраслях. Прежде чем защитить дипломную работу в области исследования английского языка, Брайан изучал компьютерные технологии и философию, а карьеру построил на стыке всех трех специальностей. Том посвятил годы изучению психологии и статистики, прежде чем стал профессором Калифорнийского университета в Беркли, где теперь уделяет почти все свое время исследованию взаимосвязей между мыслительной деятельностью человека и вычислительными операциями.
Однако никто не может быть экспертом сразу во всех научных отраслях, задействованных в разработке алгоритмов для людей. Поэтому в поисках алгоритмов для жизни мы беседовали с людьми, которые придумали самые известные алгоритмы за последние 50 лет. И мы спрашивали, как их исследование повлияло на их же подход к решению жизненных задач – от поиска второй половины до сортировки носков после стирки.
На следующих страницах начинается наше увлекательное путешествие сквозь самые сложные задачи и вызовы, брошенные компьютерам и человеческому разуму: как существовать в условиях конечного пространственного и временнóго промежутка, ограниченного внимания, неустановленных параметров, неполной информации и непредсказуемого будущего; как жить уверенно и с достоинством; и, наконец, как делать это в рамках социума, где другие стремятся к тем же целям одновременно с нами.
Мы исследуем фундаментальную математическую основу таких задач и изучим устройство компьютерного интеллекта (который в ряде случаев работает совсем не так, как мы представляем), чтобы извлечь максимум пользы для своей жизни. Мы узнаем, как работает человеческий разум, рассмотрим его различные, но тесно взаимосвязанные методы решения одного и того же набора вопросов в условиях наличия тех же ограничений. В конечном итоге то, что мы можем приобрести в рамках нашего путешествия, – это не просто набор конкретных уроков для нашей повседневной жизни, не новый способ увидеть утонченные схемы за самыми сложными дилеммами человечества и не только признание глубинной взаимосвязи компьютеров с тяжелым человеческим трудом. Это кое-что более основательное, а именно новый словарь для изучения мира вокруг нас и шанс узнать что-то поистине новое о нас самих.
1. Задача об оптимальной остановке
Когда пора остановить поискиХотя все христиане пишут в свадебных приглашениях, что брак их совершился по воле Божьей, я, будучи философом, готов поспорить с этим утверждением…
Иоганн КеплерЕжели мистер Мартин любезнее вам всякого другого мужчины, ежели никогда и ни с кем не было вам так приятно, как в его обществе, тогда зачем колебаться?
Джейн Остин. Эмма[1]Каждый год влюбленные парочки студентов-первокурсников возвращаются после совместных каникул по случаю Дня благодарения, разругавшись в пух и прах. Это так часто происходит, что у психологов колледжей есть даже специальное словечко: turkey drop.
Однажды к психологу на прием пришел Брайан, крайне возбужденный первокурсник. Его школьная подружка уехала учиться в другой колледж, и теперь у них был классический роман на расстоянии. Кроме того, их мучил непростой философский вопрос: а хорошие ли у них отношения? Сравнивать им было не с чем. Психолог посочувствовала Брайану, сказала, что это типичная дилемма первокурсников, и невозмутимым тоном предложила удивительное: «Собирай данные».
Сторонники серийной моногамии, как правило, сталкиваются с фундаментальной неизбежной проблемой. Когда можно считать, что вы познакомились с достаточным количеством людей, чтобы найти свою половинку? А что, если вы уже пропустили ее? Настоящая «уловка-22» в любовных делах!
Ответ на крик души этого влюбленного первокурсника содержится в теории, которую математики называют «задачей об оптимальной остановке». И звучит он так: 37 %.
Ну или как-то иначе. Все зависит от ваших взглядов на любовь.
Задача о секретаре
В любой задаче об оптимальной остановке критически важный вопрос – не «какой вариант необходимо выбрать», а «как много вариантов необходимо рассмотреть и учесть». Эти задачи имеют значение не только для влюбленных или арендаторов, но и для водителей, домовладельцев, грабителей и т. д.
Правило 37 %[2] произошло от самой известной головоломки об оптимальной остановке, которая со временем стала известна как «задача о секретаре». Исходные данные задачи очень напоминают дилемму о поиске квартиры, которую мы рассматривали ранее. Представьте, что вы проводите собеседование с рядом кандидатов на позицию секретаря и ваша цель – выбрать и принять на работу единственного кандидата, лучшего из всех. Пока у вас нет представления, как распределить баллы между каждым из претендентов, вы можете легко определить, кому вы отдаете предпочтение. (В этом случае математик сказал бы, что вы оперируете только порядковыми числами – вы сравниваете только соответствующие качества, которыми обладают все кандидаты. Но вам недоступны количественные числа – вы не можете ранжировать эти качества в общей шкале.) Вы интервьюируете претендентов в произвольном порядке, по одному за раз. Вы можете принять решение нанять кандидата в любой момент собеседования, а он, в свою очередь, примет ваше предложение и завершит свои поиски работы. Но при этом, если вы упустите кандидата, решив не нанимать его, вы потеряете его навсегда.
Считается, что задача о секретаре впервые была опубликована (без непосредственного упоминания секретарей) в февральском номере журнала Scientific American в 1960 году Мартином Гарднером в качестве одной из головоломок в его популярной колонке о занимательной математике. Однако само происхождение задачи остается загадкой. Наше собственное расследование с нуля привело нас к некоторой гипотезе еще до того, как оно неожиданно превратилось для нас в детективную работу в прямом смысле слова. Мы отправились в Стэнфорд, чтобы в архивах работ Гарднера найти его переписку середины прошлого века. Чтение писем немного напоминает подслушивание чужого телефонного разговора: вы слышите только одну сторону диалога, а ответ можете лишь предположить. В нашем случае у нас были только ответы на вопросы, которыми, очевидно, задавался сам Гарднер более 50 лет назад, исследуя историю происхождения задач. Чем больше мы читали, тем более запутанной и неясной казалась нам эта история. Гарвардский математик Фредерик Мостеллер вспомнил, что слышал об этой задаче в 1955 году от своего коллеги Эндрю Глизона, который, в свою очередь, слышал о ней от кого-то еще. Лео Мозер из Альбертского университета рассказывал в своем письме, что читал о головоломке в «неких записях» Р. И. Гаскелла из компании Boeing, который приписывал авторство задачи своему коллеге. Роджер Пинкхам из Ратгерского университета писал, что впервые услышал о головоломке в 1955 году от математика по фамилии Шонфильд из Университета Дьюка, а тот, по его убеждению, сам впервые услышал о задаче от кого-то из Мичигана. Этот «кто-то из Мичигана», с большой вероятностью, носил имя Меррил Флад. И хотя за пределами мира математики его имя мало кому известно, влияние Флада на развитие компьютерной науки нельзя не отметить. Именно он обратил внимание на задачу о коммивояжере (которую мы обсудим более подробно в главе 8), изобрел математическую игру «Два бандита» (которая будет описана в главе 11) и даже, весьма вероятно, ввел термин «программное обеспечение». По его же собственным словам, Флад приступил к изучению вопроса в 1949-м и в 1958 году стал автором своего первого известного открытия – правила 37 %. Хотя он и отдает пальму первенства в этом вопросе другим математикам.
Ознакомительная версия. Доступно 19 страниц из 91
