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




НазваниеКомбинаторные задачи Комбинаторные задачи
Дата конвертации18.07.2013
Размер445 b.
ТипПрезентации



      • Что такое комбинаторика?
      • Какие задачи считают комбинаторными?
      • Перестановки
      • Размещения
      • Сочетания


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

  • Комбинаторика – радел математики, в котором рассматриваются задачи о подсчёте числа комбинаций составленных по определённым правилам.



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

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

  • Задачи подсчёта числа комбинаций из конечного числа элементов

  • Комбинаторика от латинского слова combinare, что означает «соединять, сочетать».

  • Методы комбинаторики находят широкое применение в физике, химии, биологии, экономики и др. областях знания.

  • Комбинаторику можно рассматривать как часть теории множеств – любую комбинаторную задачу можно свести к задаче о конечных множествах и их отображениях.



1. Начальный уровень.

  • 1. Начальный уровень.

  • Задачи поиска хотя бы одного решения, хотя бы одного расположения объектов, обладающих заданным свойствами

  • - отыскание такого расположения десяти точек на пяти отрезках, при котором на каждом отрезке лежит по четыре точки;

  • - такого расположения восьми ферзей на шахматной доске, при котором они не бьют друг друга.

  • Иногда удаётся доказать, что данная задача не имеет решения

  • (например, нельзя расположить 10 шаров в 9 урнах так, что

  • бы в каждой урне было не более одного шара – хотя бы в

  • одной урне окажется не менее двух шаров).



2. Второй уровень.

  • 2. Второй уровень.

  • Если комбинаторная задача имеет несколько решений, то возникает вопрос о подсчете числа таких решений, описании всех решений данной задачи.

  • 3. Третий уровень.

  • Решения данной комбинаторной задачи отличаются друг от друга некоторыми параметрами. В этом случае возникает вопрос отыскания оптимального варианта решения такой задачи.

  • Например:

  • Путешественник хочет выехать из города А, посетить города В, С, и D. После чего вернуться в город А.





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

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



Мы будем рассматривать лишь задачи о подсчёте числа решений комбинаторной задачи.

  • Мы будем рассматривать лишь задачи о подсчёте числа решений комбинаторной задачи.

  • Этот раздел комбинаторики, называемый теорией перечислений, тесно связан с теорией вероятностей.



1. Сколько различных коктейлей можно составить из четырёх напитков, смешивая их в равных количествах по два?

  • 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 различных двузначных чисел.



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

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

  • 4 + 4 + 4 = 4·3 = 12 различных двузначных чисел.

  • Первая цифра вторая цифра

  • 1

  • 2

  • 3



Если элемент А можно выбрать из множества элементов п способами и для каждого такого выбора элемент В можно выбрать т способами, то два элемента (пару) А и В можно выбрать п·т способами.

  • Если элемент А можно выбрать из множества элементов п способами и для каждого такого выбора элемент В можно выбрать т способами, то два элемента (пару) А и В можно выбрать п·т способами.





К в а р т е т

  • К в а р т е т

  • Проказница Мартышка,

  • Осёл,

  • Козёл

  • Да косолапый Мишка

  • Затеяли сыграть Квартет.

  • …………………………………………………….

  • Ударили в смычки, дерут, а толку нет.

  • «Стой, братцы, стой! - кричит Мартышка. –

  • Погодите!

  • Как музыке идти? Ведь вы не так сидите»



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

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

  • Рп- число перестановок (Р первая буква французского слова permutation- перестановка)

  • Рп= n·(n-1)·(n-2)·(n-3)·(n-4)·. . .·3 ·2 ·1= n!

  • Рп = n!



Четыре попутчик решили обменяться визитными карточками. Сколько всего карточек при этом было использовано?

  • Четыре попутчик решили обменяться визитными карточками. Сколько всего карточек при этом было использовано?

  • получилось 12 карточек. Каждый из четырёх

  • попутчиков вручил визитку каждому из

  • трёх попутчиков

  • 4 · 3 = 12



Пуст имеется 4 шара и 3 пустых ячейки. Обозначим шары буквами a, b, c, d. В пустые ячейки можно по разному разместить три шара из этого набора.

  • Пуст имеется 4 шара и 3 пустых ячейки. Обозначим шары буквами a, b, c, d. В пустые ячейки можно по разному разместить три шара из этого набора.

  • Выбирая по-разному первый, второй и третий шары, будем получать различные упорядоченные тройки шаров

  • Каждая упорядоченная тройка, которую можно составить из четырёх элементов называется размещением из четырёх элементов по три



Сколько же размещений можно составить из 4-х элементов (abcd) по три?

  • Сколько же размещений можно составить из 4-х элементов (abcd) по три?

  • abc abd acb acd adb adc

  • bac bad bca bcd bda bdc

  • cab cad cba cbd cda cdb

  • dab dac dba dbc dca dcb



Можно решить и не выписывая самих размещений:

  • Можно решить и не выписывая самих размещений:

  • первый элемент можно выбрать четырьмя способами, так им может быть любой элемент из четырёх;

  • для каждого первого второй можно выбрать тремя способами;

  • для каждых первых двух можно двумя способами выбрать третий элемент из двух оставшихся.

  • Получаем



Сочетанием из п элементов по k называют любое множество, составленное из k элементов, выбранных из п элементов

  • Сочетанием из п элементов по k называют любое множество, составленное из k элементов, выбранных из п элементов



1. На плоскости отмечено 5 точек.

  • 1. На плоскости отмечено 5 точек.

  • Сколько получится отрезков, если соединить точки попарно?



1. В.Ф.Бутузов, Ю.М.Колягин, Г.Л. Луканкин, Э.Г.Позняк и др. «Математика» учебное пособие для 11кл общеобразовательных учреждений /рекомендовано Министерством образования РФ/ М., Просвещение, 1996.

  • 1. В.Ф.Бутузов, Ю.М.Колягин, Г.Л. Луканкин, Э.Г.Позняк и др. «Математика» учебное пособие для 11кл общеобразовательных учреждений /рекомендовано Министерством образования РФ/ М., Просвещение, 1996.

  • 2. Е.А. Бунимович, В.А. Булычёв: «Вероятность и статистика», пособие для общеобразовательных учебных заведений 5 – 9 классы / допущено Министерством образования Российской Федерации // Дрофа Москва 2002

  • 3. Н.Я. Виленкин, Р.С. Гутер, С.И. Шварцбурд, Б.В. Овчинский, В.Г. Ашкенузе:

  • «Алгебра» учебное пособие для IX – X классов средних школ с математической специализацией» / второе издание, «Просвещение», Москва 1972. 237 – 240)

  • 4. Ю.Н. Макарычев, Н.Г.Миндюк «Алгебра: элементы статистики и теории вероятностей 7 – 9 классы» Под редакцией С.А.Теляковского М: Просвещение , 2006 г

  • 5. Н.Я. Виленкин: «Индукция. Комбинаторика». Пособие для учителей. М., «Просвещение», 1976

  • 6. В.Л. Лютикас: «Школьнику о теории вероятностей» Учебное пособие по факультативному курсу для учащихся 8 – 10 классов,/ М., «Просвещение» 1976

  • 5.Журналы «Математика в школе»: № 10 – 2003 г, № 5 – 2004 г, № 6 – 2004 г, № 7 – 2004 г.

  • 6. Математика 10-11 классы



Похожие:

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

Комбинаторные задачи Комбинаторные задачи iconОтработать умения решать простейшие комбинаторные задачи отработать умения решать простейшие комбинаторные задачи

Комбинаторные задачи Комбинаторные задачи iconПарамонова Татьяна Павловна
Комбинаторные задачи и начальные сведения из теории вероятностей в курсе алгебры 9 класса
Комбинаторные задачи Комбинаторные задачи iconОбщие комбинаторные алгоритмы Общие комбинаторные алгоритмы
Кнут Д. Искусство программирования, т Сортировка и поиск. М.: Вильямс, 2011. 824 с
Комбинаторные задачи Комбинаторные задачи iconОткрытые задачи (пока, оценочные)
Паскаль (основные типы данных и операторы, понятие сложности алгоритмов, процедуры и функции, рекурсия, арифметические и комбинаторные...
Комбинаторные задачи Комбинаторные задачи iconЭлементы статистики и вероятность. В ходе изучения курса должны уметь
Решать комбинаторные задачи путем перебора возможных вариантов, а также используя правила
Комбинаторные задачи Комбинаторные задачи iconКомбинаторные задачи. Правило умножения. Моу «Лашманская сош» Салахова Р. Х
Запишите все возможные двухзначные и трехзначные числа с помощью цифр 7 и 8 (повторение цифр допускается)?
Комбинаторные задачи Комбинаторные задачи iconПриближенные алгоритмы Комбинаторные алгоритмы

Разместите кнопку на своём сайте:
dok.opredelim.com


База данных защищена авторским правом ©dok.opredelim.com 2015
обратиться к администрации
dok.opredelim.com
Главная страница