Prezentacija na temu "kombinatorika". Prezentacija „Diskretna analiza

permutacije

MBOU "Osnovna škola Yanishevskaya"

Nastavnik: Zvereva T.I.

Riješite problem:

Anton, Boris i Viktor kupili

3 fudbalske karte za 1., 2., 3. sedišta u prvom redu stadiona. Na koliko načina dječaci mogu zauzeti ova mjesta?

Rješenje problema:

Slijed bi mogao biti ovakav:

A B C A C B

Moglo bi biti ovako:

B V A B A V

Ili bi moglo biti ovako:

V A B V B A

Odgovor: 6 opcija

Zapamti!!!

Preuređenje se naziva skupom n elementi napisani u određenom ok.

Teorema o permutacijama elemenata konačnog skupa:

n različiti elementi se mogu postaviti jedan po jedan n tačno na različitim mestima n! načine.

Broj načina je jednak broju permutacija

od 3 elementa. Koristeći formulu za broj permutacija, nalazimo to

R3=3!= 1 ∙ 2 ∙3 = 6

Pet prijatelja je odlučilo da se fotografiše. Na koliko načina se to može učiniti?

zadatak:

U 9. razredu srijedom ima 6 časova: matematika, književnost,

ruski jezik, engleski jezik, biologiju i fizičko vaspitanje. Koliko opcija rasporeda možete kreirati?

Artikle sređujemo po redoslijedu:

Total options

rasporedi:

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

Stavka

Matematika

Broj opcija

Književnost

ruski jezik

engleski jezik

Biologija

Fizička obuka

zadatak:

Postoji devet različitih knjiga, od kojih su četiri udžbenici. Na koliko načina se ove knjige mogu složiti na policu tako da svi udžbenici budu jedan do drugog? Plan:

1) udžbenici = knjiga

2) P6 permutacije knjiga

3) P6=6!

4) P4 preuređenje udžbenika

5) P4=4!

6) P 6 ∙ P4

domaći zadatak:

1. U proljeće majka kupuje svom djetetu puno voća. Kupila je bananu, jabuku, narandžu, limun, krušku i kivi. Pronađite broj mogućih opcija za jelo voće.

2 . Jedanaest igrača postavlja se u red prije početka utakmice. Prvi je kapetan, drugi je

golman, a ostali - nasumično.

Koliko metoda izgradnje postoji?

3. Na koliko načina se na polici može složiti 10 knjiga, od kojih su 4 knjige istog autora, a ostale različitih autora, tako da knjige istog autora stoje jedna do druge?

Do sljedećeg puta

sa kombinatornim problemima

Permutacije su kombinacije sastavljene od istih elemenata i koje se razlikuju po redoslijedu u kojem se pojavljuju. Broj svih mogućih permutacija elemenata označava se sa P n, a može se izračunati pomoću formule: Formula permutacije: P n =n! Prilikom permutiranja, broj objekata ostaje nepromijenjen, mijenja se samo njihov redoslijed Kako se broj objekata povećava, broj permutacija raste vrlo brzo i postaje teško jasno ih prikazati.

Zadatak 1. Na turniru učestvuje sedam ekipa. Koliko je opcija za raspodjelu mjesta između njih moguće? P 7 =7!=1*2*3*4*5*6*7=5040 Odgovor: 5040 Zadatak 2. Na koliko načina 10 ljudi može sjediti za okruglim stolom? R 10 =10! = = 1*2*3*4*5*6*7*8*9*10 = Odgovor:

Neka postoji n različitih objekata. Od njih ćemo odabrati m objekata i preurediti ih na sve moguće načine među sobom. Rezultirajuće kombinacije nazivaju se smještajima n objekata po m, a njihov broj je jednak: Prilikom postavljanja mijenja se i sastav odabranih objekata i njihov redoslijed. Formula plasmana:

Problem: Na koliko načina se tri vaučera za jedan sanatorijum mogu podijeliti na pet osoba? Budući da se vaučeri dodjeljuju jednom sanatoriju, mogućnosti distribucije se međusobno razlikuju po najmanje jednoj osobi. Dakle, broj metoda distribucije Odgovor: 10 metoda.

Zadatak: U radionici radi 12 ljudi: 5 žena i 7 muškaraca. Na koliko načina se može formirati tim od 7 ljudi tako da u njemu budu 3 žene? Od pet žena, tri moraju biti odabrane, otuda i broj metoda selekcije. Pošto je potrebno izabrati četiri muškarca od sedam, onda je broj metoda za odabir muškaraca Odgovor: 350

Osnove kombinatorike.

Plasmani, preuređenje,

kombinacije.

Naughty Monkey

magarac,

koza,

Da, klupkonogi Mishka

Počeli smo da sviramo kvartet

Stanite, braćo, prestanite! –

Majmun viče, - čekaj!

Kako treba da ide muzika?

Uostalom, ti ne sediš tako...

I ovako i da su se zamenili - opet muzika ne ide.

Sada postaju još intenzivniji nego ikad

I sporovi

Ko i kako da sedi...

znati:

definicije tri najvažnijih koncepata kombinatorika:
postavljanje n elemenata po m;
kombinacije od n elemenata, po m;
permutacije n elemenata;
osnovne kombinatorne formule

biti u stanju:

razlikovati zadatke „permutacije“, „kombinacije“, „pozicije“ jedne od drugih;
primijeniti osnovne kombinatorne formule pri rješavanju jednostavnih kombinatornih problema.

mnogi

Skup karakterizira udruživanje nekih homogenih objekata u jednu cjelinu.

Objekti koji formiraju skup nazivaju se elementi skupa.

Napisat ćemo skup raspoređujući njegove elemente u vitičaste zagrade ( a, b, c, … , e, f}.

U skupu, redoslijed elemenata nije bitan, pa ( a, b} = {b, a}.

Poziva se skup koji ne sadrži niti jedan element prazan set i označen je simbolom ø.

mnogi

Ako svaki element skupa A je element skupa B, onda kažemo da je skup A je podskup skupa IN.

Mnogi ( a, b) je podskup skupa ( a, b, c, … , e, f}.

Određeno

Lista moguće opcije podskupovi skupa ( 3 , 4 , 5 , 7, 9 }.

Kombinatorika je grana matematike koja proučava pitanja o tome koliko različitih kombinacija, pod određenim uvjetima, može biti napravljeno od elemenata koji pripadaju datom skupu.

Kombinatorika je važna grana matematike koja proučava obrasce rasporeda, poretka, odabira i raspodjele elemenata iz fiksnog skupa.

PRAVILO ZBIRANJA

Ako se mogu izvršiti dvije međusobno isključive radnje prema k I m načina, onda se može izvršiti jedna od ovih radnji k+m načine.

Primjer br. 1

Od grada A do grada B možete stići sa 12 vozova, 3 aviona, 23 autobusa. Na koliko načina možete stići od grada A do grada B?

Rješenje

Primjer br. 2

U kutiji se nalazi n kuglica različitih boja. Nasumično vadimo jednu loptu. Na koliko načina se to može učiniti?

Rješenje. svakako, n načine.

Sada je ovih n loptica raspoređeno u dvije kutije: U prvoj m lopte, u drugom k. Nasumično vadimo jednu loptu iz neke kutije. Na koliko različitih načina se to može učiniti?

Rješenje.

Možete izvući loptu iz prve kutije m na razne načine, od drugog k na razne načine, ukupno N = m + k načine.

PRAVILO ZA PROIZVOD

Neka se u skladu s tim izvode dvije radnje koje se izvode jedna za drugom k I m načina Tada se oba mogu učiniti k∙m načine.

Primjer br. 3

Na turniru učestvuje 8 hokejaških ekipa. Na koliko načina postoji raspodjela prvog, drugog i trećeg mjesta?

Rješenje

Primjer br. 4

Koliko dvocifrenih brojeva možete zapisati u decimalnom brojevnom sistemu?

Rješenje. Pošto je broj dvocifren, onda je broj desetica ( m) može imati jednu od devet vrijednosti: 1,2,3,4,5,6,7,8,9. Broj jedinica ( k) može imati iste vrijednosti i može, osim toga, biti jednak nuli. Iz toga slijedi m= 9, a k= 10. Ukupno dobijamo dvocifrene brojeve

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

Primjer br. 5

U studentskoj grupi je 14 djevojčica i 6 dječaka. Na koliko načina dva učenika istog pola mogu biti odabrana da završe različite zadatke?

Rješenje. Prema pravilu množenja, dvije djevojčice se mogu izabrati na 14 · 13 = 182 načina, a dva dječaka na 6 · 5 = 30 načina. Treba izabrati dva učenika istog pola: dva studenta ili studentkinje. Prema pravilu sabiranja takvih metoda selekcije, postojaće

N =182 + 30 = 212.

Vrste veze

Skupovi elemenata se nazivaju veze.

Postoje tri vrste veza:

permutacije iz n elementi;
smještaj od n elementi po m;
kombinacije od n elementi po m (m < n).

Definicija: Permutacija od n elementi je bilo koji uređeni skup n elementi.

Drugim riječima, ovo je skup za koji je naznačeno koji je element na prvom mjestu, koji je na drugom, koji je na trećem, ..., koji je na n-om mjestu.

PERmutacije

Preuređenje- ovo su veze prema n elemenata iz datih elemenata koji se međusobno razlikuju po redoslijedu elemenata.

Broj permutacija n elemenata je označen sa Pn.

Rn = n · ( n- 1) · ( n– 2) · … · 2 · 1 = n!

Definicija:

Neka n- prirodni broj. Kroz n! (čitaj "en factorial") označava broj jednak proizvodu svih prirodnih brojeva 1 od do n:

n! = 1 · 2 · 3 · ... · n.

U slučaju n= 0, po definiciji se pretpostavlja: 0! = 1.

FACTORIA

Primjer br. 6

Nađimo vrijednosti sljedećih izraza: 1! 2! 3!

Primjer br. 7

Šta je jednako

A) R 5 ;

b) R 3.

Primjer br. 8

Pojednostavite

b) 12! · 13 · 14

V) κ ! · ( κ + 1)

Primjer br. 9

Na koliko načina se 8 učesnika finalne trke može rasporediti na osam traka za trčanje?

Rješenje.

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

SMJEŠTAJ

Definicija. Smještaj od n elemenata od m je bilo koji naručeni skup m elementi, koji se sastoje od elemenata n skup elemenata.

Broj plasmana od m elementi po n stoji za:

izračunato po formuli:

Primjer br. 9

Učenici 11. razreda izučavaju 9 nastavnih predmeta. Možete staviti 4 različita predmeta u svoj raspored za jedan dan. Koliko ih postoji na razne načine zakazivanje za jedan dan?

Rješenje.

Imamo skup od 9 elemenata čiji elementi obrazovnih predmeta. Prilikom kreiranja rasporeda, izabraćemo podskup od 4 elementa (lekcija) i postaviti redosled u njemu. Broj takvih metoda jednak je broju plasmana od devet do četiri ( m=9, n=4) to jest A 94:

Primjer br. 10

Na koliko načina se može izabrati župan i pomoćnik župana iz razreda od 24 učenika?

Rješenje.

Imamo skup od 24 elementa čiji su elementi učenici razreda. Prilikom izbora župana i pomoćnika župana biramo podskup od 2 elementa (učenika) i u njemu postavljamo redoslijed. Broj takvih metoda jednak je broju plasmana od devet do četiri ( m=24, n=2), tj A 242:

KOMBINACIJE

Definicija. Kombinacija bez ponavljanja n elementi po m- zove bilo koji m elementarni podskup n-komplet elemenata

Broj kombinacija od n elemenata sa m je označen sa

i izračunati po formuli:

Primjer br. 11

Na koliko načina se mogu izabrati dva polaznika iz razreda od 24 učenika?

Rješenje.

n =24, m=2

KOMBINACIJE

SMJEŠTAJ

PERmutacije

Rn = n!

Odredite kojoj vrsti veza pripada zadatak.

1. Na koliko načina možete zakazati jedan školski dan sa 5 različitih časova?

2. U odeljenju 9B ima 12 učenika. Na koliko načina možete formirati tim od 4 osobe za učešće na matematičkoj olimpijadi?

Da li se uzima u obzir redosled elemenata u vezi?

Da li su svi elementi uključeni u vezu?

Zaključak: permutacija

Da li se uzima u obzir redosled elemenata u vezi?

Da li su svi elementi uključeni u vezu?

(nije potreban odgovor na ovo pitanje)

Zaključak: kombinacije

3. Koliko ima različitih dvocifrenih brojeva u kojima se mogu koristiti brojevi 1, 2, 3, 4, 5, 6 ako brojevi u broju moraju biti različiti?

Da li se uzima u obzir redosled elemenata u vezi?

Da li su svi elementi uključeni u vezu?

Zaključak: plasman

Naughty Monkey

Da, klupkonogi Mishka

Počeli smo da sviramo kvartet

Stanite, braćo, prestanite! –

Majmun viče, - čekaj!

Kako treba da ide muzika?

Uostalom, ti ne sediš tako...

I ovako i da su zamenili mesta - opet muzika ne ide.

Sada postaju još intenzivniji nego ikad

Ko i kako da sedi...

Koliko je mogućih različitih aranžmana muzičara?

Rješenje.

Da li se uzima u obzir redosled elemenata u vezi?

Da li su svi elementi uključeni u vezu?

Zaključak: permutacija

Rn = n! =n · ( n- 1) · ( n– 2) · … · 2 · 1

P4 = 4! = 4 3 2 1=24

“Pre ili kasnije, svaka ispravna matematička ideja nađe primenu u jednoj ili drugoj stvari”?

permutacije

smještaj

kombinacija

Rezultati rješavanja problema

DOMAĆI ZADATAK

Naučite bilješke i formule.

S. 321 br. 1062

KOMBINATORIKA

Ciljevi lekcije:

Saznajte koje studije kombinatorike
Saznajte kako je nastala kombinatorika
Proučite kombinatoričke formule i naučite kako ih primijeniti prilikom rješavanja problema

Rođenje kombinatorike kao grane matematike povezuje se s radovima Blaisea Pascal-a i Pierrea Ferma-a o teoriji kockanja.

Blaise Pascal

Pierre Fermat

Veliki doprinos razvoju kombinatornih metoda dao je G.V. Leibniz, J. Bernoulli i L. Euler.

G.V. Leibniz

L. Euler.

J. Bernoulli

Lemma. Neka skup A ima m elemenata, a skup B ima n elemenata. Tada će broj svih različitih parova (a,b), gdje će a\in A,b\in B biti jednak mn. Dokaz. Zaista, sa jednim elementom iz skupa A možemo napraviti n tako različitih parova, a ukupno ima m elemenata u skupu A.

Položaji, permutacije, kombinacije Neka imamo skup od tri elementa a,b,c. Na koji način možemo odabrati dva od ovih elemenata? ab,ac,bc,ba,ca,cb.

Preuređenje Mi ćemo ih preurediti na sve moguće načine (broj objekata ostaje nepromijenjen, mijenja se samo njihov redoslijed). Dobivene kombinacije nazivaju se permutacije, a njihov broj je jednak Pn = n! =1 · 2 · 3 · ... · ( n-1)n

Simbol n! naziva se faktorijalom i označava proizvod svih cijelih brojeva od 1 do n. Po definiciji se vjeruje da 0!=1 1!=1 Primjer svih permutacija n=3 objekta (različite figure) je na slici. Prema formuli, trebalo bi da bude tačno P3=3!=1⋅2⋅3=6 , i to se dešava.

Kako se broj objekata povećava, broj permutacija raste vrlo brzo i postaje teško jasno ih prikazati. Na primjer, broj permutacija 10 objekata je već 3628800 (više od 3 miliona!).

Placements Neka postoji n različitih objekata. Od njih ćemo odabrati m objekata i preurediti ih na sve moguće načine (odnosno, mijenja se i sastav odabranih objekata i njihov redoslijed). Dobivene kombinacije nazivaju se postavljanjem n objekata po m, a njihov broj je Aⁿm =n!(n−m)!=n⋅(n−1)⋅...⋅(n−m+1)

Definicija. Postavljanjem skupa od n različitih elemenata u m elemenata (m ≤ n) su pozvani kombinacije , koji su sastavljeni od datih n elemenata po m elemenata i razlikuju se ili po samim elementima ili po redoslijedu elemenata.

Kombinacije Neka postoji n različitih objekata. Od njih ćemo odabrati m objekata na svaki mogući način (odnosno, sastav odabranih objekata se mijenja, ali redoslijed nije važan). Dobivene kombinacije nazivaju se kombinacijama od n objekata po m, a njihov broj je Cmn=n!(n−m)!⋅m!

Primjer svih kombinacija n=3 objekta (različite figure) sa m=2 je na slici ispod. Prema formuli, trebalo bi da bude tačno C23=3!(3−2)!⋅2!:3!=3. Jasno je da uvijek ima manje kombinacija nego plasmana (pošto je redoslijed važan za plasmane, ali ne i za kombinacije), a konkretno u m! puta, odnosno formula veze je tačna: Amn=Cmn⋅Pm.

Metoda 1. U jednoj igri učestvuju 2 osobe, stoga morate izračunati na koliko načina možete odabrati 2 osobe od 15, a redoslijed u takvim parovima nije bitan. Koristimo formulu da pronađemo broj kombinacija (uzoraka koji se razlikuju samo po sastavu) od n različitih elemenata od m elemenata svaki

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

Metoda 2. Prvi igrač je odigrao 14 utakmica (2., 3., 4. i tako do 15.), 2. igrač je odigrao 13 utakmica (3., 4. itd. do 15. pa isključujemo činjenicu da je već bila utakmica). prvi), 3. igrač - 12 utakmica, 4. - 11 utakmica, 5 - 10 utakmica, 6 - 9 utakmica, 7 - 8 utakmica, 8 - 7 utakmica,

a 15. je već igrao sa svima.

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

ODGOVOR. 105 utakmica.

Nastavnica matematike Svetlana Valerievna Aksenova

Srednja škola Bugrovskaya, Okrug Vsevoložsk, Lenjingradska oblast

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

Prezentaciju na temu “Diskretne analize” možete preuzeti na našoj web stranici. Predmet projekta: Računarstvo. Šarene slajdove i ilustracije pomoći će vam da uključite svoje kolege iz razreda ili publiku. Za pregled sadržaja koristite plejer, ili ako želite da preuzmete izveštaj, kliknite na odgovarajući tekst ispod plejera. Prezentacija sadrži 24 slajda.

Slajdovi za prezentaciju

Slajd 1

Diskretna analiza

Predavanje 3 Kombinatorika. Preuređenje

Slajd 2

Preuređenje

Neka je zadan skup od n elemenata. Redoslijed ovih elemenata naziva se permutacija. Ponekad dodaju “od n elemenata”. Obično se razlikuje jedno osnovno ili prirodno uređenje, koje se naziva trivijalna permutacija. Sami elementi skupa A nas ne zanimaju. Često su elementi cijeli brojevi od 1 do n ili od 0 do n-1. Označimo skup permutacija n elemenata sa Pn, a njegovu kardinalnost sa Pn. Postavimo ista tri pitanja: koliko je Pn jednako, kako iterirati kroz elemente Pn, kako ih prenumerisati.

Slajd 3

Teorema o broju permutacija

Broj permutacija n elemenata je n! - proizvod brojeva od 1 do n. (n! čitaj n-faktorski) Dokaz. Indukcijom. Za n=1 formula je očigledno tačna. Neka je tačno za n-1, dokažimo da je tačno i za n. Prvi element poretka može se odabrati na n načina, a ostali se mogu dodijeliti odabranom prvom elementu na načine. Dakle, formula Pn= Pn-1n je tačna. Ako je Pn-1=(n-1)!, tada je Pn=n!

Slajd 4

Numeracija permutacija

Za permutacije brojeva, skup Pn ćemo preslikati jedan na jedan u drugi skup Tn, na kojem će biti mnogo lakše uvesti numeraciju, a zatim ćemo za bilo koji element pPn uzeti broj njegove slike u Tn kao njegov broj. Skup Tn je direktan proizvod nekoliko numeričkih segmenata Tn =(0:(n-1))(0:(n-2) … (0). To jest, svaki element Tn je skup ne -negativni brojevi i1, i2, …, in-1, in i ikn-k.

Slajd 5

Display

Uzmimo permutaciju i napišimo trivijalnu permutaciju pored nje. Kao prvi indeks, uzimamo mjesto prvog elementa (računajući od nule) u trivijalnoj permutaciji. Umjesto trivijalne permutacije, zapišimo niz preostalih znakova. Kao drugi indeks uzimamo mjesto drugog elementa permutacije u ovom redu. Ponovimo postupak do kraja. Očigledno, k-ti indeks će biti manji od dužine k-tog niza, a posljednji indeks će biti jednak nuli. Pogledajmo ovaj proces na primjeru.

Slajd 6

Primjer prikaza

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 g 2 0 1 b 2 e 2 0 2 0 1 2 2 e e 0 2 0 1 2 2 0 0 Očigledno , ovaj proces je reverzibilan i inverzno preslikavanje će konstruirati originalnu permutaciju iz skupa indeksa.

Slajd 7

Numeracija skupa Tn

Svaki direktan proizvod uređenih skupova može se smatrati brojevnim sistemom sa promenljivom bazom. Prisjetite se primjera sekundi iz prvog predavanja ili razmotrite neku staru skalu veličine: 1 jar = 3 stope, 1 stopa = 12 inča, 1 inč = 12 linija, 1 linija = 6 bodova. (2, 0, 4, 2, 3) = 2 jarda 0 stopa 4 inča 2 linije 3 boda, koliko je to bodova? Morate prebrojati (ovo se zove Hornerova šema) (((2  3+0)  12+4)  12+2)  6+3

Slajd 8

Numeracija skupa Tn - 2

Radije pišemo formulu # koja pronalazi broj za skup indeksa i1, i2, …, in-1, in u obliku ponavljajućih izraza #(i1, i2, …, in) = a(i1, i2, …, u-1, n-1); a(i1, i2, …, ik,k) = a(i1, i2, …, ik-1,k-1)(n-k+1)+ ik; a(prazno,0) = 0; Prema ovoj formuli #(2,0,1,2,2,0,0) = a(2,0,1,2,2,0,6). Imamo 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

Iteracija preko skupova indeksa

Na osnovu gore navedenog, jednostavno je nabrojati permutacije: potrebno je nabrojati sve skupove indeksa iz i za svaki skup konstruirati odgovarajuću permutaciju. Za nabrajanje skupova indeksa, imajte na umu da je u stvari svaki skup zapis broja u posebnom brojevnom sistemu sa varijabilnom bazom (sistem se naziva faktorijalni). Pravila za sabiranje 1 u ovom sistemu su skoro isto tako jednostavna kao u binarnom sistemu: pomerajući se od poslednje cifre, pokušajte da dodate 1 na trenutnu cifru, prestanite sa dodavanjem 1. Ako to nije moguće, upišite nulu u bit i prijeđite na sljedeći bit.

Slajd 10

Nabrajanje skupova indeksa - 2

Pogledajmo primjer: 7 6 5 4 3 2 1 Ovo su promjenjive baze 3 4 4 2 1 1 0 3 4 4 2 2 0 0 Imajte na umu da je u 3 4 4 2 2 1 0 svakom redu početak 3 4 4 3 0 0 0 isto kao u prethodnom, 3 4 4 3 0 1 0 zatim dolazi element, striktno 3 4 4 3 1 0 0 veći, . . . , i 3 4 4 3 1 1 0 ono što slijedi nije značajno. 3 4 4 3 2 0 0 To znači da je svaki red 3 4 4 3 2 1 0 leksikografski veći od 3 5 0 0 0 0 0 prethodnog. 3 5 0 0 0 1 0

Slajd 11

Teorema o leksikografskom nabrajanju permutacija

Opisani algoritam iterira kroz permutacije u leksikografskom rastućem redoslijedu. Dokaz. Dovoljno je da pokažemo da ako imamo dva skupa indeksa I1 i I2, a I1 je leksikografski ispred I2, onda je permutacija (I1) leksikografski ispred (I2). Ove permutacije se formiraju sekvencijalno, i sve dok se I1 i I2 poklapaju, poklapaju se i njihove permutacije. A veća vrijednost indeksa odgovara većem elementu.

Slajd 12

Direktni algoritam za leksikografsko nabrajanje permutacija

Uzmimo bilo koju permutaciju p i direktno pronađimo sljedeću leksikografski. Uzmimo početak - prvih k elemenata. Među njegovim ekstenzijama postoji minimalno, u kojem su svi elementi raspoređeni rastućim redoslijedom, i maksimalno, u kojem su svi elementi raspoređeni u opadajućem redoslijedu. Na primjer, u permutaciji p =(4, 2, 1, 7, 3, 6, 5) svi nastavci za (4, 2, 1) leže između (3, 5, 6, 7) i (7, 6, 5, 3). Postojeći nastavak je manji od maksimuma, a 3. element još uvijek nije potrebno mijenjati. I 4. takođe. A 5. treba promijeniti. Da biste to učinili, od preostalih elemenata morate uzeti sljedeći po redu, staviti ga na 5. i dodijeliti minimalni nastavak. Dobijate (4, 2, 1, 7, 5, 3, 6).

Slajd 13

Direktan algoritam za leksikografsko nabrajanje permutacija - 2

Zapišimo sljedećih nekoliko permutacija. (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

Formalni opis algoritma

Radno stanje: Permutacija p i Boolean atribut je Aktivan. Početno stanje: Trivijalna permutacija je zapisana u i isActive = True. Standardni korak: Ako je Aktivno, vratite permutaciju kao rezultat. Krećući se s kraja, pronađite najveći monotono opadajući sufiks u permutaciji. Neka je k pozicija ispred sufiksa. Stavite isActive:= (k > 0). Ako je isActive, onda pronađite najmanji element u sufiksu koji je veći od pk, zamijenite ga s pk, a zatim "okrenite" sufiks.

Slajd 15

Drugi algoritam za nabrajanje permutacija

Pokušajmo sada da sredimo permutacije tako da se dvije uzastopne permutacije malo razlikuju jedna od druge. Koliko malo? Jedna elementarna transpozicija u kojoj se dva susjedna elementa zamjenjuju. Je li to moguće? pokazaćemo ti shematski dijagram takav algoritam će nas zanimati. Zamislite n-1 elementarnih „mehanizama“, od kojih svaki pomiče svoj element unutar skupa. Na svakom koraku mehanizam pravi pomak ulijevo ili udesno. Smjer se mijenja kada element dosegne ivicu. Promjena smjera traje jedan korak, pri čemu sljedeći mehanizam čini korak, koji, međutim, također može promijeniti smjer.

Slajd 16

Drugi algoritam za nabrajanje permutacija -2

Pogledajmo primjer. 1 2 3 4 5 Čiji je to potez 1 2 3 4 5 Čiji je to potez

Slajd 17

Nabrajanje permutacija. 1

funkcija ExistsNextPerm(var kCh: integer): Boolean; var iV,iP,iVC,iPC: cijeli broj; početak rezultata:= Netačno; za iV:= nV do 2 uradi ako se računa

Slajd 18

Problem minimalne sume proizvoda u paru

Neka su data dva skupa od po n brojeva, recimo, (ak|k1:n) i (bk|k1:n) . Ovi brojevi se dijele na parove (ak,bk) i izračunava se zbir njihovih proizvoda u paru k1:n akbk. Možete promijeniti numeraciju (ak) i (bk). Morate odabrati numeraciju koja minimizira iznos. U ovom problemu možete popraviti neke numeracije (ak) i (bk) i tražiti permutaciju  za koju se postiže minimalni zbir k1:n akb(k). Odabrat ćemo numeraciju kada je (ak) u rastućem redoslijedu, a (bk) u opadajućem.

Slajd 19

Teorema o minimalnom zbroju proizvoda u paru

Minimalni zbir proizvoda u paru postiže se trivijalnom permutacijom. Dokaz. Pretpostavimo da postoje dva indeksa k i r takva da je ak 0, tj. ar br + ak bk > ar bk + ak br . U našoj numeraciji (ak) su poredani uzlaznim redom. Ako (bk) nisu raspoređeni u rastućem redosledu, onda postoji par k i r, kao što je gore navedeno. Preuređivanjem bk i br za ovaj par, smanjit ćemo vrijednost sume. To znači da su u optimalnom rješenju (bk) u rastućem redoslijedu. Kasnije ćemo se susresti s ovom jednostavnom teoremom nekoliko puta.

Slajd 20

Problem maksimalnog povećanja podniza

Dat niz (ak|k1:n) brojeva dužine n. Potrebno je pronaći njegov niz najveće dužine u kojem bi se brojevi (ak) pojavljivali u rastućem redoslijedu. Na primjer, u nizu 3, 2, 11, 14, 32, 16, 6, 17, 25, 13, 37, 19, 41, 12, 7, 9, maksimalna podsekvenca će biti 2, 11, 14, 16 , 17, 25, 37, 41 Ovaj problem se odnosi na permutacije po tome što originalni niz može biti permutacija. Ograničićemo se na to da pokažemo kako se ovaj problem rešava, a slušaocima ćemo pružiti formalizaciju i opravdanje algoritma.

Slajd 21

Pronalaženje maksimalnog rastućeg niza

Mi ćemo što ekonomičnije naše podijeliti na opadajuće sekvence (primjer je promijenjen) 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 15 16 7 19 21 Svaki naredni broj ispisuje se na samom vrhu redova, gdje neće poremetiti redoslijed. Uzmimo broj iz donjeg reda, 21. Zašto je u 8. redu? Njega ometa 19. A broj 19 ometa 17. I on je 16. Itd. Niz 9, 11, 14, 16, 17, 19, 21 se povećava i ima dužinu 7. Bilo koji niz veći dužina sadrži dva broja iz iste linije (Dirichletov princip) i ne može se povećavati.

Slajd 22

Problem minimalnog broja inverzija

Dat je niz (ak|k1:n) brojeva dužine n. Nazovimo inverziju in-place zrcalnom slikom bilo kojeg od njenih podnizova - kontinuiranom podnizom Potrebno je rasporediti elemente niza u rastućem redoslijedu u minimalnom broju inverzija. Na primjer, "čvrsta" permutacija može se transformirati na sljedeći način (crvena slova su preuređena, velika su već na mjestu)

Slajd 23

Ispitna pitanja

Preuređenja. Njihovo nabrajanje i numerisanje. Minimalni problem tačkasti proizvod. Najveći problem rastuće podsekvencije.

Slajd 24

1. Dvosmjerna prijelazna permutacija  broj 2. Nađite permutaciju udaljenu od date za dati broj stepenice. 3. Nabrajanje permutacija elementarnim transpozicijama. 4. Pokrenite primjer za problem minimiziranja skalarnog proizvoda.

Savjeti za izradu dobre prezentacije ili izvještaja o projektu

Pokušajte da uključite publiku u priču, uspostavite interakciju sa publikom koristeći sugestivna pitanja, deo igre, ne plašite se šale i iskreno nasmešite (gde je prikladno).
Pokušajte objasniti slajd svojim riječima, dodajte dodatne zanimljive činjenice, ne morate samo čitati informacije sa slajdova, publika ih može sama pročitati.
Nema potrebe da preopterećujete slajdove vašeg projekta s više ilustracija, a minimum teksta će bolje prenijeti informacije i privući pažnju. Slajd treba da sadrži samo ključne informacije, ostalo je bolje reći slušaocima usmeno.
Tekst mora biti dobro čitljiv, inače publika neće moći vidjeti informacije koje se iznose, bit će u velikoj mjeri odvučene od priče, pokušavajući barem nešto razabrati, ili će potpuno izgubiti svaki interes. Da biste to učinili, morate odabrati pravi font, uzimajući u obzir gdje i kako će se prezentacija emitovati, kao i odabrati pravu kombinaciju pozadine i teksta.
Važno je da uvježbate svoj izvještaj, razmislite kako ćete pozdraviti publiku, šta ćete prvo reći i kako ćete završiti prezentaciju. Sve dolazi sa iskustvom.
Odaberite pravi outfit, jer... Odjeća govornika također igra veliku ulogu u percepciji njegovog govora.
Pokušajte da govorite samouvereno, glatko i koherentno.
Pokušajte da uživate u nastupu, tada ćete biti opušteniji i manje nervozni.