Комбинаторика Комбинаторный анализ, комбинаторная математика, комбинаторика, - раздел математики, посвященный решению задач выбора и расположения элементов некоторого, обычно конечного, множества в соответствии с заданными правилами. Каждое такое правило определяет способ построения некоторой конструкции из элэментов исходного множества, называемой комбинаторной конфигурацией. Поэтому можно сказать, что целью К.а. является изучение комбинаторных конфигураций, в частности, вопросы их существования, алгоритмы построения, решение задач на перечисление. Примерами комбинаторных конфигураций являются перестановки, размещения и сочетания; блок-схемы и латинские квадраты.
Математический Энциклопедический Словарь. Комбинаторика - один из разделов дискретной математики, который приобрел важное значение в связи с использованием его в теории вероятностей, математической логике, теории чисел, вычислительной технике, кибернетике. В Большой Советской Энциклопедии говорится, что комбинаторика - это раздел математики в котором изучаются некоторые операции над конечными множествами.
Основными и типичными операциями и связанными с ними задачами комбинаторики являются следующие: 1) образование упорядоченных множеств, состоящее в установлении определенного порядка следования элементов множества друг за другом, составление перестановок; 2) образование подмножеств, состоящее в выделении из данного множества некоторой части его элементов, - составление сочетаний; 3) образование упорядоченных подмножеств - составление размещений.
ТИПЫ КОМБИНАТОРНЫХ ЗАДАЧ.
1. Магический квадрат - квадратная таблица (n * n) целых чисел от 1 до nќ такая, что суммы чисел вдоль любого столбца, любой строки и двух диагоналей таблицы равны одному и тому же числу s=n(nќ+1)/2. Число n называют порядом магического квадрата. Доказано, что магический квадрат можно построить для любого n ™ 3. Уже в средние века был известен алгоритм построения магических квадратов нечетного порядка. Существуют магические квадраты, удоволетворяющие ряду дополнительных условий, например магический квадрат с n=8 , который можно разделить на четыре меньших магических квадрата 4x4. В Индии и некоторых других странах магические квадраты употреблялись как талисманы. Однако общей теории магических квадратов не существует. Неизвестно даже общее число магических квадратов порядка n.
2. Латинский квадрат - квадратная матрица порядка n, каждая строка и каждый столбец которой являются перестановками элементов конечного множества S, состоящего из n элементов.
3. Задача размещения - одна из классических комбинаторных задач, в которой требуется определить число способов размещения m различных предметов в n различных ячейках с заданным числом r пустых ячеек. Это число равно
4. Задача коммивояжера, задача о бродячем торговце - комбинаторная задача теории графов. В простейшем случае формулируется следующим образом: даны n городов и известно расстояние между каждыми двумя городами; коммивояжер, выходящий из какого-нибудь города, должен посетить n-1 других городов и вернуться в исходный. В каком порядке должен он посещять города ( по одному разу каждый ) чтобы общее пройденное расстояние было минимальным ? Методы решения задачи коммивояжера, по существу, сводятся к организации полного перебора вариантов.
МЕТОДЫ РЕШЕНИЯ КОМБИНАТОРНЫХ ЗАДАЧ
1. Метод рекуррентных соотношений. Метод рекуррентных соотношений состоит в том, что решение комбинаторной задачи с n предметами выражается через решение аналогичной задачи с меньшим числом предметов с помощью некоторого соотношения, которое называется рекуррентным. Пользуясь этим соотношением, искомую величину можно вычислить, исходя из того, что для небольшого количества предметов решение задачи легко находится.
2. Метод включения и исключения. Пусть N(A) - число элементов множества A. Тогда методом математической индукции можно доказать, что
N(A1 U A2 U ... An) = N(A1) + ... + N(An) - {N(A1 П A2) + ... + N(An-1 П An)} + + {N(A1 П A2 П A3) + ... + N(An-2 П An-1 П An)} - ... ... +(-1)^n-1*N(A1 П A2 П ... П An-1 П An). Метод подсчета числа элементов объединения множеств по этой формуле, состоящий в поочередном сложении и вычитании, называется методом включения и исключения.
3. Метод траекторий. Для многих комбинаторных задач можно указать такую геометрическую интерпретацию, которая сводит задачу к подсчету числа путей (траекторий), обладающих определенным свойством.
Рефераты по теме комбинаторика стастистика и теория вероятностей. Комбинаторика понятие и использование в морфологическом анализе. Уроки и презентации по теме Комбинаторика и теория вероятностей. Комбинаторика правило включения и исключения. Метод включений и исключений комбинаторика. Метод решения комбинаторных задач примеры. Элементы комбинаторики решение задач. Методы решения комбинаторной задаче. Комбинаторика примеры решения задач. Рефераты по элементам комбинаторики. Комбинаторика задачи на размещение. Презентация задачи на перестановку. Предметы и задачи комбинаторики. Поочередный выбор комбинаторика. Решения задач по комбинаторике.
