Комбинаторика ( Комбинаторный анализ ) раздел математики, изучающий дискретные объекты, множества ( сочетания, перестановки, размещения и перечисления. - презентация

1

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

3 Термин « комбинаторика » был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд « Рассуждения о комбинаторном искусстве ». Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов. Готфрид Вильгельм фон Лейбниц - немецкий философ, математик, юрист, дипломат

4 Древний период Комбинаторные мотивы можно заметить в символике китайской « Книги Перемен » (V век до н. э.). По мнению её авторов, всё в мире комбинируется из различных сочетаний мужского и женского начал, а также восьми стихий : земля, горы, вода, ветер, гроза, огонь, облака и небо. Историки отмечают также комбинаторные проблемы в руководствах по игре в Го и другие игры. Большой интерес математиков многих стран с древних времён неизменно вызывали магические квадраты. Классическая задача комбинаторики : « сколько есть способов извлечь m элементов из N возможных » упоминается ещё в сутрах древней Индии ( начиная примерно с IV века до н. э.). Индийские математики, видимо, первыми открыли биномиальные коэффициенты и их связь с биномом Ньютона. Во II веке до н. э. индийцы знали, что сумма всех биномиальных коэффициентов степени n равна 2 n.

5 Античные греки также рассматривали отдельные комбинаторные задачи, хотя систематическое изложение ими этих вопросов, если оно и существовало, до нас не дошло. Хрисипп (III век до н. э.) и Гиппарх (II век до н. э.) подсчитывали, сколько следствий можно получить из 10 аксиом ; методика подсчёта нам неизвестна, но у Хрисиппа получилось более миллиона, а у Гиппарха более Аристотель при изложении своей логики безошибочно перечислил все возможные типы трёхчленных силлогизмов. Аристоксен рассмотрел различные чередования длинных и коротких слогов в стихотворных размерах. Какие - то комбинаторные правила пифагорейцы, вероятно, использовали при построении своей теории чисел и нумерологии ( совершенные числа, фигурные числа, пифагоровы тройки и др.). Магический квадрат на гравюре Дюрера «Меланхолия»

6 Средневековье В XII веке индийский математик Бхаскара в своём основном труде « Лилавати » подробно исследовал задачи, связанные с перестановками и сочетаниями, включая перестановки с повторениями. В Западной Европе ряд глубоких открытий в области комбинаторики сделали два еврейских исследователя, Авраам ибн Эзра (XII век ) и Леви бен Гершом ( он же Герсонид, XIV век ). Ибн Эзра обнаружил симметричность биномиальных коэффициентов, а Герсонид дал явные формулы для их подсчёта и применения в задачах вычисления числа размещений и сочетаний. Несколько комбинаторных задач содержит « Книга абака » ( Фибоначчи, XIII век ). Например, он поставил задачу найти наименьшее число гирь, достаточное для взвешивания любого товара весом от 1 до 40 фунтов.

7 Новое время Джероламо Кардано написал математическое исследование игры в кости, опубликованное посмертно. Теорией этой игры занимались также Тарталья и Галилей. В историю зарождавшейся теории вероятностей вошла переписка заядлого игрока шевалье де Мерэ с Пьером Ферма и Блезом Паскалем, где были затронуты несколько тонких комбинаторных вопросов. Помимо азартных игр, комбинаторные методы использовались ( и продолжают использоваться ) в криптографии как для разработки шифров, так и для их взлома. Джероламо ( Джироламо, Иероним ) Кардано - итальянский математик, инженер, философ, медик и астролог, в его честь назван карданный вал

8 Блез Паскаль много занимался биномиальными коэффициентами и открыл простой способ их вычисления : « треугольник Паскаля ». Хотя этот способ был уже известен на Востоке ( примерно с X века ), Паскаль, в отличие от предшественников, строго изложил и доказал свойства этого треугольника. Наряду с Лейбницем, он считается основоположником современной комбинаторики. Сам термин « комбинаторика » придумал Лейбниц, который в 1666 году ( ему было тогда 20 лет ) опубликовал книгу « Рассуждения о комбинаторном искусстве ». Правда, термин « комбинаторика » Лейбниц понимал чрезмерно широко, включая в него всю конечную математику и даже логику. Ученик Лейбница Якоб Бернулли, один из основателей теории вероятностей, изложил в своей книге « Искусство предположений » (1713) множество сведений по комбинаторике. Блез Паскаль - французский математик, физик, лит ератор и философ.

9 В этот же период формируется терминология новой науки. Термин « сочетание » ( combination ) впервые встречается у Паскаля (1653, опубликован в 1665 году ). Термин « перестановка » ( permutation ) употребил в указанной книге Якоб Бернулли ( хотя эпизодически он встречался и раньше ). Бернулли использовал и термин « размещение » ( arrangement ). После появления математического анализа обнаружилась тесная связь комбинаторных и ряда аналитических задач. Абрахам де Муавр и Джеймс Стирлинг нашли формулы для аппроксимации факториала. Окончательно комбинаторика как самостоятельный раздел математики оформилась в трудах Эйлера. Он детально рассмотрел, например, следующие проблемы.: Задача о ходе коня Задача о семи мостах, с которой началась теория графов Построение греко - латинских квадратов Обобщённые перестановки Кроме перестановок и сочетаний, Эйлер изучал разбиения, а также сочетания и размещения с условиями. Внимание к конечной математике и, в частности, к комбинаторике значительно повысилось со второй половины XX века, когда появились компьютеры. Сейчас это чрезвычайно содержательная и быстроразвивающаяся область математики.

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

11 Структурная комбинаторика К данному разделу относятся некоторые вопросы теории графов, а также теории матроидов. Экстремальная комбинаторика Примером этого раздела может служить следующая задача : какова наибольшая размерность графа, удовлетворяющего определённым свойствам. Теория Рамсея Теория Рамсея изучает наличие регулярных структур в случайных конфигурациях элементов. Примером утверждения из теории Рамсея может служить следующее : в группе из 6 человек всегда можно найти трёх человек, которые либо попарно знакомы друг с другом, либо попарно незнакомы. В терминах структурной комбинаторики это же утверждение формулируется так : в любом графе с 6 вершинами найдётся либо клика, либо независимое множество размера 3.

12 Вероятностная комбинаторика Этот раздел отвечает на вопросы вида : какова вероятность присутствия определённого свойства у заданного множества. Топологическая комбинаторика Аналоги комбинаторных концепций и методов используются и в топологии, при изучении дерева принятия решений, частично упорядоченных множеств, раскрасок графа и др.

13 Комбинаторика, и в частности, теория Рамсея, содержит много известных открытых проблем, подчас с весьма несложной формулировкой. Например, неизвестно, при каком наименьшем N в любой группе из N человек найдутся 5 человек, либо попарно знакомых друг с другом, либо попарно незнакомых ( хотя известно, что 49 человек достаточно ).

14 Для формулировки и решения комбинаторных задач используют различные модели комбинаторных конфигураций. Примерами комбинаторных конфигураций являются : Размещением из n элементов по k называется упорядоченный набор из k различных элементов некоторого n - элементного множества. Перестановкой из n элементов ( например чисел 1,2,…, n ) называется всякий упорядоченный набор из этих элементов. Перестановка также является размещением из n элементов по n. Сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Наборы, отличающиеся только порядком следования элементов ( но не составом ), считаются одинаковыми, этим сочетания отличаются от размещений. Композицией числа n называется всякое представление n в виде упорядоченной суммы целых положительных чисел. Разбиением числа n называется всякое представление n в виде неупорядоченной суммы целых положительных чисел.

15 Примерами комбинаторных задач являются : Сколькими способами можно разместить n предметов по m ящикам так, чтобы выполнялись заданные ограничения ? Сколько существует функций F из m - элементного множества в n - элементное, удовлетворяющих заданным ограничениям ? Сколько существует различных перестановок из 52 игральных карт ? Ответ : 52! (52 факториал ) то есть или примерно × При игре в кости бросаются две кости и выпавшие очки складываются, сколько существует комбинаций, таких, что сумма очков на верхних гранях равна двенадцати ? Решение : Каждый возможный исход соответствует функции ( аргумент функции - это номер кости, значение - очки на верхней грани ). Очевидно, что лишь 6+6 даёт нам нужный результат 12. Таким образом существует лишь одна функция, ставящая в соответствие 1 число 6, и 2 число 6. Или, другими словами, существует всего одна комбинация, такая, что сумма очков на верхних гранях равна двенадцати.

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

17 Возникновение теории вероятностей как науки относят к средним векам и первым попыткам математического анализа азартных игр ( орлянка, кости, рулетка ). Первоначально её основные понятия не имели строго математического вида, к ним можно было относиться как к некоторым эмпирическим фактам, как к свойствам реальных событий, и они формулировались в наглядных представлениях.

18 Самые ранние работы учёных в области теории вероятностей относятся к XVII веку. Исследуя прогнозирование выигрыша в азартных играх, Блез Паскаль и Пьер Ферма открыли первые вероятностные закономерности, возникающие при бросании костей. Под влиянием поднятых и рассматриваемых ими вопросов решением тех же задач занимался и Христиан Гюйгенс. При этом с перепиской Паскаля и Ферма он знаком не был, поэтому методику решения изобрёл самостоятельно. Его работа, в которой вводятся основные понятия теории вероятностей ( понятие вероятности как величины шанса ; математическое ожидание для дискретных случаев, в виде цены шанса ), а также используются теоремы сложения и умножения вероятностей ( не сформулированные явно ), вышла в печатном виде на двадцать лет раньше (1657 год ) издания писем Паскаля и Ферма (1679 год )

19 Важный вклад в теорию вероятностей внёс Якоб Бернулли : он дал доказательство закона больших чисел в простейшем случае независимых испытаний. В первой половине XIX века теория вероятностей начинает применяться к анализу ошибок наблюдений ; Лаплас и Пуассон доказали первые предельные теоремы. Во второй половине XIX века основной вклад внесли русские учёные П. Л. Чебышев, А. А. Марков и А. М. Ляпунов. В это время были доказаны закон больших чисел, центральная предельная теорема, а также разработана теория цепей Маркова. Современный вид теория вероятностей получила благодаря аксиоматизации, предложенной Андреем Николаевичем Колмогоровым. В результате теория вероятностей приобрела строгий математический вид и окончательно стала восприниматься как один из разделов математики.

20

21