Журнал «Компьютерра» №31 от 30 августа 2005 года
Шрифт:
Те, кто сегодня занимается новейшими технологиями - в науке или в бизнесе, - не могли не увлекаться фантастикой двадцать-тридцать лет назад, потому что в те годы это были вещи, связанные неразрывно. Можно сколько угодно ругать советскую фантастику, поставленную тогда, как и все искусство, на службу режиму, но у нее было три безусловных достоинства. Содержательность - слово «научная» обязывало; занимательность - научная фантастика выгодно отличалась от прочей литературы оригинальностью, смелостью мысли; и качество - за счет общей высокой издательской культуры. В 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. В реальных, тем более промышленных, задачах редко используются алгоритмы со сложностью больше экспоненты: уже экспоненциальная сложность стала во многих (но не во всех, как мы увидим ниже) случаях синонимом практической неразрешимости и ужасной немасштабируемости. В этой статье мы более никакими теоретико-сложностными концепциями, кроме полиномиального и экспоненциального алгоритма, пользоваться не будем.
Математически есть смысл рассматривать лишь бесконечные последовательности задач: если размер входа ограничен, всякий алгоритм можно заменить большущей, но все же константного размера таблицей, в которой будет записано соответствие между входами и выходами, и алгоритм будет иметь константную сложность (и совершенно не важно, что константа эта может оказаться больше числа атомов во Вселенной).
Мы собирались поговорить о том, насколько теоретические успехи в теории сложности связаны с практикой. В журнальной статье, конечно, невозможно дать обзор всех успехов и неудач теории сложности, так что мы остановимся лишь на трех примерах. Первый из них - биоинформатика - позитивный; в этой области любые теоретические продвижения весьма желательны с практической точки зрения (и продвижения постоянно происходят). Другой пример - линейное программирование - напротив, негативен: здесь один из крупнейших прорывов в теории сложности оказался абсолютно неприменим на практике. Ну а третий пример - решение задачи пропозициональной выполнимости - на мой взгляд, достаточно точно отражает современный баланс между теорией и практикой. Итак, вперед.
Об успехах современной генетики наслышаны многие. Вряд ли сейчас нужно пересказывать истории об овечке Долли, а также - что куда ближе к теме этой статьи - о расшифровке генома человека. Подчеркнем лишь, что расшифровка генома вряд ли могла быть возможной без активного участия теоретической информатики.
Правила, по которым последовательность нуклеотидов гена транслируется в последовательность аминокислот соответствующего протеина (эти правила, собственно, и называются генетическим кодом), были известны еще в 1960-х годах. Каждая тройка нуклеотидов - так называемый кодон - переходит в одну аминокислоту. Нуклеотидов бывает всего четыре, поэтому возможных вариантов кодонов 64; но так как аминокислот около 20, то разные кодоны могут кодировать одну и ту же аминокислоту; есть специальный выделенный кодон, означающий «начало передачи данных», а любой из других трех выделенных кодонов (стоп-кодонов) означает «конец передачи».
Конечный (совсем небольшой) алфавит, дискретные объекты, четкие правила - ситуация идеально укладывается в общую концепцию computer science. Осталось лишь понять, что нужно сделать. Вот типичная задача (так называемая sequence alignment problem): предположим, что даны две последовательности нуклеотидов и набор возможных операций (мутаций) - например, удаление одного нуклеотида или замена одного нуклеотида на другой. Требуется определить минимальную (относительно весов, отражающих вероятности появления тех или иных мутаций) последовательность таких операций, которые первую последовательность переведут во вторую. Иным словами, нужно найти наиболее вероятную цепочку мутаций, которые привели к появлению слона из мухи или человека из обезьяны.