Knigionline.co » Наука, Образование » Золотой билет. P, NP и границы возможного

Золотой билет. P, NP и границы возможного - Фотноу Лэнс

Золотой билет. P, NP и границы возможного
«Золотой билет» – прекрасное вступление в P/NP-проблему, в котором описаны ситуация данной задачки и ее воздействиевлияние на нашу жизнь. В данной информативном и занятном издании Лэнс Фортноу прослеживает работу, которая проводилась над задачей во эпохи холодной войны по двум сторонам медали: США и СССР. Стороны «железного занавеса», и приводит примеры ее появления во огромном количестве дисциплин, охватывая экономику, физику и биологию.
Для учащихся и знатоков в области доктрины вычислений, всех, интересующихся передовыми задачами в арифметике.
В формате pdf A4. Издательский дизайн сохранен.

Золотой билет. P, NP и границы возможного - Фотноу Лэнс читать онлайн бесплатно полную версию книги

В сумме все они дают ровно 2000000. Попробуйте разбить их на две группы по девятнадцать чисел так, чтобы сумма чисел внутри каждой группы была равна 1000000. Можете свободно пользоваться калькулятором, Excel или даже написать программу. Ответ приводится в конце главы.

Не так-то просто, верно? Ведь для разбиения существует более семнадцати миллиардов вариантов! Современные компьютеры считают очень быстро, и с хорошей программой у вас есть все шансы получить ответ. Ну а что если я предложу вам не тридцать восемь чисел, а три тысячи восемьсот? Или, что еще лучше, тридцать восемь миллионов? Тут уже никакая программа не справится.

Дурацкая, никому не нужная математическая головоломка, скажете вы. А вот и нет! Представьте, что у нас есть хороший алгоритм, который быстро разбивает заданное множество чисел на две группы с равной суммой (когда это разбиение вообще существует). Тогда мы можем применить его не только для решения подобных головоломок, но и вообще любых задач, к примеру – для поиска кратчайшего маршрута коммивояжера. Дурацкая математическая головоломка на самом деле представляет собой аналог проблемы «P против NP», и любой алгоритм, решающий ее гигантскую версию, способен вычислить практически все, что угодно.

Немного о руках

Наши руки – это самый удивительный механизм на планете. Они хватают, толкают, указывают пальцем. Завязывают шнурки, выпускают из лука стрелу. Играют на фортепьяно, скрипке, демонстрируют фокусы. В совершенстве управляют автомобилем, лодкой, поездом и самолетом. Руки могут поздороваться, а могут выкрутить запястья. Могут погладить с нежностью или больно ударить. Они общаются языком жестов, пишут слова на бумаге, набирают текст на компьютере. Выполняют ювелирную работу часового мастера и справляются с бензопилой. Руки гениев создают великие картины, симфонии, поэмы… Вероятно, все, чего мы достигли, стало возможным именно благодаря рукам.

Кисть руки содержит двадцать семь костей. На ней пять пальцев, включая незаменимый большой. Под эластичной кожей спрятана сложнейшая система мышц, сухожилий и нервов. Волшебный механизм – вот только самостоятельно это чудо природной инженерии функционировать не будет. От головного мозга должны приходить соответствующие инструкции: рука мертвеца не способна двигаться и вообще что-либо делать.

Рука – это «железо», т. е. натуральное аппаратное обеспечение. А значит, для работы ей обязательно нужна программа – сообщение от мозга, объясняющее, как выполнить то или иное задание.

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

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

Конечно, одно дело знать, что некий алгоритм существует, и совсем другое – найти его. Программы со временем будут становиться все сложнее и сложнее; искусственная рука научится выполнять намного более трудные операции и однажды – как знать! – вполне может даже превзойти человеческую. Очевидно, нас ждет безумно увлекательное путешествие, вот только скорость движения, похоже, будет очень низкой.

Перейти
Наш сайт автоматически запоминает страницу, где вы остановились, вы можете продолжить чтение в любой момент
Оставить комментарий