Искусство мыслить рационально. Шорткаты в математике и в жизни - [103]
Теперь я снова помечаю город, в котором я нахожусь, как посещенный и переезжаю в следующий город, имеющий самую малую текущую сумму расстояний от начального пункта. В результате описанных выше операций таким пунктом оказывается город 3. В этом примере видно, что, хотя первое перемещение в город 2 казалось рациональным, дальнейший путь из него оказывается не самым коротким. Поэтому уже на этом этапе алгоритм может склоняться к прокладке маршрута через город 3.
Оказавшись в городе 3, я снова пересчитываю метки связанных с ним городов, которые я еще не посетил. Продолжая этот процесс, я в конце концов доберусь до пункта назначения, города 5, и его метка будет обозначать кратчайшее расстояние от города, с которого я начал. Затем можно воспроизвести все перемещения в обратном порядке, чтобы выяснить, через какие города проходит маршрут, соответствующий этому расстоянию. Обратите внимание, что в описанном случае он, как выясняется, вовсе не проходит через город 2.
Какова же длительность процесса выявления кратчайшего маршрута в шагах алгоритма? При наличии N городов она оказывается сравнимой с длительностью перестановки слов в алфавитном порядке. На каждом шаге из рассмотрения исключается очередной город, который не нужно учитывать в дальнейшем. Поэтому время, необходимое алгоритму для решения задачи, пропорционально N>2, то есть квадрату N. С точки зрения математики это несомненный шорткат!
Но на практике даже то, что на этом математическом языке называется шорткатом, может требовать для получения решения чрезвычайно долгого времени. В общем случае математики действительно считают алгоритмы полиномиального времени, подобные тому, который ищем мы, шорткатами. Квадратичные алгоритмы и в самом деле работают довольно быстро. Но, хотя математики называют быстрыми и алгоритмы третьей, четвертой или пятой степени, их работа может занимать долгое физическое время.
Если компьютер способен выполнять 100 миллионов операций в секунду, это не будет слишком большой проблемой при малом N. Но между временами работы алгоритма, находящего ответ за N>2 шагов, и алгоритма, находящего ответ за N>5 шагов, огромная разница.
За одну секунду алгоритм сложности N>2 может проверить сеть из 10 000 городов. Алгоритму сложности N>5 для проверки такого же числа городов потребуется 31 710 лет! И тем не менее это считается математическим шорткатом. По сравнению с экспоненциальным алгоритмом, который был у нас до сих пор, – а ему для перебора 10 000 городов требуется время, превосходящее возраст Вселенной, – это, несомненно, и есть шорткат. Более того, за время, равное возрасту Вселенной, алгоритм сложности 2>N не способен перебрать даже 100 городов.
Однако с практической точки зрения целесообразно бороться за алгоритмы с как можно более низкими степенями N. Некоторые короткие пути бывают короче других.
Иголки в стогах
Вы можете надеяться, что, раз вы не коммивояжер, отсутствие шортката к прокладке кратчайшего маршрута, позволяющего объехать всех покупателей, вас не касается. Беда в том, что задач с такими же осложнениями существует очень много. Например, инженеру может понадобиться спроектировать электронную схему из сотни элементов так, чтобы робот прокладывал соединения между ними самым рациональным образом. Поскольку этот робот будет производить тысячи таких плат в сутки, сокращение времени его путешествия по соединениям этой сети даже на несколько секунд может дать компании огромную экономию средств. Но нам хотелось бы найти шорткаты не только к маршрутам перемещения по сетям. Ниже перечислены некоторые из задач, обладающих тем же качеством, что и задача коммивояжера, – задач, к решению которых, насколько нам известно, может не существовать шорткатов. Возможно, даже великий Гаусс не избежал бы при их решении долгой и нудной работы!
Задача о багажнике. Вам нужно перевезти в багажнике автомобиля коробки разных размеров. Задача требует отобрать те коробки, при укладке которых останется меньше всего неиспользованного пространства. Как выясняется, никакого рационального алгоритма, позволяющего выбрать оптимальное сочетание коробок, исходя из их размеров, не существует. Предположим, что все коробки имеют одинаковую высоту и ширину, которые точно совпадают с внутренними размерами багажника, но разную длину. Длина багажника – 150 см, а длина имеющихся в вашем распоряжении коробок равна 16, 27, 37, 42, 52, 59, 65 и 95 см. Есть ли какой-нибудь удобный способ выбрать такое сочетание коробок, которое заполнит багажник с наименьшими потерями?
Задача о расписании уроков. В начале каждого учебного года каждая школа сталкивается с задачей составления расписания для учеников. Но у возможностей распределения занятий по расписанию есть ограничения, связанные с тем, какие предметы выбирает каждый из учеников. Поскольку Ада решила заниматься химией и музыкой, уроки по этим предметам нельзя назначать на одно и то же время. А Алан выбрал химию и киноведение. Но в день может быть всего восемь уроков. Школе нужно каким-то образом втиснуть в расписание все предметы так, чтобы ни у кого не было нескольких уроков в одно и то же время. С учетом всех этих ограничений составление расписания иногда бывает похоже на укладку ковра в комнате с не вполне подходящими размерами. Не успеешь уложить ковер в одном углу, как он вспучивается в другом. Еще это похоже на решение судоку: казалось бы, все числа наконец оказались на нужных местах, как вдруг обнаруживается, что в одной из строк стоят две двойки. Черт!
Знаменитый оксфордский профессор и популяризатор науки Маркус дю Сотой исследует природу творчества, освещая наиболее важные аспекты работы алгоритмов и математических правил, которые лежат в их основе. Он задается вопросом, насколько наш эмоциональный отклик на произведения искусства обусловлен реакцией мозга на закономерности и структуры и что именно означает заниматься творчеством в математике, изобразительном искусстве, литературе и музыке. На основе ярких примеров того, как «поверяется алгеброй гармония» мировых шедевров, среди которых «Евгений Онегин» Пушкина, «Песнь льда и пламени» Джорджа Р.
«Хотя эта книга посвящена тому, чего мы знать не можем, также очень важно понять, что мы знаем. В этом путешествии к пределам знаний мы пройдем через области, уже нанесенные учеными на карты, до самых пределов последних на сегодняшний день достижений науки. В пути мы будем задерживаться, чтобы рассмотреть те моменты, когда ученые считали, что зашли в тупик и дальнейшее продвижение вперед невозможно, но следующее поколение исследователей находило иные пути. Это позволит нам по-новому взглянуть на то, что мы сегодня можем считать непознаваемым.
«Умение математиков заглядывать в будущее наделило тех, кто понимает язык чисел, огромным могуществом. От астрономов древних времен, способных предсказать движения планет в ночном небе, до сегодняшних управляющих хедж-фондами, прогнозирующих изменения цен на фондовом рынке, – все они использовали математику, чтобы постичь будущее. Сила математики в том, что она может гарантировать стопроцентную уверенность в свойствах мира». Маркус дю Сотой Профессор математики Оксфордского университета, заведующий кафедрой Симони, сменивший на этой должности Ричарда Докинза, Маркус дю Сотой приглашает вас в незабываемое путешествие по необычным и удивительным областям науки, лежащей в основе каждого аспекта нашей жизни. В формате pdf A4 сохранен издательский дизайн.
Монография посвящена проблеме самоидентификации русской интеллигенции, рассмотренной в историко-философском и историко-культурном срезах. Логически текст состоит из двух частей. В первой рассмотрено становление интеллигенции, начиная с XVIII века и по сегодняшний день, дана проблематизация важнейших тем и идей; вторая раскрывает своеобразную интеллектуальную, духовную, жизненную оппозицию Ф. М. Достоевского и Л. Н. Толстого по отношению к истории, статусу и судьбе русской интеллигенции. Оба писателя, будучи людьми диаметрально противоположных мировоззренческих взглядов, оказались “versus” интеллигентских приемов мышления, идеологии, базовых ценностей и моделей поведения.
Монография протоиерея Георгия Митрофанова, известного историка, доктора богословия, кандидата философских наук, заведующего кафедрой церковной истории Санкт-Петербургской духовной академии, написана на основе кандидатской диссертации автора «Творчество Е. Н. Трубецкого как опыт философского обоснования религиозного мировоззрения» (2008) и посвящена творчеству в области религиозной философии выдающегося отечественного мыслителя князя Евгения Николаевича Трубецкого (1863-1920). В монографии показано, что Е.
Эксперты пророчат, что следующие 50 лет будут определяться взаимоотношениями людей и технологий. Грядущие изобретения, несомненно, изменят нашу жизнь, вопрос состоит в том, до какой степени? Чего мы ждем от новых технологий и что хотим получить с их помощью? Как они изменят сферу медиа, экономику, здравоохранение, образование и нашу повседневную жизнь в целом? Ричард Уотсон призывает задуматься о современном обществе и представить, какой мир мы хотим создать в будущем. Он доступно и интересно исследует возможное влияние технологий на все сферы нашей жизни.
Настоящая книга представляет собой интереснейший обзор развития инженерного искусства в истории западной цивилизации от истоков до двадцатого века. Авторы делают акцент на достижения, которые, по их мнению, являются наиболее важными и оказали наибольшее влияние на развитие человеческой цивилизации, приводя великолепные примеры шедевров творческой инженерной мысли. Это висячие сады Вавилона; строительство египетских пирамид и храмов; хитроумные механизмы Архимеда; сложнейшие конструкции трубопроводов и мостов; тоннелей, проложенных в горах и прорытых под водой; каналов; пароходов; локомотивов – словом, все то, что требует обширных технических знаний, опыта и смелости.
Что такое, в сущности, лес, откуда у людей с ним такая тесная связь? Для человека это не просто источник сырья или зеленый фитнес-центр – лес может стать местом духовных исканий, служить исцелению и просвещению. Биолог, эколог и журналист Адриане Лохнер рассматривает лес с культурно-исторической и с научной точек зрения. Вы узнаете, как устроена лесная экосистема, познакомитесь с различными типами леса, характеризующимися по составу видов деревьев и по условиям окружающей среды, а также с видами лесопользования и с некоторыми аспектами охраны лесов. «Когда видишь зеленые вершины холмов, которые волнами катятся до горизонта, вдруг охватывает оптимизм.
Что значат для демократии добровольные общественные объединения? Этот вопрос стал предметом оживленных дискуссий после краха государственного социализма и постепенного отказа от западной модели государства всеобщего благосостояния, – дискуссий, сфокусированных вокруг понятия «гражданское общество». Ответ может дать обращение к прошлому, а именно – к «золотому веку» общественных объединений между Просвещением и Первой мировой войной. Политические теоретики от Алексиса де Токвиля до Макса Вебера, равно как и не столь известные практики от Бостона до Санкт-Петербурга, полагали, что общество без добровольных объединений неминуемо скатится к деспотизму.
Канадский ученый, эколог и политолог Вацлав Смил знаменит своими работами о связи энергетики с экологией, демографией и реальной политикой, а также виртуозным умением обращаться с большими массивами статистических данных. Эта книга, которая так восхитила Билла Гейтса, обобщает самые интересные материалы, которые Смил пишет для журнала IEEE Spectrum – одного из ведущих научно-инженерных изданий мира, и представляет собой актуальное руководство для понимания истинного положения дел на нашей планете.
Наша сегодняшняя жизнь перенасыщена информацией, однако большинство людей все же не знают, как на самом деле устроен наш мир. Эта книга освещает основные темы, связанные с обеспечением нашего выживания и благополучия: энергия, производство продуктов питания, важнейшие долговечные материалы, глобализация, оценка рисков, окружающая среда и будущее человека. Поиск эффективного решения проблем требует изучения фактов — мы узнаем, например, что глобализация не была неизбежной и что наше общество все сильнее зависит от ископаемого топлива, поэтому любые обещания декарбонизации к 2050 году — не более чем сказка.
Сочинение итальянского дипломата, писателя и поэта Бальдассаре Кастильоне (1478–1529) «Придворный», соединяющее воспоминания о придворной жизни герцогства Урбино в начале XVI века с размышлениями о морали, предназначении, стиле поведения дворянина, приближенного к государю, – одна из тех книг эпохи Возрождения, что не теряли популярности на протяжении последующих веков и восхищали блестящие умы своего и будущих столетий. Для истории культуры труд Кастильоне явился подлинной сокровищницей, и сложно представить, насколько более скудными оказались бы знания потомков об эпохе Возрождения, не будь он создан. Составленное в виде сборника занимательных и остроумных бесед, это ярко и непринужденно написанное произведение выходит за рамки источника сведений о придворных развлечениях своего времени и перечня достоинств совершенного придворного как всесторонне образованного и утонченно воспитанного человека, идеального с точки зрения гуманистических представлений.
«Эта книга посвящена захватывающей и важной для любого человека теме – осознанию себя как части общества и рассмотрению самого феномена общества под лупой эволюционных процессов в животном мире. Марк Моффетт сравнивает человеческое общество с социальными образованиями общественных насекомых, и эти сравнения вполне уместны. И его последующий интерес к устройству социальных систем у широкого круга позвоночных, от рыб до человекообразных обезьян, не случаен. Как эволюциониста, его интересы связаны с выявлением причин и факторов, влияющих на трансформации социального поведения у разных таксонов, роли экологии в усложнении общественных связей, с поиском связей между морфологическими и психологическими преобразованиями, в конечном итоге приведших к возникновению нашего вида.