3.1. Комбинаторные вычисления

При решении теоретико-множественных задач большое значение имеет определение мощности конечных множеств.

Очевидно, что |AB|=|A|+|B|–|AB|, т.е., когда А и В в «общем положении», т.е. пересекаются.

Кроме того, |A\B|=|A|–|B|, когда А включается в В, |A\B|=|A|–|AB|, когда А и В в «общем положении», т.е. пересекаются.

Нетрудно заметить, что |AB|=|A|+|B|–2|AB|.

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

Пусть в базе данных имеется n записей об объектах недвижимости (например, квартирах) в виде запроса (что требуется) и предложения (что имеется) Требуется найти такие пары записей, в которых предложение первой записи совпадает с запросом второй и, наоборот, предложение второй записи совпадает с запросом первой («подбор вариантов обмена»).

Допустим, на проверку варианта обмена тратится одна миллисекунда. Можно показать, что при сравнении каждой записи с каждой требуется n(n-1)/2 сравнений.

Например, n=8:

(1,2),(1,3),(1,4),(1,5),(1,6),(1,7),(1,8),

(2,3),(2,4),(2,5),(2,6),(2,7),(2,8),

(3,4),(3,5),(3,6),(3,7),(3,8),

(4,5),(4,6),(4,7),(4,8),

(5,6),(5,7),(5,8),

(6,7),(6,8),(7,8) – всего 28 вариантов: 8´7/2=28=7+6+5+4+3+2+1. Здесь отношение сравнения симметрично и сам с собой вариант не сравнивается.

Если n=100, то при указанном быстродействии, на сравнения уйдет 4,95 секунды. Но, если n=100000 (в задачах реальной размерности), то необходимо 1999950 секунд, т.е. без малого – 1389 часов! Столько ждать клиент вряд ли будет. Это и есть «проклятие размерности». И это только сравнение прямых вариантов, а существуют варианты, в которых число участников сделки больше двух.

Поэтому комбинаторные вычисления требуют предварительного анализа и ориентировочной количественной оценки исходных данных. Иначе, можно подумать, что компьютер просто «завис» и не выдаёт ответа. Здесь речь идет о сложности вычислений в смысле времени решения. В ряде задач комбинаторной сложности необходимо время, сравнимое с геологическими эпохами. Но есть еще и пространственная сложность – в смысле объема памяти. Ведь промежуточные результаты часто надо где-то хранить. В ряде задач требуется объем памяти, превышающий количество атомов во Вселенной.

Основным инструментом такого анализа сложности вычислений и является комбинаторика.