`

СПЕЦИАЛЬНЫЕ
ПАРТНЕРЫ
ПРОЕКТА

Архив номеров

Как изменилось финансирование ИТ-направления в вашей организации?

Best CIO

Определение наиболее профессиональных ИТ-управленцев, лидеров и экспертов в своих отраслях

Человек года

Кто внес наибольший вклад в развитие украинского ИТ-рынка.

Продукт года

Награды «Продукт года» еженедельника «Компьютерное обозрение» за наиболее выдающиеся ИТ-товары

 

Игорь Дериев

В чем сила компьютера, брат?

+1111
голосов

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

Поводом для настоящего сообщения стал очередной успех исследователей. Им удалось доказать, что в популярной игре судоку - знаете, там где нужно вычислить все цифры в квадрате 9x9 по сравнительно небольшому числу известных, при условии, что в каждой строке, каждом столбце и квадрате 3х3 они не повторяются - для однозначного решения подсказок (известных цифр) должно быть не меньше 17 (обычно их, конечно, больше, иначе слишком сложно). Т.е. 16 в любом случае дают несколько возможных решений.

Не берусь сказать, какая от этого открытия польза народному хозяйству, возможно, задача имеет какие-то выходы на криптографию. Но машинного времени исследователи убили изрядно - 7.1 млн "ядерных" часов (т.е. это совокупное время работы всех задействованных вычислительных ядер). Ядер, правда, тоже было немало. Использовался ирландский суперкомпьютер Stokes из 320 узлов с двумя 6-ядерными Xeon каждый. На все про все ушел весь 2011 год (были какие-то перерывы, т.к. задания выдавались блоками).

Что же все это время делал Stokes? Да, именно перебирал варианты. Всего таких квадратов порядка 10^21 (здесь и дальше мантиссы просто опускаю), но большая часть эквивалентны друг другу, поэтому было достаточно исследовать всего лишь порядка 5 млрд, ну и для каждого - различные наборы из 16-и подсказок. В общем, было чем заняться, и справился Stokes, как мы уже знаем, с честью.

Примечательно, что работа по ссылке помечена 1 января 2012 г. Но едва ли это заслуживает пафосных речей о "новой эре". Подобные открытия случались и раньше. Если не ошибаюсь, около 5 лет назад, компьютеры по сути убили русские (64-клеточные) шашки. Тупо за несколько лет (!) перебрали все 10^20 партий. Почему убили? Потому что таким образом было доказано существование беспроигрышной стратегии и за белых, и за черных. Конечно, алгоритма построения правильной игры нет, но для самых популярных дебютов ее можно рассчитать и запомнить на достаточную глубину, а после (когда шашек на доске станет поменьше) человек и сам разберется. Дошло до того, что в некоторых турнирах участники вынуждены разыгрывать одни и те же случайным образом выбранные дебюты.

На самом деле сегодня большинство логических игр компьютеру уже "неинтересны". Насколько я понимаю, держатся еще те, где перебор составляет порядка 10^40 и выше. Например, шахматы. Хотя все, наверное, знают, что компьютеры и их перевели в иную плоскость. Владимир Крамник, довольно красиво проиграв компьютеру одну из партий (весь матч, впрочем, тоже), сказал, что это была "нечеловеческая игра" - т.е. человек так бы не сыграл. Не смог бы просчитать такой вариант. Да, пожалуй, и не стал бы его рассматривать, положившись на общепризнанные тактические принципы. Компьютер же (опять же, благодаря использованию перебора) подобных предрассудков лишен.

Конечно, у компьютеров есть и неигровые достижения. Значительная часть решения задачи о четырех красках - тоже перебор специальных комбинаций.

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

Между прочим, облачные вычисления вполне могут дать этому процессу дополнительный толчок. Amazon недавно подала пример. И кстати, решение задачи судоку на их виртуальном суперкомпьютере было бы не таким уж и дорогим, всего-то 1.5 млн долл без учета возможных скидок :)

+1111
голосов

Напечатать Отправить другу

Читайте также

Жаль только что такая мощь не напралена на что то более прикладное чем судоку. Вот интересно неужели нельзя решить хотябы в общих чертах с последующей проверкой в натурных экспериментах проблему рака, спида, термоядерной энергии или наоборот подобрать материалы для солнечных батарей доведя кпд до 50-70%. Полеты в космос уже 50 лет осуществляются на многоступенчатых ракетах сжигающих керосин тоннами - нельзя разработать новый двигатель?
Да если бы хотя бы 1/5 тех денег которые ушли на разработку касметики, бытовой химии, гигиены (памперсы, прокладки, новые станки для бритв) направить на разработки в области энергетики - нам бы сейчас не газа за 416 у.е., ни бензина по 10грн/литр не нужно было бы. А тут народ развлекается.

Странно слышать ваши слова.
<социальное негодование не маленького украинца он>
Такая мощ бесконечно мала для чего-то более прикладного, где как правило нужно обеспечивать редукцию функционала на пространстве функций 10^100. К таким задачам относятся задачи полной победы рака и доведения КПД лдл требуемых преобразований до 70%
Термояд требует поменьше, и если сами хотите поиграться (а кто вам что должен?), можно попользоваться, например, этим. Народ даже что-то там строит.

Ракеты, к сожалению, летают не на керосине (очень уж мала удельная энергия химической реакции окисления широкой фракции углеводородов кислородом). К сожалению, потому что прочая химия и ядерные взрывы хуже с точки зрения экологии. Все что надо, практически было посчитано в 50-60х.

И что характерно, вот именно там, где основные деньги крутятся на разработку косметики и бытовой химиии, удельное потребление энергии на порядок ниже чем у нас. И именно потому, что там умеют избегать подобных идей (нечто подобное по духу, помнится, предлагало политбюро ЦК КПСС с призывами об опережающем развитии первого сектора, а с рацухами выступал А. Райкин). И опять же, именно там разработали Флюку, Сайнтифик-Линукс и прочее разное.

А газ тут такой и бензин потому, что буровые платформы по 450 млн., а не за 200, и прочие корупционные налоги на добыче логистике доганяют общий итог в ~50% от спота. И хоть вы судите за расходы на косметику, ситуация не изменится.
Потому что тем не менее, углеводороды продолжают оставаться топливом, обеспечивающим экономическую геодезическую.

А общую выгоду продолжает обеспечивать подход, когда деньги тратят кто может как считает нужным,
и особенно вредными оказываются порывы отнять деньги у тех кто может (разработать косметику, посчитать варианты для неалгаритмизируемой игры), и потратить на всеобщее балаго неблагодарных предтавителей человечества, не желающих отодрать задницу (во всех смыслах) ради, в первую очередь, построения благосостояния своими руками, а не чужим баблом.

Думаю, все денеги, которые потрачены на косметику, потрачены вполне правильно.

1)Про коррупцию не спорю.
2)Насчет экологии - думаю что водород был бы не худшим топливом, если наладить его производство по вменяемой цене.
3)Ядерные, плазменные или какие то другие двигатели - антигравитация или что еще можно придумать - никто не запрещает использовать за приделами Земли. Так что не принимается.
4)Насчет меньшего удельного потребления энергии - вряд ли это достигается именно компаниями производящих эту косметику. Там просто была возможность для других людей в других компаниях заняться энергосбережением.
5)Насчет общей выгоды категорически не согласен. Если бы вы сказали что: "в краткосрочной перспективе наибольшую выручку обеспечивает подход, когда деньги тратят кто может как считает нужным" - ваше утверждение было бы правильно. Я не призываю методами военного коммунизма отнять средства у одних и дать другим. Я просто вижу что ресурсов становится меньше, продукты и промышленные товары дорожают и становятся менее качественными. А прорывных технологических или организационных открытий - сравнимых с паровой машиной, ДВС, научных подходом в сельском хозяйстве, гигиеной и вакцинацией - просто нет. За последние 20 лет кроме интернета нечего номинировать на прорыв. Все прочее это допиливание того что еще в 50-60 научно обосновали.
Из крупных фундаментальных проектов можно разве что БАК выделить - но опять же, лично мне бы хотелось что бы его разместили не ближе Луны.
Так что в целом текущее положение дел это сваливание в стагнацию или застой.
Зуб здесь уже писал на эту тему

1)
2) дело не только в цене производства, но и в проблемах безопасного использования водорода и связанной с этим ценой. протая экономика: именно потому пока выгодно топить углем, а водородом охлаждать подшипники генераторов.
3) в километре от станций метро на левом берегу в Киеве - заброшенные необработанные земли, Большая часть Африки и Австралии пустуют. Хотя поддерживать экосистемы даже в поледних дешевле, чем вывести на орбиту все что надо для построения антигравитационного двигателя. атомные и плазменные уже летают. в чем смысл.
4) задача компаний по производсву косметики - производить и продавать косметику. если кто-нибуть придумает вечную не греющуюся лампочку накаливания, заработает огромные деньги. но не думаю, что мы сможем такого искуссника распознать и выдать ему денег от продаж косметики до события придумывания. пока что все чудесные изобретения на поверку оказывались откровенным дебилизмом недоучившихся фантазеров. в этом тоже проблема.
5) намедни был в одной европейской стране. Продукты качественные, и не дороже чем некачественные в Киеве. Парадокс? Нет, все как-то понятно: люди не раздумывают о целесообразности, а принимают мир таким, каким он есть без всяческих теорий. застой у них уже лет двести (так они считают) - так, работают понемногу.
В квартале от места где я жил придумали язык программирования Скала, но также активно занимались вдуванием золота в керамическу (23-ти каратное "золото" с твердостью корунда для бижутерии). Абсолютно никто не воспринимал ситуацию так, что первая придумка чудо, а вторая отстой. Потому что не дано предугадать, как обернется то или другое дейвсвие. Потому лучше уж как-нибуть, без соображений непричастных как оно должно быть лучше для других.

А прорывов за последнее время качественных полно. И величайших для тех кто следит - немало, да хоть доказательво теоремы геометризации, т.е. понимание, что летать и прыгать, как это показано в "Стартреке" таки не получится. А вот летать со скоростью больше скорости света можно (доказано, посчитано, надены ошгибки, потребная энергия снижена на порядки). просто надо научиться сжигать ядра галактики. Но это уже не вопрос экономики, а целесообразности. И есть в связи с этим уже результаты и метаматериалы (но не в наноместах).

А я бы номинировал на экономический прорыв паровые минитурбины, а на суперпрорыв - возможность изготавливать их коллективами, не превышающими число Данбара. Первое есть, второе на подходе. Социальные измененния, конечно, более инерционны.
Эволюция видна (мне) в местностях и группах, где в этом есть смысл, естественный пресинг обратных связей, без искусственного перераспределения ресурсов. И виден распил, запустение и отрицательный отбор странных личностей во всех других локациях. Вот в этом все дело, ну и в экономике, естественно.

1)Не хочу показаться занудой, но большинство прорывов перечисленных вами - это либо узкоспециальные, либо сугубо теоретические прорывы. Как зачастую бывало в математике скажем изобретенный математический аппарат можно было приспособить к делу зачастую через 100 и более лет. Мне как практику интересны прежде всего то что можно применить с пользой уже сегодня или на худой конец работающая модель, а не сугубо теоретическая находка. Тут некоторые собирались в 60-е 70-е через черные дыра попадать в прошлое или другие галактики, но пока нет даже возможности к ним долететь.
2)Насчет заброшенных земель под Киевом или в центральной Африке - тут готов с вами во многом согласиться.
3)Завидую европейцам за возможность потратить деньги на качественные товары.

1) прорывы, перечисленные мной, изменяют качество. в большинстве случаев, прорыв - это сделать старое экономически целесообразным.
также припоминаю, что эти сами некоторые в 80-м году обещали построить коммунизм, а к черным дырам летали, прогнав предварительно в мировом пролетарском ВЦ собственноручно набитую на перфокартах програмуму.
что страннее, даже не скажу сразу: верить в прогностическую ценность этакого, или игнорировать факт потребных количеств энергии (плюс-минус несколько порядков можно прикинуть на коленке) для доставки 1 кг. с бердичевской мостовой в центр галактики.
-
3) не всем европейчам. и что характерно, относительная мера потраченного за качественнный меньше, чем в остальных местах за некачесвенный.
Демонстрация на практике данной в ощущениях правильных подходов - тоже прорыв. Например, по статистике, в 2011 около 40 миллионов китайцев смогло съездить за рубежь. Основная страна для поездок - США (потому что гегемон, китайцам интересно). Основное занятие при посещении гегемона - шоппинг. Хотя большинсво товаров произведено в Китае, обеспеченным китайцам товары на американском рынке покупать интереснее, потому что стандарты выше, а логистика эффективнее. Для меня, глобальные прорывы они не в том, чтобы дейтерит лития поджечь в зажигалке наперекор существующим локальным физическим законам, но в отакие от возможностях в логистике и управлении обязательвами. которые стали возможны в результате эволюции систем SCM косметики уже на сравнительно маломощных системах.

Интересно, предпринимаются ли составителями программ для перестановочно-вычислительных доказательств специальные меры, призванные убедить общественность в том, что ни один из мириадов циклов не нарушился, к примеру, вследствие прободения регистра данных космическими лучами

В статье написано, что в 2008 г. юная немецкая студентка опубликовала аналитическое доказательство невозможности 16-цифирьного судоку, которое некоторое время считалось верным, пока некий университетский математик из спортивного интереса не выловил в нем ошибку.

Наверное, ее доказательство занимало страниц 10

Доказательство, представленное авторами программы для суперкомпьютера это, собственно говоря, исходники. Занимают они страниц 500, и если в них есть ошибка, то шансов, что на ее вылавливание почти нет, особенно если они плохо документированы и плохо форматированы.

Похоже, математика находится на пороге первого этапа краха: доказательства теорем станосятся непостижимо сложными. Второй (и окончательный) этап настанет, когда непостижимо сложными станут т.ж. и формулировки теорем:)

в принципе, ученые задаются подобными вопросами. хотя я и не встречал, чтобы они реально _обосновывались_ в каких-то серьезных задачах. но может быть я просто недостаточно вчитывался.
исключить вероятность стороннего воздействия на массивные вычисления можно повторными прогонами. грубо говоря, еще 7 млн часов, и сомнения в решении задачи судоку отпадут :)
что же до текстов программ, то в software engineering существуют специальные методы доказательства их корректности. для этого, кстати, активно применяются машинные "пруверы" :)
ну а о крахе говорить не приходится :) если математика переварила открытия Гёделя, то с машинными парадоксами и подавно справится ;) другое дело, что наука на глазах действительно приобретает некое новое качество. о чем-то подобном, насколько понимаю, писал г-н Вольфрам.

Вообщем, математика уподобляется физике и химии, в которых критерий истины - воспроизводимость результатов.

PS повторный прогон сам по себе не очень эффективен: к примеру, если один прогон с результатом 0 свидетельствует о том, что вероятность отсутствия решаемых 16-цифирьных судоку составляет 99%, то четыре прогона с результатом 0 поднимут вероятность до 99.999999%

Другое дело - два прогона с результатами (0, 45621354321355132), где второе число - CR-код, модифицирующийся после каждой арифметической операции. Тут рост уверености в бессбойности вычислений (при сопоставимости накладных расходов) будет астрономическим.

Этот хак я придумал в 2 минуты, а у теоретиков программирования, наверное, на этот счет целые статьи отгроханы...

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

Все желающие могут принять участие во втором прогоне, устроенном тайваньцами на платформе BOINC под девизом "You may be the first who found 16-clue Sudoku puzzles. Let us make the history together!"
http://sudoku.nctu.edu.tw/joomla/

Специальные меры принимаются даже при расчетах простых чисел. Потому подтверждение простоты очередного прайма иногда затягивается на пару лет - пока пересчитают.

Исходники это - одна проблема из области теории алгоритмов. Сложная но в целом понятная. Для сложных проблем вполне работает лямбда-исчисление, в данном случае нужно просто гарантировать перебор всех вариантов, при этом аналитическиая оценка есть и проверка в целом дело не сложная. Интерпретация результатов - другая, особенно если мы имеем дело с R, когда даже сложение на реальной машине не комутативная операция.
Форматирование исходников - не проблема, достаточно нажать в IDE какое-нибуть Alt-Shift-F.

Что касается сложности. Вот простая формулировка: всякое односвязное компактное трёхмерное многообразие без края гомеоморфно трёхмерной сфере. Возьмите первых 100 человек, попросите доходчиво объяснить что это значит.

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

Так что о чем говорить, собственно?
Более чем для 99% елементарное изменение констант настоящим админом какого-нибуть selinuxa выглядит как чистая магия, недоступная пониманию, применение которой влечет пробой облачных сфер и предвестие гибели богов. Но ведь никто же не говорит об окончательном крахе системного администрирования.
ггг

 
 
IDC
Реклама

  •  Home  •  Рынок  •  ИТ-директор  •  CloudComputing  •  Hard  •  Soft  •  Сети  •  Безопасность  •  Наука  •  IoT