Компьютеры не найдут лекарство от рака

Изменится ли к лучшему окружающий мир, если подавляющее население Земли договорится использовать временно простаивающую вычислительную мощь домашних компьютеров для решения глобальных проблем современности при помощи технологии распределенных вычислений? То есть решать сложную задачу не на одном самом мощном компьютере, а использовать компьютерные информационные технологии, распределив вычисления между персональными ЭВМ, каждая из которых будет решать небольшую часть общей проблемы и обмениваться с остальными полученными результатами.

Не секрет, что развитие информационных технологий значительно увеличило быстродействие персональных компьютеров . Чтобы получить наглядное представление о достигнутом прогрессе, в одном научно-популярном журнале приводилось следующее сравнение. Если бы прогресс в авиации шел такими же темпами, как и в микроэлектронике, то современный пассажирский лайнер тратил бы на полет вокруг света меньше часа и при этом расходовал бы канистру авиационного керосина!

Вместе с тем возросшая вычислительная мощь далеко не всегда используется полностью. Например, когда набирается текст в MS Word, компьютер в основном простаивает. Потому что на то, чтобы получить символы с клавиатуры и вывести их в окно редактора, требуется очень мало вычислительных "усилий".

Верно ли, что если объединить домашние персональные компьютеры в сеть, занятую поиском решения одной из глобальных проблем человечества, то, пока вы печатаете в MS Word текст, объединенные компьютеры, работающие параллельно, смогут найти вакцину от неизлечимого вируса? Или разработают способ производства качественных и безопасных для человека и окружающей среды продуктов питания?

Как известно, в основе решения любой задачи компьютером лежит алгоритм. Алгоритм действий - результат четкого, последовательного описания задачи. При помощи программиста алгоритм переводится в набор команд, понятных компьютеру. Так создается любая программа.

Казалось бы, с огромной вычислительной мощью можно браться за решение любой задачи. А если не получается найти решение, его можно искать методом перебора всех возможных вариантов. Мощи ведь хоть отбавляй! Оказывается, даже если задействовать объединенные усилия всех компьютеров Земли, прогресс в решении некоторых задач будет незначителен. Почему?

С каждой решаемой алгоритмической задачей связана такая величина, как размерность. Что это такое? Это количество самых существенных параметров задачи. Например, если требуется составить алгоритм, переставляющий исходный набор целых чисел таким образом, чтобы все числа оказались расположенными по возрастанию, то размерность данной задачи равна количеству исходных целых чисел.

Другой важной характеристикой является сложность алгоритма, реализующего задачу. Сложность алгоритма задачи всегда связана с ее размерностью и измеряется количеством необходимых команд присваивания или проверки условий.

Например, алгоритм, реализующий поиск наибольшего числа среди исходных 30 целых чисел, может быть "устроен" следующим образом. Сначала запоминается первое число. Оно объявляется "временно наибольшим". Просматриваются оставшиеся 29 чисел. Каждое сравнивается с "временно наибольшим". Если, например, второе число оказывается больше запомненного, "временно наибольшим" становится второе число.

И так далее, до 30-го числа. Полученное в результате "временно наибольшее" число будет являться наибольшим среди всех исходных чисел.

Нетрудно увидеть, что размерность N данной задачи равна 30 - по количеству чисел, среди которых выполняется поиск. Сложность алгоритма в данном случае так же равна N. Поскольку требуется один раз вначале выполнить операцию присваивания, а затем N-1 раз сравнить оставшиеся числа.

Но не все задачи решаются так просто. Например, размерность задачи перестановки набора из N целых чисел, чтобы все числа расположились по возрастанию, так же равна N. А вот сложность "очевидного" алгоритма, решающего эту задачу, уже пропорциональна N2.

Сначала в исходном наборе из N целых чисел нужно найти наибольшее. Как было показано, сложность вспомогательного алгоритма, решающего эту задачу, равна N. Найденное наибольшее число помещается в конец результирующего набора и вычеркивается из исходного. Аналогичные действия повторяются на наборе оставшихся N-1 чисел. Размерность задачи уменьшилась на 1, поэтому сложность вспомогательного алгоритма уже равна N-1. В результате повторного выполнения алгоритма на N-1 числе полученное наибольшее число помещается перед числом, найденным на начальном шаге алгоритма, и так же вычеркивается из исходного набора. Действия повторяются для оставшихся чисел.

Нетрудно заметить, что на первом шаге вспомогательным алгоритмом выполняется N команд сравнения или присваивания, на втором - (N-1), и т.д. Всего вспомогательный алгоритм вызывается N-1 раз. Просуммировав полученную арифметическую прогрессию, несложно получить оценку сложности алгоритма. Она пропорциональна N2.

Что означает полученная оценка? Если требуется расположить по возрастанию 30 чисел, то компьютеру в "худшем" случае - когда исходные числа расположены в убывающем порядке - потребуется выполнить 302 операций. А для 1000 чисел? Уже миллион.

А что будет, если для решения какой-то задачи используется алгоритм сложности N3? Количество операций возрастает. Так, для задачи размерности 1000 потребуется выполнить порядка миллиарда операций. Для задачи размерности 3000 еще больше - порядка девяти миллиардов операций.

Поэтому на практике стараются найти и составить программу по алгоритму, имеющему сложность порядка N2. В противном случае, если найти такой алгоритм не удается, организуют интерактивное взаимодействие программы и человека, "направляющего" алгоритм по наиболее перспективному пути.

Произойдет ли интеллектуальный прорыв, ждут ли нас новые открытия, если все жители Земли объединят домашние компьютеры для решения глобальных задач, имеющих значительную вычислительную сложность алгоритма? К сожалению, нет. Например, если сложность алгоритма пропорциональна 3N, то увеличение количества домашних компьютеров в 1000 раз позволит решить задачу размерности всего лишь на 6 или 7 больше исходной. Такова вычислительная сложность практически любого алгоритма, реализующего полный перебор вариантов.

Таким образом, возможность решения глобальных проблем современности - если ответ будет искаться при помощи компьютера - будет целиком и полностью зависеть от сложности найденного алгоритма.