Prezentacja na temat „kombinatoryka”. Prezentacja „Analiza dyskretna

permutacje

MBOU „Szkoła podstawowa Yaniszewskaja”

Nauczyciel: Zvereva T.I.

Rozwiąż problem:

Anton, Borys i Wiktor kupili

3 bilety na mecze piłkarskie na I, II, III miejsce w pierwszym rzędzie stadionu. Na ile sposobów chłopcy mogą zająć te miejsca?

Rozwiązanie problemu:

Może istnieć taka sekwencja:

A B C A C B

Może być tak:

B V A B A V

Lub mogłoby to wyglądać tak:

V A B V B A

Odpowiedź: 6 opcji

Pamiętać!!!

Przegrupowanie nazywa się zbiorem N elementy zapisane w konkretnym OK.

Twierdzenie o permutacjach elementów zbioru skończonego:

N można na nim umieszczać różne elementy pojedynczo N dokładnie w różnych miejscach N! sposoby.

Liczba sposobów jest równa liczbie permutacji

z 3 elementów. Korzystając ze wzoru na liczbę permutacji, znajdujemy to

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

Pięciu przyjaciół zdecydowało się zrobić zdjęcie. Na ile sposobów można to zrobić?

Zadanie:

W klasie 9 w środę odbywa się 6 lekcji: matematyki, literatury,

język rosyjski, Język angielski, biologii i wychowania fizycznego. Ile opcji harmonogramu możesz utworzyć?

Układamy elementy w kolejności:

Całkowite opcje

harmonogramy:

1 ∙ 2∙ 3 ∙ 4 ∙5 ∙ 6 = 720

Przedmiot

Matematyka

Liczba opcji

Literatura

Język rosyjski

Język angielski

Biologia

Trening fizyczny

Zadanie:

Istnieje dziewięć różnych książek, z których cztery to podręczniki. Na ile sposobów można ułożyć te książki na półce, tak aby wszystkie podręczniki znajdowały się obok siebie? Plan:

1) podręczniki = książka

2) Permutacje P6 książek

3) P6=6!

4) P4 przegrupowanie podręczników

5) P4=4!

6) P 6 ∙ P4

Praca domowa:

1. Wiosną mama kupuje dziecku dużo owoców. Kupiła banana, jabłko, pomarańczę, cytrynę, gruszkę i kiwi. Znajdź liczbę możliwych opcji jedzenia owoców.

2 . Przed rozpoczęciem meczu ustawia się jedenastu zawodników. Pierwszy jest kapitanem, drugi jest

bramkarz, a reszta - losowo.

Ile jest metod konstrukcyjnych?

3. Na ile sposobów można ułożyć na półce 10 książek, z których 4 to książki tego samego autora, a pozostałe różnych autorów, tak aby książki tego samego autora stały obok siebie?

Do następnego razu

z problemami kombinatorycznymi

Permutacje to kombinacje składające się z tych samych elementów i różniące się kolejnością ich występowania. Liczbę wszystkich możliwych permutacji pierwiastków oznaczamy P n i można ją obliczyć ze wzoru: Wzór permutacji: P n = n! Podczas permutacji liczba obiektów pozostaje niezmieniona, zmienia się jedynie ich kolejność. Wraz ze wzrostem liczby obiektów liczba permutacji rośnie bardzo szybko i trudno jest je wyraźnie przedstawić.

Zadanie 1. W turnieju bierze udział siedem drużyn. Ile jest możliwych opcji podziału miejsc pomiędzy nimi? P 7 =7!=1*2*3*4*5*6*7=5040 Odpowiedź: 5040 Zadanie 2. Na ile sposobów 10 osób może usiąść przy okrągłym stole? R 10 = 10! = = 1*2*3*4*5*6*7*8*9*10 = Odpowiedź:

Niech będzie n różnych obiektów. Wybierzemy z nich m obiektów i przestawimy je między sobą na wszystkie możliwe sposoby. Powstałe kombinacje nazywane są rozmieszczeniami n obiektów na m, a ich liczba jest równa: Podczas rozmieszczania zmienia się zarówno kompozycja wybranych obiektów, jak i ich kolejność. Formuła umieszczenia:

Zadanie: Na ile sposobów można rozdzielić trzy bony do jednego sanatorium pomiędzy pięć osób? Ponieważ bony przekazywane są do jednego sanatorium, możliwości dystrybucji różnią się od siebie co najmniej o jedną osobę. Dlatego liczba metod dystrybucji Odpowiedź: 10 metod.

Zadanie: W warsztacie pracuje 12 osób: 5 kobiet i 7 mężczyzn. Na ile sposobów można ułożyć zespół składający się z 7 osób, w którym będą znajdować się 3 kobiety? Z pięciu kobiet należy wybrać trzy, stąd liczba metod selekcji. Ponieważ wymagane jest wybranie czterech mężczyzn z siedmiu, liczba metod selekcji mężczyzn Odpowiedź: 350

Podstawy kombinatoryki.

Umiejscowienia, przegrupowania,

kombinacje.

Niegrzeczna Małpa

Osioł,

Koza,

Tak, końskostopy Mishka

Zaczęliśmy grać w kwartecie

Stójcie bracia, stójcie! –

Małpa krzyczy – czekaj!

Jak powinna brzmieć muzyka?

W końcu tak nie siedzisz...

I w ten sposób zmienili miejsca – znowu muzyka nie szła dobrze.

Teraz stają się jeszcze bardziej intensywne niż kiedykolwiek

I spory

Kto i jak siedzieć...

wiedzieć:

definicje trzech najważniejsze pojęcia kombinatoryka:
rozmieszczenie n elementów na m;
kombinacje n elementów, m każdy;
permutacje n elementów;
podstawowe wzory kombinatoryczne

móc:

odróżniać od siebie zadania „permutacji”, „kombinacji”, „umieszczenia”;
stosować podstawowe wzory kombinatoryczne przy rozwiązywaniu prostych problemów kombinatorycznych.

wiele

Zbiór charakteryzuje się połączeniem pewnych jednorodnych obiektów w jedną całość.

Obiekty tworzące zbiór nazywane są elementami zestawu.

Zbiór napiszemy układając jego elementy w nawiasy klamrowe ( A, B, C, … , mi, F}.

W zbiorze kolejność elementów nie ma znaczenia, więc ( A, B} = {B, A}.

Zbiór, który nie zawiera ani jednego elementu, nazywa się pusty zestaw i jest oznaczony symbolem ø.

wiele

Jeżeli każdy element zbioru A jest elementem zbioru B, to mówimy, że zbiór A jest podzbiorem zbioru W.

Wiele ( A, B) jest podzbiorem zbioru ( A, B, C, … , mi, F}.

Wyznaczony

Lista możliwe opcje podzbiory zbioru ( 3 , 4 , 5 , 7, 9 }.

Kombinatoryka to dział matematyki zajmujący się pytaniami o to, ile różnych kombinacji, pod pewnymi warunkami, można utworzyć z elementów należących do danego zbioru.

Kombinatoryka jest ważną gałęzią matematyki badającą wzorce rozmieszczenia, uporządkowania, selekcji i dystrybucji elementów z ustalonego zbioru.

ZASADA SUMACJI

Jeżeli można wykonać dwie wzajemnie wykluczające się akcje wg k I M sposoby, wówczas można wykonać jedną z tych akcji k+m sposoby.

Przykład nr 1

Z miasta A do miasta B można dostać się 12 pociągami, 3 samolotami i 23 autobusami. Na ile sposobów można przedostać się z miasta A do miasta B?

Rozwiązanie

Przykład nr 2

W pudełku znajduje się n kulek w różnych kolorach. Losowo wyciągamy jedną piłkę. Na ile sposobów można to zrobić?

Rozwiązanie. Z pewnością, N sposoby.

Teraz te n kulek jest rozmieszczonych w dwóch pudełkach: W pierwszym M piłki, w drugim k. Wyciągamy losowo jedną kulkę z jakiegoś pudełka. Na ile różnych sposobów można to zrobić?

Rozwiązanie.

Możesz wyciągnąć piłkę z pierwszego pudełka M na różne sposoby, od drugiego k na różne sposoby, łącznie N = M + k sposoby.

ZASADA PRODUKTU

Niech dwie czynności wykonane jedna po drugiej zostaną wykonane zgodnie k I M sposoby Wtedy można wykonać oba km sposoby.

Przykład nr 3

W turnieju bierze udział 8 drużyn hokejowych. Na ile sposobów można rozdzielić pierwsze, drugie i trzecie miejsca?

Rozwiązanie

Przykład nr 4

Ile liczb dwucyfrowych można zapisać w systemie dziesiętnym?

Rozwiązanie. Ponieważ liczba jest dwucyfrowa, liczba dziesiątek ( M) może przyjmować jedną z dziewięciu wartości: 1,2,3,4,5,6,7,8,9. Liczba jednostek ( k) może przyjmować te same wartości i dodatkowo może być równy zero. Wynika z tego M= 9, a k= 10. W sumie otrzymujemy liczby dwucyfrowe

N= M · k= 9·10 =90.

Przykład nr 5

W grupie uczniów znajduje się 14 dziewcząt i 6 chłopców. Na ile sposobów można wybrać dwóch uczniów tej samej płci do wykonania różnych zadań?

Rozwiązanie. Zgodnie z zasadą mnożenia dwie dziewczynki można wybrać na 14 · 13 = 182 sposoby, a dwóch chłopców na 6 · 5 = 30 sposobów. Powinieneś wybrać dwóch uczniów tej samej płci: dwóch uczniów płci męskiej lub żeńskiej. Zgodnie z zasadą dodawania takich metod selekcji, nie będzie

N =182 + 30 = 212.

Typy połączeń

Nazywa się zbiory elementów znajomości.

Istnieją trzy typy połączeń:

permutacje z N elementy;
zakwaterowanie od N elementy wg M;
kombinacje N elementy wg M (M < N).

Definicja: Permutacja N elementy to dowolny uporządkowany zbiór N elementy.

Inaczej mówiąc, jest to zbiór, dla którego wskazano, który element jest na pierwszym miejscu, który jest na drugim, który jest na trzecim,…, który jest na n-tym miejscu.

PERmutacje

Przegrupowania- są to połączenia wg N elementy z danych elementów, które różnią się między sobą kolejnością elementów.

Liczbę permutacji n elementów oznaczamy przez Pn.

Рn = N · ( N- 1) · ( N– 2) · … · 2 · 1 = N!

Definicja:

Pozwalać N- liczba naturalna. Poprzez N! (czytaj „en silnia”) oznacza liczbę równą iloczynowi wszystkich liczb naturalnych 1 od do N:

N! = 1 · 2 · 3 · ... · N.

Na wszelki wypadek N= 0, z definicji przyjmuje się: 0! = 1.

SILNIA

Przykład nr 6

Znajdźmy wartości następujących wyrażeń: 1! 2! 3!

Przykład nr 7

Co jest równe

A) R 5 ;

B) R 3.

Przykład nr 8

Upraszczać

b) 12! · 13 · 14

V) κ ! · ( κ + 1)

Przykład nr 9

Na ile sposobów można ustawić 8 uczestników finałowego wyścigu na ośmiu bieżniach?

Rozwiązanie.

R 8=8! = 8 7 6 5 4 3 2 1 =40320

ZAKWATEROWANIE

Definicja. Zakwaterowanie od n elementów m jest dowolnym uporządkowanym zbiorem M elementy, składający się z elementów zestaw n elementów.

Liczba miejsc docelowych od M elementy wg N oznaczać:

obliczane według wzoru:

Przykład nr 9

Uczniowie klas 11 uczą się 9 przedmiotów akademickich. W planie zajęć na jeden dzień możesz umieścić 4 różne przedmioty. Ilu istnieje na różne sposoby planujesz na jeden dzień?

Rozwiązanie.

Mamy 9-elementowy zestaw, którego elementy przedmioty edukacyjne. Tworząc plan zajęć wybierzemy 4-elementowy podzbiór (lekcji) i ustalimy w nim kolejność. Liczba takich metod jest równa liczbie miejsc docelowych od dziewięciu do czterech ( m=9, n=4) to jest A 94:

Przykład nr 10

Na ile sposobów można wybrać prefekta i zastępcę prefekta z klasy liczącej 24 uczniów?

Rozwiązanie.

Mamy 24-elementowy zbiór, którego elementami są uczniowie danej klasy. Wybierając prefekta i zastępcę prefekta, wybierzemy 2-elementowy podzbiór (uczeń) i ustalimy w nim porządek. Liczba takich metod jest równa liczbie miejsc docelowych od dziewięciu do czterech ( m=24, n=2), to jest A 242:

KOMBINACJE

Definicja. Kombinacja bez powtórzeń N elementy wg M- zadzwonił dowolny M podzbiór elementarny N-zestaw elementów

Liczba kombinacji n elementów przez m jest oznaczona przez

i obliczane ze wzoru:

Przykład nr 11

Na ile sposobów można wybrać dwóch nauczycieli z klasy liczącej 24 uczniów?

Rozwiązanie.

N =24, M=2

KOMBINACJE

ZAKWATEROWANIE

PERmutacje

Рn = N!

Określ, do jakiego typu połączeń należy zadanie.

1. Na ile sposobów można zaplanować jeden dzień szkolny składający się z 5 różnych lekcji?

2. W klasie 9B jest 12 uczniów. Na ile sposobów można utworzyć czteroosobową drużynę, która weźmie udział w Olimpiadzie Matematycznej?

Czy brana jest pod uwagę kolejność elementów w połączeniu?

Czy wszystkie elementy są uwzględnione w połączeniu?

Wniosek: permutacja

Czy brana jest pod uwagę kolejność elementów w połączeniu?

Czy wszystkie elementy są uwzględnione w połączeniu?

(na to pytanie nie jest wymagana odpowiedź)

Wniosek: kombinacje

3. Ile jest różnych liczb dwucyfrowych, w których można zastosować liczby 1, 2, 3, 4, 5, 6, jeśli liczby w liczbie muszą być różne?

Czy brana jest pod uwagę kolejność elementów w połączeniu?

Czy wszystkie elementy są uwzględnione w połączeniu?

Wniosek: umiejscowienie

Niegrzeczna Małpa

Tak, końskostopy Mishka

Zaczęliśmy grać w kwartecie

Stójcie bracia, stójcie! –

Małpa krzyczy – czekaj!

Jak powinna brzmieć muzyka?

W końcu tak nie siedzisz...

I w ten sposób i że zamienili się miejscami – znowu muzyka nie idzie dobrze.

Teraz stają się jeszcze bardziej intensywne niż kiedykolwiek

Kto i jak siedzieć...

Ile różnych aranżacji muzyków jest możliwych?

Rozwiązanie.

Czy brana jest pod uwagę kolejność elementów w połączeniu?

Czy wszystkie elementy są uwzględnione w połączeniu?

Wniosek: permutacja

Рn = N! =N · ( N- 1) · ( N– 2) · … · 2 · 1

P4 = 4! = 4 3 2 1=24

„Wcześniej czy później każda poprawna idea matematyczna znajdzie zastosowanie w tej czy innej rzeczy”?

permutacje

zakwaterowanie

połączenie

Wyniki rozwiązywania problemów

PRACA DOMOWA

Naucz się notatek i formuł.

S. 321 nr 1062

KOMBINATORIKA

Cele lekcji:

Dowiedz się, czym zajmuje się kombinatoryka
Dowiedz się, jak powstała kombinatoryka
Przestudiuj formuły kombinatoryki i naucz się je stosować przy rozwiązywaniu problemów

Narodziny kombinatoryki jako gałęzi matematyki wiążą się z pracami Blaise'a Pascala i Pierre'a Fermata na temat teorii hazardu.

Błażeja Pascala

Pierre’a Fermata

Wielki wkład w rozwój metod kombinatorycznych wniósł G.V. Leibniza, J. Bernoulliego i L. Eulera.

G.V. Leibniza

L. Eulera.

J. Bernoulliego

Lemat. Niech zbiór A ma m elementów, a zbiór B ma n elementów. Wtedy liczba wszystkich odrębnych par (a,b), gdzie a\in A,b\in B będzie równa mn. Dowód. Rzeczywiście, z jednego elementu ze zbioru A możemy utworzyć n takich różnych par, a w sumie w zbiorze A znajduje się m elementów.

Umiejscowienia, permutacje, kombinacje Miejmy zbiór trzech elementów a, b, c. W jaki sposób możemy wybrać dwa z tych elementów? ab,ac,bc,ba,ca,cb.

Przegrupowania Będziemy je przestawiać na wszystkie możliwe sposoby (liczba obiektów pozostaje niezmieniona, zmienia się jedynie ich kolejność). Powstałe kombinacje nazywane są permutacjami, a ich liczba jest równa Pn = N! =1 · 2 · 3 · ... · ( n-1)n

Symbol n! nazywa się silnią i oznacza iloczyn wszystkich liczb całkowitych od 1 do n. Z definicji uważa się, że 0!=1 1!=1 Przykład wszystkich permutacji n=3 obiektów (różnych figur) pokazano na rysunku. Według wzoru powinno być dokładnie P3=3!=1⋅2⋅3=6 i tak się dzieje.

Wraz ze wzrostem liczby obiektów liczba permutacji rośnie bardzo szybko i trudno jest je wyraźnie przedstawić. Przykładowo liczba permutacji 10 obiektów wynosi już 3628800 (ponad 3 miliony!).

Miejsca docelowe Niech będzie n różnych obiektów. Wybierzemy z nich m obiektów i przestawimy je na wszystkie możliwe sposoby (tzn. zmieni się zarówno kompozycja wybranych obiektów, jak i ich kolejność). Powstałe kombinacje nazywane są rozmieszczeniami n obiektów na m, a ich liczba wynosi O poranku =n!(n−m)!=n⋅(n−1)⋅...⋅(n−m+1)

Definicja. Umieszczając zbiór n różnych elementów w m elementach (m ≤ N) są nazywane kombinacje , które składają się z danych n elementów na m elementów i różnią się albo samymi elementami, albo kolejnością elementów.

Kombinacje Niech będzie n różnych obiektów. Wybierzemy z nich m obiektów w każdy możliwy sposób (tzn. skład wybranych obiektów ulegnie zmianie, ale kolejność nie będzie istotna). Powstałe kombinacje nazywane są kombinacjami n obiektów na m, a ich liczba wynosi Cmn=n!(n−m)!⋅m!

Przykład wszystkich kombinacji n=3 obiektów (różnych figur) przez m=2 widać na poniższym obrazku. Według wzoru powinno być dokładnie C23=3!(3−2)!⋅2!:3!=3. Oczywiste jest, że zawsze jest mniej kombinacji niż miejsc docelowych (ponieważ kolejność jest ważna w przypadku miejsc docelowych, ale nie w przypadku kombinacji), a konkretnie w m! razy, czyli formuła połączenia jest poprawna: Amn=Cmn⋅Pm.

Metoda 1. W jednej grze biorą udział 2 osoby, dlatego należy obliczyć, na ile sposobów można wybrać 2 osoby z 15, a kolejność w takich parach nie jest istotna. Skorzystajmy ze wzoru, aby znaleźć liczbę kombinacji (próbek różniących się jedynie składem) n różnych elementów po m elementów każdy

n!= 1⋅ 2 ⋅3⋅...⋅ n , gdzie n=2, m=13.

Metoda 2. Pierwszy gracz rozegrał 14 partii (2., 3., 4. itd. do 15.), drugi gracz rozegrał 13 partii (3., 4. itd. do 15. cóż, wykluczamy fakt, że była już gra z). pierwszy), 3. gracz – 12 gier, 4. – 11 gier, 5 – 10 gier, 6 – 9 gier, 7 – 8 gier, 8 – 7 gier,

a 15-ty grał już ze wszystkimi.

Razem: 14+13+12+11+10+9+8+7+6+5+4+3+2+1=105 gier

ODPOWIEDŹ. 105 gier.

Nauczycielka matematyki Svetlana Valerievna Aksenova

Szkoła średnia Bugrowskaja, obwód wsiewołożski, obwód leningradzki

Slajd 1

Slajd 2

Slajd 3

Slajd 4

Slajd 5

Slajd 6

Slajd 7

Slajd 8

Slajd 9

Slajd 10

Slajd 11

Slajd 12

Slajd 13

Slajd 14

Slajd 15

Slajd 16

Slajd 17

Slajd 18

Slajd 19

Slajd 20

Slajd 21

Slajd 22

Slajd 23

Slajd 24

Prezentację na temat „Analiza dyskretna. Permutacje” można pobrać całkowicie bezpłatnie na naszej stronie internetowej. Temat projektu: Informatyka. Kolorowe slajdy i ilustracje pomogą Ci zaangażować kolegów z klasy lub publiczność. Aby obejrzeć zawartość użyj odtwarzacza lub jeśli chcesz pobrać raport kliknij odpowiedni tekst pod odtwarzaczem. Prezentacja zawiera 24 slajdy.

Slajdy prezentacyjne

Slajd 1

Analiza dyskretna

Wykład 3 Kombinatoryka. Przegrupowania

Slajd 2

Przegrupowania

Niech będzie dany zbiór n elementów. Kolejność tych elementów nazywa się permutacją. Czasami dodają „z n elementów”. Zwykle wyróżnia się jeden porządek podstawowy lub naturalny, który nazywa się permutacją trywialną. Elementy zbioru A same w sobie nas nie interesują. Często elementy są liczbami całkowitymi od 1 do n lub od 0 do n-1. Oznaczmy zbiór permutacji n elementów przez Pn, a jego liczność przez Pn. Zadajmy te same trzy pytania: czym jest Pn równe, jak iterować po elementach Pn, jak je przenumerować.

Slajd 3

Twierdzenie o liczbie permutacji

Liczba permutacji n elementów wynosi n! - iloczyn liczb od 1 do n. (n! czytaj n-silnia) Dowód. Przez indukcję. Dla n=1 wzór jest oczywiście poprawny. Niech to będzie prawdą dla n-1, udowodnijmy, że jest to prawdą także dla n. Pierwszy element porządku można wybrać na n sposobów, a pozostałe przypisać do wybranego pierwszego elementu na różne sposoby. Zatem wzór Pn= Pn-1n jest poprawny. Jeżeli Pn-1=(n-1)!, to Pn=n!

Slajd 4

Numerowanie permutacji

Aby numerować permutacje, odwzorujemy zbiór Pn jeden do jednego na inny zbiór Tn, na którym znacznie łatwiej będzie wprowadzić numerację, a następnie dla dowolnego elementu pPn przyjmiemy liczbę jego obrazu w Tn jako jego numer. Zbiór Tn jest iloczynem kilku segmentów liczbowych Tn =(0:(n-1))(0:(n-2) … (0). Oznacza to, że każdy element Tn jest zbiorem nie -liczby ujemne i1, i2, …, in-1, in i ikn-k.

Slajd 5

Wyświetlacz

Weźmy permutację i napiszmy obok niej trywialną permutację. Jako pierwszy indeks zajmujemy miejsce pierwszego elementu (licząc od zera) w trywialnej permutacji. Zamiast trywialnej permutacji zapiszmy ciąg pozostałych znaków. Jako drugi indeks zajmujemy miejsce drugiego elementu permutacji w tym wierszu. Powtarzajmy proces aż do końca. Oczywiście k-ty indeks będzie mniejszy niż długość k-tego ciągu, a ostatni indeks będzie równy zero. Spójrzmy na ten proces na przykładzie.

Slajd 6

Przykładowy pokaz

0 1 2 3 4 5 6 Indeks 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 e 0 2 0 1 2 2 0 0 Oczywiście , proces ten jest odwracalny, a mapowanie odwrotne skonstruuje oryginalną permutację na podstawie zestawu indeksów.

Slajd 7

Numeracja zbioru Tn

Dowolny iloczyn bezpośredni uporządkowanych zbiorów można uznać za system liczbowy o zmiennej podstawie. Przypomnij sobie przykład sekund z pierwszego wykładu lub rozważ starą skalę rozmiarów: 1 jard = 3 stopy, 1 stopa = 12 cali, 1 cal = 12 linii, 1 linia = 6 punktów. (2, 0, 4, 2, 3) = 2 jardy 0 stóp 4 cale 2 linie 3 punkty, ile to jest punktów? Musisz policzyć (nazywa się to schematem Hornera) (((2  3+0)  12+4)  12+2)  6+3

Slajd 8

Numeracja zbioru Tn - 2

My wolimy napisać wzór #, który znajdzie liczbę dla zbioru indeksów i1, i2, …, in-1, w postaci wyrażeń powtarzalnych #(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(pusty,0) = 0; Zgodnie z tym wzorem #(2,0,1,2,2,0,0) = a(2,0,1,2,2,0,6). Mamy 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;

Slajd 9

Iterowanie po zbiorach indeksów

Bazując na powyższym, łatwo jest wyliczyć permutacje: należy wyliczyć wszystkie zbiory indeksów i dla każdego zbioru skonstruować odpowiednią permutację. Aby wyliczyć zbiory indeksów należy pamiętać, że tak naprawdę każdy zbiór jest zapisem liczby w specjalnym systemie liczbowym o zmiennej podstawie (system ten nazywany jest silnią). Zasady dodawania 1 w tym systemie są prawie tak proste, jak w systemie binarnym: przechodząc od ostatniej cyfry, spróbuj dodać 1 do obecnej cyfry. Jeśli to możliwe, przestań dodawać 1. Jeśli nie jest to możliwe, wpisz zero do bitu i przejdź do następnego bitu.

Slajd 10

Wyliczanie zbiorów indeksów - 2

Spójrzmy na przykład: 7 6 5 4 3 2 1 To są podstawy zmiennych 3 4 4 2 1 1 0 3 4 4 2 2 0 0 Zauważ, że w 3 4 4 2 2 1 0 początek każdej linii to 3 4 4 3 0 0 0 tak jak w poprzednim, 3 4 4 3 0 1 0 następnie pojawia się element, ściśle 3 4 4 3 1 0 0 większy, . . . i 3 4 4 3 1 1 0 to, co następuje, nie jest istotne. 3 4 4 3 2 0 0 Oznacza to, że każdy wiersz 3 4 4 3 2 1 0 jest leksykograficznie większy od 3 5 0 0 0 0 0 poprzedniego. 3 5 0 0 0 1 0

Slajd 11

Twierdzenie o leksykograficznym wyliczaniu permutacji

Opisany algorytm iteruje poprzez permutacje w porządku leksykograficznym rosnącym. Dowód. Wystarczy, że pokażemy, że jeśli mamy dwa zbiory indeksów I1 i I2, a I1 jest leksykograficznie wcześniejsze od I2, to permutacja (I1) jest leksykograficznie wcześniejsza od (I2). Permutacje te powstają sekwencyjnie i dopóki I1 i I2 pokrywają się, ich permutacje również się pokrywają. A większa wartość indeksu odpowiada większemu elementowi.

Slajd 12

Algorytm bezpośredni leksykograficznego wyliczania permutacji

Weźmy dowolną permutację p i bezpośrednio znajdźmy następną leksykograficznie. Weźmy początek - pierwszych k elementów. Wśród jego rozszerzeń znajduje się minimalne, w którym wszystkie elementy są ułożone w kolejności rosnącej, oraz maksymalne, w którym wszystkie elementy są ułożone w kolejności malejącej. Na przykład w permutacji p = (4, 2, 1, 7, 3, 6, 5) wszystkie kontynuacje (4, 2, 1) leżą pomiędzy (3, 5, 6, 7) a (7, 6, 5, 3). Istniejąca kontynuacja jest mniejsza niż maksymalna, a trzeci element nadal nie wymaga zmiany. I 4. też. A piąty trzeba zmienić. Aby to zrobić, z pozostałych elementów musisz wziąć następny w kolejności, umieścić go na piątym miejscu i przypisać minimalną kontynuację. Otrzymujesz (4, 2, 1, 7, 5, 3, 6).

Slajd 13

Algorytm bezpośredni leksykograficznego wyliczania permutacji - 2

Zapiszmy kilka następujących permutacji. (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)

Slajd 14

Formalny opis algorytmu

Stan operacyjny: Permutacja p i atrybut logiczny są aktywne. Stan początkowy: Zapisano trywialną permutację i isActive = True. Krok standardowy: jeśli jest aktywny, zwróć jako wynik permutację. Idąc od końca, znajdź największy monotonicznie malejący przyrostek w permutacji. Niech k będzie pozycją przed przyrostkiem. Umieść isActive:= (k > 0). Jeśli jest Aktywny, znajdź najmniejszy element w przyrostku, który jest większy niż pk, zamień go na pk, a następnie „odwróć” przyrostek.

Slajd 15

Kolejny algorytm wyliczania permutacji

Spróbujmy teraz tak uporządkować permutacje, aby dwie kolejne permutacje niewiele się od siebie różniły. Jak mało? Jedna elementarna transpozycja, w której zamieniane są dwa sąsiednie elementy. Czy to możliwe? Pokażemy ci schematyczny diagram taki algorytm, będziemy nim zainteresowani. Wyobraź sobie elementarne „mechanizmy” n-1, z których każdy porusza swoim elementem w zestawie. Na każdym kroku mechanizm przesuwa się w lewo lub w prawo. Kierunek zmienia się, gdy element dotrze do krawędzi. Zmiana kierunku odbywa się w jednym kroku, podczas którego następny mechanizm wykonuje krok, który jednak może również zmienić kierunek.

Slajd 16

Inny algorytm wyliczania permutacji -2

Zobaczmy przykład. 1 2 3 4 5 Czyj to ruch 1 2 3 4 5 Czyj to ruch a b d e a d ce b a a c b d e b d a c e b a a c d be a d c a e b a c a d b e a d c e a b a

Slajd 17

Wyliczanie permutacji. 1

funkcja ExistsNextPerm(var kCh: integer): Boolean; var iV,iP,iVC,iPC: liczba całkowita; wynik rozpoczęcia:= Fałsz; dla iV:= nV do 2, wykonaj, jeśli policzysz

Slajd 18

Problem minimalnej sumy produktów parami

Niech zostaną dane dwa zbiory n liczb, powiedzmy (ak|k1:n) i (bk|k1:n) . Liczby te dzielone są na pary (ak,bk) i obliczana jest suma ich iloczynów parami k1:n akbk. Można zmienić numerację (ak) i (bk). Musisz wybrać numerację, która minimalizuje kwotę. W tym zadaniu można skorygować niektóre numeracje (ak) i (bk) i poszukać permutacji , dla której osiągnięta zostanie minimalna suma k1:n akb(k). Numerację wybierzemy wtedy, gdy (ak) będzie w kolejności rosnącej, a (bk) w kolejności malejącej.

Slajd 19

Twierdzenie o minimalnej sumie iloczynów parami

Minimalną sumę produktów parami osiąga się na trywialnej permutacji. Dowód. Załóżmy, że istnieją dwa wskaźniki k i r takie, że ak 0, tj. ar br + ak bk > ar bk + ak br . W naszej numeracji (ak) ułożone są w kolejności rosnącej. Jeśli (bk) nie są ułożone w porządku rosnącym, to istnieje para k i r, jak stwierdzono powyżej. Przestawiając bk i br dla tej pary, zmniejszymy wartość sumy. Oznacza to, że w rozwiązaniu optymalnym (bk) są w porządku rosnącym. Z tym prostym twierdzeniem spotkamy się kilka razy później.

Slajd 20

Problem maksymalnego rosnącego podciągu

Dany ciąg (ak|k1:n) liczb o długości n. Należy znaleźć jego ciąg o największej długości, w którym liczby (ak) występowałyby w kolejności rosnącej. Na przykład w sekwencji 3, 2, 11, 14, 32, 16, 6, 17, 25, 13, 37, 19, 41, 12, 7, 9 maksymalny podciąg będzie wynosił 2, 11, 14, 16 , 17, 25, 37, 41 Problem ten jest związany z permutacjami w tym sensie, że pierwotna sekwencja może być permutacją. Ograniczymy się do pokazania, jak rozwiązano ten problem, a słuchaczom udostępnimy formalizację i uzasadnienie algorytmu.

Slajd 21

Znajdowanie maksymalnego podciągu rosnącego

Będziemy, jak najbardziej ekonomicznie, podzielić nasze na ciągi malejące (przykład został zmieniony) 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 Każdy kolejny numer wpisany jest na samej górze wierszy, tak aby nie zakłócał porządku. Weźmy liczbę z dolnej linii, 21. Dlaczego jest ona w 8. linii? Przeszkadza mu 19. A liczba 19 jest przeszkodą 17. A on ma 16. Itd. Ciąg 9, 11, 14, 16, 17, 19, 21 jest rosnący i ma długość 7. Dowolny ciąg większych długość zawiera dwie liczby z tej samej linii (zasada Dirichleta) i nie może rosnąć.

Slajd 22

Problem minimalnej liczby inwersji

Dany ciąg (ak|k1:n) liczb o długości n. Nazwijmy inwersję lokalnym lustrzanym odbiciem któregokolwiek z jej podciągów – ciągłym podciągiem. Wymagane jest ułożenie elementów ciągu w porządku rosnącym w minimalnej liczbie inwersji. Na przykład „pełną” permutację można przekształcić w następujący sposób (czerwone litery zostały przestawione, duże są już na swoim miejscu)

Slajd 23

Pytania egzaminacyjne

Przegrupowania. Ich wyliczenie i numeracja. Minimalny problem produkt kropkowy. Największy rosnący problem podciągu.

Slajd 24

1. Permutacja przejścia dwukierunkowego  liczba 2. Znajdź permutację odległą od podanej przez podany numer kroki. 3. Wyliczanie permutacji poprzez elementarne transpozycje. 4. Uruchom przykład problemu minimalizacji iloczynu skalarnego.

Wskazówki dotyczące tworzenia dobrej prezentacji lub raportu z projektu

Staraj się zaangażować publiczność w historię, nawiązuj interakcję z publicznością za pomocą pytań wiodących, części gry, nie bój się żartować i szczerze się uśmiechać (w stosownych przypadkach).
Spróbuj wyjaśnić slajd własnymi słowami, dodaj dodatkowe ciekawe fakty, nie musisz po prostu czytać informacji ze slajdów, publiczność może je przeczytać sama.
Nie ma potrzeby przeładowywania slajdów projektu blokami tekstu; więcej ilustracji, a minimalna ilość tekstu lepiej przekaże informacje i przyciągnie uwagę. Slajd powinien zawierać tylko kluczowe informacje, resztę lepiej powiedzieć słuchaczom ustnie.
Tekst musi być dobrze czytelny, w przeciwnym razie widz nie będzie mógł zobaczyć prezentowanych informacji, będzie mocno odwrócony od historii, próbując przynajmniej coś zrozumieć, lub całkowicie straci zainteresowanie. Aby to zrobić, należy wybrać odpowiednią czcionkę, biorąc pod uwagę miejsce i sposób emisji prezentacji, a także wybrać odpowiednią kombinację tła i tekstu.
Ważne jest, aby przećwiczyć swój raport, zastanowić się, jak przywitasz się z publicznością, co powiesz jako pierwsze i jak zakończysz prezentację. Wszystko przychodzi z doświadczeniem.
Wybierz odpowiedni strój, bo... Ubiór mówiącego również odgrywa dużą rolę w odbiorze jego wypowiedzi.
Staraj się mówić pewnie, płynnie i spójnie.
Spróbuj cieszyć się występem, a wtedy będziesz bardziej spokojny i mniej zdenerwowany.