Применение математических методов в прикладной информатике

Много было сказано и написано на тему проектирования и анализа алгоритмов. Существует большое количество замечательных учебников, передовых монографий и высококачественных специализированных журналов в этой области. Они охватывают ряд вопросов, связанных со стратегиями проектирования (такими как жадность, разделение и завоевание, ветвление и связывание, двоичное удвоение и т.д.), реализацией (выбор структур данных для хранения и обработки информации) и анализом (модель вычислений, асимптотика, нижние границы, структуры сложности и т.д.).
Прекрасное резюме общих черт, общих для алгоритмического мышления и математического мышления, сделано Кнутом [5]. Эти две формы мышления характеризуются такими особенностями, как манипулирование формулами, представление реальности, сведение к более простым проблемам, абстрактное мышление. Заметными различиями в функциях являются способ обработки бесчисленного континуума в математике и способ обработки понятия размера доказательства (вычислительной сложности) в информатике.
Алгоритм Евклида (Элементы, Книга 7) для вычисления наибольшего общего делителя (gcd) двух целых чисел является прекрасным примером современного понятия алгоритма. Он отображает все свойства и функции, связанные с установлением правильности и вычислительной сложности. Один измеряет вычислительную сложность алгоритма, выражая количество основных шагов, предпринятых алгоритмом для решения задачи, в терминах размеров входных данных (и размеров всех промежуточных результатов). В общем, максимальное количество шаги, выполняемые по всем возможным входным данным по асимптотически большим входным данным, используются в качестве верхней границы и служат для характеристики поведения алгоритма.
Эта мера, выраженная как функция размера входных данных, известна как наихудшая асимптотическая (временная) сложность алгоритма. Размер элемента обычно равен количеству двоичных битов, необходимых для кодирования элемента. Пусть размеры двух входных целых чисел x, y равны n битам. Евклидов алгоритм gcd для получения gcd(x, y) требует количества шагов (или квивалентно времени), пропорционального O(n3). Таким образом, вычислительная сложность алгоритма евклидова gcd называется кубической по размеру входных данных. Алгоритм, сложность которого полиномиальна по размеру входных данных, считается хорошим.
Задача, допускающая алгоритм полиномиального времени, считается выполнимой или простой. С другой стороны, существует большое количество
проблем, которые не кажутся легкими (т.е. они не кажутся разрешимыми с помощью алгоритма полиномиального времени). Рассмотрим график математической структуры:
G = (V, E) - граф,
где V - множество из n вершин, а E представляет собой набор ребер (подмножество множества n(n – 1)/2 пар вершин). Размер входных данных в случае графа пропорционален количеству вершин и ребер и ограничен O(n2). Например, проблема определения того, имеет ли граф G гамильтонов цикл (циклический обход ребер графа, посещающих каждую вершину ровно один раз), не кажется простой в приведенном выше техническом смысле. Ясно, перечисляя все возможные n! перестановки вершин и проверка возможности обхода графа по ребрам в соответствии с вершиной перестановка, можно решить проблему. Очевидно, что этот алгоритм использует подход грубой силы, заключающийся в исчерпывающем перечислении всех возможных решений. Вычислительная сложность экспоненциальна по числу вершин, так как функция n! растет примерно как O(nn + 1/2exp–n).