Те, кто сегодня занимается новейшими технологиями - в науке или в бизнесе, - не могли не увлекаться фантастикой двадцать-тридцать лет назад, потому что в те годы это были вещи, связанные неразрывно. Можно сколько угодно ругать советскую фантастику, поставленную тогда, как и все искусство, на службу режиму, но у нее было три безусловных достоинства. Содержательность - слово «научная» обязывало; занимательность - научная фантастика выгодно отличалась от прочей литературы оригинальностью, смелостью мысли; и качество - за счет общей высокой издательской культуры. В 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. В реальных, тем более промышленных, задачах редко используются алгоритмы со сложностью больше экспоненты: уже экспоненциальная сложность стала во многих (но не во всех, как мы увидим ниже) случаях синонимом практической неразрешимости и ужасной немасштабируемости. В этой статье мы более никакими теоретико-сложностными концепциями, кроме полиномиального и экспоненциального алгоритма, пользоваться не будем.