Страница:
Борис Стругацкий до сих пор пишет. Так же сильно, как и раньше. Однако лично мне он не очень интересен. Не потому, что мир изменился, а потому, что не изменился сам писатель. В его книгах, написанных под псевдонимом Сергей Витицкий, до сих пор живут те же коммунистические идеи - в частности о воспитании детей отдельно от родителей. Витицкий по-прежнему (как в «Гадких лебедях») считает, что детей надо воспитывать общественно, что дети будут хорошими, только бы их увести от старых испорченных взрослых куда-нибудь подальше. И обычное для Стругацких дело - мораль в конце книги Витицкого опять оказывается плоской, вызывает разочарование. И что - ради этого все и написано? Мне кажется, эти книги сейчас смотрятся уже немного несуразно. Как, например, последние фильмы Рязанова.
Тем не менее сыну я купил собрание сочинений Стругацких. Ну и Лема, Булычева, естественно. Их тогдашние книги задают хороший нравственный ориентир, чего не скажешь о современной фантастике. Она довольно подлая - не только потому, что теперь у нее главными являются рыночные ориентиры, но и из-за отсутствия четкого представления о добре и зле в голове авторов. Однако в целом, по-моему, именно сейчас фантастика снова пользуется большой популярностью. Сейчас наступило время, когда идея смены эпох и приближения нового технического века снова стала очень популярной. Начало века. У человечества есть ощущение гигантской перспективы. Искусственный интеллект, информационные технологии, биоинженерия, космический туризм, Марс. Нечто похожее было и в начале ХХ века. Автомобили, самолеты, электричество, радио, пенициллин, успехи физики и медицины. Неуязвимый «Титаник». Буквально взрыв надежд на технически совершенное будущее. Тогда, правда, дело кончилось не построением совершенного мира, а гибелью «Титаника», двумя мировыми войнами, атомной бомбежкой и газовыми камерами. Поэтому теперь фантастика рисует уже не такой безоблачный мир, достаточно почитать киберпанк Гибсона. Следующий скачок был в 60-х (помните обожание физиков и презрение к лирикам?). Он и дал энергию взрыву популярности фантастики 60-70-х.
Начав читать фантастику в1970-х, я в самом деле вскоре окунулся в этот фантастический мир и так из него и не вылез. Окончив мехмат МГУ, в 1983 году я начал работать в Вычислительном центре Академии наук, в Отделе искусственного интеллекта. ВЦ АН СССР чем-то напоминал НИИ ЧАВО. У сотрудников был довольно свободный график, каждый мог заниматься тем, что ему по душе (продолжая аналогию - своим видом магии). В нашем отделе бились над пониманием текста, в соседнем - занимались распознаванием речи, через дверь - распознаванием лица, за углом писали «Тетрис», на следующем этаже рассчитывали ядерную зиму и так далее. Бурлила смесь программистов, психологов, лингвистов… Моя трудовая книжка так и лежит в ВЦ РАН уже 22 года, а в своей фирме я занимаюсь поисковыми машинами, говорящими роботами, автоматическим извлечением смысла из текстов - предметами реквизита фантастической литературы. Прошлым летом мы с моим двенадцатилетним сыном Стасом смотрели фильм «Я, робот» по Айзеку Азимову, и я сказал ему: а ведь из всех сидящих в этом зале только мы с тобой разрабатываем вот таких говорящих роботов (сын тоже поучаствовал в разработке модулей диалогов), так что смотри фильм с профессиональной гордостью.
Ренат Юсупов, старший вице-президент компании Kraftway
Те, кто сегодня занимается новейшими технологиями - в науке или в бизнесе, - не могли не увлекаться фантастикой двадцать-тридцать лет назад, потому что в те годы это были вещи, связанные неразрывно. Можно сколько угодно ругать советскую фантастику, поставленную тогда, как и все искусство, на службу режиму, но у нее было три безусловных достоинства. Содержательность - слово «научная» обязывало; занимательность - научная фантастика выгодно отличалась от прочей литературы оригинальностью, смелостью мысли; и качество - за счет общей высокой издательской культуры. В 70-80-е годы вся фантастика была научной без разделения на жанры и несла в себе немалую познавательную составляющую.
Современная же фантастика перестала быть научной. Это объективный факт, поскольку наука настолько далеко ушла вперед, что авторам стало трудно придумывать и предсказывать технологии будущего. Реальность во многих случаях выглядит гораздо фантастичнее.
Сегодня практически не осталось ученых, охватывающих своей эрудицией все пиковые направления науки, - что уж говорить о писателях-фантастах. Ни широкой эрудиции, ни желания копаться в научных деталях у нынешних авторов не видно (в России - пожалуй. А вот австралиец Грег Иган [Greg Egan] вполне отвечает этим критериям. - Л.Л.-М.). Да и законы современного бизнеса требуют скоростного конвейера по выпуску книг, а это возможно только с абсолютно оторванными от реальностей науки, придуманными мирами. С трудом удается найти двух-трех авторов, которые хоть относительно следуют законам жанра и кропотливо пытаются писать настоящую научную фантастику. Перечислю их, поскольку они вызывают у меня уважение. Из молодых - только Татьяна Семенова. Из среднего поколения - с некоторыми оговорками - Александр Громов, Михаил Тырин, Станислав Гимадеев, Владимир Ильин. Из тех, кто еще старше, - Павел Амнуэль, живущий ныне в Израиле, и, возможно, Геннадий Прашкевич. Остальные фантасты обретают популярность у молодежи за счет лихих, но примитивных сюжетов, обилия сленга, грубости и кровавых сцен - независимо от того, фэнтези это или космический боевик.
Пытаясь хоть немного воздействовать на текущую ситуацию с настоящей научной фантастикой, я поддерживаю авторов, работающих в этом жанре. Издаю НФ-книги, принимаю участие в писательской премии «Бронзовый Икар», присуждаемой за настоящую НФ, пишу научно-популярные статьи по физике для научно-фантастических книг Татьяны Семеновой, которые она, творчески перерабатывая, вставляет в текст. Возможно, эта деятельность и даст свои плоды, поскольку всем ИТ-бизнесменам известно: качественный контент и смелая идея - основа любого успешного проекта. Несмотря на то что традиционная печатная книга медленно умирает, на смену ей приходят электронные книги (допустим, на гибкой электронной бумаге), аудиокниги, возможно, появится что-нибудь еще. Печатное слово с увлекательным и познавательным содержанием в жанре настоящей НФ вполне может возродиться как новая форма получения знаний.
АНАЛИЗЫ: Теория и практика сложности
Компьютеры становятся все быстрее, объемы памяти - все больше. Можно подумать, что уже не столь важно, какие алгоритмы применять, - современный компьютер может все. Однако алгоритм для решения какой-нибудь нехитрой задачки на триста-пятьсот переменных грубой силой (brute force - вполне официальный термин в computer science) может потребовать порядка 2300 шагов - больше, чем во Вселенной элементарных частиц…
Этой проблемой занимается теория сложности: пытается придумать алгоритмы, которые бы работали быстро, а затем доказать, что они быстро работают. Или, на худой конец, доказать, что таких алгоритмов придумать нельзя.
Но как связаны теория и практика? Насколько то, чем занимаются гуру теоретической информатики, применимо к живым, практически полезным вычислениям? Или практическая польза была целиком извлечена во времена Эдсгера Дейкстры (Edsger Dijkstra), а современная теория сложности - лишь теоретическая забава, занимающая умы математиков, применения которой неясны и отдаленны (таковыми сейчас являются или по крайней мере кажутся многие области математики)? Попробуем разобраться…
Немного теории
Теория сложности (complexity theory) - это раздел теоретической информатики, связанный с оценками сложности работы алгоритмов. Сложность - понятие многогранное: здесь и время работы, и память, которая требуется алгоритму, и возможность его распараллеливания на несколько «процессоров»… Кстати, процессоры в теории сложности, как правило, моделируются машинами Тьюринга[Алан Тьюринг, один из отцов-основателей современной computer science, заложил основы теории сложности в середине 30-х годах прошлого века, когда из компьютеров (то есть «устройств для счета») доступны были абаки, арифмометры да не доведенная до «железа» машина Бэббиджа. Возможно, без его основополагающих работ никаких компьютеров бы и не появилось] - системами из бесконечной ленты и одной пишущей и читающей головки, безо всякого произвольного доступа; оказывается, в такое прокрустово ложе можно уместить все разнообразие компьютерных архитектур… но это уже тема для отдельного обстоятельного разговора.
Что же это такое - сложность алгоритма (в рамках статьи речь пойдет лишь о временно,й сложности [time complexity] классических детерминированных алгоритмов, а о сложности по объему требуемой памяти, вероятностных алгоритмах, протоколах для бесед вездесущих Боба и Алисы, параллельных и квантовых вычислениях мы, возможно, расскажем в следующих сериях)? Интуитивно это понятие довольно простое. У алгоритма есть вход (input) - описание задачи, которую нужно решить. На ее решение алгоритм тратит какое-то время (то есть количество операций). Сложность - это функция от длины входа, значение которой равно максимальному (по всевозможным входам данной длины) количеству операций, требуемых алгоритму для получения ответа.
Пример. Пусть дана последовательность из нулей и единиц, и нам нужно выяснить, есть ли там хоть одна единица. Алгоритм будет последовательно проверять, нет ли единицы в текущем бите, а затем двигаться дальше, пока вход не кончится. Поскольку единица действительно может быть только одна, для получения точного ответа на этот вопрос в худшем случае придется проверить все n символов входа. В результате получаем сложность порядка cn, где c - количество шагов, потребное для проверки текущего символа и перехода к следующему. Поскольку такого рода константы сильно зависят от конкретной реализации, математического смысла они не имеют, и их обычно прячут за символом O: в данном случае специалист по теории сложности сказал бы, что алгоритм имеет сложность O(n); иными словами, он линейный. Говорят, что алгоритм полиномиальный, если его сложность оценивается сверху некоторым многочленом p(n); алгоритм экспоненциальный, если его сложность имеет порядок 2cn. В реальных, тем более промышленных, задачах редко используются алгоритмы со сложностью больше экспоненты: уже экспоненциальная сложность стала во многих (но не во всех, как мы увидим ниже) случаях синонимом практической неразрешимости и ужасной немасштабируемости. В этой статье мы более никакими теоретико-сложностными концепциями, кроме полиномиального и экспоненциального алгоритма, пользоваться не будем.
Математически есть смысл рассматривать лишь бесконечные последовательности задач: если размер входа ограничен, всякий алгоритм можно заменить большущей, но все же константного размера таблицей, в которой будет записано соответствие между входами и выходами, и алгоритм будет иметь константную сложность (и совершенно не важно, что константа эта может оказаться больше числа атомов во Вселенной).
Мы собирались поговорить о том, насколько теоретические успехи в теории сложности связаны с практикой. В журнальной статье, конечно, невозможно дать обзор всех успехов и неудач теории сложности, так что мы остановимся лишь на трех примерах. Первый из них - биоинформатика - позитивный; в этой области любые теоретические продвижения весьма желательны с практической точки зрения (и продвижения постоянно происходят). Другой пример - линейное программирование - напротив, негативен: здесь один из крупнейших прорывов в теории сложности оказался абсолютно неприменим на практике. Ну а третий пример - решение задачи пропозициональной выполнимости - на мой взгляд, достаточно точно отражает современный баланс между теорией и практикой. Итак, вперед.
Pro: биоинформатика
Об успехах современной генетики наслышаны многие. Вряд ли сейчас нужно пересказывать истории об овечке Долли, а также - что куда ближе к теме этой статьи - о расшифровке генома человека. Подчеркнем лишь, что расшифровка генома вряд ли могла быть возможной без активного участия теоретической информатики.
Правила, по которым последовательность нуклеотидов гена транслируется в последовательность аминокислот соответствующего протеина (эти правила, собственно, и называются генетическим кодом), были известны еще в 1960-х годах. Каждая тройка нуклеотидов - так называемый кодон - переходит в одну аминокислоту. Нуклеотидов бывает всего четыре, поэтому возможных вариантов кодонов 64; но так как аминокислот около 20, то разные кодоны могут кодировать одну и ту же аминокислоту; есть специальный выделенный кодон, означающий «начало передачи данных», а любой из других трех выделенных кодонов (стоп-кодонов) означает «конец передачи».
Конечный (совсем небольшой) алфавит, дискретные объекты, четкие правила - ситуация идеально укладывается в общую концепцию computer science. Осталось лишь понять, что нужно сделать. Вот типичная задача (так называемая sequence alignment problem): предположим, что даны две последовательности нуклеотидов и набор возможных операций (мутаций) - например, удаление одного нуклеотида или замена одного нуклеотида на другой. Требуется определить минимальную (относительно весов, отражающих вероятности появления тех или иных мутаций) последовательность таких операций, которые первую последовательность переведут во вторую. Иным словами, нужно найти наиболее вероятную цепочку мутаций, которые привели к появлению слона из мухи или человека из обезьяны.
Другая задача, которая составляла основу проекта по реконструкции генома человека, - составление единой последовательности нуклеотидов из данных обрывков (задача возникает потому, что существующие биотехнологии не позволяют выявить структуры длинных последовательностей нуклеотидов - их приходится «разрезать» на кусочки и потом собирать по частям). Нечто вроде сборки паззла, только неизвестно, как сильно перекрываются кусочки и дают ли они в сумме полную картину.
Главная сложность, которая и делает подобные задачи интересными, - это, конечно, их размер[Мы никоим образом не хотим умалить трудности сугубо биологического характера: до середины 1970-х никто и мечтать не мог о том, что такие задачи вообще возникнут, и современное положение дел создано в первую очередь руками биологов. И сейчас биологические проблемы получения и интерпретации данных для комбинаторных задач стоят очень остро, но мы сейчас сконцентрируемся на математических трудностях]. Длина генома человека - более трех миллиардов нуклеотидов; собирать паззлы такого размера могут только компьютеры. А, например, пространство поиска для задачи sequence alignment для двух последовательностей длины 100 содержит порядка 1030 вариантов! Кроме того, задач еще и очень много (конечно, геном у человека один, но ведь есть и другие задачи, и другие организмы): база данных GenBank, содержащая практически всю известную на сей момент генетическую информацию, насчитывает в общей сложности около 50 млрд. нуклеотидов (желающие могут скачать базу с ftp.ncbi.nih.gov/genbank - только будьте готовы к тому, что в ней больше сотни гигабайт).
В результате каждое продвижение в теории сложности алгоритмов для нужд биоинформатики находит практическое применение: ведь зачастую входом алгоритму служит весь GenBank, и сказываются даже минимальные асимптотические улучшения.
Например, одна из связанных с sequence alignment задач - найти минимальное количество операций разворота подпоследовательности (reversals), с помощью которых можно получить данную перестановку из единичной. Поскольку эта задача NP-полна (это означает, что, вероятнее всего, никакого алгоритма быстрее экспоненциального существовать для неё не может), теоретическая борьба шла за создание аппроксимационных алгоритмов, которые бы работали полиномиальное время и давали результат с приемлемой точностью. В 1995 году появился алгоритм, вычисляющий это количество с точностью 2 (т.е. он мог ошибаться в 2 раза). В течение последующих трёх лет этот результат различными исследователями улучшался трижды (!): сначала до 1.75, затем до 1.5, и, наконец, до 1.375.
Характер задач биоинформатики таков, что теоретические оценки, как правило, подтверждаются на практике. Но это не всегда так, и один из важнейших контрпримеров мы рассмотрим в следующем разделе.
Contra: линейное программирование
Линейное программирование (ЛП) - это задача оптимизации линейной функции при линейных же на нее ограничениях. В наиболее простой переформулировке она сводится к тому, разрешима ли данная система линейных неравенств. Эта кажущаяся абстрактной задача имеет огромное количество применений и возникает в самых разных оптимизационных приложениях. В клиентах у крупнейшего производителя софта для решения задач ЛП - французской компании - ходят такие индустриальные гиганты, как Siemens, IBM, Visa International, France Telecom, United Airlines и многие другие. Говорят, что когда-то советская государственная программа развития Госплана фактически сводилась к тому, чтобы закодировать всю экономику СССР в виде огромной задачи линейного программирования, а потом ее решить и получить оптимальный план[Об этом Л. В. Канторович говорил в своей Нобелевской лекции. Кстати, векторы, лежащие в ограниченном задачей многограннике, в русской терминологии до сих пор называют планами].
Хотя о пользе решения систем линейных неравенств размышлял еще Фурье, впервые о применениях ЛП заговорили во второй четверти XX века. Начавшиеся исследования сразу же привели к успеху: по всей видимости, независимо друг от друга американец Джордж Данциг (George Dantzig) и советский математик Леонид Витальевич Канторович пришли (для разных, но эквивалентных формулировок исходной задачи) фактически к одному и тому же результату. Этот результат называется сейчас симплекс-методом; суть его - в обходе вершин соответствующего задаче многогранника в поиске оптимума. Симплекс-метод прост как для математического интуитивного понимания, так и для реализации, и преподается ныне в базовых вузовских курсах оптимальных задач. Важность его столь велика и бесспорна, что после того, как работы Канторовича были опубликованы, его приоритет доказан, а сам математик начал активно пропагандировать применение оптимизационных задач на практике, Л. В. Канторович получил Нобелевскую премию - по экономике, разумеется.
Симплекс-метод был прост и понятен, но оказался экспоненциальным - для разных эвристик выбора следующей вершины обхода исследователи сумели построить набор задач, для решения которых симплекс-методу было необходимо экспоненциально большое число итераций. И все же долгое время симплекс-метод был даже теоретически лучшим известным алгоритмом для решения задач линейного программирования. Однако в конце 1970-х годов здесь состоялся один из самых знаменитых прорывов в теории сложности: Л. Г. Хачиян[Как я узнал во время подготовки статьи, 29 апреля 2005 года Леонид Генрихович, в последние годы работавший в США, скоропостижно скончался] (везло нашим соотечественникам на фундаментальные открытия в этой области) построил алгоритм, который решает задачу линейного программирования за полиномиальное число шагов - так называемый метод эллипсоидов Хачияна. Суть алгоритма в том, чтобы окружить данный многогранник эллипсоидом, а затем постепенно сжимать этот эллипсоид; оказывается, на каждом этапе объем эллипсоида уменьшается в константное число раз.
Казалось бы, радость практиков должна быть беспредельной: полиномиальный алгоритм мог бы стать новым стандартом программирования. Но увы. Алгоритм Хачияна не просто плох, он безнадежен на практике. Существуют задачи размером в 50 переменных, для которых требуются более 24 тысяч итераций метода Хачияна, причем итерации эти отнюдь не тривиальны (хоть и полиномиальны, конечно). Количество итераций симплекс-метода в таких случаях исчисляется сотнями, если не десятками, и пересчет каждой из них гораздо проще. Метод эллипсоидов несравним с симплекс-методом: последний хоть и экспоненциален в худшем случае, однако на практике справляется с задачами ЛП многократно лучше. Все промышленные (да и кустарные) реализации решения ЛП основаны на симплекс-методе и его вариантах (которых - столь же экспоненциальных, сколь и их прародитель - уже накопилось довольно много).
Кстати, симплекс-метод для решения ЛП тоже отнюдь не стоит на месте, и производительность софта прирастает не только благодаря закону Мура. Один из основателей компании ILOG Роберт Биксби (Robert E. Bixby) рассказывал, что как-то раз, забавы ради, он взял ILOG 1.0 (выпущенный в середине восьмидесятых) и установил (видимо, перекомпилировал) его на современном компьютере. Разница между ILOG 1.0 и последней версией нынешнего ILOG оказалась видна невооруженным взглядом - свежий софт работал в несколько тысяч раз быстрее.
Метод эллипсоидов Хачияна стал, наверное, самым ярким примером разграничения между теоретически и практически успешными алгоритмами. Алгоритм, имеющий лучшую верхнюю оценку сложности, вовсе не обязательно будет наиболее удачен для практической реализации.
Pro et contra: выполнимость
Хотите миллион долларов? Нет проблем. Clay Mathematics Institute давно уже опубликовал список математических «задач на миллион». Решайте любую, ждите два года после публикации (нужно, чтобы никто не нашел ошибок в течение двух лет) - и золотой ключик у вас в кармане[Наш соотечественник, петербуржец Григорий Перельман уже года два как одну из них решил. Но почему-то не хочет публиковать свое решение (которое уже, по всей видимости, общепризнано) в официальных журналах, а интернет-публикации и прочие препринты для доллароносного фонда не годятся (что вполне логично). Но это, опять же, тема для совсем другого разговора]. Кстати, заработаете вы, конечно, гораздо больше миллиона, хоть бы и с учетом налогов: положение человека, решившего великую задачу, весьма завидно.
Одна из этих задач - центральная проблема современной теории сложности: равны ли P и NP? Sapienti sat, а поля этой статьи не настолько шире полей «Арифметики» Диофанта, чтобы вдаваться в подробные объяснения того, что же такое класс задач NP (с P мы уже разобрались - это задачи, которые можно решить полиномиальным алгоритмом). Однако простую переформулировку привести можно: рассмотрим булевскую формулу - то есть формулу, составленную из логических переменных при помощи дизъюнкции, конъюнкции и отрицания (обычно рассматривают формулы в конъюнктивной нормальной форме - это когда формула представлена как большая конъюнкция маленьких дизъюнкций, а отрицания бывают только непосредственно перед входящими в эти дизъюнкции переменными). Внимание, вопрос: существуют ли такие значения переменных, входящих в формулу, что значение всей формулы будет истинным? Такая задача называется задачей пропозициональной выполнимости (satisfiability, SAT). Если вам удастся найти полиномиальный (от длины формулы) алгоритм для решения SAT, вам обеспечен не только миллион долларов, но и вечная память благодарного потомства.
А пока информатика ждет новых гениев, простые (и даже совсем не простые) смертные совершенствуют экспоненциальные алгоритмы для решения этой задачи - ибо она тоже весьма полезна, а кое-где жизненно важна.
Лирическое отступление. Помните знаменитый баг в процессорах Intel, который принес компании несколько миллиардов долларов убытка? Подобные истории до сих пор не редкость. Схемы современных процессоров (и даже отдельных компонентов этих процессоров) настолько сложны, что вручную проверить их соответствие спецификациям не представляется возможным. Оказывается, математически проверка на вшивость базовой схемы из логических компонентов записывается именно в виде SAT, когда решения описывающей схему (точнее - описывающей соответствие схемы модельной схеме или спецификации) формулы соответствуют ошибкам. Невыполнима формула - значит, багов нет, можно запускать в производство.
Сейчас существуют два основных типа алгоритмов для решения SAT: алгоритмы локального поиска, которые начинают с какого-то набора значений (он, конечно, не выполняет всю формулу), а затем модифицируют его, пытаясь последовательно приблизиться к выполняющему набору, и так называемые DPLL-алгоритмы[По именам создателей: Davis, Putnam, Logemann, Loveland; их описание базовых принципов работы этого метода относится к 1968 году], которые обходят дерево всевозможных наборов и выполняют поиск в глубину. Анализ сложности алгоритмов локального поиска, как правило, носит вероятностный характер - ведь нужно начать с какого-то набора, который иначе как случайно выбрать трудно, а от него может зависеть очень многое.
Анализ же сложности DPLL-подобных алгоритмов более детерминирован, во многом благодаря развитой Оливером Кульманом (Oliver Kullmann) и Хорстом Люкхардтом (Horst Luckhardt) теории, связывающей эти оценки с решением рекуррентных уравнений, - их идея оказалась столь плодотворной, что позволила даже создать программы, автоматически доказывающие новые верхние оценки сложности для основанных на этих принципах алгоритмов.