Использование других наук в алгоритмах

Информатика и ее центральная область, теория алгоритмов, возникла недавно. И естественно, что она многое берет у старших наук-соседей.

Физика. Влияние физики в информатике проявилось только в последние годы и вызвало настоящий взрыв новых исследований. Центральным направлением, объединяющим эти науки, стало изучение нестандартных моделей вычислений. Как показал еще физик Ричард Фейнман, физические явления, такие как спин электрона, могут быть использованы для вычислений. Современные исследования показали, по-видимому, квантовые алгоритмы не сводятся к обычной (использующей биты) модели вычислений. Следовательно, пространство эффективно решаемых задач расширяется. Упомянем здесь также такие темы, как вычисления с вещественными числами (Real RAM), оптический компьютер и даже (!) бильярдные вычисления.

Теория вероятностей. Одна из наиболее применяемых математических теорий в информатике. Два ключевых направления: оценка времени работы алгоритма «в среднем», и вероятностные алгоритмы. Исследования в теории сложности показывают, что детерминированные алгоритмы не всегда дают наилучшие решение. Более того, на практике вероятностные алгоритмы могут работать заметно быстрее даже при наличии альтернативного детерминированного алгоритма (например, задача проверки на простоту).

Биология. Для решения самых трудных задач своей деятельности человек обращается за помощью к природе. Что делать, если мы хотим найти решение для таких трудных и неформализуемых задач, как классификация и распознавание образов?  Посмотреть, как эта задача решается в природе – то есть человеческим мозгом! Так возникла идея симуляции и моделирования вычислительных способностей нейронов. Предложенная модель получила название нейронных сетей. Затем был сделан следующий шаг. Важно не только как человек решает конкретную задачу (младенцы довольно плохо приспособлены к жизни), важно с какой феноменальной скоростью человек обучается в течении своей жизни. Так возникла теория машинного обучения (machine learning).

Теория графов и комбинаторика. Современные компьютеры работают с дискретными данными. Наиболее простыми объектами такого рода являются натуральные числа, последовательности, конечные множества и графы. Поэтому их основные свойства, изученные в соответствующих разделах математики, используются в теории алгоритмов невероятно часто. Когда специалисты по алгоритмам дорастут до работы с более сложными объектами, наверное, следующие уровни математики найдут свое применение.

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

Функциональный анализ. Оказывается, что и непрерывная математика необходима в разработке алгоритмов. Это случается, в основном, при компьютерной обработке явлений, имеющих непрерывную природу. Это, конечно же, цифровая обработка аудио и видео записей. Такие широко используемые стандарты, как MPEG и JPG содержат идеи, взятые из свойств преобразования Фурье и активно используют дискретный аналог операции свертки.