Adatstruktúrák, algoritmusok, objektumok

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.


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



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



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



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



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



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


Megvalósítási eszköz

Végrehajtó eszköz


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


1960

1970

1980


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



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



11

11

A Neumann-architektúra Az ENIAC számítógép (1946)

V1.0



12

12

Adatstruktúrák, algoritmusok, objektumok

Recommend Documents