Vissza az előzőleg látogatott oldalra (nem elérhető funkció)Vissza a modul kezdőlapjáraUgrás a tananyag előző oldalára (5)Ugrás a tananyag következő oldalára (7)Fogalom megjelenítés (nem elérhető funckió)Fogalmak listája (nem elérhető funkció)Oldal nyomtatása (nem elérhető funkció)Oldaltérkép megtekintéseSúgó megtekintése

Tanulási útmutató

Összefoglalás

A lecke célja, hogy a programozással még „frissen” barátkozóknak segítséget nyújtson az algoritmus megírásához az első lépésektől a komolyabb tervezés megkezdéséig. Bemutatjuk az algoritmikus gondolkodásba során szokásosan felvetődő problémákat és azok megoldási módszereit. Szóba kerülnek az elsődleges algoritmikus és programozásnyelvi utasítások és az elemi adattípusok.

Követelmény

Önállóan megoldható feladatok

A programozás nyelvi alapjai

Az elkövetkezőkben az algoritmikus és a programozási nyelvek két nagy „fejezetének” legfontosabb tudnivalóit tekintjük át: az utasítások és az adatok leginkább nélkülözhetetlen szókincsét.

1. Az algoritmizálás alapjai

Tárgyalásmódunkra jellemző lesz az, hogy nagyjából azokból a kérdésekből indulunk ki – és olyan sorrendben –, amelyeket a kezdő programkészítő kimondatlanul is gyakran feltesz magának – szerencsésebb esetben meg is fogalmazza, és neki is szegezi a rutinosabb programozóknak. Az ilyen naiv kérdéseket fogalmazzuk át precízebb, kicsit célratörőbb problémafelvetésekké, amelyeket minden egyes későbbi feladat megoldásánál újra elő lehet venni és az adott konkrét problémára újra lehet gondolni. Így ez mintegy vörös fonala lehet a kezdeti feladatmegoldási útkeresésnek. (A matematikai problémamegoldásra ugyanezt a hozzáállást valósította meg évtizedekkel ezelőtt Pólya György, a nemzetközi hírű magyar matematikus; az ő tiszteletére neveztük el a precízebb kérdéseket pólyai kérdéseknek.

1. pólyai kérdés: Elegendők-e az ismereteink a feladatról?

Meg kell fogalmazni, hogy pontosan mit kíván a feladat, azaz milyen adat(ok)ból (input) mi(ke)t (output) és milyen összefüggés alapján kell „kiszámolni”? A pontos, precíz megfogalmazást hívják specifikációnak, amellyel az előző fejezetben már foglalkoztunk, itt csak megemlítjük.

2. pólyai kérdés: Lehet-e tudni valamit a programról a konkrét feladattól függetlenül?

Úgy gondoljuk, különösebb megfontolást nem igényel az, hogy lássuk: a legtöbb program nagybani szerkezetében három jól körülhatárolható résznek kell lennie (legalábbis e három funkciót kell megvalósítani). Ezek a funkcionális részegységek:

Nem mindig érdemes, sőt nem mindig lehetséges e merev részfeladatokra bontás, de mi az egyszerűség kedvéért csak ilyenekkel fogunk foglalkozni. (Ha nem lenne ilyen a feladat, akkor nem lehetne pusztán a „feldolgozás” részre összpontosítani, hanem azt össze kellene vonni valamelyik másikkal. Ekkor a programunk bonyolódik, de a feladat nem megoldhatatlan.)

Ami a beolvasást és a megjelenítést illeti, többnyire – algoritmikus szempontból – elég egyszerűen elintézhetők. A három részfeladat közül tehát problematikusnak – általában – a középső tekinthető, így vizsgálódásunk középpontjába is ezt helyezzük. Folytassuk tehát a kérdezést!

3. pólyai kérdés: Elegendők-e ismereteink az adatokról?

Induljunk ki az input (= bemenő) és az output (= kimenő) adatok egy formai tulajdonságának, a „sokság”-nak a csoportosításából. Ilyen alapon a feladatok az alábbi félék lehetnek:

Input

Output

A. egyből

egyet

( pl. x ↦ ex )

B. egyből

sok(félét)

( pl. x ↦ sin(x), cos(x), tg(x) )

C. sok, azonos jellegűből

egyet

( pl. xi (i=1..n) ↦ ∑xi)

D. sok, azonos jellegűből

sok, azonos jellegűt

( xi (i=1..n) ↦ yj (j=1..m): yj>0 )

Megjegyzés

A sok, de különböző input adatból kiinduló feladat visszavezethető az „A” vagy a „B” esetekre!

Hogy mit értsünk egy alatt, az nem mindig egyértelmű. A fogalom megvilágítására álljon itt néhány példa (mert egyszerű, de precíz definíciót adni rá igen nehéz):

Összefoglalva: több adat együttese is alkothat egységet (sőt egységnek tekintendő!), ha egyetlen függvény vagy valami egységként elképzelendő dolog „állapotát” határozza meg.

E meggondolás arra jó, hogy a készülő program szerkezetéről legalább „heurisztikusan” megtudjunk valamit. Így a program:

A – egy „közönséges” transzformáció, amely például egy képlettel kiszámolható;

B – sok „közönséges” transzformáció, amelyek például egy-egy képlettel – elvileg akár párhuzamosan is, azaz egy időben – kiszámolhatók;

C és D – közös sajátosságuk, hogy valamit – éppen a „sok” egy elemének feldolgozását – kell sokszor elvégezni (esetleg akkumulálva az addigi számítás részeredményét).

4. pólyai kérdés: Nem lehet további ismereteket szerezni az adatokról? Nincs az adatainknak „finomabb” szerkezete?

Most az adatféleségek konkrétabb szerkezete alapján próbáljunk újabb információkat szerezni leendő programunkról! Még választási lehetőségünk is van. E célból ugyanis akár az input, akár az output adatokat szemügyre vehetjük. Az adatféleségekről:

A – „arctalan”, azaz szerkezet nélküli:

skalár adat (pl. egy vizsgált populáció egyedszáma, az adott helyen mért hőmérséklet);

B – sok, azonos valamik sokasága:

vektor, mátrix, halmaz, fájl (pl. korcsoportstruktúra, függvénytáblázat, virágszínek halmaza);

C – több, esetleg különféle valaminek az együttese:

rekord [pl. egy dátum (=év+hó+nap), egy gombahatározó egyes bejegyzései];

D – több, esetleg különféle valaminek többértelmű („sokarcú”) együttese:

alternatív (változó részt tartalmazó) rekord [pl. egy személy adatai (nemtől függően: ha hölgy, akkor leánykori név; ha úr, akkor katonakönyvszám)].

Talán ennyi ismeret után remélhetjük, hogy valamivel tisztábban tehető föl az „algoritmikus” kérdés, a kérdés a hogyanra, és persze a válasz sem várat magára.

5. pólyai kérdés: Elegendőek-e ismereteink az algoritmusról?

Nem véletlenül piszkálgattuk eddig az adatokat, pontosabban a feladatot meghatározó adatokat: először is ezek azok a „valamik”, amelyek eleve ismertek; másodszor, ha a fenti osztályba sorolást akár az inputra, akár az outputra elvégezzük, egyértelműen meg tudjuk mondani a feldolgozás „logikáját”, vagyis az eredményt kiszámoló program globális szerkezetét.

A – A program egy elemi transzformáció, amely egy – esetleg bonyolultan kiszámolható függvény hívását tartalmazó – értékadás vagy eljáráshívás output paraméter értékének visszaadása formájában realizálható, illetve – a tágabb környezetet is a program részének tekintve – egy kiírás vagy egy beolvasás révén változtatja meg a program állapotát. Hadd jegyezzük meg itt, hogy a probléma „elodázását” megtestesítő eljárások és függvények, amelyek az általuk kijelölt részfeladatok megoldását hivatottak elvégezni, argumentumukban tartalmazzák – ún. paraméterként – azokat az objektumokat, amelyekre vonatkoznak; vagyis amelyekből kiindulva (bemenő paraméterek) számolják ki az eredményt jelentő objektumokat (kimenő paraméterek) értékét. Érdemes észrevenni, hogy az eljárások, függvények be- és kimenő paraméterei nem mások, mint a megfelelő részfeladatok specifikációjának adatmegtestesülései.

B – A program egy ciklus, amelynek magja az ismétlődő elem kiszámolását hivatott elvégezni (és persze megszervezi az ismétlődést magát).

C – A feldolgozás szekvenciája (egymásutánja) az egyes „valamiket” feldolgozó tevékenységeknek.

D – A megoldás egy elágazás a „sokarcúság” szempontja szerint.

Az adatszerkezet és az algoritmikus szerkezet közötti fontos kapcsolatot nevezik a szakirodalomban a struktúra szerinti feldolgozás elvének.

Az alábbi ábra az eddigiek tömör összefoglalását adja.

Adatok és tevékenységek rajzos egymáshoz rendelése.Adatok, tevékenységek és kapcsolatuk.

Eszerint minden feladat akár kétféleképpen is megoldható: az egyik megoldás kiindulópontja az input szerkezete, a másodiké pedig az outputé. (Valójában általában kettőnél is több megoldás található.)

Elérkeztünk ahhoz a ponthoz, amikor az egyes algoritmikus elemeket (itt a következőkben), valamint adatszerkezeteket (a következő fejezetben) részletesen megvizsgáljunk, vagyis körvonalazzuk az algoritmikus „nyelvünket”.

Vissza a tartalomjegyzékhez

2. Algoritmikus elemek

2.1. Program

A program minden esetben utasítások sorozata lesz. Általában egy sorba egy utasítást írunk, de szükség esetén egy sorba több is írható (logikai összetartozásuk hangsúlyozásra), egymástól pontosvesszővel (;) vagy kettősponttal (:) elválasztva. Megegyezünk abban, hogy most és a továbbiakban is az algoritmusleíró nyelv alapszavai vastag betűsek, így különböztetve meg azokat az egyéb azonosítóktól.

Program:

utasítássorok

Program vége.

Az egyes utasításokat a – sorok közötti, illetve soron belüli – leírásuk sorrendjében kell végrehajtani.

Példa

Program:

Be: OSZTANDÓ, OSZTÓ

HÁNYADOS:=OSZTANDÓ Div OSZTÓ: MARADÉK:=OSZTANDÓ Mod OSZTÓ

Ki: HÁNYADOS, MARADÉK

Program vége.

2.2. Értékadó utasítás

Változók legtöbbször értékadó utasítással kapnak értéket. Ezen utasítás az értékadásjel (:=) bal oldalán a célként megjelölt változót, a jobb oldalán pedig a kiszámítandó kifejezést tartalmazza.

azonosító := kifejezés

Az azonosító tetszőleges olyan objektum neve lehet, amelynek értéke megváltozhat, a kifejezés pedig a matematikában és más tudományokban használt bármely operátort, függvényt, konstanst tartalmazhat.

Példa

Y:=sin(X)

F:=eX; G:=gyök(X-Y); H:=Y

P:=Q*R; S:=RT

Ez utóbbi példában mátrixok szerepelnek, a műveletek (*,T=transzponálás) értelemszerűen mátrixműveletek.

2.3. Beolvasó utasítás

Tetszőleges adat beolvasására szolgál a felhasználó által kezelt perifériáról (billentyűzetről). Mivel a felhasználó nem része a programnak, ezért az általa beírt adatok és a program által várt paraméterek típusát, értékhalmazát ellenőrizni kell. Az adatokat karakteresen kell megadni, és beolvasáskor a megfelelő változó típusa szerinti automatikus konverzió történik.

Be: azonosítók [feltételek]

A szűkítő feltételek elmaradhatnak, ha a beolvasandó értékekre semmilyen előfeltevésünk nincs. (Vegyük észre: ez az a feltétel, amit az előző – a specifikációról szóló – fejezetben előfeltételként jelöltünk meg!)

Példa

Be: OSZTANDÓ,OSZTÓ [OSZTÓ≠0]

Be: X [X[i]≥0: i=1..n]

2.4. Kiíró utasítás

Az előbbi utasítás ellentettje: a felhasználó által figyelt perifériára helyezi el az adatokat – a belső ábrázolástól függetlenül – karakteresen.

Ki: kifejezések [formátum megkötés]

Ha a kiírás formátumára van valamilyen speciális megkötésünk, akkor az itt szerepelhet, illetve a legtöbb ilyet majd kódoláskor kell megfontolnunk.

2.5. Megjegyzés

Az algoritmusban elhelyezhetünk magyarázó szövegeket, a program állapotára vonatkozó állításokat (pl. ciklusinvariánst), általában bármit, ami az olvashatóságot növeli. Ez a későbbi munkánkat jelentősen megkönnyítheti. Formája:

[ tetszőleges szöveg ]

2.6. Elágazások

Az elágazások szerepe – mint azt a korábbiakban láttuk – feltételektől függő választás bizonyos programrészek végrehajtása között.

A legegyszerűbb esetben dönthetünk egy utasítás(csoport) végrehajtása, illetve végrehajtásának kihagyása mellett:

Ha logikai kifejezés akkor utasítássor

A logikai kifejezés a matematikában szokásos tetszőleges relációt, illetve logikai értékű kifejezést, valamint logikai műveleteket tartalmazhat. Például – a teljesség igénye nélkül – a következőket:

Relációk

Műveletek

=, ≠, <, ≤, ≥, >

∈, ∉, ⊂, ⊆, ⊇, ⊃

és (∧), vagy (∨), nem (¬)

Példa

Ha I≤N és prím(I) akkor Ki: I

Ha I | N és nem (páros(I) vagy I>N/2) akkor K:=I

Az utasítás második fajtájában két utasításcsoport végrehajtása között választunk a logikai kifejezés igazságértékétől függően. Két változata lehetséges:

Ha logikai kifejezés akkor utasítássor1

különben utasítássor2

vagy

Ha logikai kifejezés akkor

utasítássorok1

különben

utasítássor2

Elágazás vége

Az első, rövidebb változatot akkor használjuk, ha ebből is egyértelmű, hogy az elágazás ágai hol fejeződnek be. Ha az elágazás valamelyik ágán több sort is akarunk írni, akkor pedig a második változatra lesz szükségünk.

Mindkettő lényege: ha a logikai kifejezés igaz értékű, akkor az akkor alapszó utáni utasításokat kell végrehajtani, ha pedig nem, akkor a különben alapszó utániakat.

Példa

Ha X<Y akkor Ki: X,Y

különben Ki: Y,X

Ha e∈H akkor H:=H-{e}

Ki: e," benne volt a halmazban."

különben H:=H+{e}

Ki: e," nem volt benne a halmazban."

Elágazás vége

Elképzelhető, hogy az elágazás ágain újabb elágazás következik. Ennek gyakori esete, hogy az elágazás különben ágán kell az újabbat elhelyezni. Ekkor tulajdonképpen az egyes ágak egyenrangúak, és ez az elágazás leírásában is tükrözhető.

Ha logikai kifejezés1 akkor

utasítássorok1

különben ha logikai kifejezés2 akkor

utasítássorok2

különben

utasítássorokn

Elágazás végen

A logikai kifejezéseket itt a felírás sorrendjében kell megvizsgálnunk, és az első igaz értékűnek megfelelő utasításcsoportot kell végrehajtani. Ha egyik sem teljesül, akkor az utolsó különben ágon levő utasításokkal kell foglalkozni.

Példa

Ha I<0 akkor Ki: "negatív"

különben ha I=0 akkor Ki: "nulla"

különben Ki: "pozitív"

Elágazás vége

Bizonyos esetekben a sokirányú elágazás feltételeinek kiértékelési sorrendjét nem akarjuk megkötni (tetszőleges sorrendben, illetve párhuzamosan is elvégezhetők lehetnek). Ekkor egy újfajta elágazást használunk:

Elágazás

feltétel1 esetén utasítássorok1

feltétel2 esetén utasítássorok2

feltételn esetén utasítássorokn

egyéb esetben utasítássorokn+1

Elágazás vége

Az „egyéb” a „nem feltétel1 és nem feltétel2 ésés nem feltételn” kifejezéseket rövidíti.

Itt az igaz feltételű elágazáságat kell végrehajtani. Ha több ilyen is van, akkor közülük tetszőlegeset, ha egy sincs, akkor az egyéb esetben alapszó utánit. Ez utóbbi ág el is maradhat; ha egyik feltétel sem teljesül, akkor az elágazás egyik ágát sem hajtjuk végre.

Példa

Elágazás
I=0 esetén F:=0

I=1 esetén F:=1

I>1 esetén F:=Fibonacci_szám(I-1)+Fibonacci_szám(I-2)

Elágazás vége

Mivel nem fogunk sem párhuzamos, sem nemdeterminisztikus algoritmusokat írni, viszont az utóbbi sokirányú elágazásszerkezet lényegesen áttekinthetőbb, ezért gyakran alkalmazzuk az előbbi helyett, vele megegyező értelemben.

A fentebb megfogalmazott kérdésfelvetéseket és a rájuk adható válaszokat láthatjuk a következő animációban.

Az animáció az ehhez a témához tartozó előadásrészletet tartalmazza.

Flash lejátszó letöltése

Algoritmikus alapok

Vissza a tartalomjegyzékhez

3. Az adatjellemzők összefoglalása

3.1. Azonosító

Az a jelsorozat, amellyel hivatkozhatunk a tartalmára, amely által módosíthatjuk tartalmát.

Például:

Vegyük észre a változó nevének Janus-arcúságát! Az x:=x+1 értékadásban a bal oldali x címhivatkozást reprezentál, amíg a jobb oldalon ugyanaz értékhivatkozást jelent. Ezért fontos az eljárásoknál a paraméterek ilyen szempontú megkülönböztetése: annak explicit jelzése, hogy input vagy output (is!) paraméter, ami a paraméterátadás-átvétel szempontjából érték- vagy címhivatkozást jelent.

3.2. Hozzáférési jog

Adatokat módosítani, illetve értéküket lekérdezni, használni lehet; eszerint egy adat a hozzáférés szempontjából négyféle lehet:

neve a külvilágban

módosítható

lekérdezhető

neve a memóriában

független

input

output

I/O

nem

nem

igen

igen

nem

igen

nem

igen

független

konstans

virgin

változó

3.3. Kezdőérték

A születéskor hozzárendelt érték. Konstansoknál nyilvánvaló; változóknál deklarációban kap-e, adható-e, vagy futáskor szerez értéket magának. Vegyük észre: ha a „nem definiált” érték egy speciális érték, akkor mód van ellenőrzésre is (virgin)!

3.4. Hatáskör

A programszöveg azon tartománya, amelyben az adathoz hozzáférés megengedett (nem független). Például az egyes eljárások használják egymás változóit, konstansait.

Az alábbi ábrán vázolt programhierarchia mindegyik eljárása (e1, ..., e5) használ egy i azonosítójú változót. Kérdés: milyen kapcsolatban állhatnak ezek az azonos nevű változók egymással, ha az eljárások kapcsolatát az alábbi séma írja le?

Egy hierarchia-diagram, amely bemutat egy konkrét program eljárás-hierarchiáját.Példa a hatáskörre.

Elképzelhető válaszok az i változók viszonyáról:

Példa

Jellemző

1. e1,...,e5-ben i ugyanaz

globális (az egész programra nézve)

2. e1, e4, e5-ben i ugyanaz, de e2, illetve e3-belitől független

lokális (az e1-re nézve; de az alatt levő szintek szempontjából globális)

3. e1,...,e5-ben mind különböző

lokális (minden eljárásra nézve; mondhatnánk: saját)

3.5. Élettartam

A futási időnek az az intervalluma, amelyben az adat azonosítója végig ugyanazt az objektumot jelöli.

Például:

A dinamikus adatok életét (futási időben) nem deklaratívan működő utasítások határozzák meg: létrehozzák, megszüntetik őket (így nem kötődnek a hatáskörhöz...).

3.6. Értéktípus

Az adatoknak az a tulajdonsága, hogy értékei mely halmazból származnak, és a tevékenységeknek (függvények, operátorok, utasítások) mely „készlete az, amelyik alkalmazható rá: létrehozza, felépíti, lerombolja és részekre bontja”.

Vissza a tartalomjegyzékhez

Fel a lap tetejére
Új Széchenyi terv
A projekt az Európai Unió támogatásával, az Európai Szociális Alap társfinanszirozásával valósul meg.