Формальные системы и алгоритмы.
Формальные системы оказываются столь же мощным средством для задания конструктивных объектов, что и алгоритмы. С их помощью можно имитировать поведение машин Тьюринга, т. е. строить формальные системы, в некотором смысле аналогичные алгоритмам. Возможны две концепции построения системы основных понятий, формализующих идеи эффективности и конструктивности. Концепция, описанная ранее и являющаяся исторически первой, кладет в основу понятие алгоритма. Вторая концепция, созданная Э. Постом, опирается на понятий формальной (конкретнее, канонической) системы и перечислимого множества, которое определяется просто как множество теорем формальной системы. Нормальную каноническую систему над алфавитом А можно представить как граф с одной выделенной вершиной — аксиомой, остальные вершины которого помечены словами в A—теоремами, ребра — это применения продукций, а пути из выделенной вершины в данную—возможные выводы данного слова. Множество слов в А, порождаемое системой,— это множество всех вершин графа, помеченных словами в А. Алгоритм — это формальная система особого, детерминированного вида, характеризующаяся тем, что в ней к каждой теореме применима не более чем одна продукция. Соответствующий граф представляет собой цепочку, изображающую вычислительный процесс; аксиома в таком графе — это просто исходные данные алгоритма.
|
|
Другой способ детерминизации формальных систем — это фиксация порядка применения правил вывода. Например, нормальный алгоритм Маркова — это упорядоченная система подстановок с двумя дополнительными соглашениями.
Основной акцент «алгоритмической» концепции — в ее детерминизме. Поэтому она естественна и удобна при описания вычислительных процессов и устройств. Основной акцент «формально-системной» концепции — в компактности конструктивного описания множеств.
Комбинаторика, — раздел математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного,, множества в соответствии с заданными правила-; ми. Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множества, называемой комбинаторной конфигурацией. Поэтому целями комбинаторного анализа являются изучение комбинаторных конфигураций, алгоритмов их построения, оптимизация таких алгоритмов, а также решение задач перечисления. Простейшими примерами комбинаторных конфигураций являются перестановки, размещения, сочетания и разбиения.
На практике часто встречаются задачи, в которых необходимо подсчитать число всех возможных способов размещения некоторых предметов конечного множества или число всех возможных способов выполнения определенного действия из конечного множества таких действий. Например, сколькими разными способами можно расставить скобки в выражении а + b + с + d + е + f, если операция + ассоциативна, а буквы а, b, с, d, е, f – некоторые действительные числа? Сколькими способами могут распределиться медали на чемпионате мира по футболу среди шестнадцати команд-участниц финальной группы? Задачи такого типа называются комбинаторными, а методы их решения - методами комбинаторного анализа. Поскольку комбинаторика имеет дело с конечными множествами, то ее часто называют теорией конечных множеств.
|
|
Комбинаторика – раздел математики посвященный подсчёту числа элементов конечного множества. – имеет широкий круг приложений: теория вероятности, теория информации, теория надёжности, алгебраическая топология и алгебра и, наконец, математический анализ. Особенно полезными являются сами комбинаторные рассуждения, они позволяют обойтись без излишнего формализма, и там, где эти принципы срабатывают, получаются красивые и понятные результаты. Ярким примером эффективности комбинаторного подхода является теория бинома Ньютона.