рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Комбинаторика

Комбинаторика - раздел Математика, Комбинаторный Анализ, Комбинаторная Математика, Комбинаторика Раздел Математ...

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

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

Основными и типичными операциями и связанными с ними задачами комбинаторики являются следующие: 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. Метод траекторий. Для многих комбинаторных задач можно указать такую геометрическую интерпретацию, которая сводит задачу к подсчету числа путей (траекторий), обладающих определенным свойством.

– Конец работы –

Используемые теги: Комбинаторика0.04

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Комбинаторика

Что будем делать с полученным материалом:

Если этот материал оказался полезным для Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Еще рефераты, курсовые, дипломные работы на эту тему:

Основные понятия теории вероятностей. Случайное событие. Вероятность. Статистическая вероятность. Геометрическая вероятность. Основные формулы комбинаторики
Случайные события... Случайные события бывают х видов... Невозможные Обозначение V Достоверные Случайные...

Правила суммы и произведения в комбинаторике
Перейти к навигация поиск... Все разнообразие комбинаторных формул может быть выведено из двух основных... Содержание Количество размещений Размещение с повторениями Количество размещений с...

Элементы комбинаторики
На сайте allrefs.net читайте: "Элементы комбинаторики"

Элементы статистики, комбинаторики и теории вероятностей в основной школе
О необходимости изучения в школе элементов теории вероятностей и статистики речь идет очень давно. Ведь именно изучение и осмысление теории вероятностей и статистических проблем… Современная концепция школьного математического образования ориентирована, прежде всего, на учет индивидуальности…

Методика обучения школьников основам комбинаторики, теории вероятностей и математической статистики в рамках профильной школы
Выводы по главе 1 Глава 2. Методика обучения школьников основам комбинаторики, теории вероятностей и математической статистики в рамках профильной… Библиографический списокПриложения Глава 1 Теоретические аспекты обучения… Оно является важнейшим средством дифференциации и индивидуализации обучения, позволяющим за счет изменений в…

0.031
Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • По категориям
  • По работам