Искусство мыслить рационально. Шорткаты в математике и в жизни - [105]
Получается еще одна задача, в которой необходимо учитывать множество разных комбинаций матчей и их результатов. Приписывая командам победы, поражения и ничьи, я снова и снова бываю вынужден возвращаться назад, как в судоку, потому что оказывается, что один из результатов, которые я приписал раньше, разрушает все с таким трудом выстроенное равновесие.
Если всего в турнире осталось сыграть N матчей, каждый из них может закончиться для принимающей стороны победой, поражением или ничьей. Следовательно, нужно учесть в общей сложности 3>N разных исходов: их число растет экспоненциально. А хотелось бы найти шорткат, который поможет мне быстро понять, может ли еще моя команда, чисто математически, надеяться на победу в турнире.
Но эта задача так нравится мне потому, что, когда я был школьником, такой алгоритм существовал. Что же случилось с тех пор? Нет, дело не в том, что мы утратили этот алгоритм, а в том, что изменились правила начисления очков. Раньше команды получали за победу всего лишь по два очка, а в случае ничьей – по одному каждая. Потом решили, что это побуждает футболистов сводить матчи к скучным ничьим. Поэтому в 1981 году было принято решение усилить привлекательность побед для команд. Вместо двух очков победившая в матче команда стала получать три. Это, казалось бы, безобидное новшество резко изменило ситуацию с точки зрения задачи о возможности выхода той или иной команды на верхнюю строчку турнирной таблицы Премьер-лиги.
Важнее всего то обстоятельство, что до 1981 года суммарное число очков, распределяющееся между командами, не зависело от того, кто выигрывает, проигрывает или заканчивает матч вничью. В турнире участвуют 20 команд; каждая из них встречается со всеми остальными по два раза, на своем поле и на выезде, то есть всего получается 20 × 19 матчей. В старой системе в каждом матче разыгрывались два очка, которые распределялись в зависимости от его исхода. Стало быть, суммарное число очков, распределенных между 20 командами к концу сезона, было равно 2 × 20 × 19 = 760.
Но теперь все совсем иначе. В каждом матче могут быть присуждены либо три очка – их получает победитель, – либо два, которые делят между собой команды, сыгравшие вничью. Если все матчи сезона будут сыграны вничью, сумма очков по-прежнему будет равна 760. Но, если не будет ни одной ничьей, сумма составит 3 × 20 × 19 = 1140 очков. Появление этих вариаций суммарного количества очков привело к тому, что действовавший до этого алгоритм, который позволял мне понять, остаются ли у моей команды математические шансы на победу в лиге, перестал работать.
Все эти задачи замечательны тем, что, если удается найти какое-нибудь решение, можно быстро проверить, действительно ли оно подходит к задаче. Я называю их «задачами об иголке в стоге сена»: сначала нужно проделать долгую, изнурительную работу, чтобы понять, где именно находится иголка, но как только вы ее нащупаете, не останется никаких сомнений, что вы ее нашли! Взломщик может долго возиться с сейфом, пробуя одну комбинацию за другой, но, как только комбинация окажется правильной, дверь тут же откроется.
У задач об иголке в стоге сена, или, если использовать их официальное название, NP-полных задач, есть одно довольно необычное свойство. Может показаться, что каждая из них требует своей, индивидуальной стратегии поисков алгоритма, который позволит решать ее за кратчайшее возможное время. Однако, если будет открыт алгоритм полиномиального времени, находящий кратчайший маршрут по любой карте, с которой может столкнуться пресловутый коммивояжер, это будет означать, что такие алгоритмы гарантированно существуют и для всех остальных таких задач. Хотя бы это дает шорткат к решению задачи поиска шорткатов. Если обнаружится, что существует шорткат к решению какой-нибудь из задач нашего списка, его можно будет преобразовать в шорткат к решению любой другой. Толкин сказал бы, что это один шорткат, чтоб все решить.
Я могу дать вам подсказку, которая показывает, почему это так: посмотрите, как некоторые из задач, которые я описал, можно преобразовывать друг в друга. Возьмем, например, задачу о расписании уроков. Там есть уроки, временные отрезки и накладки, которых необходимо избегать. Используя эту информацию, можно построить сеть, в которой каждый урок будет обозначен точкой, а накладки – линиями, каждая из которых соединяет два урока, между которыми возникает противоречие. Тогда распределение уроков по временным отрезкам превратится в задачу, точно совпадающую с задачей о раскрашивании точек графа таким образом, чтобы никакая линия не соединяла две точки одного и того же цвета.
Использование отсутствия шорткатов
Бывают такие ситуации, в которых важно, чтобы никаких шорткатов не было. Например, разработка нераскрываемых шифров. Разработчикам шифров выгодно такое положение вещей, когда взломать зашифрованное сообщение бывает, по-видимому, невозможно без полного перебора всех возможных вариантов. Взять, к примеру, кодовый замок. Если у него есть четыре колесика, на каждом из которых по десять цифр, то, чтобы его открыть, нужно перебрать 10 000 разных чисел, от 0000 до 9999. Некачественно изготовленные замки иногда выдают то положение, в котором замок открывается, потому что при установке правильной цифры в механизме замка происходит физический сдвиг, но в общем случае у взломщика нет никакого шортката, кроме перебора всех комбинаций.
Знаменитый оксфордский профессор и популяризатор науки Маркус дю Сотой исследует природу творчества, освещая наиболее важные аспекты работы алгоритмов и математических правил, которые лежат в их основе. Он задается вопросом, насколько наш эмоциональный отклик на произведения искусства обусловлен реакцией мозга на закономерности и структуры и что именно означает заниматься творчеством в математике, изобразительном искусстве, литературе и музыке. На основе ярких примеров того, как «поверяется алгеброй гармония» мировых шедевров, среди которых «Евгений Онегин» Пушкина, «Песнь льда и пламени» Джорджа Р.
«Хотя эта книга посвящена тому, чего мы знать не можем, также очень важно понять, что мы знаем. В этом путешествии к пределам знаний мы пройдем через области, уже нанесенные учеными на карты, до самых пределов последних на сегодняшний день достижений науки. В пути мы будем задерживаться, чтобы рассмотреть те моменты, когда ученые считали, что зашли в тупик и дальнейшее продвижение вперед невозможно, но следующее поколение исследователей находило иные пути. Это позволит нам по-новому взглянуть на то, что мы сегодня можем считать непознаваемым.
«Умение математиков заглядывать в будущее наделило тех, кто понимает язык чисел, огромным могуществом. От астрономов древних времен, способных предсказать движения планет в ночном небе, до сегодняшних управляющих хедж-фондами, прогнозирующих изменения цен на фондовом рынке, – все они использовали математику, чтобы постичь будущее. Сила математики в том, что она может гарантировать стопроцентную уверенность в свойствах мира». Маркус дю Сотой Профессор математики Оксфордского университета, заведующий кафедрой Симони, сменивший на этой должности Ричарда Докинза, Маркус дю Сотой приглашает вас в незабываемое путешествие по необычным и удивительным областям науки, лежащей в основе каждого аспекта нашей жизни. В формате pdf A4 сохранен издательский дизайн.
Работа представляет комплексный анализ антропологических и этических учений с древнейших времен до современности в их взаимозависимости и взаимовлиянии. Адресуется студентам и аспирантам гуманитарных вузов, а также широкому кругу читателей.
Штрихи к портретам известных отечественных и зарубежных деятелей науки: академиков – Г. Марчука, Л. Окуня, Ж. Алферова, А.Сахарова, С.Вавилова, Ф.Мартенса, О.Шмидта, А. Лейпунского, Л.Канторовича, В.Кирюхина, А.Мигдала, С.Кишкина, А. Берга, философов – Н.Федорова, А. Богданова (Малиновского), Ф.Энгельса, А. Пятигорского, М.Хайдеггера, М. Мамардашвили, В.Катагощина, выдающихся ученых и конструкторов – П.Чебышёва, К. Циолковского, С.Мальцова, М. Бронштейна, Н.Бора, Д.Иваненко, А.Хинчина, Г.Вульфа, А.Чижевского, С. Лавочкина, Г.Гамова, Б.
После Альбигойского крестового похода — серии военных кампаний по искоренению катарской ереси на юге Франции в 1209–1229 годах — католическая церковь учредила священные трибуналы, поручив им тайный розыск еретиков, которым все-таки удалось уберечься от ее карающей десницы. Так во Франции началось становление инквизиции, которая впоследствии распространилась по всему католическому миру. Наталия Московских рассказывает, как была устроена французская инквизиция, в чем были ее особенности, как она взаимодействовала с папским престолом и королевской властью.
В книге собраны воспоминания участников Отечественной войны 1812 года и заграничного похода российской армии, окончившегося торжественным вступлением в Париж в 1814 году. Эти свидетельства, принадлежащие самым разным людям — офицерам и солдатам, священнослужителям и дворянам, купцам и городским обывателям, иностранцам на русской службе, прислуге и крепостным крестьянам, — либо никогда прежде не публиковались, либо, помещенные в периодической печати, оказались вне поля зрения историков. Лишь теперь, спустя двести лет после Отечественной войны 1812 года, они занимают свое место в истории победы русского народа над наполеоновским нашествием.
Автор книги рассказывает о появлении первых календарей и о том, как они изменялись, пока не превратились в тот, по которому мы сейчас живем. Вы узнаете много интересного и познавательного о метрических системах, денежных единицах и увлекательных парадоксах физики, химии и математики. Занимательные исторические примеры, иллюстрируя сухие факты, превращаются в яркие рассказы, благодаря живому и образному языку автора.
Одна из первых монографий Александра Койре «Этюды о Галилее» представляет собой три, по словам самого автора, независимых друг от друга работы, которые тем не менее складываются в единое целое. В их центре – проблема рождения классической науки, становление идей Нового времени, сменивших антично-средневековые представления об устройстве мира и закономерностях физических явлений. Койре, видевший научную, философскую и религиозную мысли в тесной взаимосвязи друг с другом, обращается здесь к сюжетам и персонажам, которые будут находиться в поле внимания философа на протяжении значительной части его творческого пути.
Канадский ученый, эколог и политолог Вацлав Смил знаменит своими работами о связи энергетики с экологией, демографией и реальной политикой, а также виртуозным умением обращаться с большими массивами статистических данных. Эта книга, которая так восхитила Билла Гейтса, обобщает самые интересные материалы, которые Смил пишет для журнала IEEE Spectrum – одного из ведущих научно-инженерных изданий мира, и представляет собой актуальное руководство для понимания истинного положения дел на нашей планете.
Сочинение итальянского дипломата, писателя и поэта Бальдассаре Кастильоне (1478–1529) «Придворный», соединяющее воспоминания о придворной жизни герцогства Урбино в начале XVI века с размышлениями о морали, предназначении, стиле поведения дворянина, приближенного к государю, – одна из тех книг эпохи Возрождения, что не теряли популярности на протяжении последующих веков и восхищали блестящие умы своего и будущих столетий. Для истории культуры труд Кастильоне явился подлинной сокровищницей, и сложно представить, насколько более скудными оказались бы знания потомков об эпохе Возрождения, не будь он создан. Составленное в виде сборника занимательных и остроумных бесед, это ярко и непринужденно написанное произведение выходит за рамки источника сведений о придворных развлечениях своего времени и перечня достоинств совершенного придворного как всесторонне образованного и утонченно воспитанного человека, идеального с точки зрения гуманистических представлений.
Наша сегодняшняя жизнь перенасыщена информацией, однако большинство людей все же не знают, как на самом деле устроен наш мир. Эта книга освещает основные темы, связанные с обеспечением нашего выживания и благополучия: энергия, производство продуктов питания, важнейшие долговечные материалы, глобализация, оценка рисков, окружающая среда и будущее человека. Поиск эффективного решения проблем требует изучения фактов — мы узнаем, например, что глобализация не была неизбежной и что наше общество все сильнее зависит от ископаемого топлива, поэтому любые обещания декарбонизации к 2050 году — не более чем сказка.
«Эта книга посвящена захватывающей и важной для любого человека теме – осознанию себя как части общества и рассмотрению самого феномена общества под лупой эволюционных процессов в животном мире. Марк Моффетт сравнивает человеческое общество с социальными образованиями общественных насекомых, и эти сравнения вполне уместны. И его последующий интерес к устройству социальных систем у широкого круга позвоночных, от рыб до человекообразных обезьян, не случаен. Как эволюциониста, его интересы связаны с выявлением причин и факторов, влияющих на трансформации социального поведения у разных таксонов, роли экологии в усложнении общественных связей, с поиском связей между морфологическими и психологическими преобразованиями, в конечном итоге приведших к возникновению нашего вида.