Золотой билет - [3]
Задача о разбиении
Взгляните на эти тридцать восемь чисел:
14175, 15055, 16616, 17495, 18072, 19390, 19731, 22161, 23320, 23717, 26343, 28725, 29127, 32257, 40020, 41867, 43155, 46298, 56734, 57176, 58306, 61848, 65825, 66042, 68634, 69189, 72936, 74287, 74537, 81942, 82027, 82623, 82802, 82988, 90467, 97042, 97507, 99564.
В сумме все они дают ровно 2000000. Попробуйте разбить их на две группы по девятнадцать чисел так, чтобы сумма чисел внутри каждой группы была равна 1000000. Можете свободно пользоваться калькулятором, Excel или даже написать программу. Ответ приводится в конце главы.
Не так-то просто, верно? Ведь для разбиения существует более семнадцати миллиардов вариантов! Современные компьютеры считают очень быстро, и с хорошей программой у вас есть все шансы получить ответ. Ну а что если я предложу вам не тридцать восемь чисел, а три тысячи восемьсот? Или, что еще лучше, тридцать восемь миллионов? Тут уже никакая программа не справится.
Дурацкая, никому не нужная математическая головоломка, скажете вы. А вот и нет! Представьте, что у нас есть хороший алгоритм, который быстро разбивает заданное множество чисел на две группы с равной суммой (когда это разбиение вообще существует). Тогда мы можем применить его не только для решения подобных головоломок, но и вообще любых задач, к примеру – для поиска кратчайшего маршрута коммивояжера. Дурацкая математическая головоломка на самом деле представляет собой аналог проблемы «P против NP», и любой алгоритм, решающий ее гигантскую версию, способен вычислить практически все, что угодно.
Немного о руках
Наши руки – это самый удивительный механизм на планете. Они хватают, толкают, указывают пальцем. Завязывают шнурки, выпускают из лука стрелу. Играют на фортепьяно, скрипке, демонстрируют фокусы. В совершенстве управляют автомобилем, лодкой, поездом и самолетом. Руки могут поздороваться, а могут выкрутить запястья. Могут погладить с нежностью или больно ударить. Они общаются языком жестов, пишут слова на бумаге, набирают текст на компьютере. Выполняют ювелирную работу часового мастера и справляются с бензопилой. Руки гениев создают великие картины, симфонии, поэмы… Вероятно, все, чего мы достигли, стало возможным именно благодаря рукам.
Кисть руки содержит двадцать семь костей. На ней пять пальцев, включая незаменимый большой. Под эластичной кожей спрятана сложнейшая система мышц, сухожилий и нервов. Волшебный механизм – вот только самостоятельно это чудо природной инженерии функционировать не будет. От головного мозга должны приходить соответствующие инструкции: рука мертвеца не способна двигаться и вообще что-либо делать.
Рука – это «железо», т. е. натуральное аппаратное обеспечение. А значит, для работы ей обязательно нужна программа – сообщение от мозга, объясняющее, как выполнить то или иное задание.
Профессор Йоки Мацуока из Вашингтонского университета – специалист по робототехнике. Под ее руководством группа исследователей разработала так называемую «анатомически правильную» кисть, пальцы которой в точности повторяют движения человеческих. Технически искусственная рука способна творить те же чудеса, что и настоящая, однако на деле под силу ей оказываются лишь самые простые операции. Нелегко создать программу, которая управляла бы всеми функциями кисти; простейшие движения требуют идеальной координации большого числа мышц, и реализующие их алгоритмы далеко не тривиальны.
Впрочем, наш мозг умудряется контролировать руки без особых проблем. По сути мозг представляет собой сверхмощный компьютер, и раз он может объяснить рукам, как завязать шнурки или создать картину, то написать подобную программу теоретически возможно.
Конечно, одно дело знать, что некий алгоритм существует, и совсем другое – найти его. Программы со временем будут становиться все сложнее и сложнее; искусственная рука научится выполнять намного более трудные операции и однажды – как знать! – вполне может даже превзойти человеческую. Очевидно, нас ждет безумно увлекательное путешествие, вот только скорость движения, похоже, будет очень низкой.
Или не очень? Представьте, что для любой поставленной задачи тут же появляется программа со всей необходимой функциональностью. Например, вы загружаете в компьютер ролик, в котором человек завязывает галстук, и через секунду механические руки уже воспроизводят этот процесс. Или подаете на вход полное собрание сочинений Шекспира, а компьютер в ответ сочиняет новую «шекспировскую» пьесу. Представьте: все, что можно описать словами, можно и создать. Реально ли это? Да – но только если P равно NP.
Вот почему проблема равенства P и NP так будоражит умы. Неужели все задачи мы сможем щелкать как орешки? Или над некоторыми все же придется трудиться? Ответа пока нет, хотя на самом деле на «халяву» мало кто надеется. Вряд ли когда-нибудь выяснится, что P = NP; и все же помечтать об идеальном мире бывает очень и очень приятно.
P против NP
Проблема «P против NP» касается не только описанных выше задач, но и тысяч других, схожих с ними по сути. Насколько быстро можно перебрать огромное число потенциальных вариантов? Насколько трудно будет отыскать тот самый золотой билет, т. е. оптимальное решение поставленной задачи?
В тайниках тела (Приключения в микромире. Том VI). — Б.м.: Salamandra P.V.V., 2014. - 155 c., илл. — (Polaris: Путешествия, приключения, фантастика. Вып. LХI). Гигантские пауки и крошечные люди, кровопролитные битвы муравьев, отчаянные сражения микробов, путешествия внутри человеческого тела и невообразимые вселенные, заключенные в атомах — проникновение в микромир издавна было заветной мечтой фантастов. Публикацию забытых и редких произведений, объединенных общей темой «приключений в микромире», продолжает в серии «Polaris» познавательная книга Г.
В книге рассказывается история главного героя, который сталкивается с различными проблемами и препятствиями на протяжении всего своего путешествия. По пути он встречает множество второстепенных персонажей, которые играют важные роли в истории. Благодаря опыту главного героя книга исследует такие темы, как любовь, потеря, надежда и стойкость. По мере того, как главный герой преодолевает свои трудности, он усваивает ценные уроки жизни и растет как личность.
В этой книге говорится об Исконной Вере и Стари у Южных Славян. Исследование, которое мы провели, не основывается на песнях, преданиях и обрядах, сохранившихся до сих пор, ни даже на письменных летописях. Главная особенность научного подхода, примененного в этой книге, это его опора на образные представления, которые у Южных Славян, совместно со многими другими народами, возникли со временем.
«Древние люди летали в космос!», «Гагарин не был первым космонавтом!», «Американцы сфальсифицировали высадку на Луну!», «Космонавты встречали инопланетян и ангелов!». Подобные заголовки часто встречаются в прессе. В них не было бы большой беды, если бы из-за порождаемых мифов не формировалось конспирологическое мировоззрение, отрицающее историю космонавтики и достижения науки. Космическую мифологию легко опровергнуть фактами, но чтобы добраться до них, нужны знания и опыт. Книга Антона Первушина, писателя и научного журналиста, поможет сориентироваться в потоках информации и научиться отделять правду от вымысла.
В книге рассказывается история главного героя, который сталкивается с различными проблемами и препятствиями на протяжении всего своего путешествия. По пути он встречает множество второстепенных персонажей, которые играют важные роли в истории. Благодаря опыту главного героя книга исследует такие темы, как любовь, потеря, надежда и стойкость. По мере того, как главный герой преодолевает свои трудности, он усваивает ценные уроки жизни и растет как личность.
Всю жизнь мы видим сны: впервые они являются нам в утробе матери и не покидают до смертного часа. Но что же такое — сон? Нужен ли человеку этот «бесценный дар Морфея»? Можно ли считать сном гипноз? Почему во сне вспоминается забытое, казалось бы, навсегда? Есть ли связь между сном и памятью? Ответы на эти вопросы вы найдете в работе, посвященной этим еще не до конца изученным проблемам, связанным с деятельностью мозга.* * * Подписная серия «Знак вопроса» издательства «Знание» выпускалась ежемесячно, начиная с 1989 года.