Előadás az algebra és az elemzési elvek leckéhez a "Kombinatorika: mozgások, permutációk, kombinációk" témában. Előadás „Diszkrét elemzés

A kombinatorika elemei

PERmutációk

Az óra céljai

1. Határozza meg a „permutáció” fogalmát

2. Vezesse le a permutációs képletet!

3. Ismerkedjen meg a „faktoriális” fogalmával

4. Tanuld meg a permutációs képlet alkalmazását a legegyszerűbb esetekben

5. A megszerzett tudás felhasználása új helyzetekben

Óraterv

1. Bibliográfiai információk

2. A permutáció fogalmának bemutatása és a képlet levezetése

3. Feladatok megoldása permutációs képlet segítségével

4. Önálló munkavégzés

5. Óra összefoglalója

6. Házi feladat

Bibliográfiai információk

A " kifejezés permutációk »

első használat

svájci matematikus

odin egyik alapítója

valószínűségszámítás és

matematikai elemzés Jacob Bernoulli

(27.12.1654 - 16.8.1705)

a "Spekuláció művészete" című könyvben

Meghatározás

1. A permutációk ugyanazokból álló kombinációk n különböző elemek és csak elrendezésük sorrendjében különböznek egymástól

2. Permutációk - olyan vegyületek, amelyek n objektumból állhatnak, sorrendjüket minden lehetséges módon megváltoztatva

Permutációs képlet

4∙3∙2∙1 = 24

1∙2∙3∙4∙5=120

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

Az egymást követő első n természetes szám szorzatát n-nel jelöljük! és olvassa el az „en factorial”

"tényező" - szorzó

„en faktoriális” – n faktorból áll

Faktoriális

Képlet n ! = 1∙2∙3∙4∙ … ∙ ( n-1 )∙ n

Például

3! = 1∙2∙3 = 6

Emlékezz 0-ra! = 1 és 1! = 1

Kényelmes formula n ! = ( n-1 )!∙ n

Például: 6! = 5!∙6 = 120∙6 = 720

Helyesen van megírva a permutációk számításának képlete?

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

Elmezavar

1. Számolja ki:

Hányféleképpen lehet különböző zászlókat készíteni három egyenlő méretű fehér, kék és piros anyagdarab vízszintes elhelyezésével?

P 3 = 3! = 1,2∙3 = 6

Válasz: 6 módon

Egyes országok állami jelképei

• Oroszország zászlaja

• Hollandia zászlaja Jugoszlávia zászlaja

A megszerzett ismeretek alkalmazása új helyzetben

1. Számolja ki:

7 = 9!∙6! 7!∙8! Válasz: 9!∙6! 7!∙8! "width="640"

Sőt: 9!∙6! vagy 7!∙8! ?

Mert 9! = 8!∙9, majd 9!∙6! = 8!∙9∙6!

Mert 7! = 6! ∙ 7, majd 7!∙8! = 6! ∙ 7∙ 8!

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

Válasz: 9!∙6! 7!∙8!

Önálló munkavégzés

I. lehetőség

• Hányféleképpen ütemezhet be egy tanítási napot 5 különböző leckével?
• 2. Anya, Vera és Tanya vettek mozijegyet az első sor 1., 2. és 3. helyére. Hányféleképpen foglalhatják el a lányok ezt a három helyet?

lehetőség II

1. Hányféleképpen lehet 4 különböző könyvet elhelyezni egy könyvespolcon?

2. Hányféleképpen állhat sorba 3 ember a jegypénztárnál?

Vizsgálat

I. lehetőség

lehetőség II

• Válasz: 120 lehetőség
• Válasz: 6 módon

• Válasz: 24 módon
• Válasz: 6 módon

Sinkwine

1. sor – a fő témát kifejező főnév.

2. sor – a fő gondolatot kifejező két jelző.

3. sor – három ige, amelyek a témán belüli cselekvéseket írják le.

A 4. sor egy kifejezés, amely bizonyos jelentést hordoz.

5. sor – következtetés főnévi formában (asszociáció az első szóval).

Házi feladat

6.4. pont, tanulja meg a permutációs képletet

I. szint: 611. sz., 612. sz.,

II. szint: 616., 621. sz.

permutációk

MBOU "Yanishevskaya Basic School"

Tanár: Zvereva T.I.

A probléma megoldása:

Anton, Boris és Victor vásárolt

3 futballjegy a stadion első sorának 1., 2., 3. helyére. Hányféleképpen foglalhatják el a fiúk ezeket a helyeket?

Probléma megoldás:

• A sorrend a következő lehet:

A B C A C B

Ilyen lehet:

B V A B A V

Vagy lehet így:

V A B V B A

Válasz: 6 lehetőség

Emlékezz!!!

Átrendezés halmazának nevezzük n konkrétban írt elemek Rendben.

• Tétel egy véges halmaz elemeinek permutációiról:

n Különböző elemek helyezhetők el egyenként n pontosan különböző helyeken n! módokon.

Az utak száma megegyezik a permutációk számával

3 elemből. A permutációk számának képletével azt találjuk

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

Öt barát úgy döntött, hogy lefényképez. Hányféleképpen lehet ezt megtenni?

Feladat:

A 9. osztályban szerdán 6 óra van: matematika, irodalom,

Orosz nyelv, angol nyelv, biológia és testnevelés. Hány ütemezési lehetőséget hozhat létre?

Sorrendbe rakjuk a tételeket:

Összes opció

menetrendek:

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

Tétel

Matematika

Opciók száma

Irodalom

orosz nyelv

angol nyelv

Biológia

Testedzés

Feladat:

• Kilenc különböző könyv van, ebből négy tankönyv. Hányféleképpen lehet ezeket a könyveket egy polcon elhelyezni úgy, hogy az összes tankönyv egymás mellett legyen? Terv:

1) tankönyvek = könyv

2) A könyvek P6 permutációi

3) P6=6!

4) A tankönyvek P4 átrendezése

5) P4=4!

6) P 6 ∙ P4

Házi feladat:

1. Anya tavasszal sok gyümölcsöt vesz a gyermekének. Vett egy banánt, egy almát, egy narancsot, egy citromot, egy körtét és egy kivit. Keresse meg a lehetséges gyümölcsfogyasztási lehetőségek számát.

2 . Tizenegy játékos áll fel a mérkőzés kezdete előtt. Az első a kapitány, a második az

kapus, a többi pedig - véletlenszerűen.

Hány építési mód létezik?

3. Hányféleképpen lehet egy polcon elhelyezni 10 könyvet, amelyek közül 4 ugyanannak a szerzőnek, a többinek pedig különböző szerzőjétől van így, hogy egyazon szerző könyvei egymás mellett álljanak?

A következő alkalomig

kombinatorikus problémákkal

A permutációk ugyanazon elemekből álló kombinációk, amelyek megjelenési sorrendben különböznek egymástól. Az elemek összes lehetséges permutációjának számát P n jelöli, és a következő képlettel számítható ki: Permutációs képlet: P n =n! A permutáció során az objektumok száma változatlan marad, csak a sorrend változik Az objektumok számának növekedésével a permutációk száma nagyon gyorsan növekszik, és nehézkessé válik világosan ábrázolni.

1. feladat. Hét csapat vesz részt a versenyen. Hány lehetőség van köztük a helyek elosztására? P 7 =7!=1*2*3*4*5*6*7=5040 Válasz: 5040 2. feladat. Hányféleképpen ülhet 10 ember egy kerek asztalnál? R 10 = 10! = = 1*2*3*4*5*6*7*8*9*10 = Válasz:

Legyen n különböző objektum. M objektumot választunk ki belőlük, és minden lehetséges módon átrendezzük őket egymás között. Az így létrejövő kombinációkat n objektum m-es elhelyezésének nevezzük, és számuk egyenlő: Az elhelyezések során a kiválasztott objektumok összetétele és sorrendje is változik. Elhelyezési képlet:

Probléma: Hányféleképpen osztható ki öt ember között három utalvány egy szanatóriumra? Mivel az utalványokat egy szanatórium kapja, a kiosztási lehetőségek legalább egy személyben különböznek egymástól. Ezért az elosztási módszerek száma Válasz: 10 módszer.

Feladat: A műhelyben 12 fő dolgozik: 5 nő és 7 férfi. Hányféleképpen alakítható ki egy 7 fős csapat úgy, hogy 3 nő legyen benne? Öt nőből hármat kell kiválasztani, innen ered a kiválasztási módok száma. Mivel hétből négy férfit kell kiválasztani, a férfiak kiválasztásának módjainak száma Válasz: 350

1. dia

2. dia

3. dia

4. dia

5. dia

6. dia

7. dia

8. dia

9. dia

10. dia

11. dia

12. dia

13. dia

14. dia

15. dia

16. dia

17. dia

18. dia

19. dia

20. dia

21. dia

22. dia

23. dia

24. dia

A „Diszkrét elemzés” témájú előadás teljesen ingyenesen letölthető honlapunkról. A projekt tárgya: Számítástechnika. A színes diák és illusztrációk segítenek elkötelezni osztálytársait vagy közönségét. A tartalom megtekintéséhez használja a lejátszót, vagy ha le szeretné tölteni a jelentést, kattintson a megfelelő szövegre a lejátszó alatt. Az előadás 24 diát tartalmaz.

Bemutató diák

1. dia

Diszkrét elemzés

3. előadás Kombinatorika. Átrendezések

2. dia

Átrendezések

Legyen adott egy n elemű halmaz. Ezen elemek sorrendjét permutációnak nevezzük. Néha hozzáteszik, hogy „n elemből”. Általában egy alapvető vagy természetes sorrendet különböztetnek meg, amit triviális permutációnak neveznek. Maguk az A halmaz elemei nem érdekelnek bennünket. Az elemek gyakran 1-től n-ig vagy 0-tól n-1-ig terjedő egész számok. Jelöljük n elem permutációinak halmazát Pn-nel, számosságát pedig Pn-nel. Tegyük fel ugyanazt a három kérdést: mi egyenlő Pn, hogyan iterálhatjuk át a Pn elemeit, hogyan kell újraszámozni őket.

3. dia

Tétel a permutációk számáról

n elem permutációinak száma n! - 1-től n-ig terjedő számok szorzata. (n! olvasni n-tényezős) Bizonyítás. Indukcióval. n=1 esetén a képlet nyilvánvalóan helyes. Legyen igaz n-1-re, bizonyítsuk be, hogy n-re is igaz. A rendezés első eleme n módon választható ki, a többi pedig a kiválasztott első elemhez rendelhető hozzá. Ezért a Pn= Pn-1n képlet helyes. Ha Pn-1=(n-1)!, akkor Pn=n!

4. dia

Permutációk számozása

A permutációk számozásához a Pn halmazt egy az egyben leképezzük egy másik Tn halmazba, amelyen sokkal egyszerűbb lesz számozást bevezetni, majd bármely pPn elemre felvesszük a Tn-beli képének számát. a számát. A Tn halmaz több Tn =(0:(n-1))(0:(n-2) … (0) numerikus szegmens közvetlen szorzata, vagyis Tn minden eleme nem halmaza. -negatív számok i1, i2, …, in-1, in és ikn-k.

5. dia

Kijelző

Vegyünk egy permutációt, és írjuk mellé a triviális permutációt. Első indexként az első elem helyét foglaljuk el (nullától számolva) a triviális permutációban. Egy triviális permutáció helyett írjuk fel a megmaradt karakterek sztringjét. Második indexként a permutáció második elemének helyét foglaljuk el ebben a sorban. Ismételjük meg a folyamatot a végéig. Nyilvánvaló, hogy a k-adik index kisebb lesz, mint a k-adik karakterlánc hossza, az utolsó index pedig nullával egyenlő. Nézzük meg ezt a folyamatot egy példán keresztül.

6. dia

Kijelző példa

0 1 2 3 4 5 6 Index 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 12 2 2 e b e 0 2 0 1 2 2 e e 0 2 0 1 2 2 0 0 nyilvánvalóan , ez a folyamat megfordítható, és az inverz leképezés az eredeti permutációt indexek halmazából hozza létre.

7. dia

A Tn halmaz számozása

A rendezett halmazok bármely közvetlen terméke változó alapú számrendszernek tekinthető. Idézzük fel az első előadás második példáját, vagy vegyünk egy régi méretskálát: 1 yard = 3 láb, 1 láb = 12 hüvelyk, 1 hüvelyk = 12 sor, 1 sor = 6 pont. (2, 0, 4, 2, 3) = 2 yard 0 láb 4 hüvelyk 2 vonal 3 pont, hány pont ez? Számolnod kell (ezt nevezik Horner-sémának) (((2  3+0)  12+4)  12+2)  6+3

8. dia

A Tn - 2 halmaz számozása

Szívesebben írjuk fel a # képletet, amely megkeresi az i1, i2, …, in-1, in indexek számát ismétlődő kifejezések formájában #(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(üres,0) = 0; E képlet szerint #(2,0,1,2,2,0,0) = a(2,0,1,2,2,0,6). Van 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. dia

Indexkészletek iterálása

A fentiek alapján a permutációk felsorolása egyszerű: minden indexkészletet fel kell sorolni, és minden halmazhoz létre kell hozni egy megfelelő permutációt. Az indexhalmazok számbavételéhez vegye figyelembe, hogy valójában mindegyik halmaz egy szám rekordja egy változó bázisú speciális számrendszerben (a rendszert faktoriálisnak nevezik). Az 1 hozzáadásának szabályai ebben a rendszerben majdnem olyan egyszerűek, mint a bináris rendszerben: az utolsó számjegytől kezdve próbáljon meg 1-et hozzáadni az aktuális számjegyhez, majd hagyja abba az 1 hozzáadását. Ha ez nem lehetséges, írjon nullát a bitre, és lépjen tovább a következő bitre.

10. dia

Indexkészletek felsorolása - 2

Nézzünk egy példát: 7 6 5 4 3 2 1 Ezek változó alapok. 0 0 0 ugyanaz, mint az előzőnél, 3 4 4 3 0 1 0 ezután jön az elem, szigorúan 3 4 4 3 1 0 0 nagyobb, . . . , és 3 4 4 3 1 1 0 az alábbiak nem jelentősek. 3 4 4 3 2 0 0 Ez azt jelenti, hogy minden 3 4 4 3 2 1 0 sor lexikográfiailag nagyobb, mint az előző 3 5 0 0 0 0 0. 3 5 0 0 0 1 0

11. dia

Tétel a permutációk lexikográfiai felsorolásáról

A leírt algoritmus permutációkon keresztül, lexikográfiai növekvő sorrendben iterál. Bizonyíték. Elég megmutatnunk, hogy ha két I1 és I2 indexhalmazunk van, és I1 lexikográfiailag I2 előtt van, akkor a (I1) permutáció lexikográfiailag (I2) előtt áll. Ezek a permutációk egymás után jönnek létre, és amíg I1 és I2 egybeesik, a permutációik is egybeesnek. A nagyobb indexérték pedig nagyobb elemnek felel meg.

12. dia

Közvetlen algoritmus permutációk lexikográfiai felsorolására

Vegyünk egy tetszőleges p permutációt, és közvetlenül keressük meg lexikográfiailag a következőt. Vegyük az elejét – az első k elemet. Kiterjesztései között van egy minimális, amelyben minden elem növekvő sorrendben, és egy maximum, amelyben minden elem csökkenő sorrendben van elrendezve. Például a p =(4, 2, 1, 7, 3, 6, 5) permutációban a (4, 2, 1) összes folytatása (3, 5, 6, 7) és (7, 6, 5, 3). A meglévő folytatás kisebb, mint a maximum, és a 3. elemet továbbra sem kell módosítani. És a 4. is. Az 5-öst pedig változtatni kell. Ehhez a fennmaradó elemekből sorba kell venni a következőt, 5. helyre kell tenni, és hozzá kell rendelni egy minimális folytatást. Kapsz (4, 2, 1, 7, 5, 3, 6).

13. dia

Közvetlen algoritmus a permutációk lexikográfiai felsorolásához - 2

Jegyezzük fel a következő néhány permutációt. (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. dia

Az algoritmus formális leírása

Működési állapot: A p permutáció és a logikai attribútum aktív. Kezdeti állapot: triviális permutáció van írva, és isActive = True. Normál lépés: Ha aktív, adja vissza a permutációt eredményként. A végétől haladva keresse meg a legnagyobb monoton csökkenő utótagot a permutációban. Legyen k az utótag előtti pozíció. Tedd isActive:= (k > 0). Ha aktív, akkor keresse meg az utótag legkisebb elemét, amely nagyobb, mint pk, cserélje fel pk-ra, majd „fordítsa meg” az utótagot.

15. dia

Egy másik algoritmus a permutációk számbavételére

Most próbáljuk meg úgy rendezni a permutációkat, hogy két egymást követő permutáció alig térjen el egymástól. Milyen kevés? Egy elemi transzpozíció, amelyben két szomszédos elem felcserélődik. Lehetséges ez? Mutassunk egy ilyen algoritmus sematikus diagramját, érdekelni fogunk. Képzeljünk el n-1 elemi „mechanizmust”, amelyek mindegyike mozgatja elemét a halmazon belül. A mechanizmus minden lépésnél balra vagy jobbra tolódik. Az irány megváltozik, amikor az elem eléri a szélét. Az irányváltás egy lépést tesz, közben a következő mechanizmus tesz egy lépést, amely azonban irányt is változtathat.

16. dia

Egy másik algoritmus a permutációk számbavételére -2

Lássunk egy példát. Kinek a lépése ez

17. dia

Permutációk felsorolása. 1

függvény ExistsNextPerm(var kCh: integer): Logikai; var iV,iP,iVC,iPC: egész szám; kezdő eredmény:= False; iV:= nV esetén 2 do if count

18. dia

A páronkénti termékek minimális összege

Legyen adott két-két n számból álló halmaz, mondjuk (ak|k1:n) és (bk|k1:n) . Ezeket a számokat párokra osztjuk (ak,bk), és kiszámítjuk a páronkénti szorzataik k1:n akbk összegét. Módosíthatja a számozást (ak) és (bk). Olyan számozást kell választania, amely minimalizálja az összeget. Ebben a feladatban kijavíthat néhány számozást (ak) és (bk), és kereshet egy  permutációt, amelyre a minimális k1:n akb(k) összeget elérjük. A számozást akkor választjuk ki, ha az (ak) növekvő sorrendben, a (bk) pedig csökkenő sorrendben van.

19. dia

Tétel a páronkénti szorzatok minimális összegéről

A páronkénti szorzatok minimális összegét triviális permutációval érjük el. Bizonyíték. Tegyük fel, hogy van két olyan k és r index, amelyre ak 0, azaz. ar br + ak bk > ar bk + ak br . Számozásunkban (ak) növekvő sorrendben vannak. Ha a (bk) nincs növekvő sorrendbe rendezve, akkor van egy k és r pár, amint azt fentebb leírtuk. A bk és br átrendezésével erre a párra csökkentjük az összeg értékét. Ez azt jelenti, hogy az optimális megoldásban (bk) növekvő sorrendben vannak. Ezzel az egyszerű tétellel később többször is találkozunk.

20. dia

Maximálisan növekvő utósorozat probléma

Adott egy n hosszúságú számsorozat (ak|k1:n). Meg kell találni annak a legnagyobb hosszúságú sorozatát, amelyben a számok (ak) növekvő sorrendben jelennének meg. Például a 3, 2, 11, 14, 32, 16, 6, 17, 25, 13, 37, 19, 41, 12, 7, 9 sorozatban a maximális részsorozat 2, 11, 14, 16 , 17, 25, 37, 41 Ez a probléma a permutációkkal kapcsolatos, mivel az eredeti sorozat lehet permutáció. A probléma megoldásának bemutatására szorítkozunk, és az algoritmus formalizálását és indoklását adjuk a hallgatóknak.

21. dia

A maximális növekvő utósorozat megkeresése

A lehető leggazdaságosabban felosztjuk a miénket csökkenő sorozatokra (a példa megváltozott) 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 157176 19 21 Minden következő szám a sorok legtetejére van írva, ahol nem zavarja a sorrendet. Vegyük a számot az alsó sorból, 21. Miért van a 8. sorban? A 19 akadályozza őt. És a 19-es számot 17 akadályozza. És ő 16. Stb. A 9, 11, 14, 16, 17, 19, 21 sorozat növekszik, hossza 7. Bármely nagyobb sorozat A hossza két számot tartalmaz ugyanabból a sorból (Dirichlet-elv), és nem növekedhet.

22. dia

Az inverziók minimális száma probléma

Adott egy n hosszúságú számsorozat (ak|k1:n). Nevezzük az inverziót bármely részkarakterláncának helybeni tükörképének – folytonos részsorozatnak. A sorozat elemeit minimális számú inverzióban növekvő sorrendbe kell rendezni. Például a „szilárd” permutáció a következőképpen alakítható át (a piros betűket átrendezték, a nagyok már a helyükön vannak)

23. dia

Vizsgakérdések

Átrendezések. Felsorolásuk és számozásuk. A skalárszorzat minimalizálásának problémája. A legnagyobb növekvő utósorozat probléma.

24. dia

1. Kétirányú átmenet permutáció  szám 2. Keressen egy permutációt, amely adott lépésszámra van az adotttól távol. 3. Permutációk felsorolása elemi transzpozíciókkal. 4. Futtasson példát a skalárszorzat minimalizálásának problémájára.

Tippek egy jó prezentáció vagy projektjelentés elkészítéséhez

1. Próbálja bevonni a közönséget a történetbe, alakítson ki interakciót a közönséggel irányító kérdések, játékrész segítségével, ne féljen viccelni és őszintén mosolyogni (adott esetben).
2. Próbáld meg saját szavaiddal elmagyarázni a diát, adj hozzá további érdekességeket, nem csak a diákról kell olvasnod, hanem a közönség is elolvashatja.
3. Nem kell túlterhelni a projekt diákjait szövegblokkokkal, és a minimális szöveg jobban átadja az információkat és felkelti a figyelmet. A dia csak kulcsfontosságú információkat tartalmazzon, a többit legjobban szóban kell elmondani a hallgatóságnak.
4. A szövegnek jól olvashatónak kell lennie, különben a közönség nem fogja látni a bemutatott információt, nagyon eltereli a figyelmét a történetről, megpróbál legalább valamit kitalálni, vagy teljesen elveszíti érdeklődését. Ehhez ki kell választania a megfelelő betűtípust, figyelembe véve, hogy hol és hogyan kerül adásba a prezentáció, valamint ki kell választania a háttér és a szöveg megfelelő kombinációját.
5. Fontos, hogy ismételje meg a beszámolót, gondolja át, hogyan köszönti a hallgatóságot, mit mond először, és hogyan fejezi be az előadást. Minden tapasztalattal jön.
6. Válassza ki a megfelelő ruhát, mert... A beszélő ruházata is nagy szerepet játszik beszédének észlelésében.
7. Próbáljon magabiztosan, gördülékenyen és koherensen beszélni.
8. Próbáld meg élvezni az előadást, akkor nyugodtabb és kevésbé ideges leszel.