Algoritmizálás, adatmodellezés tanítása 1. előadás

Algoritmizálás, adatmodellezés tanítása 1. előadás

Az algoritmus fogalma  végrehajtható

ELTE

2010.09.06.

(van hozzá végre-hajtó)  lépésenként hajtható végre  a lépések maguk is algoritmusok  pontosan definiált, adott végre-hajtási sorrenddel  egy folyamat véges hosszúságú, időben esetleg végtelen leírása

Zsakó László: Algoritmizálás, adatmodellezés tanítása

2

Az algoritmus fogalma

ELTE

2010.09.06.

Az algoritmusok összerakási módjai:  Szekvencia (egymás utáni végrehajtás)  Elágazás (választás 2 vagy több tevékenységből)  Ciklus (ismétlés adott darabszámszor vagy adott feltételtől függően)


3

A specifikáció

ELTE

2010.09.06.

1. Bemenő adatok (értékhalmaz, mértékegység) 2. Ismeretek a bemenetről (előfeltétel) 3. Eredmények (értékhalmaz, …) 4. Az eredmény kiszámítási szabálya (utófeltétel) 5. A megoldással szembeni követelmények 6. Korlátozó tényezők 7. A használt fogalmak definíciói Zsakó László: Algoritmizálás, adatmodellezés tanítása

4

A specifikáció

ELTE

2010.09.06.

Tulajdonságai  1. Egyértelmű, pontos, teljes  2. Rövid, tömör, formalizált  3. Szemléletes, érthető Specifikációs eszközök  1. Szöveges leírás  2. Matematikai megadás


5

Tömb  Sorozat:

ELTE

2010.09.06.

azonos típusú elemek egymásutánja, az elemei sorszámozhatók.  Tömb: véges hosszúságú sorozat, a sorozat i-edik tagjával végezhetünk műveleteket; adott a legkisebb és a legnagyobb index.  Indexek: sokszor 1..N, máskor a..b.  Példa: X: Tömb[1..N: Egész] Szín: Tömb[0..4: Szöveg]= (”zöld”,”piros”,”sárga”,”fehér”,”fekete”) Zsakó László: Algoritmizálás, adatmodellezés tanítása

6

Programozási tételek

ELTE

2010.09.06.

Mi van a ciklusokkal?  Programozási tételek! Mi az, hogy programozási tétel? Típusfeladat általános megoldása.  Sorozat  érték  Sorozat  sorozat  Sorozat  sorozatok  Sorozatok  sorozat Zsakó László: Algoritmizálás, adatmodellezés tanítása

7

1. Sorozatszámítás

ELTE

2010.09.06.

Feladatok:  Ismerjük egy ember havi bevételeit és kiadásait. Adjuk meg, hogy év végére mennyivel nőtt a vagyona!  Ismerjük egy autóversenyző körönkénti idejét. Adjuk meg az átlagkörének idejét!  Adjuk meg az N számhoz az N faktoriális étékét! Zsakó László: Algoritmizálás, adatmodellezés tanítása

8


ELTE

2010.09.06.

Feladatok:  Ismerjük egy iskola szakköreire járók tanulóit szakkörönként. Adjuk meg a szakkörre járó tanulókat!  Ismerünk N szót. Adjuk meg a belőlük összeállított mondatot! Mi bennük a közös?  N darab „valamiből” kell kiszámolni egy darab „valamit”! Zsakó László: Algoritmizálás, adatmodellezés tanítása

9

1. Sorozatszámítás  Bemenet:

ELTE

2010.09.06.

N: Egész, X: Tömb[1..N: Valami]  Kimenet: S: Valami  Előfeltétel:   Utófeltétel: S=F(X[1],…,X[N])  Probléma: a programozásban nincs N paraméteres művelet.


10

1. Sorozatszámítás  Probléma:

ELTE

2010.09.06.

a programozásban nincs N paraméteres művelet.  Megoldás: visszavezetjük 2-paraméteres műveletre (pl.  helyett +) és egy null-elemre (+ esetén a 0).  F(X[1],…,X[N])= f(F(X[1],…,X[N-1]),X[N]) ha N>0  F()=F0 Zsakó László: Algoritmizálás, adatmodellezés tanítása

11


ELTE

2010.09.06.

Sorozatszámítás: S:=F0 Ciklus i=1-től N-ig S:=f(S,X[i]) Ciklus vége Eljárás vége.


12

1. Sorozatszámítás: vagyon  Bemenet:

ELTE

N: Egész, Be,Ki: Tömb[1..N: Egész]  Kimenet: S: Egész  Előfeltétel:  N  Utófeltétel:

S   Be[i ]  Ki[i ] i 1

Sorozatszámítás: S:=0 Ciklus i=1-től N-ig S:=S+Be[i]-Ki[i] Ciklus vége Eljárás vége. 2010.09.06.


13

2. Eldöntés

ELTE

2010.09.06.

Feladatok:  Egy természetes számról döntsük el, hogy prímszám-e!  Egy szóról mondjuk meg, hogy egy hónapnak a neve-e!  Egy tanuló év végi osztályzatai alapján állapítsuk meg, hogy bukott-e!  Egy szóról adjuk meg, hogy van-e benne magánhangzó! Zsakó László: Algoritmizálás, adatmodellezés tanítása

14

2. Eldöntés

ELTE

2010.09.06.

Feladatok:  Egy számsorozatról döntsük el, hogy monoton növekvő-e!  Egy tanuló év végi jegyei alapján adjuk meg, hogy kitűnő-e! Mi bennük a közös?  Döntsük el, hogy N darab „valami” között van-e adott tulajdonsággal rendelkező elem! Zsakó László: Algoritmizálás, adatmodellezés tanítása

15

2. Eldöntés  Bemenet:

ELTE

2010.09.06.

N: Egész, X: Tömb[1..N: Valami]  Kimenet: Van: Logikai  Előfeltétel:   Utófeltétel: Van=i (1iN): T(X[i])  A T tulajdonság egy logikai függvényként adható meg, minden elemről megvizsgálható, hogy rendelkezik-e az adott tulajdonsággal. Zsakó László: Algoritmizálás, adatmodellezés tanítása

16

2. Eldöntés

ELTE

2010.09.06.

Eldöntés: i:=1 Ciklus amíg iN és nem T(X[i]) i:=i+1 Ciklus vége Van:=iN Eljárás vége.


17

2. Eldöntés  Bemenet:

ELTE

N: Egész, X: Tömb[1..N: Valami]  Kimenet: Mind: Logikai  Előfeltétel:   Utófeltétel: Mind=i (1iN): T(X[i])  Másképp:

mind olyan  nincs nem

olyan! 2010.09.06.


18

2. Eldöntés

ELTE

Eldöntés: i:=1 Ciklus amíg iN és T(X[i]) i:=i+1 Ciklus vége Mind:=i>N Eljárás vége.

Az eredetihez képest két helyen kell tagadni!

2010.09.06.


19

2. Eldöntés: bukott  Bemenet:

ELTE

N: Egész, Jegy: Tömb[1..N:Egész]  Kimenet: Bukott: Logikai  Előfeltétel:i(1iN): Jegy[i]{1,2,3,4,5}  Utófeltétel: Bukott=i (1iN): Jegy[i]=1 Eldöntés: i:=1 Ciklus amíg iN és Jegy[i]1 i:=i+1 Ciklus vége Bukott:=iN Eljárás vége.

2010.09.06.


20

3. Kiválasztás

ELTE

2010.09.06.

Feladatok:  Ismerjük egy ember havi bevételeit és kiadásait. Év végére nőtt a vagyona. Adjunk meg egy hónapot, amikor nőtt a vagyona!  Adjuk meg egy természetes szám 1-től különböző legkisebb osztóját!


21

3. Kiválasztás

ELTE

2010.09.06.

Feladatok:  Adjuk meg egy magyar szó egy magánhangzóját!  Adjuk meg egy hónapnévről a sorszámát! Mi bennük a közös?  N darab „valami” közül kell megadni egy adott tulajdonságút, ha tudjuk, hogy ilyen elem biztosan van. Zsakó László: Algoritmizálás, adatmodellezés tanítása

22

3. Kiválasztás  Bemenet:

ELTE

2010.09.06.

N: Egész, X: Tömb[1..N: Valami]  Kimenet: S: Egész  Előfeltétel: i (1iN): T(X[i])  Utófeltétel: 1SN és T(X[S])  A T tulajdonság egy logikai függvényként adható meg, minden elemről megvizsgálható, hogy rendelkezik-e az adott tulajdonsággal. Zsakó László: Algoritmizálás, adatmodellezés tanítása

23

3. Kiválasztás

ELTE

Kiválasztás: i:=1 Ciklus amíg nem T(X[i]) i:=i+1 Ciklus vége S:=i Eljárás vége.

Többlet tudás: a megoldás az első adott tulajdonságú elemet adja meg.

2010.09.06.


24

3. Kiválasztás: magánhangzó  Bemenet:

ELTE

N: Egész, Szó: Tömb[1..N: Karakter]  Kimenet: S: Egész  Előfeltétel: i (1iN): magánhangzó(Szó[i])  Utófeltétel: 1SN és magánhangzó(Szó[S]) Kiválasztás: i:=1 Ciklus amíg nem magánhangzó(Szó[i]) i:=i+1 Ciklus vége S:=i Eljárás vége.

2010.09.06.


25

4. Keresés

ELTE

2010.09.06.

Feladatok:  Ismerjük egy ember havi bevételeit és kiadásait. Év végére nőtt a vagyona. Adjunk meg egy hónapot, amikor nem nőtt a vagyona!  Adjuk meg egy természetes szám egy 1-től és önmagától különböző osztóját!  Adjuk meg egy ember nevében egy abetű helyét! Zsakó László: Algoritmizálás, adatmodellezés tanítása

26

4. Keresés

ELTE

2010.09.06.

Feladatok:  Adjunk meg egy tanulóra egy tárgyat, amiből megbukott!  Adjuk meg egy számsorozat olyan elemét, amely nagyobb az előzőnél! Mi bennük a közös?  N darab „valami” közül kell megadni egy adott tulajdonságút, ha nem tudjuk, hogy ilyen elem van-e. Zsakó László: Algoritmizálás, adatmodellezés tanítása

27

4. Keresés  Bemenet:

ELTE

N: Egész, X: Tömb[1..N: Valami]  Kimenet: Van: Logikai, S: Egész  Előfeltétel:   Utófeltétel: Van=i (1iN): T(X[i]) és Van  1SN és T(X[S])  Azaz

2010.09.06.

eldöntés és kiválasztás együtt!


28

4. Keresés

ELTE

Keresés: i:=1 Ciklus amíg iN és nem T(X[i]) i:=i+1 Ciklus vége Van:=iN Ha Van akkor S:=i Eljárás vége.

Többlet tudás: a megoldás az első adott tulajdonságú elemet adja meg.

2010.09.06.


29

4. Keresés: 1-es jegy  Bemenet:

ELTE

2010.09.06.

N: Egész, Jegy: Tömb[1..N:Egész]  Kimenet: Van: Logikai, S: Egész  Előfeltétel: i(1iN): Jegy[i]{1,2,3,4,5}  Utófeltétel: Van=i (1iN): Jegy[i]=1 és Van  1SN és Jegy[S]=1


30 30

4. Keresés: 1-es jegy

ELTE

2010.09.06.

Keresés: i:=1 Ciklus amíg iN és Jegy[i]1 i:=i+1 Ciklus vége Van:=iN Ha Van akkor S:=i Eljárás vége.


31 31

5. Megszámolás

ELTE

2010.09.06.

Feladatok:  Ismerjük egy ember havi bevételeit és kiadásait. Adjunk meg, hogy hány hónapban nőtt a vagyona!  Adjuk meg egy természetes szám osztói számát!  Adjuk meg egy ember nevében levő abetűk számát! Zsakó László: Algoritmizálás, adatmodellezés tanítása

32

5. Megszámolás

ELTE

2010.09.06.

Feladatok:  Adjuk meg az éves statisztika alapján, hogy hány napon fagyott!  Adjuk meg N születéshónap alapján, hogy közöttük hányan születtek télen! Mi bennük a közös?  N darab „valamire” kell megadni, hogy hány adott tulajdonságú van közöttük. Zsakó László: Algoritmizálás, adatmodellezés tanítása

33

5. Megszámolás  Bemenet:

ELTE

N: Egész, X: Tömb[1..N: Valami]  Kimenet: Db: Egész  Előfeltétel:  N Db  1  Utófeltétel: i 1 T ( X [ i ])

2010.09.06.


34

5. Megszámolás

ELTE

2010.09.06.

Megszámolás: Db:=0 Ciklus i=1-től N-ig Ha T(X[i]) akkor Db:=Db+1 Ciklus vége Eljárás vége.


35

5. Megszámolás: télen születettek  Bemenet:

ELTE

N: Egész, Szül: Tömb[1..N:Egész]  Kimenet: Db: Egész  Előfeltétel: i (1iN): Szül[i]{1,…,12} N  Utófeltétel: Db  1 i 1 Szül[ i ]3 vagy Szül[ i ]12

Megszámolás: Db:=0 Ciklus i=1-től N-ig Ha Szül[i]<3 vagy Szül[i]=12 akkor Db:=Db+1 Ciklus vége Eljárás vége. 2010.09.06.


36

6. Maximumkiválasztás

ELTE

2010.09.06.

Feladatok:  Ismerjük egy ember havi bevételeit és kiadásait. Adjuk meg, hogy melyik hónapban nőtt legjobban a vagyona!  Adjuk meg N ember közül az ábécében utolsót!  Adjuk meg N ember közül azt, aki a legtöbb ételt szereti! Zsakó László: Algoritmizálás, adatmodellezés tanítása

37


ELTE

2010.09.06.

Feladatok:  Adjuk meg az éves statisztika alapján a legmelegebb napot!  Adjuk meg N születésnap alapján azt, akinek idén először van születésnapja! Mi bennük a közös?  N darab „valamire” kell megadni közülük a legnagyobbat (vagy a legkisebbet). Zsakó László: Algoritmizálás, adatmodellezés tanítása

38

6. Maximumkiválasztás  Bemenet:

ELTE

2010.09.06. 2010.09.06.

N: Egész, X: Tömb[1..N: Valami]  Kimenet: Max: Egész  Előfeltétel: N>0  Utófeltétel: 1MaxN és i (1iN): X[Max]X[i]  Megjegyzés: a sorszám általánosabb, mint az érték, a sorszámot adjuk meg.  Kell lenni a Valamire < relációnak! Zsakó László: Algoritmizálás, adatmodellezés tanítása

39


ELTE

Maximumkiválasztás: Max:=1 Ciklus i=2-től N-ig Ha X[i]>X[Max] akkor Max:=i Ciklus vége Eljárás vége. Többlet

tudás: ha több maximális érték is van, akkor közülük az elsőt kapjuk meg. Variációk: >, <, ≥, ≤.

2010.09.06.


40


ELTE

Maximális érték megadása: Kimenet: MaxÉrt: Valami Utófeltétel: i (1iN): MaxÉrt=X[i] és i (1iN): MaxÉrtX[i]

Maximumkiválasztás: MaxÉrt:=X[1] Ciklus i=2-től N-ig Ha X[i]>MaxÉrt akkor Maxért:=X[i] Ciklus vége Eljárás vége.

2010.09.06.


41

6. Maximumkiválasztás: legkorábbi születésnap  Bemenet:

ELTE

2010.09.06.

N: Egész, Hó,Nap: Tömb[1..N: Egész]  Kimenet: Min: Egész  Előfeltétel: N>0  Utófeltétel: 1MinN és i (1iN): Hó[Min]

42

6. Maximumkiválasztás: legkorábbi születésnap

ELTE

2010.09.06.

Minimumkiválasztás: Min:=1 Ciklus i=2-től N-ig Ha Hó[Min]>Hó[i] vagy Hó[Min]=Hó[i] és Nap[Min]>Nap[i] akkor Min:=i Ciklus vége Eljárás vége.


43

Programozási tételek 1.

2. 3. ELTE

4. 5. 6.

2010.09.06.

Sorozatszámítás (összegzés) Eldöntés Kiválasztás Keresés Megszámolás Maximumkiválasztás


44

Algoritmizálás, adatmodellezés tanítása 1. előadás vége

Algoritmizálás, adatmodellezés tanítása 1. előadás

Recommend Documents