Adatstruktúrák Algoritmusok Objektumok A számítógépes problémamegoldás modellezésének módszerei. Programozási elvek és módszerek: imperatív, strukturált, moduláris, objektumorientált programozás. Programozási nyelvek. A programozás menete
Hajnal Éva: AAO előadás
1
Tematika • A számítógépes problémamegoldás modellezésének módszerei.Programozási elvek és módszerek: imperatív, strukturált, moduláris, objektumorientált programozás. Programozási nyelvek. A programozás menete • Az algoritmus fogalma és ábrázolásának módjai.Vezérlési és D-gráf, blokkdiagram, stuktogram, pszeudokód.Adatszerkezetek • Alapvető programozási tételek (N-1): összegzés, számlálás, maximumkeresés, lineáris keresés, logaritmikus keresés. • Tömbök. Eljárások, függvények • Alapvető programozási tételek (N-N): szétválogatás, halmazműveletek Programozási tételek összeépítése Rendezések. Hajnal Éva: AAO előadás
2
• További algoritmusok (1): Horner elrendezés, Coxeter algoritmus stb • Zárthelyi írás az aláírás megszerzése érdekében. • Az objektumorientált programozási paradigma: modellezési alapelvek, programozási megoldások fejlődése, OO paradigma és OO program • Az OO paradigma alapelemei: objektum, osztály, osztályok közötti kapcsolatok. • Rektori szünet • Az OOP megvalósítások általános jellemzői (1): egységbezárás és adatrejtés, láthatóságok, osztály szintű tagok, tulajdonságok. • Az OOP megvalósítások általános jellemzői (2): öröklődés és többalakúság kód-újrafelhasználás • További algoritmusok (2): Labirintus, játékok stb • Pótlás az egész féléves anyagból Hajnal Éva: AAO előadás
3
Programozás tanulási módszerek
Hajnal Éva: AAO előadás
4
1. előadás • A számítógépes problémamegoldás modellezésének módszerei. • Programozási elvek és módszerek: imperatív, strukturált, moduláris, objektumorientált programozás. Programozási nyelvek. A programozás menete
Hajnal Éva: AAO előadás
5
Programozás alapfogalmai • Programozás: A program készítés folyamata • Program: Egy feladat elvégzéséhez szükséges utasítások összessége • Utasítás: Egy lépésben elvégezhető számítógépes művelet • Parancs: Az érvényesítést követően azonnal végrehajtódó művelet • Programozási nyelv: Nyelvi elemek és szabályok rendszere, melynek alapján a számítógép számára értelmezhető program elkészül • Algoritmus: a program terve, vagyis azon elemi lépések leírása, amelyek a bemenő adatokból elvezetnek a feladat megoldásához • Számítástechnikai modell, számítási modell • Forrásprogram: programnyelven megírt program, ebből fordítóprogram segítségével lehet a sz.g.-en futtatható programot elkészíteni • Tárgyprogram • Futtatható program • Fordítóprogram Hajnal Éva: AAO előadás
6
A számítógép informatikai modellje – Turing gép
Hajnal Éva: AAO előadás
7
Turing automata részei • egy cellákra osztott végtelenített papírszalag formában létező memóriából (szalagmemória, szalagtár, társzalag); minden cellában a gép által megértett nyelv betűi, azaz a Tár-abc egy-egy betűje van írva; • egy vezérlőegységből, mely a gép programját tartalmazza; a vezérlőegység különböző időpillanatokban különféle belső állapotokban létezhet; • egy író-olvasó fejből (I/O-fej), mely szimbólumokat ír vagy olvas a szalag celláira (ahogy a valóságos számítógépek betűket írnak ki a monitorra vagy a nyomtatóban lévő papírívre). • továbbá egy „szoftveregységből”, ez az átmenettábla, ami vezérli a gép működését, megadva, hogy adott szimbólum beolvasásának hatására adott állapotban mit tegyen: hogyan mozogjon, milyen szimbólumot írjon a tárra, és milyen belső állapotba kerüljön. Hajnal Éva: AAO előadás
8
Programnyelvek csoportosítása Imperatív
Deklaratív
SQL DBASE
Delphi Pascal Java
Visual Basic
C#
C++
PHP
Prolog Basic
Magas szintű
Algol C
Fortran
Alacsony szintű
Assembly Hajnal Éva: AAO előadás
9
Magas és alacsony szintű programnyelvek összehasonlítása Alacsony szintű • Más néven gépközeli • Egyszerű utasítások • Címek, egyszerű változók használata
Magas szintű • Ember közeli • Összetett utasítások • Címkék, adatszerkezetek használata
Hajnal Éva: AAO előadás
10
Mi a fordítóprogram feladata? • • • •
Compiler Időben elkülönül a fordítás és a futtatás Forráskód védelme megoldott Gyorsabb programfutás Futtatáshoz nem szükséges a fejlesztőkörnyezet
• • • •
Interpreter Futtatás és értelmezés programsoronként Forráskód védelme nehézkes Lassabb programfutás Futtatáshoz a fejlesztőkörnyezet (vagy annak egy modulja) szükséges
Hajnal Éva: AAO előadás
11
Programnyelvek csoportosításának további szempontjai • Programnyelvi generációk – Első G: a gépi kódhoz közel álló programozás technika – alacsony szintű programnyelv – Második G: magas szintű programnyelvek használata, az emberi gondolkodáshoz közelebb álló parancsok, és a struktúrált programozás megjelenése – Harmadik G: Objektum orientált nyelvek megjelenése – Negyedik G: Eseményvezérelt programozás, vizuális kezelőfelület segítségével
• Általános programozási nyelv – célorientált nyelvek Hajnal Éva: AAO előadás
12
A program készítés folyamata 1. A feladat meghatározása 2. Algoritmus 3. Kódolás 4. Tesztelés, hibakeresés, hibajavítás szintaktikai szemantikai hibák
5. Dokumentáció készítése Szervezési dokumentáció Programozási dokumentáció Felhasználói dokumentáció Üzemeltetési dokumentáció Hajnal Éva: AAO előadás
13
Teszt • Program • Programnyelv • Programozás
Hajnal Éva: AAO előadás
14
• • • •
Program modellje Program készítésének menete Algoritmus fogalma Algoritmussal szemben támasztott követelmények
Hajnal Éva: AAO előadás
15
A program készítés folyamata 1. A feladat meghatározása 2. Algoritmus 3. Kódolás 4. Tesztelés, hibakeresés, hibajavítás szintaktikai szemantikai hibák
5. Dokumentáció készítése Szervezési dokumentáció Programozási dokumentáció Felhasználói dokumentáció Üzemeltetési dokumentáció Hajnal Éva: AAO előadás
16
Algoritmus fogalma • Algoritmus: véges sok, időben elkülönült szekvenciális lépésekből álló megoldási módszer. • Az algoritmussal szembeni követelmények: • általános: ugyanabba a problémaosztályba tartozókra is jó legyen. • megismételhető legyen: ugyanazokkal az adatokkal ugyanaz az eredmény. • véges időn belül véget érjen. • Az algoritmus programnyelvtől független. Hajnal Éva: AAO előadás
17
Algoritmusok ábrázolása •
Vezérlési gráf: hurokmentes, összefüggő, többszörös élekkel nem rendelkező irányított gráf, melynek 3-féle csomópontját különböztetjük meg: 1. transzformációs (tevékenység) csomópont 2. döntési (vezérlési) csomópont (egy él be, 2 vagy több ki) 3. gyűjtő csomópont • •
•
Blokkdiagram: a vezérlési gráf egy értelmezése, ahol a transzformációs és a döntési csomópontok ki vannak töltve adat-transzformációkkal (adattranszformáció: az adatokat változtatja) ill. logikai feltételekkel. D(ijkstra)-gráf: a szekvencia, a feltételes elágazások és az elöltesztelő és hátultesztelő iterációk, ill. az ezekre egyszerűsíthető eljárással vissza vezethető vezérlési gráfok (a D-gráf a szerkezetileg helyes programot leíró vezérlési gráf). Struktogram (Chapin-kártya): a ~ egy strukturált ábrázolási módszer, a tervezés felülről lefelé történik. Ahogy a struktúrában lejjebb megyünk, úgy egyre kevesebb hely marad tevékenységeink leírásához Hajnal Éva: AAO előadás
18
Valódi program: olyan összefüggő, irányított gráf, melyre igazak az alábbiak: • (1) véges számú nemzérus bemenő és kimenő éllel rendelkezik • (2) csomópontjait döntési csomópontok (predikátum csomópont), függvénycsomópontok és gyűjtőcsomópontok alkotják • (3) minden csomóponton át vezet legalább egy bemenő éllel kezdődő és kimenő élben végződő útvonal. • A programgráfot ki szokás egészíteni indítási (START), befejezési csomóponttal (STOP). Hajnal Éva: AAO előadás
19
Struktúrált programozás A struktúrált programozás alaptétele (Böhm-Jacopini, 1966): Bármely program megadható ekvivalens struktúrált program formájában is, amelyben az alábbi három konstrukciós művelet szerepel. A két program ekvivalens, azaz ugyanazon input értékekre ugyanazon output értékeket számolják ki. • szekvencia (sorozat): két program közvetlen egymásután írása. • elágazás: megadott feltételektől függően más-más programot hajtunk végre. • ciklus: egy meglévő programot egy adott feltételtől függően valahányszor végrehajtunk. Megkülönböztethetünk elöltesztelő ciklusokat és hátultesztelő ciklusokat, melynél a feltétel-vizsgálat a program végrehajtása előtt illetve után történik. Az utóbbinál egyszer mindenképp végrehajtódik a program. – –
iteratív ismétléssel, fokozatos közelítéssel dolgozó Hajnal Éva: AAO ciklus előadás taxatív felsorolással dolgozó
20
• Miért jó a strukturált program? – Egyszerű (minden D-gráf „lényeges bonyolultsága” 1) – a strukturált programot le lehet bontani elemi Dgráfokra, ez csökkenti a bonyolultságot
•
Miért rossz a nem strukturált program?
– mert bonyolult, bonyolultsági metrika nagy lesz – nagy (>50) bonyolultságú program „tesztelhetetlen” ! – nem lehet egyszerűsíteni (lebontani D-gráfokra)
Hajnal Éva: AAO előadás
21
Algoritmus leíró módszerek I. Grafikus/szöveges Áttekinthetőség Szerkesztés Struktúrált programozást
Folyamatábra grafikus áttekinthető Rajzoló programmal, speciális szerkesztőprogrammal Nem támogatja
Struktogram grafikus áttekinthető Rajzoló programmal Táblázatkezelővel
Pszeudokód szöveges Nem áttekinthető Szövegszerkesztővel
támogatja
Támogatja
Elemei -
Határoló jel
Program azonosító Program vége Vagy Eljárás azonosító Eljárás vége Utasítás1 Utasítás2 …
Start, vagy end
Szekvencia
Ut1
Ut1 Ut2
Ut2
Ut3
Szelekció
feltétel feltétel el
Ut1
ut2
Hajnal Éva: AAO előadás
Ha
akkor Utasítás1 Különben Utasítás2 Elágazás vége 22
Algoritmus leíró módszerek II. Ciklus amíg
Iteráció 1. Elöltesztelt ciklus
f c. m.
Iteráció 2. Hátultesztelt ciklus
c.m.
Iteráció 3. Számlálós ciklus
I:=1 től N-ig u
Utasítás1 Utasítás2… Ciklus vége Ciklus Utasítás1 Utasítás2 Ciklus vége ha Ciklus i:=1-től N ig Utasítás1 Utasítás2… Ciklus vége
Be:N Ki: N
Input/Output Be: N
Be: N
Hajnal Éva: AAO előadás
23
Teszt • Algoritmus fogalma és az algoritmussal szemben támasztott követelmények • Feladat: n pénzérméből 1 hamis, állapítsuk meg kétkarú mérleggel a lehető legkevesebb méréssel, hogy melyik. Adjuk meg a teljes algoritmust!
Hajnal Éva: AAO előadás
24
start
Írja át az algoritmust struktogrammá, mondatszerű leírássá!
Be: a, b
i
a
Mi az eredmény, ha a=120, b=35
c:=b b:=a a:=c
h h a=b
a:=a-b i Ki: a end
Hajnal Éva: AAO előadás
25
Adatszerkezetek • A program feladata, hogy a bemenő adatokból, általában közbülső adatokon keresztül előállítsa a kimenő adatokat. • Program=Algoritmus+Adatok (Wirth) • A legtöbb programnyelv kategóriái: – Egyszerű adat – Összetett adat – Mutató Hajnal Éva: AAO előadás
26
Adattípusok csoportosítása • Egyszerű (megszámozható, v. skalár) típusok: – – – –
logikai karakter egész valós (ez gyakran nem számít megszámozhatónak)
• Strukturált (összetett) típusok: – – – – – –
tömb rekord egyesítés halmaz sorozat rekurzív típus Hajnal Éva: AAO előadás
27
Adattípusok jellemzői • • • • •
Neve Helyfoglalása Adattárolási mód Értékkészlet Műveletek
Hajnal Éva: AAO előadás
28
Néhány elemi adattípus a C# nyelvben C# típus
.NET típus
Helyfoglalás (byte)
Adattárolási mód
Értékkészlet
Műveletek
byte
System.Byte
1
Kettes számr.
0..255
+-/*%, =, ==
char
System.Char
1
Unicode
0..255
bool
System.Boolean
1
0 hamis >0 igaz
true, false
sbyte
System.SByte
1
kettes komplemens
-128..127
short
System.Int16
2
Kettes komplemens
-32768..32767
int
System.Int32
4
Kettes komplemens
-2147483647.. 2147483647
float
System.Single
4
IEEE 857
double
System.Double
8
IEEE 857
long
System.Int64
8
Kettes komplemens
string
System.String
Változó
Unicode karaktersor
object
System.Object
Változó
&&,&,||,|, >>,<<
/,*
Változó
29
Programozási tételek • Gyakran előforduló programozási alapfeladatok megoldására szolgáló alapalgoritmusok. • Helyességük matematikailag bizonyított. • A legtöbb nagy feladat ezekre a kisebb feladatokra felbontható. • Elvileg helyes, de nem mindig a leghatékonyabb megoldások egy-egy feladatra. Hajnal Éva: AAO előadás
30
Programozási tételek megadása • Feladat specifikációja: Pl. Számítsuk ki n darab billentyűzetről bekért egész szám (<20000) összegét. Az n értéke változó, de az adatsor előtt bekérhető. • Bemenő és kimenő adatok felsorolása, típusa esetleg a belső adatok felsorolása és típusa • Előfeltételek a bemenő adatokkal szemben • Utófeltétel vagy programfüggvény megadása • Algoritmus leírása • (Bonyolultság elemzése) Hajnal Éva: AAO előadás
31
Összegzés Eljárás Összegzés(s,n,összeg) Változó: i:egész összeg:elemtípus összeg:=0 Ciklus i:=0-tól n-ig 1-sével összeg:=összeg+s[i] Ciklus vége Eljárás vége Hajnal Éva: AAO előadás
32
Tömb adatszerkezet fogalma és jelentősége • A tömb olyan adatcsoport, amelynek elemei azonos típusúak és az elemekre sorszámmal ún. index-szel lehet hivatkozni. Az index sorszám jellegű adat, de nem csak szám lehet. • Az adatok dimenziók szerint vannak elrendezve. A dimenziószám azt jelenti, hogy hány kijelölő érték (index) kell ahhoz, hogy az adatcsoportból egy elemet kiválasszunk.
Hajnal Éva: AAO előadás
33
Egy dimenziós tömb : vektor Két dimenziós tömb: mátrix T T[4]
T
T[2,4] Hajnal Éva: AAO előadás
34
Megszámolás Eljárás Megszámolás(s,n,T,db) Változó: i,db:egész db:=0 Ciklus i:=0-tól n-ig 1-sével Ha s[i] T tul akkor db:=db+1 Elágazás vége Ciklus vége Eljárás vége Hajnal Éva: AAO előadás
35
Sorozatszámítás Eljárás Sorozatszámítás(s,n,f,a) Változó: i:egész a:elemtípus a:=f0 Ciklus i:=0-tól n-ig 1-sével a:=f(a,s[i]) Ciklus vége Eljárás vége Hajnal Éva: AAO előadás
36
Teszt • Készítsen algoritmust, amely kiszámítja az első n szám faktoriálisát!
Hajnal Éva: AAO előadás
37
Összegzés Eljárás Összegzés(s,n,összeg) Változó: i:egész összeg:elemtípus összeg:=0 Ciklus i:=0-tól n-ig 1-sével összeg:=összeg+s[i] Ciklus vége Eljárás vége Hajnal Éva: AAO előadás
38
Tömb adatszerkezet fogalma és jelentősége • A tömb olyan adatcsoport, amelynek elemei azonos típusúak és az elemekre sorszámmal ún. index-szel lehet hivatkozni. Az index sorszám jellegű adat, de nem csak szám lehet. • Az adatok dimenziók szerint vannak elrendezve. A dimenziószám azt jelenti, hogy hány kijelölő érték (index) kell ahhoz, hogy az adatcsoportból egy elemet kiválasszunk.
Hajnal Éva: AAO előadás
39
Egy dimenziós tömb : vektor Két dimenziós tömb: mátrix T T[4]
T
T[2,4] Hajnal Éva: AAO előadás
40
Megszámolás Eljárás Megszámolás(s,n,T,db) Változó: i,db:egész db:=0 Ciklus i:=0-tól n-ig 1-sével Ha s[i] T tul akkor db:=db+1 Elágazás vége Ciklus vége Eljárás vége Hajnal Éva: AAO előadás
41
Sorozatszámítás Eljárás Sorozatszámítás(s,n,f,a) Változó: i:egész a:elemtípus a:=f0 Ciklus i:=0-tól n-ig 1-sével a:=f(a,s[i]) Ciklus vége Eljárás vége Hajnal Éva: AAO előadás
42
Lineáris keresés Eljárás lineáris_keresés (A[N] sorozat, e: keresett elem) I=0 Ciklus amig ie i=i+1 Ciklus vége Ha i
43
Logaritmikus keresés Eljárás binaris_keresés(A[N] sorozat, e: keresett elem) also=0, felso=n-1 Ciklus amig alsoe kozepso=(also+felso)/2 Ha A[kozepso]< e akkor also=kozepso+1 Elágazás vége Ha A[kozepso]> e akkor felso=kozepso-1 Elágazás vége Ciklus vege Ha A[kozepso]= e eredmeny=kozepso Különben eredmeny=-1 Elágazás vége Eljárás vége Hajnal Éva: AAO előadás
44
Maximum kiválasztás Eljárás Maximumkiválasztás(s,n,max) Változó: i:egész max:elemtípus max:=s[0] Ciklus i:=1-t/l n-ig 1-sével Ha s[i]>max akkor max:=s[i] Elágazás vége Ciklus vége Eljárás vége Hajnal Éva: AAO előadás
45
Teszt • Mit nevezünk programozási tételnek? • Fibonacci sorozat n. elemének meghatározása
Hajnal Éva: AAO előadás
46
Maximum kiválasztás Eljárás Maximumkiválasztás(s,n,max) Változó: i:egész max:elemtípus max:=s[0] Ciklus i:=1-től n-1 ig 1-sével Ha s[i]>max akkor max:=s[i] Elágazás vége Ciklus vége Eljárás vége Hajnal Éva: AAO előadás
47
Kiválogatás ELJÁRÁS KIVÁLOGATÁS (A[],N,T,B[],DB) DB=0 I= 0 CIKLUS AMÍG I < N HA A[I] T tulajdonságú AKKOR B[DB]=A[I] DB=DB+1 ELÁGAZÁS VÉGE I=I+1 CIKLUS VÉGE ELJÁRÁS VÉGE Hajnal Éva: AAO előadás
48
Szétválogatás Eljárás Szétválogatás(s,n,dt,dbt,dnt,dbnt,T) Változó: i,dbt,dbnt:egész dbt:=0; dbnt:=0 Ciklus i:=0-tól n-ig 1-sével Ha s[i] T tul. akkor dbt:=dbt+1 dt[dbt]:=s[i] különben dbnt:=dbnt+1 dnt[dbnt]:=s[i] Elágazás vége Ciklus vége Eljárás vége Hajnal Éva: AAO előadás
49
Unio Eljárás Unioképzés(s,n,z,m,unio,db) Változó: i,j,db:egész unio:=s db:=n-1 Ciklus j:=0-tól m-ig 1-sével i:=0 Ciklus amíg i
Hajnal Éva: AAO előadás
50
Feladat • Ismert Magyarország I. osztályú focibajnokságának összes eddigi góllövőlistája. Készítsük el az abszolút listát. • Rekord adatszerkezet fogalma
Hajnal Éva: AAO előadás
51
Összefuttatás Eljárás Összefuttatás(s,n,z,m,unio,db) Változó: i,j,db:egész i:=0; j:=0; db:=-1 Ciklus amíg iz[j] esetén unio[db]:=z[j]; j:=j+1 Elágazás vége Ciklus vége Ciklus amíg i
52
Metszet Eljárás Metszetképzés(s,n,z,m,metszet,db) Változó: i,j,db:egész db:=0 Ciklus i:=0-tól n-ig 1-sével j:=0 Ciklus amíg j<m és s[i]!=z[j] j:=j+1 Ciklus vége Ha j<m akkor db:=db+1 metszet[db]:=s[i] Elágazás vége Ciklus vége Eljárás vége Hajnal Éva: AAO előadás
53
Rendezés • Fogalma: Rendezésnek nevezzük azt a folyamatot, amikor egy halmaz elemeit valamilyen szabály szerint sorba állítjuk. A rendezés meggyorsítja az elemek későbbi keresését. • A rendezendő adattömeg néha olyan nagy, hogy nem fér be a tárba. Ezek rendezésére valók a külső rendezések. • Az alábbi rendezési algoritmusok belső rendezések. Hajnal Éva: AAO előadás
54
Közvetlen cserés rendezés Eljárás Rendezés(s,n) Változó i,j:egész Ciklus i:=0-tól n-2-ig, 1-sével Ciklus j:=i+1-től n-1 ig, 1-sével Ha s[i]>s[j] akkor csere(s[i],s[j]) Elágazás vége Ciklus vége Ciklus vége Eljárás vége Hajnal Éva: AAO előadás
55
Közvetlen cserés rendezés indexvektorral Eljárás Rendezés(s,n) Változó i,j:egész ind:Tömb[0..n:egész] Ciklus i:=0-tól n-ig, 1-sével ind[i]:=i Ciklus vége Ciklus i:=0-től n-1-ig, 1-sével Ciklus j:=i+1-től n-ig, 1-sével Ha s[ind[i]]>s[ind[j]] akkor csere(ind[i],ind[j]) Elágazás vége Ciklus vége Ciklus vége Eljárás vége Hajnal Éva: AAO előadás
56
A rendezés ára • Műveletigény • Tárigény • Programbonyolultság
Hajnal Éva: AAO előadás
57
Rendezőalgoritmusok időbonyolultsága • Bonyolultság tényezői: – Összehasonlítások száma – Cserék – Értékadások száma
• Legrosszabb és átlagos eset • közvetlen cserés rendezés összehasonlítások és cserék (legrosszabb eset) száma:
n (n 1) O(n 2 ) 2
Hajnal Éva: AAO előadás
58
Minimum kiválasztásos rendezés Eljárás Rendezés(s,n) Változó i,j:egész Ciklus i:=0-tól n-1-ig, 1-sével érték:=s[i] index:=i Ciklus j:=i+1-től n-ig, 1-sével Ha érték>s[j] akkor érték:=s[j]; index:=j Elágazás vége Ciklus vége s[index]:=s[i] s[i]:=érték Ciklus vége Eljárás vége Hajnal Éva: AAO előadás
59
Buborékos rendezés Eljárás Rendezés(s,n) Változó i,j:egész Ciklus i:=0-től n-1 ig, 1-sével Ciklus j:=n-től i-ig -1-sével (visszafele) Ha s[j-1]>s[j] akkor csere(s[j-1],s[j]) Elágazás vége Ciklus vége Ciklus vége Eljárás vége ,
Hajnal Éva: AAO előadás
60
Javított buborékos rendezés ELJÁRÁS JOBB_BUBORÉK(S[],N) CSERE = 1 CIKLUS AMÍG CSERE ==1 CSERE = 0 J=0 CIKLUS AMÍG JS[J+1] AKKOR csere(S[J],S[J+1]) CSERE =1 ELÁGAZÁS VÉGE J=J+1 CIKLUS VÉGE CIKLUS VÉGE ELJÁRÁS VÉGE
ELJÁRÁS LEGJOBB_BUBORÉK(S[],N) CSERE = 1 DB = N CIKLUS AMÍG CSERE == 1 CSERE = 0 J=0 CIKLUS AMÍG J< DB -1 HA S[J]>S[J+1] AKKOR csere(S[J], S[J+1]) CSERE =1 ELÁGAZÁS VÉGE J=J+1 CIKLUS VÉGE DB = DB-1 CIKLUS VÉGE ELJÁRÁS VÉGE
Hajnal Éva: AAO előadás
61
Egyszerű beillesztéses rendezés (kártyás rendezés) Eljárás Rendezés(s,n) Változó i,j:egész M:elemtípus Ciklus i:=1-től n-1 ig, 1-sével M:=s[i] j:=i-1 Ciklus amíg M<s[j] és j>=0 s[j+1]:=s[j] j:=j-1 Ciklus vége s[j+1]:=M Ciklus vége Eljárás vége Hajnal Éva: AAO előadás
62
Beillesztéses rendezés bonyolultsága • Mozgatások száma • Összehasonlítások száma
Hajnal Éva: AAO előadás
63
Az összehasonlításon alapuló rendezések összehasonlításainak száma Alsó becslés: k>=lg(n!) K db kódszó (igen, nem) a sorrend helyességére.
Bemenet
Kódszó variációk
123
nnn
132
nin
213
inn
231
nii
312
iin
321
iii
Hajnal Éva: AAO előadás
64
Shell rendezés
Hajnal Éva: AAO előadás
65
Shell rendezés Eljárás Rendezés(s,n) Változó i,j,d,B:egész REK:elemtípus d:=n-1 Ciklus i:=0 Ciklus amíg i0 és REK<s[B] S[B+d]:=s[B]; B:=B-d Ciklus vége S[B+d]:=REK Ciklus vége i:=i+1 Ciklus vége d:=int(d/2) Ciklus vége amíg d<1 Eljárás vége Hajnal Éva: AAO előadás
66
ZH • Elfogadva 40% fölött • 20% alatt letiltás • Feladattípusok: – – – – –
Elmélet ~50% Készíts algoritmust! Melyik programozási tételre vezethető vissza? Írd át struktogramból mondatszerű leírássá…! Milyen értéket vesznek fel a változók a program végén? – Milyen adatokkal lehet tesztelni? Hajnal Éva: AAO előadás
67
Feladat – Programozási tételek alkalmazása • Egy iskolában sportdélutánt szerveznek. A sportoló tanulók nevét sportáganként tartjuk nyilván. Állapítsuk meg a sportdélutánon résztvevő tanulók számát. • Adott az A(N) egészekből álló számsorozat. Válogassuk ki azokat az egymástól különböző elemeket, amelyeknél a számjegyek összege 10. • Ismert Magyarország I. osztályú focibajnokságának összes eddigi góllövőlistája. Készítsük el az abszolút listát. Hajnal Éva: AAO előadás
68
Függvények A függvény utasítások logikailag összefüggő csoportja, mely önálló névvel és visszatérési értékkel rendelkezik. • Hívása printf(„Hello”); Console.Clear(); Consol.WriteLine(„Hello”); a=sin(x); Consol.WriteLine(sin(x));
• Szerkezete Visszatérésiértéktípusa FüggvényNeve(paraméterlista) { Utasítások; Return visszatérési érték; } Adatszerkezetek, algoritmusok, objektumok Dr. Hajnal Éva
69
Függvény végrehajtása, és definíciója static void terulet() { Console.WriteLine("Kérem a négyzet oldalát:"); int t = Int32.Parse(Console.ReadLine()); Console.WriteLine( t * t); } static void Main(string[] args) { terulet(); Console.ReadLine(); } 1. Program belépési pontja (Entry point)
Adatszerkezetek, algoritmusok, objektumok Dr. Hajnal Éva
70
Eljárás végrehajtása I.
Adatszerkezetek, algoritmusok, objektumok Dr. Hajnal Éva
71
Eljárás végrehajtása II.
Adatszerkezetek, algoritmusok, objektumok Dr. Hajnal Éva
72
Változók hatásköre • A változók hatásköre az őket tartalmazó blokkra terjed ki. • Ha több eljárás közt „osztunk meg „ egy változót: Static módosítóval rendelkező eljáráshoz static módosítójú változót kell definiálni.
Adatszerkezetek, algoritmusok, objektumok Dr. Hajnal Éva
73
Függvény visszaadott értéke • • • •
void int double Összetett adat
Eljárás
függvény
– pl. tömb
Adatszerkezetek, algoritmusok, objektumok Dr. Hajnal Éva
74
Paraméter átadás static void Kiiras(int a,int b) { Console.WriteLine("A {0}+{1}={2}",a,b,a+b); }
Adatszerkezetek, algoritmusok, objektumok Dr. Hajnal Éva
75
Függvény paraméterei
• Bemenő-Kimenő paraméterek • Érték szerinti – cím szerinti paraméter átadás • Paraméterek, helyi változók tárolása
Adatszerkezetek, algoritmusok, objektumok Dr. Hajnal Éva
76
Átadott paraméter egyeztetése
Adatszerkezetek, algoritmusok, objektumok Dr. Hajnal Éva
77
Érték szerinti paraméter átadás
Adatszerkezetek, algoritmusok, objektumok Dr. Hajnal Éva
78
Cím szerinti paraméter átadás • Átmenő, kimenő paraméter • Ref, out
Adatszerkezetek, algoritmusok, objektumok Dr. Hajnal Éva
79
Paraméterátadás • Szignatúra: függvény neve, és paraméterlistája az abban levő típusokkal • Írhatunk azonos nevű függvényeket, ha a szignatúrájuk különböző. Polimorfizmus.
Adatszerkezetek, algoritmusok, objektumok Dr. Hajnal Éva
80
Programozási feladat: 1. Készítsünk olyan függvényt, amely meghatározza két tömb elemeinek ismeretében a metszetük elemszámát! 2. Készítsünk olyan függvényt, amely meghatározza egy paraméterben megadott, int típusú tömbben a leghosszabb egyenlő elemekből álló szakasz hosszát! Adatszerkezetek, algoritmusok, objektumok Dr. Hajnal Éva
81
Teszt • Mit nevezünk függvénynek, eljárásnak? • Mit jelent a paraméterátadás kifejezés? • Mit jelent az érték szerinti, cím szerinti paraméter átadás?
Hajnal Éva: AAO előadás
82
Tömb Feladat: • Tételek alkalmazása mátrixokra – Adott egy tanulócsoport, minden diákhoz tartozik 4 vizsgaeredmény. Adjuk meg az átlagot, a bukások számát, a bukottak számát.
• Mátrix transzponáltja • Forgatás Hajnal Éva: AAO előadás
83
Ritka mátrix • •
A ritka mátrix olyan mátrix, melynek sok eleme nulla, vagy sok azonos értékű eleme van. Speciális eset pl. a háromszögmátrix – – –
•
2 3 0 0 5 1 4 0
Általános eset –
–
•
1 0 0 0
Tárolás vektorban Elemek száma: n*(n+1)/2 Elemek indexe: L=(j*(j-1)/2)+K
2 1 7 3
1. Háromsoros reprezentáció A három egydimenziós tömb azonos elemei írnak le 1-1 elemet sorfolytonos ábrázolásban. Mátrix n sor ,3 oszlop sorfolytonos ábrázolással, a 0. elem az elemszám
pl. az A mátrix:
•
120006 040000 000000 000000 000002
vagy
Ekkor tehát: SOR = (1,1,1,2,5) OSZLOP = (1,2,6,2,6) ÉRTÉK = (1,2,6,4,2)
5 6 5 1 1 1 1 2 2 1 6 6 2 2 4 5 6 2
Hajnal Éva: AAO előadás
84
Leképzés ritka mátrixra
Fordítva, amikor visszafelé Eljárás lekepez() keressük egy elem, pl. az A(ij)-t int i, j, k = 0; Eljárás keres(int i, int j) ciklus i=1-től N ig int l=1; ciklus j=1 –től Míg ciklus amíg (sor[l] != i OR OSZLOP[l] != j) and ha(A[i,j] != 0) akkor l i) Elágazás vége eredmény= 0 elágazás vége ciklus vége Ciklus vége ciklus vége Eljárás vége Eljárás vége Hajnal Éva: AAO előadás 85
Feladat: Adjuk meg egy három x n –es mátrixban tárolt ritka mátrix transzponáltját M=A[0,1], n=A[0,2], t=A[0,3] B[0,1]=n, B[0,2]=m, B[0,3]=t db=1 Ciklus sor=1 től n-ig ciklus p=1 től t-ig Ha A[p,2]=sor akkor B[db,1]=A[p,2], B[db,2]=A[p,1], B[db,3]=A[p,3] db=db+1 Elágazás vége ciklus vége Ciklus vége Hajnal Éva: AAO előadás
86
Verem, sor • Speciális tömb adatszerkezet, az adat beírás és az olvasás/törlés helye korlátozott. • Verem: LIFO Last In First Out – Műveletei: push – adatbeírás (ráhelyezés) – Pop – olvasás/törlés (leemelés) – Top - tetőelem
• Sor: FIFO First In First Out – Műveletei: sorból – Qdelete – Sorba - Qinsert Hajnal Éva: AAO előadás
87
Feladat verem, sor alkalmazására • • • • •
Szöveg megfordítása Szöveg szavainak megfordítása Szavak sorrendjének a megfordítása Ügyintézés modellezése Otp fiók várólista modellezése
Hajnal Éva: AAO előadás
88
Teszt: Feladat verem, sor alkalmazására Készítsen algoritmust az alábbi feladatok megoldására • Szöveg megfordítása • Szöveg szavainak megfordítása • Szavak sorrendjének a megfordítása • Ügyintézés modellezése • Otp fiók várólista modellezése Hajnal Éva: AAO előadás
89
Objektum Orientált paradigma • A szoftver krízis a szoftverfejlesztés válsága, miszerint egy hagyományos módszer (strukturált programozás) már nem képes az igényeknek megfelelő, minőségi szoftver előállítására. • Cél: – – – – –
Olcsó Jó minőségű szoftver Szoftver elemek újrafelhasználhatósága Szoftver fejlesztés csapatmunkában (design és kód különválasztása) Hajnal Éva: AAO előadás
90
Objektum definíció • Elv: Legkisebb modul az objektum, melyben adatok és eljárások össze vannak zárva. Objektumok, más néven példányok Adata: •neve
Bimbi (Kutya)
osztály
Blöki (Kutya)
•Fajtája •Testsúly
Kutya Bukfenc (Kutya)
Eljárás:
•hangot ad •eszik Hajnal Éva: AAO előadás
91
Objektumok jellemzője • Egységbe zárás (Encapsulation) • Felelősség • Zártság • Osztályozás
• Polimorfizmus • Öröklődés • Futás alatti kötés
Hajnal Éva: AAO előadás
92
Előzmények • SIMULA67: Algol verzió , hajók modellezése objektumokkal • 1969 Alan Kay egyetemista szakdolgozata az objektum orientált programozásról. • 1970 Xerox Smalltalk az első tiszta objektumorientált nyelv • 80-as évek: OO paradigma általánosan elfogadottá vált Hajnal Éva: AAO előadás
93
Programnyelvek csoportosítása • Tiszta OO nyelv pl. C# - Programozás csak oo alapon képzelhető el. Minden komponens objektum. Feladat a saját osztályok elhelyezése a hierarchiában. • Hibrid nyelvek pl. Turbo Pascal, C++ kétféle paradigma mentén is elképzelhető a programozás. • Objektum alapú nyelvek pl. Visual Basic, Javascript, PHP 4 Hajnal Éva: AAO előadás
94
Objektum • Elv: Legkisebb modul az objektum, melyben adatok és eljárások össze vannak zárva. • Objektumok jellemzője: – Zártság : a mezők tárolják az információt, a metódusok kommunikálnak a külvilággal. Az osztály változóit csak a metódusokon keresztül változtathatjuk meg. – Felelősség – Polimorfizmus – Osztályozás – Öröklődés – Futás alatti kötés Hajnal Éva: AAO előadás
95
UML feladata • Egységesített modellező nyelv • A program osztályainak és objektumainak megtervezését, és elemzését segítő modellező nyelv • Jogilag is szabványos jelölésrendszer • Grafikus nyelv, azaz a modellt diagramok segítségével ábrázolja • Alkalmazható a vállalatok közötti információcsere eszközeként • Nincs matematikailag bizonyítva a helyessége Hajnal Éva: AAO előadás
96
UML Unified Modeling Language 1.0 1997.01.13. Rumbaugh Booch Jacobsen • Az Objektumorientált rendszer saját feladattal bíró, egymással kommunikáló objektumok összesége. – – – –
Felhasználói interfész Kontroll Implementáció objektum – konténer Információ hordozó Hajnal Éva: AAO előadás
97
UML diagramtípusok • Osztálydiagram : Az objektumokat és az objektumok közötti kapcsolatokat jeleníti meg. • Objektumdiagram: Egyedi objektumpéldányok kapcsolatának megjelenítése • Állapotdiagram: az objektum időbeli viselkedését írja le. figyel
eszik gazda
alszik
ugat
támad
Ember
Hajnal Éva: AAO előadás
Kutya
98
Kapcsolattípusok • Asszociáció • Öröklés • Tartalmazási kapcsolat
Hajnal Éva: AAO előadás
99
Osztály fogalma • Az osztály: Névvel ellátott típus, ami az adattagokat és a rajtuk végzett műveleteket egységben kezeli. UML
adatta Class Kutya g { private int lábszám; private int kg; public int Ugat(paraméterek) {kód} } Metódus Felület: műveletek összesége Hajnal Éva: AAO előadás
Osztály -lábszám int -kg int + Ugat()
100
Adatok és metódusok láthatósága • Alap láthatóság módosítószavak – + publikus (public) – - privát (private) – # védett (protected) – (internal – protected internal C#)
Hajnal Éva: AAO előadás
101
Tervezzünk programot, amely síkidomok kerületét, területét tudja kiszámítani
Hajnal Éva: AAO előadás
102
Teszt • Tervezzünk programot, amely különböző síkidomok kerületét, területét tudja kiszámítani. (Készítsük el az osztály és az objektum diagramot az UML szabvány szerint!) • Tervezzünk programot, amely különböző irányba mozgó karaktereket tud kezelni. Hajnal Éva: AAO előadás
103
Játékprogramok • A számítógép feladata – Játék szimuláció – Játék szereplő
Hajnal Éva: AAO előadás
104
Backtrack algoritmus • 8 királynő problémája • Labirintus játékok • Lefedési feladatok
Hajnal Éva: AAO előadás
105
Backtrack algoritmus kezdetben d[] := 0 Eljárás bt(i) Ha i > 0 akkor d[i] := d[i] + 1 // adott szinten a következő döntés Ciklus amíg rossz(i) és d[i] még növelhető d[i] := d[i] + 1 Ciklus vége Ha nem rossz(i) // az i. szinten volt jó döntés akkor Ha megoldást találtunk akkor a megoldás kiírás/tárolása különben bt(i+1) // megyünk tovább a következő szintre Elágazás vége különben d[i] := 0 bt(i-1) // visszalépünk az előző döntési szintre Elágazás vége Elágazás vége Eljárás vége Hajnal Éva: AAO előadás
106
• Eljárás bt(i) 8 királynő megoldása Ha i > 0 akkor d[i] := d[i] + 1 Ciklus amíg d[i]<=8 és rossz(i) d[i] := d[i] + 1 Ciklus vége Ha d[i] <= 8 akkor Ha i = 8 akkor KI( d[] ) különben bt(i+1) Elágazás vége különben d[i] := 0; bt(i-1); Elágazás vége Elágazás vége Eljárás vége Hajnal Éva: AAO előadás
107
rossz: •egymás mellett •Azonos főátlóban
•Azonos mellékátlóban Függvény rossz(i):logikai rossz := hamis Ciklus j := 1-től (i-1)-ig Ha (T[j]=T[i]) vagy (T[j]-j=T[i]-i) vagy (T[j]+j=T[i]+i) akkor rossz := igaz kiugrás a ciklusból Elágazás vége Ciklus vége Függvény vége Hajnal Éva: AAO előadás
108
Vizsga • Írásbeli – Elméleti kérdések az órák anyaga alapján – Feladatok – Min 50%
• Érdeklődőknek: http://prog.berzsenyi.hu:8080/prog/View/ http://www.hsin.hr/coci/
Hajnal Éva: AAO előadás
109
Vizsgafeladat példa • • • •
•
•
A Sóhivatalban minden ügyintézőhöz naponta 1-10 új elintézendő akta érkezik, és minden ügyintéző naponta 1-10 ügyet old meg. Új ügyintézőt vesznek fel, aki úgy dolgozik, hogy a beérkező aktákat az asztalán egymás tetejére teszi. Először a legfelső aktával foglalkozik, majd veszi a következőt. (Mindig a kupac tetejéről.) Írjon algoritmust, amely verem adatszerkezettel kimutatást készít arról, hogy egy 10 napos ciklusban naponta mennyi ügyet dolgozott fel az ügyintéző, és a végén mennyi elintézetlen aktája maradt! A reggelente beérkező, valamint a napi elintézendő akták számát olvassa be. Az aktákat a beérkezés szerinti sorszámukkal tárolja a veremben! Az egy napon elintézett akták sorszámait írja ki a képernyőre, majd a 10. nap után az elintézetlen akták sorszámait is írja ki! A vermet megvalósító tömb legfeljebb 20 elemű legyen. Ha a verembe nem férnek be az új akták, akkor később kell őket betenni, ahogy a hely felszabadul. Ha viszont nincs annyi elintézetlen akta, amennyit fel kellene dolgozni egy napon, akkor aznap kevesebbet dolgozik az ügyintéző. A megoldáshoz csak egy tömböt használhat!
Hajnal Éva: AAO előadás
110