Выбранный для просмотра документ Комбинаторика.pptx
Скачать материал "Комбинаторика. Классические алгоритмы решения комбинаторных задач"
Рабочие листы
к вашим урокам
Скачать
1 слайд
Комбинаторика. Классические алгоритмы решения комбинаторных задач
Карандаева А.В.
МДИ-113
2 слайд
«Вперед поедешь – голову сложишь, направо поедешь – коня потеряешь, налево поедешь – меча лишишься»
3 слайд
КОМБИНАТОРИКА – это раздел математики, посвященный задаче выбора и расположения элементов некоторого конечного множества в соответствии с заданными правилами.
4 слайд
Классические алгоритмы (методы) решения комбинаторных задач
Метод перебора возможных вариантов;
Табличный метод;
Построение дерева возможных вариантов решений;
Построение граф-схемы.
5 слайд
Метод перебора возможных вариантов
Задача 1. Для своих двух книг Маша купила три разные обложки. Сколькими различными способами она может обернуть книги купленными обложками?
Ответ: Для решения обозначим обложки буквами а, б, в. Составим из букв всевозможные пары: аб, ав, бв, ба, ва, вб. Всего получилось 6 способов.
6 слайд
Задача 2. Какие двузначные числа можно составить из цифр 1, 2, 3, 4, 5?
Ответ: 11, 12, 13, 14, 15, 21, 22, 23, 24, 25, 31, 32, 33, 34, 35, 41, 42, 43, 44, 45, 51, 52, 53, 54, 55.
Метод перебора возможных вариантов
7 слайд
Задача 3. В финальном забеге на 100 м участвуют Иванов, Громов и Орлов. Назовите возможные варианты распределения призовых мест.
Ответ:
Вариант 1: 1. Иванов, 2. Громов, 3. Орлов.
Вариант 2: 1. Иванов, 2. Орлов, 3. Громов.
Вариант 3: 1. Орлов, 2. Иванов, 3. Громов.
Вариант 4: 1. Орлов, 2. Громов, 3. Иванов.
Вариант 5: 1. Громов, 2. Орлов, 3. Иванов.
Вариант 6: 1. Громов, 2. Иванов, 3. Орлов.
Метод перебора возможных вариантов
8 слайд
Табличный метод
Задача 1. Сколько нечетных двузначных чисел можно составить из цифр 1, 3, 4, 6, 7, 8, 9?
Решение: Составим таблицу: слева первый столбец – первые цифры искомых чисел, вверху первая строка – вторые цифры.
Ответ: 28.
9 слайд
Задача 2. В школьной столовой приготовили на завтрак плов (П), кашу (К), блины (Б), а из напитков – сок (С), чай (Ч) и молоко (М). Сколько различных вариантов завтрака можно составить?
Решение:
Ответ: 9 вариантов.
Табличный метод
10 слайд
Метод построения дерева возможных вариантов решений
Задача 1. Учитель попросил Олега разложить на полке 3 волшебных шара – желтый, красный, синий. Сколькими способами Олег может это сделать?
Ответ: 6 способами.
11 слайд
Задача 2. Катя собирается на каникулы. Она может поехать с бабушкой или с родителями. Если Катя поедет с бабушкой, то она сможет провести каникулы или на даче, или в городе, или в деревне. Если она поедет с родителями, то она сможет провести каникулы или отдыхая в санатории, или путешествии по горам, или путешествуя на теплоходе. Сколько разных вариантов есть у Кати, чтобы провести свои каникулы?
Метод построения дерева возможных вариантов решений
12 слайд
Каникулы Кати
Бабушка
Родители
Дача
Город
Деревня
Санаторий
Горы
Теплоход
Ответ: 6 вариантов
13 слайд
Метод построения граф-схемы
Задача 1. Андрей, Борис, Виктор и Григорий играли в шахматы. Каждый сыграл с каждым по одной партии. Сколько партий было сыграно?
Ответ: сыграно 6 партий
А
Б
Г
В
14 слайд
Задача 2. Вася, Коля, Петя, Аня и Наташа – лучшие лыжники в пятом классе. Для участия в соревнованиях нужно выбрать из них одного мальчика и одну девочку. Сколькими способами это можно сделать?
Ответ: 6 способов.
Метод построения граф-схемы
В
К
А
Н
П
Рабочие листы
к вашим урокам
Скачать
Выбранный для просмотра документ Реферат.docx
Скачать материал "Комбинаторика. Классические алгоритмы решения комбинаторных задач"
Рабочие листы
к вашим урокам
Скачать
Рабочие листы
к вашим урокам
Скачать
В обычной жизни нам нередко встречаются задачи, которые имеют несколько различных вариантов решения. Чтобы сделать правильный выбор, важно не упустить ни один из них. Для этого надо уметь осуществлять перебор возможных вариантов или подсчитать их число. Задачи, требующие такого решения, называются комбинаторными. Раздел математики, в котором изучают комбинаторные задачи, называют комбинаторикой.
Комбинаторика – раздел математики, посвящённый решению задач выбора и расположения элементов некоторого, обычно конечного множества в соответствии с заданными правилами.
Каждое такое правило определяет способ построения некоторой конструкции из элементов исходного множества, называемой комбинаторной конфигурацией. Поэтому можно сказать, что целью комбинаторного анализа является изучение комбинаторных конфигураций. Это изучение включает в себя вопросы существования комбинаторных конфигураций, алгоритмы их построения, оптимизацию таких алгоритмов, а также решение задач перечисления, в частности определение числа конфигураций данного класса. Простейшим примером комбинаторных конфигураций являются перестановки, сочетания и размещения.
Большой вклад в систематическое развитие комбинаторных методов был сделан Г. Лейбницем (диссертация "Комбинаторное искусство"), Я. Бернулли (работа "Искусство предположений"), Л. Эйлером. Можно считать, что с появлением работ Я. Бернулли и Г. Лейбница комбинаторные методы выделились в самостоятельную часть математики.
Возвращение интереса к комбинаторному анализу относится к 50-м годам ХХ в. в связи с бурным развитием кибернетики и дискретной математики и широким использованием электронно-вычислительной техники. В этот период активизировался интерес к классическим комбинаторным задачам.
Классические комбинаторные задачи – это задачи выбора и расположения элементов конечного множества, имеющие в качестве исходной некоторую формулировку развлекательного содержания типа головоломок.
Существуют такие классические алгоритмы (методы) решения комбинаторных задач, как метод перебора возможных вариантов, табличный метод, построение дерева возможных вариантов решений, построение граф-схемы.
6 671 593 материала в базе
«Информатика», Босова Л.Л., Босова А.Ю.
Больше материалов по этому УМКНастоящий материал опубликован пользователем Карандаева Анастасия Валерьевна. Инфоурок является информационным посредником и предоставляет пользователям возможность размещать на сайте методические материалы. Всю ответственность за опубликованные материалы, содержащиеся в них сведения, а также за соблюдение авторских прав несут пользователи, загрузившие материал на сайт
Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.
Удалить материалВаша скидка на курсы
40%Курс профессиональной переподготовки
500/1000 ч.
Курс профессиональной переподготовки
300/600 ч.
Курс повышения квалификации
36/72 ч.
Курс повышения квалификации
72 ч. — 180 ч.
Мини-курс
3 ч.
Мини-курс
6 ч.
Оставьте свой комментарий
Авторизуйтесь, чтобы задавать вопросы.