Студента Группы ПР – 101(К) Савченко А.А Проверила Малыгина Г.С. - презентация

1

2 Студента Группы ПР – 101(К) Савченко А.А Проверила Малыгина Г.С.

3 ( Комбинаторный анализ ) раздел математики, изучающий дискретные объекты, множества ( сочетания, перестановки, размещения и перечисления э лементов ) и отношения на них ( например, частичного порядка ). Комбинаторика связана со многими другими областями математики алгеброй, геометрией, теорией вероятностей, и имеет широкий спектр применения в различных областях знаний ( например в генетике, информатике, статистической физике ). математики множества сочетания перестановки размещения перечисления частичного порядка математики алгеброй геометрией теорией вероятностей генетике информатике статистической физике Термин « комбинаторика » был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд « Рассуждения о комбинаторном искусстве ». Лейбницем1666 году

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

5 Комбинаторика – от латинского слова combinare, что означает «соединять, сочетать». Методы комбинаторики находят широкое применение в физике, химии, биологии, экономики и др. областях знания. Комбинаторику можно рассматривать как часть теории множеств – любую комбинаторную задачу можно свести к задаче о конечных множествах и их отображениях.

6 1. Начальный уровень. Задачи поиска хотя бы одного решения, хотя бы одного расположения объектов, обладающих заданным свойствами - отыскание такого расположения десяти точек на пяти отрезках, при котором на каждом отрезке лежит по четыре точки; - такого расположения восьми ферзей на шахматной доске, при котором они не бьют друг друга. Иногда удаётся доказать, что данная задача не имеет решения (например, нельзя расположить 10 шаров в 9 урнах так, что бы в каждой урне было не более одного шара – хотя бы в одной урне окажется не менее двух шаров). 6

7 2. Второй уровень. Если комбинаторная задача имеет несколько решений, то возникает вопрос о подсчете числа таких решений, описании всех решений данной задачи. 3. Третий уровень. Решения данной комбинаторной задачи отличаются друг от друга некоторыми параметрами. В этом случае возникает вопрос отыскания оптимального варианта решения такой задачи. Например: Путешественник хочет выехать из города А, посетить города В, С, и D. После чего вернуться в город А. 7

8 ПутьДлина путиПутьДлина пути ABCDA1555ACDBA1300 ABDCA1300ADBCA1450 ACBDA1450ADCBA С В А D На рис. изображена схема путей, связывающих эти города. Различные варианты путешествий отличаются друг от друга порядком посещения городов В, С, и.D. Существует шесть вариантов путешествия. В таблице указаны варианты и длин каждого пути:

9 1. Сколько различных коктейлей можно составить из четырёх напитков, смешивая их в равных количествах по два ? AB, AC, AD, BC, BD, CD – всего 6 коктейлей 2. Сколько различных двузначных чисел можно составить из цифр 0, 1, 2, 3 ? Первой цифрой двузначного числа может одна из цифр 1, 2, 3 (цифра 0 не может быть первой). Если первая цифра выбрана, то вторая может быть любая из цифр 0, 1, 2, 3. Т.к. каждой выбранной первой соответствует четыре способа выбора второй, то всего имеется = 4·3 = 12 различных двузначных чисел. 9 А D С В

10 2. Сколько различных двузначных чисел можно составить из цифр 0, 1, 2, 3 ? = 4·3 = 12 различных двузначных чисел. Первая цифра вторая цифра

11 11 1.Сколькими с пособами м огут б ыть р асставлены 4 у частниц ф инального забега н а ч етырёх б еговых д орожках ? Р п = 4· 3 ·2 ·1= 24 способа (перестановки из 4-х элементов) дорожка 2 доржка 3доржка 4 дор. Р е ш е н о п е р е б о р о м в а р и а н т о в

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

13

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

15 Этот раздел отвечает на вопросы вида : какова вероятность присутствия определённого свойства у заданного множества.

16 Первые работы, в которых зарождались основные понятия теории вероятностей, представляли собой попытки создания теории азартных игр ( Кардано, Гюйгенс, Паскаль, Ферма и другие в XVIXVII вв.). Следующий этап развития теории вероятностей связан с именем Якоба Бернулли ( ). Доказанная им теорема, получившая впоследствии название « Закона больших чисел », была первым теоретическим обоснованием накопленных ранее фактов. Дальнейшими успехами теория вероятностей обязана Муавру, Лапласу, Гауссу, Пуассону и др. Новый, наиболее плодотворный период связан с именами П. Л. Чебышева ( ) и его учеников А. А. Маркова ( ) и А. М. Ляпунова ( ). В этот период теория вероятностей становится стройной математической наукой. Ее последующее развитие обязано в первую очередь русским и советским математикам ( С. Н. Бернштейн, В. И. Романовский, А. Н. Колмогоров, А. Я. Хинчин, Б. В. Гнеденко, Н. В. Смирнов и др.). В настоящее время ведущая роль в создании новых ветвей теории вероятностей также принадлежит советским математикам.

17 1. В. Ф. Бутузов, Ю. М. Колягин, Г. Л. Луканкин, Э. Г. Позняк и др. «Математика» учебное пособие для 11 кл общеобразовательных учреждений / рекомендовано Министерством образования РФ / М., Просвещение, Е. А. Бунимович, В. А. Булычёв : «Вероятность и статистика», пособие для общеобразовательных учебных заведений 5 – 9 классы / допущено Министерством образования Российской Федерации // Дрофа Москва Н. Я. Виленкин, Р. С. Гутер, С. И. Шварцбурд, Б. В. Овчинский, В. Г. Ашкенузе : «Алгебра» учебное пособие для IX – X классов средних школ с математической специализацией» / второе издание, «Просвещение», Москва – 240) 4. Ю. Н. Макарычев, Н. Г. Миндюк «Алгебра : элементы статистики и теории вероятностей 7 – 9 классы» Под редакцией С. А. Теляковского М : Просвещение, 2006 г 5. Н. Я. Виленкин : «Индукция. Комбинаторика». Пособие для учителей. М., «Просвещение», В. Л. Лютикас : «Школьнику о теории вероятностей» Учебное пособие по факультативному курсу для учащихся 8 – 10 классов,/ М., «Просвещение» Журналы «Математика в школе» : 10 – 2003 г, 5 – 2004 г, 6 – 2004 г, 7 – 2004 г. 6. Математика классы 17

18 Спасибо за Внимание !