Презентация «Перестановки» представляет учебный материал для школьного урока по данной теме. Презентация содержит определение перестановок, наглядные примеры для понимания смысла данной операции, описание математического аппарата для решения задач с перестановками, примеры решения задач. Задача презентации - в удобной, понятной форме донести до учеников учебный материал, способствовать лучшему его пониманию и запоминанию.
В презентации используются специальные приемы, помогающие учителю объяснить новую тему. Учебные материалы заранее структурированы. При помощи анимационных эффектов они представляют примеры и задачи, делая акценты на важные особенности примеров и задач при демонстрации. Важные понятия выделяются цветом, что облегчает их запоминание.
После представления темы урока ученикам демонстрируется определение перестановок как простейших комбинаций, которые можно составить из некоторого множества элементов. Текст выделен знаком восклицания как важный для запоминания.
Далее демонстрируется пример перестановок на цветных карандашах, которые можно разместить в различном порядке. Для этого карандаши подписываются первой буквой названия их цвета: С, К, Ж. При помощи анимированного представления наглядно демонстрируются варианты размещения данных карандашей по порядку. На одном слайде первыми размещаются синие карандаши, а рядом с ними два варианта размещения - красный и желтый, желтый и красный. На следующем слайде продемонстрированы варианты размещения карандашей после красного - синий и желтый, желтый и синий. Последние возможные варианты - после желтого красный и синий, синий и красный. После наглядной демонстрации выполненные операции подписываются как перестановки из трех элементов. Более точное определение перестановки из трех элементов дается на отдельном слайде 7. В рамке для запоминания выделен текст, что каждое расположение данных элементов в определенном порядке будет называться перестановкой из трех элементов.
На слайде 8 продемонстрировано обозначение перестановок из n элементов - P n . Указано, что перестановки из трех элементов были подробно рассмотрены на примере карандашей, при этом очевидно, что таких перестановок будет 6. На слайде отмечена математическая запись количества перестановок: P 3 =6. Далее на экране отмечается, что для нахождения количества перестановок из трех элементов существует комбинаторное правило умножения.
На следующем слайде процедура перестановок раскладывается на этапы, чтобы получить правило для нахождения количества перестановок. Указано, что для подсчета необходимо на первое место ставить любой из трех элементов. Для него есть две возможности выбрать второй элемент. Для выбора третьего элемента остается единственная возможность. Это означает, что количество перестановок из 3 элементов будет находиться перемножением 3.2.1=6. Получаем общее число возможных вариантов перестановок. Аналогично процессу поиска вариантов перестановок рассматривается вариативность для n элементов.
Пусть есть некоторое множество n элементов. Для него на второе место помещается один из n-1 элементов, на третье место соответственно помещается один из n-2 элементов и т.д. Таким образом, можно вывести общее правило для поиска числа перестановок из n элементов: P n =n(n-1)(n-2).….3.2.1.
На слайде 11 на экран выведена формула P n в виде P n =1.2.3.….(n-2)(n-1)n. Таким образом вводится понятие факториала, обозначение которого продемонстрировано ниже формулы: n!. Рассмотрены примеры нахождения факториала от некоторого числа: 3!=1.2.3=6, а также 6!=1.2.3.4.5.6=720. Также указано, что 1!=1. Текст общего правила нахождение количества перестановок как n факториала расположен внизу слайда.
Далее предлагается рассмотреть несколько задач на нахождение числа перестановок. На слайде 12 предлагается к решению задача на нахождение количества способов разложения семи шаров по семи ячейкам. Указано, что способом решения является вычисление числа перестановок из 7 элементов: P 7 =7!=5040.
На слайде 13 рассматривается решение задачи на нахождение количества четырехзначных чисел, которые составлены из 0,1,2,3, при этом цифры в одном числе не повторяются. Решение предусмотрено в два этапа - сначала находится число всех перестановок из 4 элементов, а затем из них вычитается число перестановок, в которых числа с 0 впереди, так числа, начинающиеся с нуля, не будут четырехзначными. Таким образом, решение сводится к вычислению P 4 -P 3 =4!-3!=18. То есть вариантов образования таких чисел - 18.
На последнем слайде рассматривается решение задачи, в которой предлагается найти количество способов, которыми можно расставить 9 тарелок, 4 из которых - красные, так, чтобы красные располагались рядом. Основная трудность в решении данной задачи - понять, что красные тарелки в данных перестановках необходимо принимать за одну. Таким образом, решение сводится к нахождению произведения P 6 .P 4 =6!.4!=17280.
Презентация «Перестановки» предназначена для наглядного сопровождения объяснения учителя по теме «Перестановки». Подробное понятное представление учебного материала может быть также полезно при дистанционном обучении, а рассмотренные при этом задачи помогут ученику разобраться с решением самостоятельно.
Перестановки это комбинации, составленные из одних и тех же элементов и отличающиеся порядком их следования. Число всех возможных перестановок элементов обозначается P n, и может быть вычислено по формуле: Формула перестановки: Р n =n! При перестановке число объектов остается неизменными, меняется только их порядок С ростом числа объектов количество перестановок очень быстро растет и изображать их наглядно становится затруднительно.
Задача 1. В турнире участвуют семь команд. Сколько вариантов распределения мест между ними возможно? Р 7 =7!=1*2*3*4*5*6*7=5040 Ответ: 5040 Задача 2. Сколькими способами могут разместиться за круглым столом 10 человек? Р 10 =10! = = 1*2*3*4*5*6*7*8*9*10 = Ответ:
Пусть имеется n различных объектов. Будем выбирать из них m объектов и переставлять всеми возможными способами между собой. Получившиеся комбинации называются размещениями из n объектов по m, а их число равно: При размещениях меняется и состав выбранных объектов, и их порядок. Формула размещения:
Задача: Сколькими способами можно распределить три путевки в один санаторий между пятью желающими? Так как путевки предоставлены в один санаторий, то варианты распределения отличаются друг от друга хотя бы одним желающим. Поэтому число способов распределения Ответ: 10 способов.
Задача: В цехе работают 12 человек: 5 женщин и 7 мужчин. Сколькими способами можно сформировать бригаду из 7 человек, чтобы в ней было 3 женщины? Из пяти женщин необходимо выбирать по три, поэтому число способов отбора. Так как требуется отобрать четырех мужчин из семи, то число способов отбора мужчин Ответ: 350
перестановки
МБОУ «Янишевская основная школа»
Учитель: Зверева Т.И.
Решите задачу:
Антон, Борис и Виктор купили
3 билета на футбол на 1-е, 2-е, 3-е места первого ряда стадиона. Сколькими способами мальчики могут занять эти места?
Решение задачи:
- Может быть такая последовательность:
А Б В А В Б
Может быть и так:
Б В А Б А В
А может быть и так:
В А Б В Б А
Ответ: 6 вариантов
Запомните!!!
Перестановкой называется множество из n элементов, записанных в определённом порядке.
- Теорема о перестановках элементов конечного множества:
n различных элементов можно расставить по одному на n различных мест ровно n! способами.
Число способов равно числу перестановок
из 3 элементов. По формуле числа перестановок находим, что
Р3=3!= 1 ∙ 2 ∙3 = 6
Пять друзей решили сфотографироваться. Сколькими способами это можно сделать?
Задача:
В 9 классе в среду 6 уроков: математика, литература,
русский язык, английский язык, биология и физкультура. Сколько вариантов расписания можно составить?
Расставляем предметы по порядку:
Всего вариантов
расписания:
1 ∙ 2∙ 3 ∙ 4 ∙5 ∙ 6 = 720
Предмет
Математика
Число вариантов
Литература
Русский язык
Английский язык
Биология
Физкультура
Задача:
- Имеется девять различных книг, четыре из которых - учебники. Сколькими способами можно расставить эти книги на полке так, чтобы все учебники стояли рядом? План:
1) учебники = книга
2) Р6 перестановок книг
3) Р6=6!
4) Р4 перестановки учебников
5) Р4=4!
6) Р 6 ∙ Р4
Домашнее задание:
1. Весной мама покупает ребенку много фруктов. Она купила банан, яблоко, апельсин, лимон, грушу и киви. Найдите число возможных вариантов съедания фруктов.
2 . Одиннадцать футболистов строятся перед началом матча. Первым становится капитан, вторым –
вратарь, а остальные – случайным образом.
Сколько существует способов построения?
3. Сколькими способами можно расставить на полке 10 книг, из которых 4 книги одного автора, а остальные – разных авторов, так, чтобы книги одного автора стояли рядом?
До новых встреч
с комбинаторными задачами
Слайд 1
Слайд 2
Слайд 3
Слайд 4
Слайд 5
Слайд 6
Слайд 7
Слайд 8
Слайд 9
Слайд 10
Слайд 11
Слайд 12
Слайд 13
Слайд 14
Слайд 15
Слайд 16
Слайд 17
Слайд 18
Слайд 19
Слайд 20
Слайд 21
Слайд 22
Слайд 23
Слайд 24
Презентацию на тему "Дискретный анализ. Комбинаторика. Перестановки" можно скачать абсолютно бесплатно на нашем сайте. Предмет проекта: Информатика. Красочные слайды и иллюстрации помогут вам заинтересовать своих одноклассников или аудиторию. Для просмотра содержимого воспользуйтесь плеером, или если вы хотите скачать доклад - нажмите на соответствующий текст под плеером. Презентация содержит 24 слайд(ов).
Слайды презентации
Слайд 1
Дискретный анализ
Лекция 3 Комбинаторика. Перестановки
Слайд 2
Перестановки
Пусть задано множество из n элементов. Упорядочение этих элементов называется перестановкой. Иногда добавляют «из n элементов». Обычно выделяется одно, основное или естественное, упорядочение, которое называется тривиальной перестановкой. Сами элементы множества A нас не интересуют. Часто в качестве элементов берут целые числа от 1 до n или от 0 до n-1. Обозначим множество перестановок из n элементов через Pn , а его мощность через Pn. Зададим все те же три вопроса: чему равно Pn, как перебрать элементы Pn , как их перенумеровать.
Слайд 3
Теорема о числе перестановок
Число перестановок из n элементов равно n! - произведению чисел от 1 до n. (n! читается n–факториал) Доказательство. По индукции. Для n=1 формула очевидно верна. Пусть она верна для n-1, докажем, что она верна и для n. Первый элемент упорядочения можно выбрать n способами, а к выбранному первому элементу можно способами приписать остальное. Поэтому верна формула Pn= Pn-1n. Если Pn-1=(n-1)!, то Pn=n!
Слайд 4
Нумерация перестановок
Чтобы нумеровать перестановки, мы отобразим множество Pn взаимнооднозначно в другое множество Tn, на котором ввести нумерацию будет гораздо проще, а затем для любого элемента pPn в качестве его номера возьмем номер его образа в Tn. Множество Tn– это прямое произведение нескольких числовых отрезков Tn =(0:(n-1))(0:(n-2) … {0}. Т.е. каждый элемент Tn– это набор неотрицательных чисел i1, i2, …, in-1, in, причем ikn-k.
Слайд 5
Отображение
Возьмем перестановку и выпишем рядом с ней тривиальную перестановку. В качестве первого индекса возьмем место первого элемента (считая от нуля) в тривиальной перестановке. Запишем вместо тривиальной перестановки строку оставшихся символов. В качестве второго индекса возьмем место второго элемента перестановки в этой строке. Повторим процесс до конца. Очевидно, что k–й индекс будет меньше длины k–й строки, а последний индекс будет равен нулю. Посмотрим этот процесс на примере.
Слайд 6
Пример отображения
0 1 2 3 4 5 6 Индекс c a d f g b e a b c d e f g 2 2 a d f g b e a b d e f g 0 2 0 d f g b e b d e f g 1 2 0 1 f g b e b e f g 2 2 0 1 2 g b e b e g 2 2 0 1 2 2 b e b e 0 2 0 1 2 2 0 e e 0 2 0 1 2 2 0 0 Очевидно, что этот процесс обратим и обратное отображение построит по набору индексов исходную перестановку.
Слайд 7
Нумерация множества Tn
Любое прямое произведение упорядоченных множеств можно рассматривать как систему счисления с переменным основанием. Вспомните пример с секундами из первой лекции или рассмотрите какую-либо старую шкалу размеров: 1 ярд = 3 фута, 1 фут = 12 дюймов, 1 дюйм = 12 линий, 1 линия = 6 пунктов. (2, 0, 4, 2, 3) = 2 ярда 0 футов 4 дюйма 2 линии 3 пункта, сколько же это пунктов? Нужно сосчитать (это называется схемой Горнера) (((2 3+0) 12+4) 12+2) 6+3
Слайд 8
Нумерация множества Tn - 2
Формулу #, находящую номер для набора индексов i1, i2, …, in-1, in, мы предпочтем написать в виде рекуррентных выражений #(i1, i2, …, in) = a(i1, i2, …, in-1,n-1); a(i1, i2, …, ik,k) = a(i1, i2, …, ik-1,k-1)(n-k+1)+ ik; a(пусто,0) = 0; По этой формуле #(2,0,1,2,2,0,0) = a(2,0,1,2,2,0,6). Имеем a(2,1)=2; a(2,0,2) = 26+0=12; a(2,0,1,3)=125+1=61; a(2,0,1,2,4) =614+2=246; a(2,0,1,2,2,5) =2463+2=740; a(2,0,1,2,2,0,6) =7402+0=1480;
Слайд 9
Перебор наборов индексов
Исходя из вышеизложенного, перебрать перестановки просто: нужно перебрать все наборы индексов из и по каждому набору строить соответствующую ему перестановку. Для перебора наборов индексов заметим, что фактически каждый набор – это запись числа в особой системе счисления с переменным основанием (система называется факториальной). Правила прибавления 1 в этой системе почти так же просты, как в двоичной: двигаясь от последнего разряда пытаться прибавить в текущем разряде 1. Если это возможно, то прибавив 1 остановиться. Если невозможно, записать в разряд нуль и перейти к следующему разряду.
Слайд 10
Перебор наборов индексов - 2
Рассмотрим пример: 7 6 5 4 3 2 1 Это переменные основания 3 4 4 2 1 1 0 3 4 4 2 2 0 0 Обратите внимание, что в 3 4 4 2 2 1 0 каждой строке начало такое 3 4 4 3 0 0 0 же, как в предыдущей, 3 4 4 3 0 1 0 затем идет элемент, строго 3 4 4 3 1 0 0 больший, . . . , а 3 4 4 3 1 1 0 дальнейшее не существенно. 3 4 4 3 2 0 0 Значит, каждая строка 3 4 4 3 2 1 0 лексикографически больше 3 5 0 0 0 0 0 предыдущей. 3 5 0 0 0 1 0
Слайд 11
Теорема о лексикографическом переборе перестановок
Описанный алгоритм перебирает перестановки в порядке лексикографического возрастания. Доказательство. Нам достаточно показать, что если мы имеем два набора индексов I1 и I2, и I1 лексикографически предшествует I2, то перестановка (I1) лексикографически предшествует (I2). Эти перестановки формируются последовательно, и пока совпадают I1 и I2, совпадают и их перестановки. А большему значению индекса соответствует и больший элемент.
Слайд 12
Прямой алгоритм лексикографического перебора перестановок
Возьмем какую-либо перестановку p и прямо найдем лексикографически следующую. Возьмем начало – первые k элементов. Среди его продолжений известны минимальное, в котором все элементы расположены по возрастанию, и максимальное, в котором по убыванию. Например, в перестановке p =(4, 2, 1, 7, 3, 6, 5) все продолжения для (4, 2, 1) лежат между (3, 5, 6, 7) и (7, 6, 5, 3). Имеющееся продолжение меньше максимального, и 3-й элемент еще можно не менять. И 4-й тоже. А 5-й нужно сменить. Для этого из оставшихся элементов нужно взять следующий по порядку, поставить его 5-м и приписать минимальное продолжение. Получится (4, 2, 1, 7, 5, 3, 6).
Слайд 13
Прямой алгоритм лексикографического перебора перестановок - 2
Выпишем несколько следующих перестановок. (4, 2, 1, 7, 5, 3, 6) (4, 2, 1, 7, 5, 6, 3) (4, 2, 1, 7, 6, 5, 3) (4, 2, 3, 1, 5, 6, 7) (4, 2, 3, 1, 5, 7, 6) (4, 2, 3, 1, 6, 5, 7) (4, 2, 3, 1, 6, 7, 5) (4, 2, 3, 1, 7, 5, 6) (4, 2, 3, 1, 7, 6, 5) (4, 2, 3, 5, 1, 6, 7)
Слайд 14
Формальное описание алгоритма
Рабочее состояние: Перестановка p и булев признак isActive. Начальное состояние: В записана тривиальная перестановка и isActive = True. Стандартный шаг: Если isActive, выдать перестановку в качестве результата. Двигаясь с конца, найти в перестановке наибольший монотонно убывающий суффикс. Пусть k – позиция перед суффиксом. Положить isActive:= (k > 0). Если isActive, то найти в суффиксе наименьший элемент, превосходящий pk, поменять его местами с pk, а потом суффикс «перевернуть».
Слайд 15
Еще алгоритм перебора перестановок
Попробуем теперь перебрать перестановки так, чтобы две последовательные перестановки мало отличались друг от друга. Насколько мало? На одну элементарную транспозицию, в которой меняются местами два соседних элемента. Возможно ли это? Покажем принципиальную схему такого алгоритма, нам будет интересна именно она. Представьте себе n-1 элементарных «механизмов», каждый из передвигает свой элемент внутри набора. На каждом шаге механизм делает сдвиг налево или направо. Направление меняется, когда элемент доходит до края. На смену направления тратится один шаг, во время которого шаг делает следующий механизм, который, впрочем, тоже может менять направление.
Слайд 16
Еще алгоритм перебора перестановок -2
Посмотрим пример. 1 2 3 4 5 Чей ход 1 2 3 4 5 Чей ход a b c d e a c d a b e a b a c d e a c d b a e a b c a d e a c d b e a b b c d a e a c d e b a a b c d e a b c d e a b a c b d e a a c d a e b a c b d a e a c a d e b a c b a d e a a c d e b c c a b d e a a d c e b a a c b d e b d a c e b a a c d b e a d c a e b a c a d b e a d c e a b a
Слайд 17
Перебор перестановок. 1
function ExistsNextPerm(var kCh: integer): Boolean; var iV,iP,iVC,iPC: integer; begin result:= False; for iV:= nV downto 2 do if count
Слайд 18
Задача о минимуме суммы попарных произведений
Пусть заданы два набора по n чисел, скажем, {ak|k1:n} и {bk|k1:n} . Эти числа разбиваются на пары (ak,bk) и вычисляется сумма их попарных произведений k1:n akbk. Можно менять нумерацию {ak} и {bk}. Требуется выбрать такую нумерацию, при которой сумма минимальна. В этой задаче можно зафиксировать какие-то нумерации {ak} и {bk} и искать перестановку , для которой достигается минимум суммы k1:n akb(k). Мы выберем нумерации, когда {ak} расположены по возрастанию, а {bk} – по убыванию.
Слайд 19
Теорема о минимуме суммы попарных произведений
Минимум суммы попарных произведений достигается на тривиальной перестановке. Доказательство. Предположим, что существуют такие два индекса k и r, что ak 0, т.е. ar br + ak bk > ar bk + ak br . В нашей нумерации {ak} расположены по возрастанию. Если {bk} расположены не по возрастанию, то найдется такая пара k и r, как сказано выше. Переставив у этой пары bk и br , мы уменьшим значение суммы. Значит, в оптимальном решении {bk} стоят по возрастанию. Эта простая теорема несколько раз встретится нам в дальнейшем.
Слайд 20
Задача о максимальной возрастающей подпоследовательности
Задана последовательность {ak|k1:n} чисел длины n. Требуется найти ее последовательность наибольшей длины, в которой числа {ak} шли бы в возрастающем порядке. Например, в последовательности 3, 2, 11, 14, 32, 16, 6, 17, 25, 13, 37, 19, 41, 12, 7, 9 максимальной будет подпоследовательность 2, 11, 14, 16, 17, 25, 37, 41 С перестановками эта задача связана тем, что исходная последовательность может быть перестановкой. Мы ограничимся тем, что покажем, как решается эта задача, а формализацию и обоснование алгоритма предоставим слушателям.
Слайд 21
Нахождение максимальной возрастающей подпоследовательности
Будем по возможности экономно разбивать нашу на убывающие последовательности (пример изменен) 9 12 11 14 18 16 6 17 15 13 37 19 21 8 7 5 9 6 5 12 11 8 7 14 13 18 16 15 17 37 19 21 Каждое следующее число пишется в самую верхнюю из строчек, где оно не нарушит порядка. Возьмем число из нижней строчки, 21. Почему оно стоит в 8-й строчке? Ему мешает 19. А числу 19 мешает 17. А ему 16. И т. д. Последовательность 9, 11, 14, 16, 17, 19, 21 возрастает и имеет длину 7. Любая последовательность большей длины содержит два числа из одной строки (принцип Дирихле) и не может быть возрастающей.
Слайд 22
Задача о минимальном числе инверсий
Задана последовательность {ak|k1:n} чисел длины n. Инверсией назовем выполняемое на месте зеркальное отражение какой-либо ее подстроки – сплошной подпоследовательности.Требуется за минимальное число инверсий расположить элементы последовательности по возрастанию. Например, перестановку «сплошная» можно преобразовывать так (красные буквы переставлены, большие уже стоят на месте) сплошнаЯ сплоанШЯ наолПСШЯ АнолПСШЯ АнлОПСШЯ АЛНОПСШЯ (за пять инверсий)
Слайд 23
Экзаменационные вопросы
Перестановки. Их перебор и нумерация. Задача о минимуме скалярного произведения. Задача о наибольшей возрастающей подпоследовательности.
Слайд 24
1. Двусторонний переход перестановка число 2. Найти перестановку, отстоящую от данной на данное число шагов. 3. Перебор перестановок элементарными транспозициями. 4. Выполнить пример для задачи о минимуме скалярного произведения.
Советы как сделать хороший доклад презентации или проекта
- Постарайтесь вовлечь аудиторию в рассказ, настройте взаимодействие с аудиторией с помощью наводящих вопросов, игровой части, не бойтесь пошутить и искренне улыбнуться (где это уместно).
- Старайтесь объяснять слайд своими словами, добавлять дополнительные интересные факты, не нужно просто читать информацию со слайдов, ее аудитория может прочитать и сама.
- Не нужно перегружать слайды Вашего проекта текстовыми блоками, больше иллюстраций и минимум текста позволят лучше донести информацию и привлечь внимание. На слайде должна быть только ключевая информация, остальное лучше рассказать слушателям устно.
- Текст должен быть хорошо читаемым, иначе аудитория не сможет увидеть подаваемую информацию, будет сильно отвлекаться от рассказа, пытаясь хоть что-то разобрать, или вовсе утратит весь интерес. Для этого нужно правильно подобрать шрифт, учитывая, где и как будет происходить трансляция презентации, а также правильно подобрать сочетание фона и текста.
- Важно провести репетицию Вашего доклада, продумать, как Вы поздороваетесь с аудиторией, что скажете первым, как закончите презентацию. Все приходит с опытом.
- Правильно подберите наряд, т.к. одежда докладчика также играет большую роль в восприятии его выступления.
- Старайтесь говорить уверенно, плавно и связно.
- Старайтесь получить удовольствие от выступления, тогда Вы сможете быть более непринужденным и будете меньше волноваться.
