что такое комбинаторика в информатике

Презентация по информатике на тему «Комбинаторика»(10 класс)

Ищем педагогов в команду «Инфоурок»

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

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

Основные вопросы, которые будут разобраны в презентации:

Что такое комбинаторика?
Комбинаторные комбинации
Формулы комбинаторных комбинаций
Факториал числа
Правило произведения

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

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

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

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

4. Факториал натурального числа n определяется как произведение всех натуральных чисел от 1 до n включительно:
1. Название происходит от латинского factorialis — действующий, производящий, умножающий.
3. Факториал активно используется в различных раздела математики: комбинаторике, математическом анализе, теории чисел, функциональном анализе.
Для решения заданий применяется ФАКТОРИАЛ числа
Что это такое?

2. Обозначается n!, произносится эн факториал.

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

Для формулировки и решения комбинаторных задач используют различные модели комбинаторных комбинаций:

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

Сочетания
Комбинаторные комбинации и формулы
Во всех формулах n- число всех объектов множества,
m- число выбираемых объектов из этого же множества.

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

1. Перестановки
1. Перестановки-это комбинации, составленные из одних и тех же элементов и
отличающиеся порядком их следования, т.е., при перестановках число объектов
остается неизменным, меняется только их порядок.

2. Число всех возможных перестановок элементов обозначается Рₙ.
(от французского слова “Permutation”, что значит “перестановка”)

3. Формула перестановок Рₙ = n!

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

Разберём детскую задачку!
Дано множество из 3 объектов
Определите возможное количество перестановок этих объектов.

Можно это выполнить вручную,
способов получилось 6.
Воспользуемся
формулой перестановок
и сравним результаты.
Ответ: Р= 6.
Результаты совпали!

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

2. Размещения- это комбинации, где важен и состав элементов m, и порядок их размещения.

3. Число всех возможных комбинаций элементов обозначается А.
(от французского слова “Аrrangement”, что означает размещение)

4. Формула размещений
1. Размещения — комбинации, каждая из которых составлена из m элементов, взятых из n различных элементов, у которых состав элементов или их порядок отличают их друг от друга.

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

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

4. Число всех возможных комбинаций элементов обозначается С.
( от французского слова “Сombinasion”, что значит “сочетание”)

5. Формула сочетания
Количество сочетаний всегда меньше количества размещений.
1.Сочетания- это комбинации, каждая из которых составлена из m элементов, выбранных из n различных элементов, состав которых отличается хотя бы на один элемент.
2. В сочетаниях в отличии от размещений не учитывается порядок элементов.

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

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

«Правило произведения» в комбинаторике
N=n1*n2*n3…*nk
Пусть требуется выполнить последовательно k действий.

Если первое действие можно выполнить n1 способами,
второе действие n2 способами,
третье – n3 способами
и так до k-го действия, которое можно выполнить nk способами,
то все k действий вместе могут быть выполнены N способами:

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

«Правило произведения» в комбинаторике
N=n1*n2*n3…*nk
1. Первую цифру числа (объект n₁) можем выбрать 9 способами, так как число не может начинаться с нуля.
2. Вторую цифру числа (объект n₂ ) можем выбрать 10 способами, так как у нас есть 10 цифр.
3. Найдем N- количество чисел N= n₁*n₂=9*10=90
Ответ: 90 чисел
Рассмотрим пример: Cколько чисел можно составить из цифр 0,1,2,3,4,5,6,7,8,9, если число должно быть двузначным?

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

3. В коробке находится 16 клубков шерсти.
Сколькими способами можно взять 4 клубка?

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

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

4. Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если имеется материал пяти цветов?
5. Сколькими способами можно выбрать гласную и согласную буквы в слове «полка»?

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

.
Проверим решение заданий!
Вычислите: 14!/12!

14! 12! = 12!∗13∗14 12! =13∗14=182 Ответ: 182

2. Сколькими способами можно переставить 4 различные предмета? В нашем случае это фрукты.
Нам нужно найти сколькими способами можно переставить между собой n различных предметов в разной последовательности, а значит применим формулу перестановок.

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

Проверим решение заданий!
3. В коробке находится 16 клубков шерсти. Сколькими способами можно взять 4 клубка?

Что это значит? Это значит, что из набора 16 различных клубков нужно составить какое-то количество уникальных сочетаний 4 клубков. То есть, каждая такая комбинация из 4 клубков будет отличаться от других комбинаций хотя бы одним клубком, а может и двумя!

Таким образом, у нас имеют место сочетания клубков. Применим формулу сочетания.

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

Ответ: 6
4. Сколькими способами можно составить флаг, состоящий из трех горизонтальных полос различных цветов, если имеется материал пяти цветов?

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

Если Вы считаете, что материал нарушает авторские права либо по каким-то другим причинам должен быть удален с сайта, Вы можете оставить жалобу на материал.

Курс повышения квалификации

Дистанционное обучение как современный формат преподавания

Курс повышения квалификации

Современные педтехнологии в деятельности учителя

Курс профессиональной переподготовки

Математика и информатика: теория и методика преподавания в образовательной организации

Найдите материал к любому уроку, указав свой предмет (категорию), класс, учебник и тему:

также Вы можете выбрать тип материала:

Общая информация

Международная дистанционная олимпиада Осень 2021

Похожие материалы

Презентация по информатике на тему «Кодирование текстовой и графической информации» (7 класс)

Презентация по информатике на тему «Носители информации» (9 класс)

Программирование в Компьютерных системах

Чайнворд по информатике (4 класс)

Дидактический материал для проведения зачета по информатике

Презентация по информатике на тему: «Классификация информационных технологий. Часть 7. Корпоративные информационные системы (КИС).»

Презентация по информатике на тему: «Классификация информационных технологий. Часть 6. Технологии электронного документооборота.»

Презентация по информатике на тему: «Классификация информационных технологий. Часть 5. Технология распределенной обработки данных (РОД).»

Не нашли то что искали?

Воспользуйтесь поиском по нашей базе из
5294342 материала.

Вам будут интересны эти курсы:

Оставьте свой комментарий

Авторизуйтесь, чтобы задавать вопросы.

Безлимитный доступ к занятиям с онлайн-репетиторами

Выгоднее, чем оплачивать каждое занятие отдельно

СК предложил обучать педагогов выявлять деструктивное поведение учащихся

Время чтения: 1 минута

Студентам вузов могут разрешить проходить практику у ИП

Время чтения: 1 минута

В школе в Пермском крае произошла стрельба

Время чтения: 1 минута

В российских школах оборудуют кабинеты для сообщества «Большой перемены»

Время чтения: 1 минута

В Минпросвещения предложили приравнять нападения на школы к терактам

Время чтения: 1 минута

Путин попросил привлекать родителей к капремонту школ на всех этапах

Время чтения: 1 минута

Подарочные сертификаты

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

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

Источник

КОМБИНАТОРИКА

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

Правила сложения и умножения в комбинаторике

Правило суммы. Если два действия А и В взаимно исключают друг друга, причем действие А можно выполнить m способами, а В – n способами, то выполнить одно любое из этих действий (либо А, либо В) можно n + m способами.

Пример 1.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить одного дежурного?

Дежурным можно назначить либо мальчика, либо девочку, т.е. дежурным может быть любой из 16 мальчиков, либо любая из 10 девочек.

По правилу суммы получаем, что одного дежурного можно назначить 16+10=26 способами.

Правило произведения. Пусть требуется выполнить последовательно k действий. Если первое действие можно выполнить n₁ способами, второе действие n₂ способами, третье – n₃ способами и так до k-го действия, которое можно выполнить n_k способами, то все k действий вместе могут быть выполнены:

Пример 2.

В классе учится 16 мальчиков и 10 девочек. Сколькими способами можно назначить двух дежурных?

Первым дежурным можно назначить либо мальчика, либо девочку. Т.к. в классе учится 16 мальчиков и 10 девочек, то назначить первого дежурного можно 16+10=26 способами.

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

По теореме умножения двое дежурных могут быть выбраны 26*25=650 способами.

Сочетания без повторений. Сочетания с повторениями

Классической задачей комбинаторики является задача о числе сочетаний без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать m из n различных предметов ?

Пример 3.

Необходимо выбрать в подарок 4 из 10 имеющихся различных книг. Сколькими способами можно это сделать?

Нам из 10 книг нужно выбрать 4, причем порядок выбора не имеет значения. Таким образом, нужно найти число сочетаний из 10 элементов по 4:

.

Рассмотрим задачу о числе сочетаний с повторениями: имеется по r одинаковых предметов каждого из n различных типов; сколькими способами можно выбрать m () из этих (n*r) предметов?

.

Пример 4.

В кондитерском магазине продавались 4 сорта пирожных: наполеоны, эклеры, песочные и слоеные. Сколькими способами можно купить 7 пирожных?

Т.к. среди 7 пирожных могут быть пирожные одного сорта, то число способов, которыми можно купить 7 пирожных, определяется числом сочетаний с повторениями из 7 по 4.

.

Размещения без повторений. Размещения с повторениями

Классической задачей комбинаторики является задача о числе размещений без повторений, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n различных предметов?

Пример 5.

В некоторой газете 12 страниц. Необходимо на страницах этой газеты поместить четыре фотографии. Сколькими способами можно это сделать, если ни одна страница газеты не должна содержать более одной фотографии?

В данной задаче мы не просто выбираем фотографии, а размещаем их на определенных страницах газеты, причем каждая страница газеты должна содержать не более одной фотографии. Таким образом, задача сводится к классической задаче об определении числа размещений без повторений из 12 элементов по 4 элемента:

Таким образом, 4 фотографии на 12 страницах можно расположить 11880 способами.

Также классической задачей комбинаторики является задача о числе размещений с повторениями, содержание которой можно выразить вопросом: сколькими способами можно выбрать и разместить по m различным местам m из n предметов, среди которых есть одинаковые?

Пример 6.

У мальчика остались от набора для настольной игры штампы с цифрами 1, 3 и 7. Он решил с помощью этих штампов нанести на все книги пятизначные номера– составить каталог. Сколько различных пятизначных номеров может составить мальчик?

Можно считать, что опыт состоит в 5-кратном выборе с возращением одной из 3 цифр (1, 3, 7). Таким образом, число пятизначных номеров определяется числом размещений с повторениями из 3 элементов по 5:

.

Перестановки без повторений. Перестановки с повторениями

Классической задачей комбинаторики является задача о числе перестановок без повторения, содержание которой можно выразить вопросом: сколькими способами можно разместить n различных предметов на n различных местах?

Пример 7.

Сколько можно составить четырехбуквенных «слов» из букв слова«брак»?

Генеральной совокупностью являются 4 буквы слова «брак» (б, р, а, к). Число «слов» определяется перестановками этих 4 букв, т. е.

Для случая, когда среди выбираемых n элементов есть одинаковые (выборка с возвращением), задачу о числе перестановок с повторениями можно выразить вопросом: сколькими способами можно переставить n предметов, расположенных на n различных местах, если среди n предметов имеются k различных типов (k

Пример 8.

Сколько разных буквосочетаний можно сделать из букв слова «Миссисипи»?

Здесь 1 буква «м», 4 буквы «и», 3 буквы «c» и 1 буква «п», всего 9 букв. Следовательно, число перестановок с повторениями равно

ОПОРНЫЙ КОНСПЕКТ ПО РАЗДЕЛУ «КОМБИНАТОРИКА»

Источник

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

Описание разработки

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

В XVIII веке к решению комбинаторных задач обращались выдающиеся математики. Так, Леонард Эйлер рассматривал задачи о разбиении чисел, о паросочетаниях, о циклических расстановках, о построении магических и латинских квадратов.

В знаменитой басне Крылова «Квартет» «проказница Мартышка, Осёл, Козёл да косолапый Мишка» устроили любопытный эксперимент: они исследовали влияние взаимного расположения музыкантов на качество исполнения. И если бы не вмешался Соловей, участники квартета, наверное, перепробовали бы все возможные варианты. Зададимся вопросом: сколько существует способов, чтобы рассадить, например в один ряд, четырёх музыкантов?

«Особая примета» комбинаторных задач — вопрос, который всегда можно сформулировать так, чтобы он начинался словами: «Сколькими способами. ».

Презентация содержит 20 слайдов.

Содержимое разработки

Что такое комбинаторика?

« Комбинаторика»( лат. «combinare», соединять, сочетать)

Что такое комбинаторика?

ввел в математический обиход

Что такое комбинаторика?

В XVIII веке к решению комбинаторных задач обращались выдающиеся математики. Так, Леонард Эйлер рассматривал задачи о разбиении чисел, о паросочетаниях, о циклических расстановках,

о построении магических

и латинских квадратов.

В знаменитой басне Крылова

«Квартет» «проказница Мартышка,

Осёл, Козёл да косолапый Мишка» устроили любопытный эксперимент: они исследовали влияние взаимного расположения музыкантов на качество исполнения. И если бы не вмешался Соловей, участники квартета, наверное, перепробовали бы все возможные варианты. Зададимся вопросом:

сколько существует способов, чтобы рассадить, например в один ряд, четырёх музыкантов?

Например, ГХ-РГ № 062993. Разумеется, все паспорта должны иметь разные номера.

Сколько может быть различных паспортов?

Нас приглашают сыграть в Лотто-Миллион. Суть игры в том, что нужно из 49 номеров угадать 6, которые выпадут во время тиража. Для участия в игре следует приобрести специальную карточку и вычеркнуть в ней 6 любых квадратов, пронумерованных числами от 1 до 49. Чтобы выиграть наверняка можно было бы запастись таким количеством карточек, какое необходимо для вычёркивания 6 номеров всеми возможными способами

Сколько этих способов?

Общее у всех трёх задач то, что их решением занимается отдельная область математики, называемая комбинаторикой.

«Особая примета» комбинаторных задач — вопрос, который всегда можно сформулировать так, чтобы он начинался словами: «Сколькими способами. ».

Размещения без повторений

Имеется n различных элементов. Сколько из них можно составить к расстановок?

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

В первой группе класса «А» первенства по футболу участвуют 17 команд. Разыгрываются медали: золотые, серебряные, бронзовые. Сколькими способами они могут быть распределены?

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

Перестановки с повторениями

До сих пор мы переставляли предметы, которые были попарно различны. Если же некоторые переставляемые предметы одинаковы, то получается меньше перестановок- некоторые перестановки совпадут друг с другом.

Сколько перестановок можно сделать из букв слова «Миссисипи»?

Всякая неупорядоченная выборка объема к из множества, состоящего из n различных объектов, полученная в схеме выбора без возвращений, называется сочетанием из n элементов по к.

В полуфинале по шахматам участвуют 20 человек, а в финал выходят только трое. Сосчитать число различных исходов полуфинала.

Задачи по программированию

Сколькими способами можно набрать n рублей, если существуют монеты 1, 2, 5, 10 и 50 рублей.

for j:=0 to n div 2 do

for k:=0 to n div 5 do

for l:=0 to n div 10 do

for m:=0 to n div 50 do

if i+j*2+k*5+l*10+m*50=n then begin

writeln(‘ Комбинаций ‘,s);

Задачи по программированию

Сколько можно составить слов из 4 букв, при этом алфавит состоит из 20 букв

a:array[1..n] of string=(‘ а ‘,’ б ‘,’ в ‘,’ г ‘,’ д ‘,’ е ‘,’ ж ‘,’ з ‘,’ и ‘,’ к ‘,

‘ л ‘,’ м ‘,’ н ‘,’ о ‘,’ п ‘,’ р ‘,’ с ‘,’ т ‘,’ у ‘,’ ф ‘);

var i,j,k,l:integer; s:real;

for l:=k+1 to n do begin

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

Источник