Adatstruktúrák, algoritmusok, objektumok 1. Számítási modellek és programozási paradigmák
Miklós Árpád, BMF NIK, 2006
[email protected]
1
Modellezési alapelvek A modellezés célja A modellezés célja a világ minél teljesebb körő megértése – Elemek, folyamatok, összefüggések, viszonyok
A modellezés során a fenti cél érdekében az ember: – ábrázolásokat készít a világról, majd – leképezi a világ egyes szeleteit az általa használt eszközökben (ennek során egy vagy több szempontot kiemel más szempontokkal szemben).
V1.0
2006. szeptember 12.
Miklós Árpád, BMF NIK, 2006
[email protected]
2
2
Modellezési alapelvek A modellezés folyamata • Absztrakció – Lényeg kiemelése, a jellegzetességek leegyszerősített leképezése
• Megkülönböztetés – Elemek meghatározása, elemek és tulajdonságaik szétválasztása
• Osztályozás – Elemek típusokba, csoportokba sorolása
• Általánosítás és specializáció – Elemtípusok bıvítése és szőkítése, elemhierarchiák kialakítása
• Kapcsolatok meghatározása – Különbözı kapcsolattípusok meghatározása, elemek közötti kapcsolatok felállítása • Ismeretség, leszármazás, tartalmazás, kompozíció...
V1.0
2006. szeptember 12.
Miklós Árpád, BMF NIK, 2006
[email protected]
3
3
Programozási paradigmák A paradigma fogalma • Paradigma: szemléletmód; modellezési, problémadefiníciós és problémamegoldási módszer – Programozási paradigma: a számítógép konkrét feladatok megoldására történı felhasználásának, irányításának módja
V1.0
2006. szeptember 12.
Miklós Árpád, BMF NIK, 2006
[email protected]
4
4
Programozási paradigmák Programozási paradigmák és programozási nyelvek • A programozási nyelveket általában egy-egy paradigma ihleti – Céljuk egy adott programozási paradigma legfontosabb jellemzıinek megvalósítása – A programozási paradigmák egy-egy számítási modellre épülnek
• A programozási nyelvek absztrakciós szintje folyamatosan nı – A kiindulópont a számítógép konkrét hardvermegvalósítása volt – Minden új paradigma növeli az absztrakció szintjét • Néha „holtágak” is keletkeznek, így egyes magasabb absztrakciós szintet képviselı nyelvek „kihalnak”, de a fenti állítás a fı fejlıdési irányokra is igaz
V1.0
2006. szeptember 12.
Miklós Árpád, BMF NIK, 2006
[email protected]
5
5
Programozási megoldások Számítási modellek és programozási paradigmák (1) • Imperatív számítási modellek („hogyan számítsuk ki”) – Turing-modell • Alan Turing nevéhez főzıdik (1936) • Nincs hozzá kapcsolódó programozási paradigma (csak elvi jelentısége van)
– Neumann-modell • Neumann János nevéhez főzıdik (1945) • Procedurális/strukturált programozási paradigma – Utasításorientált; az egyes mőveletek megismételhetık; többszörös értékadás; változók; alapvetıen soros végrehajtást feltételezı modell
– Objektumorientált modell • Objektumorientált (OO) programozási paradigma – Adatorientált; adatok és a rajtuk végezhetı mőveletek összerendelése objektumokká; üzenetáramlás az egyes objektumok között; a modell nem feltételez soros végrehajtást
– Adatfolyamelvő modell • Adatfolyamelvő programozási paradigma – Adatorientált (bemenı adatokból kimenı adatok); adatok kiértékelése rendelkezésre álláskor V1.0
2006. szeptember 12.
Miklós Árpád, BMF NIK, 2006
[email protected]
6
6
Programozási megoldások Számítási modellek és programozási paradigmák (2) • Deklaratív számítási modellek („mit akarunk kiszámítani”) – Funkcionális/applikatív számítási modell • Funkcionális programozási paradigma – Függvények redukciója automatikus behelyettesítésekkel – Példa (ML programozási nyelv)
fun factorial 0 = 1 | factorial n = n * factorial(n-1)
– Logikai alapú számítási modell • Logikai programozási paradigma – Egymással összefüggésben lévı állítások levezetése (rezolúció) mintaillesztéssel és következtetésekkel – Példa (Prolog programozási nyelv)
testvér(X,Y) :- szülı(Z,X), szülı(Z,Y). szülı(X,Y) :- apa(X,Y). szülı(X,Y) :- anya(X,Y). ?- testvér(Jancsi, Ilona) anya(Klára, Jancsi). igen. apa(Péter, Jancsi). apa(Péter, Ilona). apa(József, Péter). V1.0
2006. szeptember 12.
Miklós Árpád, BMF NIK, 2006
[email protected]
7
7
Programozási megoldások A számítási modellek, számítógép-architektúrák és programozási nyelvek összefüggése
Számítási modell
Specifikációs eszköz
Programozási nyelv
V1.0
2006. szeptember 12.
Megvalósítási eszköz
Végrehajtó eszköz
Miklós Árpád, BMF NIK, 2006
[email protected]
Számítógép-architektúra
8
8
Programozási megoldások fejlődése Különbözı számítási modelleken alapuló architektúrák versenye
Logikai alapú számítási modell
Elemi mőveletek szintjén párhuzamos modellek
Funkcionális/applikatív számítási modell
Adatfolyamelvő számítási modell
Neumann-féle számítási modell
1950 V1.0
2006. szeptember 12.
1960
1970
1980
Miklós Árpád, BMF NIK, 2006
[email protected]
1990
2000 9
9
A Neumann-architektúra A Neumann-architektúra alapvetı felépítése Adat/utasítás Vezérlés Memória
Bemenet
ALU Kimenet
Vezérlés
V1.0
2006. szeptember 12.
Miklós Árpád, BMF NIK, 2006
[email protected]
10
10
A Neumann-architektúra A Neumann-architektúra fıbb jellemzıi • Utasítások és adatok tárolása egy közös memóriában – Adatok tárolása nevesített változókban (elkülönített memóriarekeszek) – Nincs külsı megkülönböztetés az utasítás és az adat között, csak az aktuális programállapot dönt az értelmezésrıl – Az utasítások sorozata a programból, külsı beavatkozás nélkül is módosítható
• Folyamatos, ciklikus programvégrehajtás – A végrehajtás a memória elsı rekeszétıl indul, majd ha elérte a memória végét, ismét az elsı rekesztıl folytatódik
• Feltételes és feltétel nélküli vezérlésátadás – „A következı utasítás végrehajtása függjön az elızı eredményétıl” – Megismételhetı mőveletek, értékadások
• Soros, szinkron mőködés V1.0
2006. szeptember 12.
Miklós Árpád, BMF NIK, 2006
[email protected]
11
11
A Neumann-architektúra Az ENIAC számítógép (1946)
V1.0
2006. szeptember 12.
Miklós Árpád, BMF NIK, 2006
[email protected]
12
12