Комбинаторный анализ

Формальные системы и алгоритмы.

Формальные системы оказываются столь же мощным средством для задания конструктивных объектов, что и алгоритмы. С их помощью можно имитировать поведение машин Тьюринга, т. е. строить формальные системы, в некотором смысле аналогичные алгоритмам. Возможны две концепции построения системы основных понятий, формализующих идеи эффективности и конструктивности. Концепция, описанная ранее и являющаяся исторически первой, кладет в основу понятие алгоритма. Вторая концепция, созданная Э. Постом, опирается на понятий формальной (конкретнее, канонической) системы и перечислимого множества, которое определяется просто как множество теорем формальной системы. Нормальную каноническую систему над алфавитом А можно представить как граф с одной выделенной вершиной — аксиомой, остальные вершины которого помечены словами в A—теоремами, ребра — это применения продукций, а пути из выделенной вершины в данную—возможные выводы данного слова. Множество слов в А, порождаемое системой,— это множество всех вершин графа, помеченных словами в А. Алгоритм — это формальная система особого, детерминированного вида, характеризующаяся тем, что в ней к каждой теореме применима не более чем одна продукция. Соответствующий граф представляет собой цепочку, изображающую вычислительный процесс; аксиома в таком графе — это просто исходные данные алгоритма.

Другой способ детерминизации формальных систем — это фиксация порядка применения правил вывода. Например, нормальный алгоритм Маркова — это упорядоченная система подстановок с двумя дополнительными соглашениями.

Основной акцент «алгоритмической» концепции — в ее детерминизме. Поэтому она естественна и удобна при описания вычислительных процессов и устройств. Основной акцент «формально-системной» концепции — в компактности конструктивного описания множеств.

Комбинаторика, — раздел математики, посвященный реше­нию задач выбора и расположения элементов некоторого, обыч­но конечного,, множества в соответствии с заданными правила-; ми. Каждое такое правило определяет способ построения неко­торой конструкции из элементов исходного множества, называ­емой комбинаторной конфигурацией. Поэтому целями комбина­торного анализа являются изучение комбинаторных конфигу­раций, алгоритмов их построения, оптимизация таких алгорит­мов, а также решение задач перечисления. Простейшими при­мерами комбинаторных конфигураций являются перестановки, размещения, сочетания и разбиения.

На практике часто встречаются задачи, в которых необходимо подсчитать чис­ло всех возможных способов размещения некоторых предметов конечного множества или число всех возможных способов выполнения определенного действия из конечного множества таких действий. Например, сколькими раз­ными способами можно расставить скобки в выражении а + b + с + d + е + f, если операция + ассоциативна, а буквы а, b, с, d, е, f – некоторые действи­тельные числа? Сколькими способами могут распределиться медали на чем­пионате мира по футболу среди шестнадцати команд-участниц финальной группы? Задачи такого типа называются комбинаторными, а методы их ре­шения - методами комбинаторного анализа. Поскольку комбинаторика имеет дело с конечными множествами, то ее часто называют теорией конеч­ных множеств.

Комбинаторика – раздел математики посвященный подсчёту числа элементов конечного множества. – имеет широкий круг приложений: теория вероятности, теория информации, теория надёжности, алгебраическая топология и алгебра и, наконец, математический анализ. Особенно полезными являются сами комбинаторные рассуждения, они позволяют обойтись без излишнего формализма, и там, где эти принципы срабатывают, получаются красивые и понятные результаты. Ярким примером эффективности комбинаторного подхода является теория бинома Ньютона.