Головна Конвертер Презентація до уроку з алгебри та початків аналізу на тему "Комбінаторика: переміщення, перестановки, поєднання". Презентація "Дискретний аналіз

Презентація до уроку з алгебри та початків аналізу на тему "Комбінаторика: переміщення, перестановки, поєднання". Презентація "Дискретний аналіз

Елементи комбінаторики

ПЕРЕСТАНОВКИ

Цілі уроку

1. Дати визначення поняття «перестановки»

2. Вивести формулу перестановок

3. Ознайомитись із поняттям «факторіал»

4. Навчитися застосовувати формулу перестановок у найпростіших випадках

5. Використовувати отримані знання у нових ситуаціях

План уроку

1. Бібліографічна довідка

2. Введення поняття перестановки та виведення формули

3. Розв'язання задач застосування формули перестановок

4. Самостійна робота

5. Підсумок уроку

6. Домашнє завдання

Бібліографічна довідка

Термін « перестановки »

вперше вжив

швейцарський математик,

один із засновників

теорії ймовірностей та

математичного аналізу Якоб Бернуллі

(27.12.1654 - 16.8.1705)

у книзі «Мистецтво припущень»

Визначення

1. Перестановками називають комбінації, що складаються з тих самих n різних елементів і відрізняються лише порядком їхнього розташування

2. Перестановки - з'єднання, які можна скласти з n предметів, змінюючи всіма можливими способами їх порядок

Формула перестановок

4∙3∙2∙1 = 24

1∙2∙3∙4∙5=120

1∙2∙3∙4∙5 ∙ …∙ n

Добуток поспіль перших n натуральних чисел, що йдуть, позначають n ! та читають «ен факторіал»

« factor » - множник

«ен факторіал» - що складається з n множників

Факторіал

Формула n ! = 1∙2∙3∙4∙ … ∙ ( n-1 )∙ n

Наприклад

3! = 1∙2∙3 = 6

Запам'ятай 0! = 1 та 1! = 1

Зручна формула n ! = ( n-1 )!∙ n

Наприклад: 6! = 5! ∙ 6 = 120 ∙ 6 = 720

Чи правильно записано формулу для обчислення перестановок

Р3 = 3! = 3∙2∙1
Р4 = 4! = 1∙2∙4∙5
Р 5 = 5! = 1∙2∙3∙4∙5
Р n = n! = 1∙2∙3∙…∙ n
Р4 = 4! = 7∙8∙9∙10

Мозковий штурм

1. Обчисліть:

Скільки способами можна виготовити різні прапори, розташувавши горизонтально три однакових за величиною шматка матерії білого, синього та червоного кольору?

Р3 = 3! = 1∙2∙3 = 6

Відповідь: 6 способів

Державна символіка деяких країн

Прапор Росії

Прапор Нідерландів Прапор Югославії

Застосування отриманих знань у новій ситуації

1. Обчислити:

7 = 9! ∙ 6! 7!∙8! Відповідь: 9!∙6! 7!∙8! " width="640"

Що більше: 9! ∙ 6! або 7!∙8! ?

Тому що 9! = 8!∙ 9, то 9!∙6! = 8! ∙ 9 ∙ 6!

Так як 7! = 6! ∙ 7, то 7!∙8! = 6! ∙ 7 ∙ 8!

9 7 = 9!∙6! 7!∙8!

Відповідь: 9!∙6! 7!∙8!

Самостійна робота

I варіант

Скільки способами можна скласти розклад одного навчального дня з 5 різних уроків?
2. Аня, Віра та Таня купили квитки до кінотеатру на 1, 2 та 3-і місця першого ряду. Скільки способами дівчатка можуть зайняти ці три місця?

II варіант

1. Скільки способами можна розставити 4 різні книги на книжковій полиці?

2. Скільки способами можуть стати в чергу в квиткову касу 3 особи?

Перевірка

I варіант

II варіант

Відповідь: 120 варіантів
Відповідь: 6 способів

Відповідь: 24 способи
Відповідь: 6 способів

Сінквейн

1 рядок – один іменник, що виражає головну тему.

2 рядок – два прикметники, що виражають головну думку.

3 рядок – три дієслова, що описують дії у рамках теми.

4 рядок - фраза, що несе певний зміст.

5 рядок – висновок у формі іменника (асоціація з першим словом).

Домашнє завдання

Пункт 6.4, вивчати формулу перестановок

І рівень: №611, №612,

ІІ рівень: №616, №621.

перестановки

МБОУ «Янішівська основна школа»

Вчитель: Звєрєва Т.І.

Розв'яжіть завдання:

Антон, Борис та Віктор купили

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 книжки одного автора, інші – різних авторів, те щоб книжки одного автора стояли поруч?

До нових зустрічей

з комбінаторними завданнями

Перестановки це комбінації, складені з тих самих елементів і відмінні порядком їх проходження. Число всіх можливих перестановок елементів позначається 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

Слайд 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 елементів". Зазвичай виділяється одне, основне чи природне, упорядкування, яке називається тривіальною перестановкою. Самі елементи безлічі нас не цікавлять. Часто як елементи беруть цілі числа від 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-1n. Якщо Pn-1=(n-1)!, то Pn=n!

Слайд 4

Нумерація перестановок

Щоб нумерувати перестановки, ми відобразимо безліч Pn взаємнооднозначно в інше безліч Tn, на якому ввести нумерацію буде набагато простіше, а потім для будь-якого елемента pPn як його номер візьмемо номер його образу Tn. Безліч Tn – це прямий добуток кількох числових відрізків Tn =(0:(n-1))(0:(n-2) … (0). Тобто кожен елемент Tn– це набір невід'ємних чисел i1, i2, …, in-1, in, причому ikn-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 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) = 26+0=12; a(2,0,1,3)=125+1=61; a(2,0,1,2,4) =614+2=246; a(2,0,1,2,2,5) =2463+2=740; a(2,0,1,2,2,0,6) =7402+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

Прямий алгоритм лексикографічного перебору перестановок.

Випишемо кілька наступних перестановок. (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 і Бульова ознака єActive. Початковий стан: У записана тривіальна перестановка та isActive = True. Стандартний крок: Якщо цеActive, видати перестановку як результат. Рухаючись з кінця, знайти в перестановці найбільший монотонно спадаючий суфікс. Нехай k - Позиція перед суфіксом. Покласти це Active:= (k > 0). Якщо єActive, то знайти в суфіксі найменший елемент, що перевищує pk, поміняти його місцями з pk, а потім суфікс «перевернути».

Слайд 15

Ще алгоритм перебору перестановок

Спробуємо тепер перебрати перестановки так, щоб дві послідовні перестановки мало відрізнялися одна від одної. Наскільки мало? На одну елементарну транспозицію, в якій змінюються місцями два сусідні елементи. Чи це можливо? Покажемо принципову схему такого алгоритму, нам буде цікавою саме вона. Уявіть собі n-1 елементарних «механізмів», кожен із яких пересуває свій елемент усередині набору. На кожному кроці механізм робить зсув ліворуч або праворуч. Напрямок змінюється, коли елемент сягає краю. На зміну напрямку витрачається один крок, під час якого крок робить наступний механізм, який теж може змінювати напрямок.

Слайд 16

Ще алгоритм перебору перестановок -2

Подивимося приклад. 1 2 3 4 5 Чий хід 1 2 3 4 5 Чий хід a b d a 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 c b d e b d a c e b 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|k1:n) і (bk|k1:n) . Ці числа розбиваються на пари (ak, bk) та обчислюється сума їх попарних творів k1:n akbk. Можна змінювати нумерацію (ak) та (bk). Потрібно вибрати таку нумерацію, коли сума мінімальна. У цій задачі можна зафіксувати якісь нумерації (ak) і (bk) та шукати перестановку , для якої досягається мінімум суми k1: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|k1: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

Знаходження максимальної зростаючої підпослідовності

Будемо по можливості економно розбивати нашу на спадні послідовності (приклад змінено) найвищу з рядків, де вона не порушить порядку. Візьмемо число з нижнього рядка, 21. Чому воно стоїть у 8-му рядку? Йому заважає 19. А числу 19 заважає 17. А йому 16. І т. д. Послідовність 9, 11, 14, 16, 17, 19, 21 зростає і має довжину 7. принцип (Діріхле) і не може бути зростаючою.

Слайд 22

Завдання про мінімальну кількість інверсій

Задано послідовність (ak|k1:n) чисел довжини n. Інверсією назвемо виконуване на місці дзеркальне відображення будь-якої її підрядки - суцільної підпослідовності. Потрібно за мінімальну кількість інверсій розмістити елементи послідовності за зростанням. Наприклад, перестановку «суцільна» можна перетворювати так (червоні літери переставлені, великі вже стоять на місці) суцільна сплоанша наолпшая анолпшая анолопшая (за п'ять інверсій)

Слайд 23

Екзаменаційні питання

Перестановки. Їх перебір та нумерація. Завдання про мінімум скалярного твору. Завдання про найбільшу зростаючу підпослідовність.

Слайд 24

1. Двосторонній перехід перестановка  число 2. Знайти перестановку, віддаленої від даної число кроків. 3. Перебір перестановок елементарними транспозиціями. 4. Виконати приклад для задачі про мінімум скалярного твору.

Презентація до уроку з алгебри та початків аналізу на тему "Комбінаторика: переміщення, перестановки, поєднання". Презентація "Дискретний аналіз

Слайди презентації

Поради як зробити хорошу доповідь презентації чи проекту