Тем не менее сыну я купил собрание сочинений Стругацких. Ну и Лема, Булычева, естественно. Их тогдашние книги задают хороший нравственный ориентир, чего не скажешь о современной фантастике. Она довольно подлая - не только потому, что теперь у нее главными являются рыночные ориентиры, но и из-за отсутствия четкого представления о добре и зле в голове авторов. Однако в целом, по-моему, именно сейчас фантастика снова пользуется большой популярностью. Сейчас наступило время, когда идея смены эпох и приближения нового технического века снова стала очень популярной. Начало века. У человечества есть ощущение гигантской перспективы. Искусственный интеллект, информационные технологии, биоинженерия, космический туризм, Марс. Нечто похожее было и в начале ХХ века. Автомобили, самолеты, электричество, радио, пенициллин, успехи физики и медицины. Неуязвимый «Титаник». Буквально взрыв надежд на технически совершенное будущее. Тогда, правда, дело кончилось не построением совершенного мира, а гибелью «Титаника», двумя мировыми войнами, атомной бомбежкой и газовыми камерами. Поэтому теперь фантастика рисует уже не такой безоблачный мир, достаточно почитать киберпанк Гибсона. Следующий скачок был в 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: линейное программирование