1144 PROGRAMOZÁSMÓDSZERTAN, PROGRAMOZÁSI NYELVEK

A PROGRAMOZÁS MATEMATIKAI ALAPJAI

1144 PROGRAMOZÁSMÓDSZERTAN, PROGRAMOZÁSI NYELVEK

ESETFELVETÉS- MUNKAHELYZET A következő fejezetekben azokkal az alapvető matematikai alapokkal ismerkedhet meg, amelyek tudása elengedhetetlen az alapvető programozási ismeretek elsajátításához. Az elméleti anyag ismertetése után találhat néhány példát, ami bemutatja gyakorlati feladatokon keresztül az anyagot. A tananyag a következő témaköröket öleli fel: • • • • • •

Halmazelmélet Számfogalmak Logika Mátrixok Gráfelmélet Kombinatorika

SZAKMAI INFORMÁCIÓTARTALOM HALMAZELMÉLET 1. Alapfogalmak A halmaz különböző dolgoknak az összessége, amit meghatároznak az elemei. A következő kifejezéseket alapfogalomnak tekintjük, és ezért külön nem definiáljuk: halmaz, elem, eleme, a következő jelöléseket használva: A halmazok jelölése mindig nagybetűvel történik: A, B, C… A halmazok megadásának módjai:

1. Vegyes halmazok esetén a halmaz elemeinek felsorolásával pl. : A:={január, február,…, december} B:={1,2,3,4,5 }

2. a halmaz elemeire jellemző tulajdonság megadásával pl. : C:={a tanfolyam hallgatói} D:={prímszámok}

Üres halmaznak nevezzük azt a halmazt, amelynek nincs egy eleme sem. Jelölése : ∅

1

A PROGRAMOZÁS MATEMATIKAI ALAPJAI A halmaz elemeinek száma jelölésekor a halmazt abszolút érték jelek közé rakjuk :⎪A⎪ = 12 Megkülönböztetünk véges és végtelen halmazokat az elemeik száma alapján: •

Véges :

E:={ x ⎪x egész és -5 ≤ x ≤ 5 }

•

Végtelen :

F:={ egy sík pontjainak száma }

A halmazokat legtöbbször venn-diagramon ábrázoljuk : a sík valamely tartományával. A halmaz elemeinek ábrázolására : a tartomány pontjai szolgálnak: A

B

1 2 3 6

45

Az A halmazt a B halmaz részhalmazának nevezünk, ha az A halmaz minden eleme a B halmaznak is eleme.

Jelölése : A⊆B ⇔ , ha ∀x∈A -ra x∈B

B A

Az A halmazt a B halmaz valódi részhalmazának nevezzük, ha az A halmaz részhalmaza

B -nek, és a B halmaznak van legalább egy olyan eleme, amely nem eleme A -nak. Jelölése :A⊂ B (⇐ A⊆B és A≠B)

B A

2


2. Műveletek halmazokkal Unióképzés

Az A és B halmaz uniójának más szóval egyesítésének nevezzük azoknak az elemeknek a halmazát, amelynek az A és B halmazok közül legalább az egyiknek elemei. Jelölése : A∪B

A

B

A∪B={ x ⏐ x∈A vagy x∈B } Tulajdonságai : A∪A=A

idempotencia

A∪B=B∪A

kommutatív

(A∪B)∪C=A∪(B∪C)=A∪B∪C

asszociatív

A∪(B∩C)=(A∪B)∩(A∪C)

disztributívitás

A∩( B∪C)=(A∪B)∪(A∩C)

Metszet képzés Az

A

és

B

halmaz metszetének (közös részének; szorzatának) nevezzük azoknak az

elemeknek a halmazát, amelyek az A és B halmazok mindegyikének elemei. Az A és B halmaz diszjunkt, ha metszetük üres halmaz. Jelölése : A∩B

A

B

3

A PROGRAMOZÁS MATEMATIKAI ALAPJAI A∩B={ x⏐x∈A és x∈B } Tulajdonságai : A∩A=A

idempotencia

A∩B=B∩A

kommutatív

(A∩B)∩C=A∩(B∩C)=A∩B∩C

asszociatív

A∪(B∩C)=(A∪B)∩(A∪C)

disztributivitás

A∩( B∪C)=(A∪B)∪(A∩C)

Különbségképzés Az A és B halmazok különbségüknek nevezzük az A halmaz azon elemeinek halmazát, amelyek nem elemei a B halmaznak. Jelölése : A \ B

A

B

A \ B={ x⏐x∈A és x∉B } Tulajdonságai : A\A=∅ A\∅=A

∅\A=∅

(A \ B)∩(B \ A)= ∅ (A \ B)∪B=A∪B

A \ B=A \ (A∩B)=(A∪B) \ B

Halmaz komplementere (kiegészítő halmaz ) Egy B ( nem üres ) halmaznak legyen egy részhalma A . Az B \ A halmazt az egy halmaz B alaphalmazra vonatkozó komplementerének nevezzük. Jelölése : A

4

A PROGRAMOZÁS MATEMATIKAI ALAPJAI B

A⊂B

A

A

Tulajdonságai :

A∪B = A∩B A∩B = A∪B A∪A = H A∩A =∅ A=A Szimmetrikus differencia Két adott halmaz, A és B szimmetrikus differenciájának nevezzük, azt mikor a két

halmaz azon elemeit vesszük, amik csak az egyikben szerepelnek. A műveletet így definiáljuk : A Jelölése : A

B= (A \ B) ∪ (B \ A)

B

A

B

Tulajdonságai :

AΔB = BΔA (AΔB)ΔC = AΔ(BΔC) AΔA = ∅ AΔ∅ = A AΔ(AΔB) = B Összefoglalás Mit nevezünk halmaznak? 5

A PROGRAMOZÁS MATEMATIKAI ALAPJAI Hogyan jelöljük? Hogyan ábrázoljuk? Mi a végtelen halmaz? Milyen halmazműveleteket ismer?

SZAKMAI INFORMÁCIÓTARTALOM LOGIKA A számítástechnikában, de a köznapi életben is sokszor használjuk a logikát, melynek során bizonyos állítások (premisszák) igazságából következtetünk valamilyen állítás igazságára.

Definíció: Egy következtetést akkor tekintünk logikailag helyesnek, ha minden olyan esetben, amikor a benne szereplő egyszerű tovább már nem bontható kijelentések helyére tetszőleges olyan kijelentéseket teszünk, amelyeknél a premisszák mind igazak lesznek, a konklúzió is mindig igaz lesz.

Az ítélet fogalma: Azok a kijelentések, amelyek egyértelműen igazak vagy hamisak. Logikai értékek: Az 'igaz' és a 'hamis' tulajdonságok lehetnek csak.

1. Műveletek ítéletekkel A logikai műveletek: Az ítélet kalkulus műveletei ítéletekből úgymint komponensekből olyan ítéleteket hoznak létre, amelyek logikai értékét komponenseik logikai értékei egyértelműen

meghatározzák.

a, Negáció: művelete egy ítéletnek a tagadása. A negáció művelet eredménye akkor és csak akkor igaz ítélet, ha a művelet komponense

hamis.

6


Jele : ⎤

A

⎤A

i

h

h

i

b, Konjunkció: művelete két ítélet az "és" kötőszóval kapcsol össze. A konjunkció művelet logikai értéke akkor és csak akkor igaz, ha mindkét komponensének logikai értéke igaz

jele: ∧

A

B

A∧B

i

i

i

i

h

h

h

i

h

h

h

h

c, Diszjunkció: művelete két ítélet a megengedő "vagy" kötőszóval kapcsol össze.

7

A PROGRAMOZÁS MATEMATIKAI ALAPJAI A diszjunkció logikai értéke akkor és csak akkor hamis, ha mindkét komponense hamis.

Jele: ∨

A

B

A∨B

i

i

i

i

h

i

h

i

i

h

h

h

Disztributivitás: (A∧B)∨(A∧C)=A∧(B∨C) (A∨B) ∧(A∨B=A∨(B∧C)

Elnyelési szabályok: A∧(A∨B)=A A∨(A∧B)=A

Idempotencia (rövidítési szabály): A logikai algebrában nincs 1-nél nagyobb kitevő és 1-nél

nagyobb együttható sem.

A∧A=A A∨A=A

De Morgan azonosságok: 8


⎤(A∧B)=⎤A∨⎤B ; ⎤(A∨B)=⎤A∧⎤B

Kettős negáció:

⎤⎤A=A

Impikáció: P és Q ítéletből "ha P, akkor Q" alakú ítéletet hoz létre. jele P→Q P (előtag); Q (utótag). Rendszerint határozatlan logikai értékű ítéletek összekapcsolására használjuk.

Implikáció akkor és csak akkor hamis, ha az előtag igaz és az utótag hamis.

Tehát a P és Q ítéletek, akkor a P→Q implikációi általában a nem P vagy Q ítéleteket értjük ez akkor és csak akkor hamis, ha P igaz és Q hamis. Ha P akkor Q ítélet logikai értéke mindig azonos a P→Q implikáció logikai értékével.

Definíció: Formula: Az ítéletkalkulusban a log- értékeket a log-i változókat és a rajtuk

végzett műveleteket leíró jelsorozatokat az ítélet kalkulus formuláinak nevezzük.

Ekvivalencia: A P és Q ítéletre ekvivalencia P akkor és csak akkor, ha Q alakú ítéletet hoz létre. Jele: P↔Q A P↔Q alakú ítéletek logikai értékét akkor és csak akkor tekintjük igaznak, ha az egyik komponens igazsága esetén a másik is igaz, az az, ha vagy mindkét komponens igaz, vagy mindkét komponens hamis.

9


Tulajdonságok: a. Az implikáció nem kommutatív (Értéktáblázata nem szimmetrikus a főátlóra) b. Az ekvivalencia kommutatív

A↔B = B ↔ A

További műveletek: "Vagy" jellemzése: a. A ∪ B : A és B közül legalább az egyik igaz akkor megengedő vagy b. A ⊕ B : A és B közül pontosan az egyik igaz akkor kizáró vagy

Kommutativitás:

A↓B=B↓A A⏐B=B⏐A A⊕B=B⊕A

Asszociativitás: (A ↓ B) ↓ C ≠ A ↓ (B ↓ C), mert ⏐A⏐ = ⏐B⏐ = i és ⏐C⏐ = k, akkor bal oldal igaz, jobb oldal hamis. (A ⏐ B) ⏐ C ≠ A ⏐ (B ⏐ C), mert ⏐A⏐ = ⏐B⏐ = k és ⏐C⏐ = i, akkor bal oldal hamis, jobb oldal igaz. Ítéletkalkulus és igazságtáblák Az ítéletkalkulus a logika azon ága, mely az egyértelműen igaz vagy hamis kijelentő mondatokkal, vagyis az ítéletekkel foglalkozik. Ezen ítéletek vizsgálatára igazságtáblákat használ. Nézzünk erre egy példát! Vizsgáljuk meg az A∨B∨C kifejezést!

A

B

A∨B

C

A∨B∨C

10


i

i

i

i

i

i

h

i

i

i

h

i

i

i

i

h

h

h

i

i

i

i

i

h

i

i

i

i

h

i

h

i

i

h

i

h

h

h

h

h

A táblázat utolsó oszlopa adja azt az értéket, ami a teljes kifejezésre vonatkozik. Láthatjuk, hogy így sokkal áttekinthetőbben és gyorsabban meg tudjuk állapítani egy kifejezés logikai értékeit.

Összefoglalás Mivel foglalkozik a logika? Milyen alapvető logikai műveleteket ismer? Ismertesse az igazságtáblájukat! Mutassa be a De-Morgan azonosságokat! Mutasson be egy példát az igazságtáblák használatára!

SZAKMAI INFORMÁCIÓTARTALOM SZÁMFOGALMAK Számelmélet

11

A PROGRAMOZÁS MATEMATIKAI ALAPJAI A számelmélet a matematika egyik ága, mely eredetileg a természetes számok oszthatósági

tulajdonságait vizsgálta. Az ilyen vizsgálatok elnevezésére még ma is alkalmazzák a számelmélet eredeti latinos elnevezését (aritmetika). A számelmélet alaptétele: Minden 1-től különböző pozitív egész szám felbontható prímszámok szorzatára. Ez a felbontás a tényezők sorrendjétől eltekintve egyértelmű. Az oszthatóság Hagyományos értelemben akkor mondjuk, hogy az a természetes szám osztható a b természetes számmal, röviden a b szám osztója az a számnak, vagy, ha van olyan egész

szám, melyet b-vel szorozva a-t kapunk, vagyis, más szóval, ha az a szám többszöröse a bnek. Jelölés: a | b

Az oszthatóság tulajdonságai: •

a|a bármely egész szám esetén. (reflexivitás)

•

1|a bármely egész szám esetén.

•

a| b ⇒ a|bc, a,b,c egész szám esetén.

•

a|b és b|c⇒ a|c, a,b,c egész szám esetén. Ez a tranzitív tulajdonság.

•

a|b és a|c ⇒ a|b+c, a,b,c egész szám esetén.

•

a|b és a|c ⇒ a|b-c, a,b,c egész szám esetén.

•

a|b és a| b + c⇒ a|c, a,b,c egész szám esetén.

•

a | b és b | d esetén ac | bd

•

a|0

•

ac | bc és c 0-tól különböző esetén a | b

•

0 | a akkor és csak akkor teljesül, ha a = 0

Oszthatósági szabályok a tízes számrendszerben felírt természetes számok körében • • •

2-vel osztható az a szám, melynek utolsó számjegye 2, 4, 6, 8 vagy 0, tehát páros 3-mal osztható az a szám, melynek számjegyeinek összege 3-mal osztható.

4-gyel osztható az a szám, melynek a két utolsó jegyéből alkotott szám osztható 4gyel. 12

A PROGRAMOZÁS MATEMATIKAI ALAPJAI • • •

5-tel osztható az a szám, melynek utolsó jegye 5 vagy 0. 6-tal osztható az a szám, mely 2-vel és 3-mal osztható.

7-tel osztható az a szám, melynek számjegyeit hátulról hármasával csoportosítva és váltakozó előjellel összeadva a kapott szám abszolút értéke osztható 7-tel.

•

8-cal osztható az a szám, melynek utolsó három jegyéből alkotott szám osztható nyolccal.

• •

9-cel osztható az a szám, melynek számjegyeinek összege 9-cel osztható. 10-zel osztható az a szám, melynek utolsó jegye 0.

Oszthatóság az egész számok körében Az oszthatóságot kiterjeszthetjük az egész számok halmazára is. Akkor például a 6-nak nem csak az 1, 2, 3, és a 6 lesz osztója, hanem a -1, -2, -3 és a -6 is, mert ezekhez is lehet olyan alkalmas egész számot találni, amivel megszorozva őket mind 6-ot adnak. Prímszámok A matematika területén prímszámnak, törzsszámnak vagy röviden prímnek nevezzük azokat a természetes számokat, amelynek pontosan két osztójuk van (1 és önmaga). A többi egynél nagyobb természetes számot összetett számnak nevezzük. Magát az 1-et egyik kategóriába sem soroljuk bele (mivel csak egy osztója van). Az általában természetes számnak tekintett 0 ugyancsak nem prím és nem is összetett.

A prímszámok megkülönböztetését az indokolja, hogy két osztója minden 1-nél nagyobb

természetes számnak van, az 1 és önmaga, de a prímszámoknak nincs is több, míg a többi 1-nél nagyobb számoknak van. Prímfelbontás A számelméletben a prímfelbontás – más néven prímfaktorizáció – az a folyamat, amikor egy összetett számot prím osztóira bontjuk (faktorizáljuk), amik összeszorozva az eredeti egész számot adják.

Kiszámítás: Keressük meg az első prímszámot, ami osztója a számnak. Osszuk el vele a

számot, majd az eredménnyel folytassuk az eljárást, amíg 1-ig nem jutunk. Ha egymás mellé írjuk az osztókat, megkapjuk a szám prímtényezős felbontását. Relatív prímek: Az a és b egész számok esetén azt mondjuk, hogy az a a b-hez relatív prím, vagy

egyszerűen a és b relatív prím, ha az 1-en kívül nincs más közös osztójuk. Vagy ami ezzel ekvivalens, ha a és b legnagyobb közös osztója 1. Legnagyobb közös osztó Két vagy több egész szám legnagyobb közös osztóján értünk egy olyan pozitív egész számot, amely közös osztó és minden közös osztónak többszöröse.

13

A PROGRAMOZÁS MATEMATIKAI ALAPJAI Kiszámítása: Prímtényezőkre bontjuk és vesszük a közös prímtényezőket a legkisebb kitevővel és összeszorozzuk őket. Legkisebb közös többszörös Két vagy több egész szám legkisebb közös többszörösén értünk egy olyan pozitív egész számot, amely közös többszörös és minden közös többszörös osztója.

Kiszámítása: Prímtényezőkre bontjuk és vesszük azokat a prímtényezőket, amelyek szerepelnek valamelyik számban. A lehető legnagyobb kitevővel és összeszorozzuk őket. Euklideszi algoritmus Az euklideszi algoritmus egy számelméleti algoritmus, mellyel két szám legnagyobb közös osztója határozható meg. Nevét az ókori görög matematikusról, Eukleidészről kapta. Ha a = b * q + r , akkor ( a , b ) = ( b , r ) , Így

a

problémát

visszavezeti

két

kisebb

szám

legnagyobb

közös

osztójának

meghatározására. Folytatva az eljárást, az utolsó, 0-tól különböző maradék a legnagyobb közös osztó.

Például, határozzuk meg a 360 és a 220 legnagyobb közös osztóját!( 360, 220 ) = ? Az euklidészi algoritmus szerint:

360=220*1+140 220=140*1+ 80 140= 80*1+ 60 80= 60*1+ 20

60=20*3+0 Tehát ( 360, 220 ) = 20.

Összefoglalás: Ismertesse a számelmélet alaptételét! Ismertesse az oszthatóság fogalmát! Milyen oszthatósági szabályokat ismer? Milyen számokat nevezünk prímnek? Ismertesse a legnagyobb közös osztó és legkisebb közös többszörös fogalmát és kiszámítási módszereit!

14

A PROGRAMOZÁS MATEMATIKAI ALAPJAI Ismertesse az Euklideszi algoritmust!

SZAKMAI INFORMÁCIÓTARTALOM MÁTRIXOK A mátrix fogalma, speciális mátrixok Definíció:: Legyen m, n természetes szám. n×m-es mátrixnak nevezzük bármilyen nxm számú aik mennyiség (i = 1, 2, . . . , n; k = 1, 2, . . . ,m) alábbi, szögletes zárójelbe tett téglalap alakú elrendezését:

⎡a11 a12 ..... a1m ⎤ ⎢a21 a22 ..... a2m ⎥ ⎢ ⎥ ⎢. . . . ⎥ ⎢ ⎥ ⎣an1 an2 ..... anm ⎦ A mátrix nxm típusú, mert n sorból és m oszlopól áll. Az aik mennyiségek a mátrix elemei, ahol az

ik

meg. A mátrixok elemei általában valós számok.

egy index, ami a sor és oszlopszámot adja

Ha egy nxm mátrix sorait és oszlopait felcseréljük egymással, akkor a mátrix transzponáltját

kapjuk meg. Az A mátrix transzponáltját A* jelöli.

⎡ 1 3 2⎤ ⎥ ⎢ Az 3 2 2 mátrix transzponáltja: ⎥ ⎢ ⎢⎣78 6 4⎥⎦

⎡1 3 78⎤ ⎢3 2 6 ⎥ ⎥ ⎢ ⎢⎣2 2 4 ⎥⎦

Az egy sorból álló mátrixot sormátrixnak, az egy oszlopból álló mátrixot pedig oszlopmátrixnak nevezzük.

⎡3⎤ ⎢ ⎥ Sormátrix: [1 44 5] Oszlopmátrix: 4 ⎢ ⎥ ⎢⎣65⎥⎦ Egy olyan mátrixot, aminek minden eleme 0, zérusmátrixnak nevezünk.

⎡0 0 0 ⎤ ⎥ ⎢ Zérusmátrix 0 0 0 ⎥ ⎢ ⎢⎣0 0 0⎥⎦

15

A PROGRAMOZÁS MATEMATIKAI ALAPJAI Ha egy mátrixnak n sora és n oszlopa van, akkor n-ed rendű négyzetes mátrixnak nevezzük.

⎡ 1 3 66⎤ ⎥ ⎢ 3-ad rendű négyzetes mátrix: 23 4 5 ⎥ ⎢ ⎢⎣11 3 3 ⎥⎦ Azt az nxn mátrixot, melynek a főátlóban levő minden eleme 1, de azon kívül minden eleme 0, n-ed rendű egységmátrixnak nevezzük.

⎡1 0 0 ⎤ ⎥ ⎢ 3-ad rendű egységmátrix: 0 1 0 ⎥ ⎢ ⎢⎣0 0 1⎥⎦ Két mátrix egyenlő, ha azonos típusúak és minden elemük megegyezik.

⎡1 3 78⎤ ⎡1 3 78⎤ ⎢3 2 6 ⎥ = ⎢3 2 6 ⎥ ⎥ ⎥ ⎢ ⎢ ⎢⎣2 2 4 ⎥⎦ ⎢⎣2 2 4 ⎥⎦ Műveletek mátrixokkal

Összeadás: Két azonos típusú mátrixot úgy adunk össze, hogy az A mátrix megfelelő elemét hozzáadjuk a B mátrix ugyan olyan indexű eleméhez. Minden elemre elvégezve kapunk egy C mátrixot, ami ugyan olyan típusú, mint az A és B mátrix.

⎡1 3 78⎤ ⎡ 4 5 22⎤ ⎢3 2 6 ⎥ + ⎢ 2 2 4 ⎥ = ⎢ ⎥ ⎢ ⎥ ⎢⎣2 2 4 ⎥⎦ ⎢⎣12 2 55⎥⎦

⎡ 5 8 100⎤ ⎢ 5 4 10 ⎥ ⎢ ⎥ ⎢⎣14 4 59 ⎥⎦

A kivonást az előbbiekhez hasonlóan végezzük el.

⎡1 3 78⎤ ⎡ 4 5 22⎤ ⎢3 2 6 ⎥ - ⎢ 2 2 4 ⎥ = ⎢ ⎥ ⎢ ⎥ ⎢⎣2 2 4 ⎥⎦ ⎢⎣12 2 55⎥⎦

⎡ − 3 − 2 56 ⎤ ⎢ 1 0 2 ⎥⎥ ⎢ ⎢⎣− 10 0 − 51⎥⎦

Mátrix szorzása egy számmal úgy történik, hogy a mátrix minden elemét megszorozzuk az adott számmal.

⎡1 3 78⎤ ⎢3 2 6 ⎥ * 2 = ⎢ ⎥ ⎢⎣2 2 4 ⎥⎦

⎡2 6 156⎤ ⎢6 4 12 ⎥ ⎢ ⎥ ⎢⎣4 4 8 ⎥⎦ 16

A PROGRAMOZÁS MATEMATIKAI ALAPJAI Mátrixok szorzása mátrixszal kicsit bonyolultabb művelet. Összeszorozni csak azokat a

mátrixokat lehet ahol a szorzandó mátrixnak annyi oszlopa van ahány sora a szorzónak. Az alábbi példa mutatja a számítás menetét:

⎡ 3 2⎤ ⎡1 1 2⎤ ⎢ ⎥ ⎡(1* 3 + 1* 2 + 2 *1) (1* 2 + 1* 2 + 2 * 2) ⎤ ⎡ 7 8⎤ ⎢0 3 1 ⎥ * ⎢2 2⎥ = ⎢(0 * 3 + 3 * 3 + 1*1) (0 * 2 + 3 * 2 + 1* 2)⎥ = ⎢10 8⎥ ⎣ ⎦ ⎢1 2⎥ ⎣ ⎦ ⎣ ⎦ ⎣ ⎦

Determináns számítása: A

determináns

kiszámítására

igen

sok

probléma

megoldásánál

lehet

szükségünk.

Determinánson egy négyzetes mátrixhoz rendelt számot értünk. A jelölése a szögletes

zárójel helyet két függőleges vonal. Ha egy A n×n-es négyzetes mátrix elemei az aik számok, akkor az (n-ed rendű) determináns a következő módszerrel: 1×1-es: Maga a szám: a =a 2×2-es:

a b ⎡a b ⎤ =ad-bc esetén a det A= ⎥ c d ⎣c d ⎦

A= ⎢

Például: 3 5 = 3*1 - 5*2 = -7 2 1 3×3-as: A Sarrus szabály szerint:

a11 a12 A= a 21

a 31

a13

a 22 a 23 =a11a22a33+a12a23a31+a13a21a32-a31a22a13-a32a23a11-a33a21a12 a 32 a 33

Példa:

17


2 4 1 7 2 3 =2*2*6+4*3*8+1*7*5-8*2*1-5*3*2-6*7*4=24+96+35-16-30-168=-59 8 5 6 Ennél nagyobb mátrixokra a kifejtés tételt és a sarus szabályt összevonva szoktuk alkalmazni.

Összefoglalás: Mit nevezünk mátrixnak? Milyen különleges mátrixokat ismer? Milyen műveletek végezhetők rajtuk? Ismertesse a Determináns fogalmát és kiszámításának módját!

SZAKMAI INFORMÁCIÓTARTALOM GRÁRELMÉLET Egy olyan ábrát, amely pontokból és ezek közül némelyeket összekötő vonalakból áll, ezt a vonal alakjára való tekintet nélkül gráfnak nevezzük. A pontok a gráf pontjai vagy csúcsai, a csúcsokat összekötő vonalak a gráf élei.

18

A PROGRAMOZÁS MATEMATIKAI ALAPJAI D C

E

A B 1.ábra Gráf Véges gráf: ha pontjainak száma véges. Egy csúcs fokszámát az adja meg, hány él fut ki belőle. Pl. az A csúcs fokszáma: 2. Ha a gráfban van két olyan pont, amelyet több él is összeköt, akkor azt mondjuk, hogy a gráf tartalmaz többszörös éleket. Az 1. ábrán a B és E csúcs ilyen.

Ha egy gráfban az “a” pontból úgy jutunk el egy “b” pontba, hogy közben bármely pontot legfeljebb egyszer érintünk, akkor azt mondjuk, hogy úton haladtunk. .Ha egy út kezdő és végpontja azonos, akkor körről beszélünk Egy út vagy kör hosszán éleinek számát értjük. Az olyan élt, amelynek mindkét vége ugyanaz a pont, hurokélnek nevezzük. Egy gráfban két pontot szomszédosnak nevezünk, ha él köti össze őket. Két élt szomszédosnak nevezünk, ha egyik végpontjuk közös.

2.ábra Egyszerű gráf Egy gráfot egyszerűnek nevezünk, ha sem hurokélt, sem pedig többszörös éleket nem tartalmaz.

19


3.ábra Teljes gráf Az olyan egyszerű gráfot, amelyben bármely két különböző pontot egy és csak egy él köt össze, teljes gráfnak nevezzük.

4.ábra Összefüggő gráf Ha egy gráfban bármely két pont úttal elérhető, akkor a gráfot összefüggőnek nevezzük.

5.ábra Gráf (fekete) és a komplementere(piros) Egy gráf komplementerén azt a gráfot értjük, amelynek az eredeti gráffal való egyesítése teljes gráfot ad.

Ha egy gráf bizonyos éleit és/vagy pontjait - a pontokat a hozzá illeszkedő élekkel együtt -

töröljük, akkor ismét egy gráfot kapunk. Az így kapott gráfot az eredeti gráf részgráfjának

nevezzük. A G gráf azon részgráfját, amely nem azonos G-vel, a G gráf egy valódi részgráfjának nevezzük.

20

A PROGRAMOZÁS MATEMATIKAI ALAPJAI A G gráf egy komponensén G egy olyan részgráfját értjük, amely összefüggő, de nem valódi részgráfja G egyetlen összefüggő részgráfjának sem.

C

E

A B 6. ábra Fa gráf A körmentes, összefüggő gráfot fa gráfnak nevezzük.

7.ábra Bináris fa Az informatikában sokszor használatos a bináris fa. Itt olyan fáról beszélünk, ahol minden csúcsnak maximálisan két leszármazottja van.

Néhány egyszerű és alapvető tétel a gráfokkal kapcsolatban: 1. tétel: Minden gráfban a fokszámok összege az élek számának kétszeresével egyenlő. 2. tétel: Minden egyszerű gráfban a páratlan fokú pontok száma páros. 3. tétel: Az n-pontú teljes gráf éleinek száma n*(n-1)/2. 4. tétel: Ha egy gráfban minden pont foka legalább 2, akkor a gráfban van kör. 5. tétel: Ha egy n-pontú gráfnak legalább n éle van, akkor van a gráfban kör.

21


8.ábra Euler vonal Euler-vonalnak nevezünk a gráfban egy utat, ha a gráf minden élén pontosan egyszer halad keresztül.

9.ábra Hamilton kör Hamilton-körnek nevezzük a gráf egy olyan körét, amely a gráf minden pontján pontosan egyszer halad keresztül.

Összefoglalás: Ismertesse a gráf fogalmát! Milyen tulajdonságokkal rendelkezhet egy gráf? Milyen alapvető tételeket ismer gráfokra? Mi az Euler vonal? Ismertesse a Hamilton kör fogalmát! 22


SZAKMAI INFORMÁCIÓTARTALOM KOMBINATORIKA

1. Permutációk:

Akkor beszélünk permutációról, ha valahány konkrét elemet sorba rendezünk. Ismétlés nélküli a permutáció, ha minden elem csak egyszer szerepel. Az ismétlés nélküli permutációk száma n elem esetén :

P=n! Nézzük meg, miért van ez így! Az első elem kiválasztása n féleképp történhet. Minden kiválasztás után további (n-1) féleképp választhatjuk a másodikat, tehát már n(n-1)

lehetőségnél tartunk. Ebből mindegyikhez a harmadikat n-2 féleképp választhatjuk, tehát már n(n-1)(n-2). és így tovább. , tehát már n(n-1)(n-2). és így tovább, ami pontosan az n!-al egyenlő! Példa: Ha van 10 darab, különböző színű kockánk, akkor hány féleképpen tudjuk sorba rendezni őket?

n!=10!=10*9*8*7*6*5*4*3*2*1=3628800 Akkor beszélünk ismétléses a permutációról, ha van olyan elem, amiből több is van a

sorban. Ekkor az elemek számának faktoriálisát el kell osztanunk az ismétlődő elemek

számának faktoriálisával!

P=

n! k !d !

Példa: Van 10 darab színes kockánk. 3 db kék és 2 darab piros, de a többi különböző színű.

Hányféleképpen rendezhetem sorba?

P=

10! 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 *1 3628800 = = = 302400 3!*2! 3 * 2 *1* 2 *1! 12

2. Variációk: Akkor beszélünk variációról, ha egy adott (k) elemszámú sorozatot kell összeállítanunk

valahány (n) fajta elemből. Fontos, hogy a sorrend itt számít!

23

A PROGRAMOZÁS MATEMATIKAI ALAPJAI A variáció ismétlés nélküli, ha egy elem csak egyszer szerepelhet. Az ismétlés nélküli

variáció majdnem, úgy számoljuk, mint a permutációt, csak hamarabb abbahagyjuk. Csak az

első k hely számít. Tehát n elem esetén majdnem n!, de csak az első k tényezőt írjuk le:

Vnk =

n! (n − k )!

Példa: Van 10 darab színes kockánk és ebből szeretnénk válogatni 4 elemből álló sorozatokat. Hány féleképpen tehetjük ezt meg?

Vnk =

10! 10! 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 *1 = = = 10 * 9 * 8 * 7 = 5040 (10 − 4)! 6! 6 * 5 * 4 * 3 * 2 *1

Ismétléses a variáció, ha egy adott (k) elemszámú sorozatot kell összeállítanunk valahány (n) fajta elemből, de egy elemet többször is kiválaszthatunk. Fontos, hogy a sorrend itt számít! a lehetséges variációk száma: . Vin;k = nk Példa:

Van 10 darab színes kockánk és ebből szeretnénk válogatni 4 elemből álló sorozatokat, de

minden egyes kiválasztás után visszateszem a kockákat. Így egy elem többször is szerepelhet! Hány féleképpen tehetjük ezt meg?

V=104=10000

3. Kombinációk: a., Az ismétlés nélküli kombinációk száma azt adja meg, hogy n elemből hányféleképp

választhatunk ki k-t, ha a sorrend nem számít. Ez majdnem olyan, mint egy ismétlés nélküli variáció, csakhogy itt a sorrend nem számít. Ezért az ismétlés nélküli variációk számát el kell osztani azzal, ahány féleképp sorba lehet rakni a kiválasztott k elemet.

⎛n⎞ n! Cn , k = ⎜⎜ ⎟⎟ = ⎝ k ⎠ k!(n − k )!

Példa:

Van 10 darab színes kockánk és ebből szeretnénk válogatni 4 elemet. A sorrend nem számít! Hány féleképpen tehetjük ezt meg?

⎛10 ⎞ 10! 10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 *1 10 * 9 * 8 * 7 Cn , k = ⎜⎜ ⎟⎟ = = = = 210 4 * 3 * 2 *1 ⎝ 4 ⎠ 4!6! 4 * 3 * 2 *1* 6 * 5 * 4 * 3 * 2 *1

24

A PROGRAMOZÁS MATEMATIKAI ALAPJAI b., Az ismétléses kombináció száma azt adja meg, hogy, hányféleképpen lehet n különböző

dologból kiválasztani k darabot, ha nem számít a kiválasztás sorrendje és egy dolgot többször is választhatunk:

⎛ n + k − 1⎞ (n + k − 1)! ⎟⎟ = Ck , i, n = ⎜⎜ k ⎝ ⎠ k!(n − 1)! Példa:

Van 10 darab színes kockánk és ebből szeretnénk válogatni 4 elemet. A választás után minden kockát visszateszünk a helyére, így többször is választhatóak! A sorrend nem számít! Hány féleképpen tehetjük ezt meg?

⎛ n + k − 1⎞ (10 + 4 − 1)! 13! 13 *12 *11*10 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 *1 13 *12 *11*10 ⎟⎟ = Ck , i, n = ⎜⎜ = = = = 715 4 * 3 * 2 *1 * 9 * 8 * 7 * 6 * 5 * 4 * 3 * 2 *1 4 * 3 * 2 *1 ⎝ k ⎠ 4!(10 − 1)! 4!9! A kombinatorikai feladatokban sok esetben nem csak tisztán az egyik típus szerepel.

Érdemes sokat gyakorolni az ilyen feladatok megoldását, ha biztosan fel szeretnénk ismerni a feladattípusokat!

Összefoglalás: Ismertesse a permutáció és ismétléses permutáció fogalmát! Ismertesse a variáció és ismétléses variáció fogalmát! Ismertesse a kombináció és ismétléses kombináció fogalmát! Mutasson be egy-egy példát mindegyikre!

25


IRODALOMJEGYZÉK FELHASZNÁLT IRODALOM KUROS, A. G. : Felsőbb algebra. Budapest (Tankönyvkiadó) 1978. KNUTH, Donald, E.: A számítógép-programozás művészete I-III. Budapest (Műszaki) 1987. OBÁDOVICS J. Gyula: Matematika. Budapest (Műszaki) 1978. REIMANN József: Matematika. Budapest 1982. WIRTH, Niklaus: Algoritmusok + Adatstruktúrák = Programok. Budapest (Műszaki) 1982.

26

1144 PROGRAMOZÁSMÓDSZERTAN, PROGRAMOZÁSI NYELVEK

Recommend Documents