Презентация на тему "комбинаторика". Презентация на тему:Элементы Комбинаторики!!! Презентация на тему применение комбинаторики в играх

Описание презентации по отдельным слайдам:

1 слайд

Описание слайда:

Комбинаторика Подготовили учащиеся МБОУ СОШ № 7 г. Мичуринска Большакова Д. , Щербинина М. Учитель Духанина О.С.

2 слайд

Описание слайда:

Ход исследования: Что такое комбинаторика Что же послужило толчком для возникновения и развития комбинаторики Где в практической деятельности человека встречается комбинаторика Задачи Социологический опрос Вывод

3 слайд

Описание слайда:

4 слайд

Описание слайда:

Что такое Комбинаторика? Комбинаторика – раздел математики, в котором изучаются вопросы о том, сколько различных комбинаций, подчиненных тем или иным условиям, можно составить из заданных объектов. Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве». Комбинаторика (от латинского combinare) означает “соединять, сочетать”.

5 слайд

Описание слайда:

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

6 слайд

Описание слайда:

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

7 слайд

Описание слайда:

Сферы применения Выбором объектов и расположением их в том или ином порядке приходится заниматься чуть ли не во всех областях человеческой деятельности, например: химику, изучающему строение органических молекул, имеющих данный атомный состав. ученому-агроному, планирующему распределение сельскохозяйственных культур на нескольких полях конструктору, разрабатывающему новую модель механизма

8 слайд

Описание слайда:

Задача №1 Государственные флаги многих стран состоят из горизонтальных или вертикальных полос разных цветов. Сколько существует различных флагов, состоящих из двух горизонтальных полос одинаковой ширины и разного цвета – белого, красного и синего? Решение: Пусть верхняя полоса флага – белая (Б). Тогда нижняя полоса может быть красной (К) или синей (С). Получили две комбинации – два варианта флага. Если верхняя полоса флага – красная, то нижняя может быть белой или синей. Получим ещё два варианта флага. Пусть, наконец, верхняя полоса – синяя, тогда нижняя может быть белой или красной. Это ещё два варианта флага. Всего получили 3 2 = 6 комбинаций – шесть вариантов флагов.

9 слайд

Описание слайда:

Задача №2 Сколько трехзначных чисел можно составить из цифр 1, 3, 5, 7? Используя в записи числа каждую из них не более одного раза. Решение: Чтобы ответить на этот вопрос, выпишем все такие числа. Пусть на первом месте стоит цифра 1. На втором месте может быть записана любая из цифр 3, 5, 7. Запишем, например, на втором месте цифру 3. Тогда в качестве третьей цифры можно взять 5 или 7. Получим два числа 135 и 137. Если на втором месте записать цифру 5, то в качестве третьей цифры можно взять цифру 3или 7. В этом случае получим числа 153 и 157. Если же, наконец, на втором месте записать цифру 7, то получим числа 173 и 175. Итак, мы составили все числа, которые начинаются с цифры 1. Таких чисел шесть: 135, 137, 153, 157, 173, 175. Аналогичным способом можно составить числа, которые начинаются с цифры 2,с цифры 5, с цифры 7. Полученные результаты запишем в четыре строки, в каждой из которых шесть чисел: 135, 137, 153, 157, 173, 175, 315, 317, 351, 357, 371, 375, 513, 517, 531, 537, 571, 573, 713, 715, 731, 735, 751, 753, Таким образом, из цифр 1, 3, 5, 7 (без повторения цифр) можно составить 24 трехзначных числа.

10 слайд

Описание слайда:

Дерево возможных вариантов 1 5 7 3 1 3 3 7 5 7 1 5 7 1 3 7 1 3 5 7 5 3 5 7 1 7 1 5 3 7 1 7 1 3 3 1 5 1 5 3 Всего 24 варианта Всего 24 варианта

11 слайд

Описание слайда:

Задача №3 Из города А в город В ведут две дороги, из города В в город С – три дороги, из города С до пристани – две дороги. Туристы хотят проехать из города А через города В и С к пристани. Сколькими способами они могут выбрать маршрут? А П С В Решение: Путь из А в В туристы могут выбрать двумя способами. Далее в каждом случае они могут проехать из В в С тремя способами. Значит, имеются 2 3 вариантов маршрута из А в С. Так как из города С на пристань можно попасть двумя способами, то всего существует 2 3 2, т.е. 12 способов выбора туристами маршрута из города А к пристани.

Презентация на тему:Элементы Комбинаторики!!!

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

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

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

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

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

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

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

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

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

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

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

Разделы Комбинаторики!

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

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

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

Перестановки элементов

Дискретный анализ. Комбинаторика. Перестановки. Нумерация перестановок. Отображение. Пример отображения. Нумерация множества. Теорема о лексикографическом переборе перестановок. Прямой алгоритм лексикографического перебора перестановок. Формальное описание алгоритма. Перебор перестановок. Задача о минимальном числе инверсий. Экзаменационные вопросы. Задача о минимуме скалярного произведения. Задача о наибольшей возрастающей подпоследовательности. Перебор перестановок элементарными транспозициями. - Комбинаторика.ppt

Комбинаторика 9 класс

Элементы комбинаторики. Не нужно нам владеть клинком, Не ищем славы громкой. Содержание курса. Тема 1. Знакомство с комбинаторикой. Основное содержание: 1. Какую задачу называют комбинаторной. Перестановка. Тематическое планирование. Обобщающий урок по теме «Элементы комбинаторики». Цель урока: I. Фронтальный опрос. Ход урока. Вопрос 1: Как обозначается произведение чисел от 1 до n? Ответ: Произведение всех натуральных чисел от 1 до n обозначается n! (n! =1 · 2 · 3…n). Вопрос 2: Что называется размещением? По какой формуле вычисляется размещение? Число размещений из n объектов по k обозначают и вычисляют по формуле: - Комбинаторика 9 класс.ppt

Понятие комбинаторики

Комбинаторика. Тонкости. Варианты решения задачи. Область математики. Граф. Дерево возможных вариантов. Комбинаторная задача. Решение элементарных задач. Цифры. 9 правил комбинаторики. Правило произведения. Формула включений и исключений. Решение. Правило размещения. Сигналы. Размещение без повторения. Правило перестановки. Сочетание без повторения. Сочетание с повторением. Капля в море. - Понятие комбинаторики.ppt

Элементы комбинаторики

Тема урока: «элементы комбинаторики» (практикум). Что такое комбинаторика? В чем состоит комбинаторное правило умножения? Что такое перестановки? Записать формулу для нахождения числа перестановок? Что такое факториал? Что такое размещения? Записать формулу для нахождения числа размещений? Что такое сочетания? Записать формулу для нахождения числа сочетаний? В чём различие между перестановками, размещениями и сочетаниями? Подбор комбинаторных задач. Сколько существует способов выбора учащихся для работы на пришкольном участке? Отгадай ребусы. Понятие науки « Комбинаторика». - Элементы комбинаторики.ppt

Комбинаторика и её применение

Комбинаторика и ее применение. Проблемный вопрос. Комбинаторика. Решение комбинаторных задач. Устный счет. Двузначное число. Сколько различных трехзначных чисел можно составить из цифр. Трехзначное число. Сколько четырехзначных чисел можно составить из 4 цифр. Четырехзначное число. Обществознание и математика. Расписание на вторник. Ученик. Обед. Сколько различных комбинаций одежды имеется у Светланы. Костюм. На полке лежат 3 книги. Решение. Опыт с листом бумаги. Складывание. Самостоятельная работа. Владелец золотой медали. Области применения комбинаторики. Химия. Комбинаторика вокруг нас. - Комбинаторика и её применение.ppt

Комбинаторика и теория вероятности

Введение в комбинаторику и теорию вероятностей. Комбинаторика. Дерево вариантов. Квадратные числа. Треугольные числа. Прямоугольные и непрямоугольные числа. Факториал. Перестановки. Восемь участниц финального забега. Цифры. Трёхтомник одного автора. Размещения. Из 12 учащихся нужно отобрать по одному человеку. Все цифры различны. Сколько существует трёхзначных чисел. Сочетания. Треугольник Паскаля. Сколькими способами можно выбрать трёх дежурных. Выбор букета. Три помидора. Частота и вероятность. Определение. Выбирается один шар. Два игральных кубика. Сложение вероятностей. - Комбинаторика и теория вероятности.ppt

Соединения в комбинаторике

Виды соединений в комбинаторике. Знакомство с теорией соединений. Раздел математики. Возникновение комбинаторики. Метод решения комбинаторных задач. Полный перебор. Встретились пятеро. Правило произведения. Обобщение правила произведения. Основные задачи комбинаторики. Виды соединений. Перестановки. Размещения. 8 участниц финального забега. Сочетания. Букет. Бином Ньютона. Разные стороны. Лишних знаний не бывает. - Соединения в комбинаторике.ppt

Комбинации

Комбинаторные задачи. Перестановки Размещения Сочетания (выборки). Самостоятельная работа. Самостоятельная работа состояла из 2 заданий. Работу писали 27 учащихся. Задачу правильно решили 13 уч., а пример-17. не справились с работой 3 ученика. Сколько учеников успешно решили самостоятельную работу. Контрольная работа состояла из задачи и примера. Работу писали 30 уч. Первое задание правильно решили 14 уч., а второе -13. не справились с контрольной 4 ученика. Сколько учеников успешно решили контрольную работу. Задача №1. Решение: АВС, АСВ, ВАС,ВСА,САВ,СВА 6 комбинаций. Перестановки: Задача №2. - Комбинации.ppt

Размещение элементов

Комбинаторика. Размещение и сочитание. Размещение. Сочетание. В комбинаторике сочетанием из n по k называется набор k элементов, выбранных из данных n элементов. Формулы: Для любых натуральных чисел n и k где n>k,справедливы равенства: Для числа выборов двух элементов из n данных: - Размещение элементов.ppt

Формулы для перестановок, сочетаний, размещений

Формулы для подсчёта количества перестановок. Подарок. Перестановки. Количество перестановок. Размещения. Количество размещений. Сочетания. Количество сочетаний. Слово «факториал». Очередь. Лесник. - Формулы для перестановок, сочетаний, размещений.ppt

Комбинаторные задачи

Комбинаторные задачи. Из цифр 1, 5, 9 составить все трёхзначные числа без повторяющихся цифр. №2. Дерево возможных вариантов. - Комбинаторные задачи.ppt

Задачи по комбинаторике

Комбинаторика. Правило сложения Правило умножения. Задача №1. Сколькими способами можно выбрать одну книгу. Решение: 30 + 40 = 70 (способами). Правило суммы. Задача № 2. Задача № 3. Пусть существует три кандидата на пост командира и 2 на пост инженера. Сколькими способами можно сформировать экипаж корабля, состоящий из командира и инженера? Решение: 3 * 2 = 6 (способ). Правило умножения. - Задачи по комбинаторике.ppt

«Комбинаторные задачи» 9 класс

Комбинаторные задачи и начальные сведения из теории вероятностей. Примерное планирование. Комбинаторные задачи. Способы решения комбинаторных задач. У Ирины пять подруг: Вера, Зоя, Марина, Полина и Светлана. Составьте все возможные трёхзначные числа. Определение. Множество, состоящее из любых К элементов. В каком порядке указаны элементы. Начальные сведения из теории вероятности. На полке стоят 12 книг, из которых 4 – это учебники. - «Комбинаторные задачи» 9 класс.ppt

Примеры комбинаторных задач

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

Решение комбинаторных зада

Решение комбинаторных задач. Что такое комбинаторика. Из истории комбинаторики. Число различных комбинаций. Лейбниц. Простые и наглядные методы. Методы решения комбинаторных задач. Правило суммы. Правило произведения. Сколько среди них чисел, кратных 11. Сколько существует способов. Сколько различных трехзначных чисел. Флаг в виде четырех горизонтальных полос. Общее количество вариантов. Сколько всего стран. Крестики и нолики. Разные значки. Сколькими способами можно посадить шестерых школьников. Коля сидит на краю. Четырехзначные числа. На входной двери дома установлен домофон. - Решение комбинаторных зада.ppt

Комбинаторные задачи и их решения

Комбинаторные задачи и их решения. Пояснительная записка. Углубление знаний учащихся. Появление стохастической линии. Требования к уровню подготовки. Учебно-тематический план. Содержание программы. Поурочное планирование. Презентации. Школьнику о теории вероятностей. - Комбинаторные задачи и их решения.ppt

Методы решения комбинаторных задач

Решение комбинаторных задач с помощью графов. Вопросы к уроку. Чем занимается комбинаторика. Что такое граф. Примеры графов. Задача. Пример полного графа. Конверт. Ужасные грабители. Число. Сколько трёхзначных чисел можно составить. Цифры в записи числа. Сколькими способами вы можете рассадить 3-х гостей на 3-х разноцветных табуретках. Правило произведения. Имеющиеся места. Способы. Расписание на пятницу. - Методы решения комбинаторных задач.ppt

Число вариантов

Комбинаторные задачи. Комбинаторика. Выбор. Расположение. Перестановки. Способы решения комбинаторных задач: Таблица вариантов Дерево вариантов Правило умножения. 1. Дерево вариантов. Из чисел 1, 5, 9 составить трёхзначное число без повторяющихся цифр. 2 комбинации. Всего 2 3=6 комбинаций. Сколько четных двузначных чисел можно составить из цифр 0,1,2,4,5,9? Ответ:15 чисел. Таблица вариантов. Сколько вариантов завтрака есть? Х/б изд. Напитки. Булочка. Кекс. Пряники. Печенье. Чай. Сок. Кефир. Выбор напитка- испытание А. Выбор хл./бул. изделия.- испытание В. Правило умножения. В коридоре висят три лампочки. - Число вариантов.pptx

Принцип Дирихле

Принцип Дирихле. Биография. Формулировка. Область применения. Задачи. Доказательство. Средние линии треугольника. 11 различных целых чисел. Принцип Дирихле для длин и площадей. Попарно не пересекающиеся отрезки. - Принцип Дирихле.ppt

Граф

Я решил разобраться какую роль в обычной жизни играют графы. Исследовать роль графов в нашей жизни. Научиться работать с программой подготовки презентаций Microsoft PowerPoint. Что такое граф. Точки называются вершинами графа, а соединяющие линии – рёбрами. Рёбра графа. Вершина графа. Количество рёбер, выходящих из вершины графа, называется степенью вершины. Нечётная степень. Чётная степень. История возникновения графов. Задача о Кенигсбергских мостах. Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. - Граф.ppt

Виды графов

Графы. Состав графа. Изображение вершин. Неориентированный граф. Граф отношения «переписываются». Ориентированный граф. Взвешенный граф. Семантическая сеть. Иерархия. Дерево – граф иерархической структуры. Корень – главная вершина дерева. Файловая структура. Самое главное. Какая связь между графом и таблицей. Как называется взвешенный граф иерархической структуры. - Виды графов.ppt

Теория графов

V-множество вершин, E- множество ребер Граф - G(V, Е). G(V, Е, f) V,E – множества, отображение инциденции f: Е? V&V множества Е в V&V. Основы теории графов. Определение инцидентности. Пусть задан абстрактный граф G(V, Е, f). Если f(е) = (x&x), то ребро называется петлей в вершине х. Определение смежности. Теорема 1. В любом конечном графе G(V, Е) количество нечетных вершин - четно. Пример операций разборки. В противном случае маршрут незамкнутый. Цепь - незамкнутый маршрут, состоящий из последовательности различных ребер. Цикл - замкнутый маршрут, состоящий из последовательности различных ребер. - Теория графов.ppt

Применение теории графов

Теория «графов». Несколько слов о памяти. Психический процесс. Человеческая память. Приём развития картографической памяти. Математическая модель. Страны. Столицы. Выполнение заданий. Задания к «графам». Проверочный практикум. Политическая карта. Панама. Возможность. - Применение теории графов.ppt

Кратчайший путь

Нахождение кратчайшего пути. Содержание. Графы: определения и примеры. Три способа изображения одного графа. Пример двух разных графов. Степень вершины. Смежные вершины и рёбра. Путь в графе. Достижимость. Длина пути. Примеры неориентированных графов. Ориентированные графы. Смешанный граф. Путь в орграфе. Примеры ориентированных графов. Взвешенные графы. Длина пути во взвешенном графе. Примеры взвешенных графов. Способы представления графов. Матрица смежности. Пример матрицы смежности. Преимущества матрицы смежности. Иерархический список. Пример иерархического списка. Преимущества иерархического списка. - Кратчайший путь.ppt

Остовное дерево

Остовные деревья. Минимальное остовное дерево. Максимальный взвешенный лес. Эквивалентные задачи. Эквивалентность. Доказательство. Условия оптимальности. Оптимальное решение. Алгоритм Краскала. Алгоритм Краскала находит оптимальное решение. Алгоритм Краскала можно реализовать. Связный граф. Как улучшить шаг. Время работы шага. Алгоритм Прима. Алгоритм Прима находит решение. Как реализовать шаг. Максимальный взвешенный ориентированный лес. Минимальное остовное ориентированное дерево. Корневое ориентированное дерево. Эквивалентность трех задач. Ориентированный лес. Ориентированный лес и циклы. -

1 слайд

Не нужно нам владеть клинком, Не ищем славы громкой. Тот побеждает, кто знаком С искусством мыслить, тонким. Английский поэт Уордсворт

2 слайд

Введение Цель работы Задачи работы Что же такое «Комбинаторика»? История возникновения Правила решения комбинаторных задач Правило суммы Правило произведения Комбинации С повторениями Без повторений Тезаурус Список используемой литературы и web-ресурсов Заключение Страница автора

3 слайд

Создать справочное пособие для учащихся 10-11 классов, обучающихся на базовом уровне, образовательных учреждений. Подготовить первую часть большого проекта «Теория вероятности как самое встречаемое в нашей жизни явление».

4 слайд

1.1 Подобрать литературу и web – ресурсы по теме «Комбинаторика». 1.2 Исследовать все возможные методы решения комбинаторных задач на основе реальной жизни. 1.3 Проследить историю выделения самостоятельной области математики – комбинаторики. 2.1 Обосновать изучение курса комбинаторики в старшей школе как реальную необходимость при осуществлении курса принципа непрерывности образования «Школа – вуз». 2.2 Наметить возможные варианты введения курса комбинаторики в школьное образовательное пространство. 2.3 Подобрать материал для создания справочника.

5 слайд

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

6 слайд

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

7 слайд

Комбинаторика как наука стала развиваться в XIII в. параллельно с возникновением теории вероятностей. Первые научные исследования по этой теме принадлежат итальянским ученым Дж. Кардано, Н. Чарталье (1499-1557), Г. Галилею (1564-1642) и французским ученым Б.Пискамо (1623-1662) и П. Ферма. Комбинаторику, как самостоятельный раздел математики первым стал рассматривать немецкий ученый Г. Лейбниц в своей работе «Об искусстве комбинаторики», опубликованной в 1666г. Он также впервые ввел термин «Комбинаторика».

8 слайд

9 слайд

Задача: На столе лежат 3 черных и 5 красных карандашей. Сколькими способами можно выбрать карандаш любого цвета? Решение: Выбрать карандаш любого цвета можно 5+3=8 способами. Правило суммы в комбинаторике: Если элемент а можно выбрать m способами, а элемент в - n способами, причем любой выбор элемента а отличен от любого выбора элементов в, то выбор «а или в» можно сделать m+n способами. Примеры задач

10 слайд

Задача: В классе 10 учащихся занимаются спортом, остальные 6 учащихся посещают танцевальный кружок. 1)Сколько пар учащихся можно выбрать так, чтобы один из пары был спортсменом, другой танцором? 2)Сколько возможностей выбора одного ученика? Решение: 1)Возможность выбора спортсменов 10, а на каждого из 10 спортсменов выборов танцора 6. Значит, возможность выбора пар танцора и спортсмена 10·6=60. 2) Возможность выбора одного ученика 10+6=16.

11 слайд

Задача: Из города А в город В ведут 3 дороги. А из города В в город С ведут 4 дороги. Сколько путей, проходящих через В, ведут из А в С? Решение: Можно рассуждать таким образом: для каждой из трех путей из А в В имеется четыре способа выбора дороги из В в С. Всего различных путей из А в С равно произведению 3·4, т.е. 12. Правило произведения: Пусть нужно выбрать к элементов. Если первый элемент можно выбрать n1 способами, второй – n2 способами и т. д., то число способов к элементов, равно произведению n1· n2·… nк. Примеры задач

12 слайд

Задача: В школьной столовой имеются 2 первых, 5 вторых и 4 третьих блюд. Сколькими способами ученик может выбрать обед, состоящий из первых, вторых и третьих блюд? Решение: Первое блюдо можно выбрать 2 способами. Для каждого выбора первого блюда существует 5 вторых блюд. Первые два блюда можно выбрать 2·5=10 способами. И, наконец, для каждой 10 этих выборов имеются четыре возможности выбора третьего блюда, т. е. Существует 2·5·4 способов составления обеда из трех блюд. Итак, обед может быть составлен 40 способами.

13 слайд

14 слайд

15 слайд

Размещением из n элементов по к (к≤n) называется любое множество, состоящее из любых к элементов, взятых в определенном порядке из данных n элементов. Количество всех размещений из n элементов по m обозначают: Примеры задач n! – факториал числа n

16 слайд

Задача: Сколькими способами 4 юноши могут пригласить четырех из шести девушек на танец? Решение: Два юноши не могут одновременно пригласить одну и ту же девушку. И варианты, при которых одни и те же девушки танцуют с разными юношами считаются, разными, поэтому: Возможно 360 вариантов.

17 слайд

Перестановкой из n элементов называется каждое расположение этих элементов в определенном порядке. Количество всех перестановок из n элементов обозначают Pn Pn=n! Примеры задач

18 слайд

Квартет Проказница Мартышка Осёл, Козёл, Да косолапый Мишка Затеяли играть квартет … Стой, братцы стой! – Кричит Мартышка, - погодите! Как музыке идти? Ведь вы не так сидите… И так, и этак пересаживались – опять музыка на лад не идет. Вот пуще прежнего пошли у них разборы И споры, Кому и как сидеть… Решение

20 слайд

Сочетанием без повторений называется такое размещение, при котором порядок следования элементов не имеет значения. Таким образом, количество вариантов при сочетании будет меньше количества размещений. Число сочетаний из n элементов по m обозначается: Примеры задач

21 слайд

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

22 слайд

Часто в задачах по комбинаторике встречаются множества, в которых какие-либо компоненты повторяются. Например: в задачах на числа – цифры. Для таких задач используются формулы: где n-количество всех элементов, n1,n2,…,nr-количество одинаковых элементов. Примеры задач Примеры задач Примеры задач

23 слайд

Задача: Сколько трехзначных чисел можно составить из цифр 1, 2, 3, 4, 5? Решение: Так как порядок цифр в числе существенен, цифры могут повторяться, то это будут размещения с повторениями из пяти элементов по три, а их число равно:

24 слайд

Задача: В кондитерском магазине продавались 4 сорта пирожных: эклеры, песочные, наполеоны и слоеные. Сколькими способами можно купить 7 пирожных. Решение: Покупка не зависит от того, в каком порядке укладывают купленные пирожные в коробку. Покупки будут различными, если они отличаются количеством купленных пирожных хотя бы одного сорта. Следовательно, количество различных покупок равно числу сочетаний четырех видов пирожных по семь -

27 слайд

Мы считаем, что работа достигла своих целей. Мы составили справочное учебное пособие, которое нацелено оживить школьную математику введением в неё интересных задач, посильных для учащихся теоретических вопросов. Работа предназначена для учащихся 10-11 классов, обучающихся на базовом уровне, образовательных учреждений для углубления знаний по математике Отличительной способностью данного пособия являются: посильная для учащихся III ступени теоретическая часть; подбор и составление задач на основе жизненного материала, сказочных сюжетов. Мы надеемся, что наша работа заинтересует учащихся, поможет развитию их кругозора и мышления, будет способствовать более качественной подготовке к сдаче единого государственного экзамена.

28 слайд

Ученик: Захаров Дмитрий Класс: 10 Руководитель: Торопова Нина Анатольевна МОУ «Средняя образовательная школа с углубленным изучением отдельных предметов №5» г. Красноярска

Слайд 2

Комбинаторика– это раздел математики, посвящённый задачам выбора и расположения предметов из раздела множеств. Типичной задачей комбинаторики является задача перечисления комбинаций, составленных из нескольких предметов.

Слайд 3

Вспомним несколько примеров таких задач

1.Несколько стран в качестве символа своего государства решили использовать флаг в виде 3-х горизонтальных полос одинаковых по ширине и цвету: синий, красный и белый. Сколько стран могут испытать такую символику при условии, что у каждой страны свой отличный от других флаг? Будем искать решение с помощью дерева возможных вариантов.

Слайд 4

Ответ: 6 комбинаций

Слайд 5

2.Сколько чётных двузначных чисел можно составить из цифр 0,1,2,4,5,9.

Составим таблицу: слева от 1 – го столбца поместим первые цифры искомых чисел, сверху – вторые цифры этих чисел (чётные цифры, тогда столбцов будет три).

Слайд 6

Так в столбце перечислены все возможные варианты, следовательно, их столько же, сколько клеток в столбце, т.е. 15.

Ответ: 15 чисел

Слайд 7

3.На завтрак Вова может выбрать плюшку, бутерброд, пряник или кекс, а запить их может кофеем, соком или кефиром. Из скольких вариантов завтрака Вова может выбирать?

Решим задачу, перебирая всевозможные варианты, путем кодирования вариантов завтрака Решение: КП КБ КПр КК СП СБ СПр СК К-рП К-рБ К-рПр К-рК Ответ: 12 вариантов.

Слайд 8

Во всех задачах был осуществлён перебор всех возможных вариантов или комбинаций. Поэтому эти задачи называют комбинаторными. Слово комбинация происходит от латинского combino– соединяю. Действительно при получении любой комбинации мы составляем её из отдельных элементов последовательно соединяя их друг с другом. С этой точки зрения: число – это комбинация цифр, слово – это комбинация букв, меню – это комбинация блюд. Во всех предложенных задачах для подсчёта числа комбинаций мы использовали простой способ подсчёта – прямое перечисление (опираясь на «дерево возможных вариантов», таблицу, кодирование). Но способ перебора возможных вариантов далеко не всегда применим, ведь количество комбинаций может исчисляться миллионами. Здесь на помощь приходят несколько замечательных комбинаторных правил, которые позволяют подсчитать количество комбинаций без их прямого перечисления.

Слайд 9

Мы рассмотрели примеры 3-х разных задач, но получили совершенно одинаковые решения, которые основаны на общем правиле умножения: Пусть имеется n элементов и требуется выбрать из них один за другим к элементов. Если первый элемент m1выбрать n1 способами, после чего второй элемент m2выбрать n2 способами из оставшихся, затем третий элемент m3 выбрать n3 способами из оставшихся и т.д., то число способов могут быть выбраны все к элементов, равно произведению Примени это правило к каждой из решённых задач. 1-я задача: выбор верхней полосы - из 3-х цветов, т.е. n1=3; средняя полоса – из 2-х цветов, т.е.n2=2; нижняя полоса – из 1-го цвета, т.е. n3=1. n1 n2 n3 = 3 * 2 * 1 = 6 2-я задача: заметим, что в этой задаче задействованы два независимых исхода, поэтому mn = 5 *3 = 15

Слайд 10

Решение задач в классе: № 714, 716,718(а),721

№714. В кафе предлагают два первых блюда: борщ, рассольник - и четыре вторых блюда: гуляш, котлеты, сосиски, пельмени. Укажите все обеды из первого и второго блюд, которые может заказать посетитель. Проиллюстрируйте ответ, построив дере­во возможных вариантов.

Слайд 11

Решение. Что бы указать все обеды из двух блюд, будем рассуждать так. Выберем одно блюдо (борщ) и будем добавлять к нему поочерёдно разные вторые блюда, получая пары: Б г; б к; б с; б п (4 пары). Теперь в качестве первого блюда выберем рассольник и будем добавлять к нему поочерёдно разные вторые блюда: Рг; р к; р с; рп (4 пары). Согласно правилу комбинаторного умножения всего обедов: 2*4=8. Построив дерево возможностей, получим 8 вариантов. Ответ: б г; б к; б с; б п; р г; р к; р с; р п.; получим восемь разных обедов из двух блюд.

Слайд 12

№ 716 Стадион имеет четыре входа: А, В, С и D. Укажите все возможные способы, какими посетитель может войти через один вход, а выйти через другой. Сколько таких способов?

Слайд 13

Решение. Из условия ясно, что порядок выбора имеет значение: АВ означает, что посетитель вошёл через А и вышел через В, а ВА означает, что вошёл через В, а вышел через А. Чтобы перечислить все варианты выбора двух входов, будем придерживаться следующего правила. Выпишем обозначения всех входов в ряд: А, В, С, Д. Берём первый вход и дописываем к нему поочерёдно каждый из остальных входов, получаем 3 пары: А В, А С, А Д. Берём второй вход и дописываем к нему поочерёдно каждый из остальных входов, кроме него самого начиная с начала ряда, т. е. с первого входа: ВА, ВС, ВД. Выбирая третий, а затем четвёртый вход, получаем СА, СВ, СД; ДА, ДВ, ДС. Общее количество способов выбора: 4*3=12 (к каждому из 4 входов мы дописывали 3 других). Замечание. Подсчитать количество способов выбора, не составляя пары, можно по правилу произведения: первый выбор (через какой вход войти) можно сделать 4 способами (А, или В, или С, или Д); после этого второй выбор (через какой вход войти) можно сделать 3 способами (любой вход, кроме того, через который вошли). Общее количество выбора равно 4*3=12. Ответ: 12 способов.