Читать «Журнал «Компьютерра» №31 от 30 августа 2005 года» онлайн - страница 71

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

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

Pro: биоинформатика

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

Правила, по которым последовательность нуклеотидов гена транслируется в последовательность аминокислот соответствующего протеина (эти правила, собственно, и называются генетическим кодом), были известны еще в 1960-х годах. Каждая тройка нуклеотидов - так называемый кодон - переходит в одну аминокислоту. Нуклеотидов бывает всего четыре, поэтому возможных вариантов кодонов 64; но так как аминокислот около 20, то разные кодоны могут кодировать одну и ту же аминокислоту; есть специальный выделенный кодон, означающий «начало передачи данных», а любой из других трех выделенных кодонов (стоп-кодонов) означает «конец передачи».