INFORMATIKA ÁLLAMVIZSGA

1. tétel: Programozás módszertan: programtervezés I.

Specifikáció. Programozási tételek (sorozathoz érték rendelése, sorozathoz sorozat rendelése, sorozatokhoz sorozat rendelése, sorozathoz sorozatok rendelése)

FOGALMAK

Specifikáció: A programkészítés menetének első lépése, a feladat meghatározása. A specifikáció egy olyan leképezést (programfüggvényt) határoz meg, amely a bemenő értékekhez hozzárendeli a jó eredmény értékét. A feladat szöveges és formalizált, matematikai leírásán túl tartalmazza a megoldással szemben támasztott követelményeket, környezeti igényeket is.

előfeltétel: A program indításakor igaznak kell lennie a bemeneti paraméterekre

leggyengébb előfeltétel: az a feltétel, amely az előfeltételek közül a legszűkebb, legmegengedőbb.

utófeltétel: A program befejeződésekor igaznak kell lennie az eredmény változók értékeire.

SPECIFIKÁCIÓ RÉSZEI:

feladatspecifikáció:

feladat szövege

bemenő és kimenő adatok elnevezése, értékhalmazának leírása

feladat szövegében használt fogalmak definíciói

bemenő adatokra felírt előfeltétel, kimenő adatokra felírt utófeltétel

programspecifikáció:

bemenő és kimenő adatok elnevezése, értékhalmazának leírása

feladat szövegében használt fogalmak definíciói

program elő- és utófeltétele (ez különbözhet a feladat elő- és utófeltételeitől)

előfeltétel lehet gyengébb, az utófeltétel szigorúbb a feladatspecifikációban leírtakhoz képest, ezzel általánosabbá téve a programot

program környezetének leírása

programmal szembeni egyéb követelmények (minőség, hatékonyság, hordozhatóság, …)

követelmények a specifikációval szemben (szöveges vagy formális specifikációval szemben egyaránt):

egyértelmű, pontos, teljes

rövid, tömör, formalizált

szemléletes, érthető

Programozási tételek: Típusfeladatok és megoldásaik, amelyekről bizonyítható, hogy egy garantáltan helyes, de a feladat szempontjából nem feltétlenül a leghatékonyabb megoldást adják. A bemenet és a kimenet szerint 4 nagy csoportba osztjuk őket:

sorozathoz érték rendelése

sorozathoz sorozat rendelése

sorozatokhoz sorozat rendelése

sorozathoz sorozatok rendelése

PROGRAMOZÁSI TÉTELEK

I. SOROZATHOZ ÉRTÉK RENDELÉSE

1. Sorozatszámítás: Adott egy N elemű sorozat. X(N) vektorban tároljuk a sorozat elemeit. Számoljuk ki a sorozat elemeinek összegét, szorzatát, ...!

2. Eldöntés: Adott egy N elemű sorozat és az elemein értelmezett T tulajdonság. X(N) vektorban tároljuk a sorozat elemeit. Döntsük el, hogy van-e a sorozatban T tulajdonságú elem!

3. Kiválasztás: Adott egy N elemű sorozat és az elemein értelmezett T tulajdonság. X(N) vektorban tároljuk a sorozat elemeit. Adjuk meg a sorozat egy T tulajdonságú elemét!

4.a. (Lineáris) keresés: Adott egy N elemű sorozat és az elemein értelmezett T tulajdonság. X(N) vektorban tároljuk a sorozat elemeit. Vizsgáljuk meg, hogy van-e T tulajdonságú elem a sorozatban! Ha van, akkor adjunk meg egyet!

4.b. (Logaritmikus) keresés: Adott egy N elemű sorba rendezett sorozat és az elemein értelmezett T tulajdonság. X(N) vektorban tároljuk a sorozat elemeit. Vizsgáljuk meg, hogy egy adott elem eleme-e a sorozatnak!

4.c. Visszalépéses keresés (Backtrack): Adott N sorozat, amelyek rendre M(1), …, M(N) elemszámúak. Ki kell választani mindegyikükből egy-egy elemet úgy, hogy az egyes sorozatokból való választások más választásokat befolyásolhatnak.

5. Megszámolás: Adott egy N elemű sorozat és az elemein értelmezett T tulajdonság. X(N) vektorban tároljuk a sorozat elemeit. Add meg, hogy hány T tulajdonságú elem van a sorozatban!

Maximumkiválasztás: Adott egy N elemű sorozat és az elemein értelmezett egy rendezés. X(N) vektorban tároljuk a sorozat elemeit. Add meg a sorozat maximális értékét!

II. SOROZATHOZ SOROZAT RENDELÉSE

1. Másolás: Adott egy N elemű sorozat. X(N) vektorban tároljuk a sorozat elemeit. Az összes elemmel csinálj valamit!

2. Kiválogatás: Adott egy N elemű sorozat és egy a sorozat elemein értelmezett T tulajdonság. X(N) vektorban tároljuk a sorozat elemeit. Válogasd ki az összes T tulajdonságú elemet!

3. Rendezések: Adott egy N elemű sorozat. X(N) vektorban tároljuk a sorozat elemeit, amelyeken rendezés értelmezhető. Rendezd a sorozatot!

	helyfoglalás	hasonlítások száma	mozgatások száma
Egyszerű cserés	N+1	N*(N-1)/2 O(n2)	0 – 3*N*(N-1)/2 között O(n2)
Minimumkiválasztásos	N+1	N*(N-1)/2 O(n2)	3*(N-1) O(n)
Buborékos	N+1	N*(N-1)/2 O(n2)	0 – 3*N*(N-1)/2 között O(n2)
Javított buborékos	N+1	N-1 – N*(N-1)/2 között O(n2)	0 – 3*N*(N-1)/2 között O(n2)
Beillesztéses	N+1	N-1 – N*(N-1)/2 között O(n2)	0 – 3*N*(N-1)/2 között O(n2)
Javított beillesztéses	N+1	N-1 – N*(N-1)/2 között O(n2)	2*(N-1) – 2*(N-1)+N*(N-1)/2 között O(n2)

Megjegyzés: Léteznek rendezési tételek azokra az esetekre, amikor valamivel több információnk van a sorozat elemeiről. (például ismerünk hozzá egy kulcsot). Ezek a következők: Szétosztó, számlálva szétosztó és számláló.

Megemlítendő még a Shell-rendezés, amely tulajdonképpen egy javított beillesztéses rendezést hajt végre nagy, egyre csökkenő lépésközzel. Fontos, hogy a lépésköz az algoritmus végén el kell, hogy érje az 1-et.

III. SOROZATOKHOZ SOROZAT RENDELÉSE

Halmazműveletek:

Metszet: Adott két sorozat. X(N) és Y(N) vektorban tároljuk a sorozatok elemeit. Készítsd el a metszet sorozatukat!

Unió: Adott két sorozat. X(N) és Y(N) vektorban tároljuk a sorozatok elemeit. Készítsd el a metszet sorozatukat!

Összefuttatás: Adott két rendezett sorozat. X(N) és Y(N) vektorban tároljuk a sorozatok elemeit. Készítsd el a metszet sorozatukat!

IV. SOROZATHOZ SOROZATOK RENDELÉSE

1. Szétválogatás: Adott egy N elemű sorozat és egy a sorozat elemein értelmezett T tulajdonság. X(N) vektorban tároljuk a sorozat elemeit. Válogasd szét a T tulajdonságú és nem T tulajdonságú elemeket!

1.a. Helyben szétválogatás: A feladatot meg lehet oldani kevesebb helyfoglalással, ha helyben válogatjuk szét az elemeket.

2. tétel: Programozás módszertan: programtervezés II.

rekurzív algoritmusok és adattípusok, rekurzió és iteráció közötti átírási szabályok, fák, gráfok, alkalmazásaik. Párhuzamos algoritmusok megvalósítási módszerei (szemafor, monitor, üzenetátadás randevúval)

Rekurzió: olyan programszerkezet, melynek definiálásakor önmagára hivatkozunk.

A rekurzió egy feladat megoldása során több ízben is előkerülhet. Legelőször a feladat megfogalmazása során, amikoris a specifikáció során képies és természetes eszközként rekurzióval rögzítik a feladatot. Máasodjára akkor kerülhet felszínre, amikor valaminek a szerkezetét, típusát vagy a végrehajtás algoritmusát definiáljuk ily módon. Végezetül a programozási nyelv maga is kínálhat lehetőséget rekurzív megfogalmazásra. Ekkor a rekurzió mint implementációs eszköz jelenik meg. Bizonyos programozási nyelvek nem támogatják a rekurzív algoritmusokat, ezeknél verem használatával oldható meg a rekurzió.

általános definíció:

f(i) =	h(i)	, ha 0 i < k

g(f(i-1),…,f(i-k))	, ha i K

Példák: faktoriális-számítás, Fibonacci-számok, Hanoi-tornyai, Ackermann-függvény, QuickSort

Átírási szabályok

Rekurzió-iteráció kapcsolata: A tapasztalatok azt mutatják, hogy sok esetben a rekurzív megoldás sokkal idő és helyigényesebb, mint az iterációs megoldás. Ezért fontos ismernünk azokat a szabályokat, amelyekkel az egyikből a másikba juthatunk át.

1. Rekurzív formulával definiált függvények

2. Jobbrekurzió : A rekurzív hívás az eljárás végén található. Nincs szükség a rekurzív hívás után az eljárás lokális változóira

3. Balrekurzió : A rekurzív hívás az eljárás elején található.

(Amennyiben a T és S eljárások nem változtatják meg a paramétereik értékét, akkor átírható az algoritmus nem rekurzívvá. Gond, hogy először N-szer alkalmaznunk kell f függvényt X-re, utána jön a T eljárás, majd visszafelé kellene haladnunk, azaz kellenek az X összes f függvénnyel kapott értékei. Ha f-nek van inverze, akkor könnyű a dolgunk, ha nincs akkor verem műveletekkel oldható meg a probléma.)

Iterációs-rekurzió kapcsolata: A funkcionális nyelvek (pl. LOGO) esetében az átírás másik irányára lehet szükségünk, ugyanis ezekben a nyelvekben nem léteznek ciklusok, vagy csak nagyon primitív formában, ezért szükség lehet arra, hogy egy ciklust rekurzív módon fogalmazzunk meg.

Rekurzív adatszerkezetek: A rekurzív adatszerkezetek megvalósításához a legtöbb nyelvben a mutatók nyújtanak segítséget. A mutató két információt tartalmaz: a következő elem memória címét, és annak típusát, amiből megfejthető, hogy mekkora helyet foglal el a memóriában.

fajtái:

típus lista:= Rekord (elem: elemtípus, köv: lista)

típus binfa := Rekord(elem: elemtípus, bal, jobb : binfa)

típus fa:= Rekord (elem: elemtípus, ágak: sorozat(fa))

Bináris fa: olyan fa, amelynek minden csúcsából max. 2 él indul ki és egy érkezik be.

(b: binfa, e: elemtípus)

műveletek: üres, létrehoz(b,e), balrailleszt(b,e), jobbrailleszt(b,e), balróllevág(b,e), jobbróllevág(b,e), …

bejárások: (BKJ(inorder), KBJ(preorder), BJK(postorder)

alkalmazásai: aritmetikai kifejezések számítása, rendezés, keresés

keresőfa: olyan fa amely lehetővé teszi a gyors keresést. Ehhez szükség van a rendezettségre:

rendezőfa: Ha e<f, akkor e az f bal ágán lesz. (rendező algoritmus: heapsort - kupacosítás)

teljes bináris fa: olyan fa, amelynek mélysége minden ágon maximum eggyel tér el. Legfeljebb egy olyan eleme van, amelynek egy gyereke van. Ilyen fát nehéz csinálni.

teljesen kiegyensúlyozott bináris fa: Olyan bináris fa, amely ha n szintű, akkor az n-1. szintig teljesen kitöltött.

kiegyensúlyozott bináris fa: Olyan bináris fa, amely amelyben igaz, hogy minden elemnek a bal és jobb gyerekének mélysége maximum egy szinttel tér el egymástól. Viszonylag könnyű létrehozni.

B-fa: elemek rendezett sorozatok (max, N elemmel) és minden szintről max. N+1 leágazás lehetséges. Mivel a törlés aránylag bonyolult feladat, ezért olyankor érdemes használni, amikor sok keresési és kevés törlési feladat adódik várhatóan.

Gráf: pontok és ezeket összekötő élek együttese

út: olyan egymásba kapcsolódó élek sorozata, amely egyetlen ponton sem megy át kétszer.

összefüggő gráf: olyan gráf, amelynek bármely két pontja között létezik út.

irányított gráf: az éleknek irányításuk van

irányítatlan gráf: az élek végpontjai nem megkülönböztettek.

súlyozott gráf: az éleknek "hosszuk" van

páros gráf: olyan gráf, amely szétosztható két diszjunkt halmazra úgy, hogy a halmazokon belül nincs él.

Ábrázolási formák:

1. csúcsmátrix: ha a gráfnak N csúcs van, akkor a csúcsmátrix egy NxN-es logikai mátrix, ahol C(i,j) igaz értéket vesz fel, ha i és j csúcsok között van él.

2. csúcslista: minden csúcshoz felsoroljuk, hogy mely csúcsokkal van összekötve (probléma: többszörös élek)

3. élmátrix: Az élek felsorolása a kezdő és végpontok segítségével, és azok szerint sorba rendezve. 3 oszlop tartalmazhatja az élek "súlyát" amennyiben súlyozott gráfról van szó.

4. csúcs-él mátrix: Ha N csúcsunk és M élünk van, akkor egy MxN-es mátrix, ahol az i. él acsa. köti össze a j. és a k. csúcsokat, ha (i,j) és (i,k) igazak.

speciális mátrixok:

Összefüggőségi mátrix: NxN-es mátrix, amelynek (i,j) csúcsának értéke igaz, ha i és j csúcs között van út.

Távolság mátrix: NxN-es mátrix, amelynek (i,j) csúcsának értéke az i és j csúcsok közti legrövidebb út hossza.

Alkalmazások: legrövidebb út, leghosszabb út keresés. munkafolyamatok leírása, szervezése. Családfa.

PÁRHUZAMOSSÁG

Fontos szerepe van az operációs rendszerek területén, amikor is azt szeretnénk, hogy egyszerre több felhasználót vagy több programot szolgáljon ki a gép. Ezenkívül felhasználják szimulációk esetében is.

A párhuzamosság lehet valódi és látszólagos is. Látszólagos, ha egy processzor tesz úgy, mintha több lenne.

Lényeges rész a közös erőforrások kezelés, ez általában lock-olással történik, annek három fajtája van:

szemafor, monitor és az üzenetátadós modell

lock-olás hatása lehet az ún. halálos ölelés, ilyenkor a processzor feladata közbelépni.

A processzor eszközei: várakoztatás, késleltetés, szinkronizáció, információátadás.

Párhuzamosság fajtái:

1. utasításon belüli párhuzamosság: megfelelő hardver szükséges hozzá: csővonal(pipeline) processzor – egyszerre felismer és betölt

2. adatpárhuzamosság: megfelelő hardver szükséges hozzá: mátrixprocesszor – sok azonos feladatot kell megoldani. Pl. mátrixösszeadás, szimuláció (molekulák mozgása)

3. utasítások közötti párhuzamosság: programozási kérdés.

párhuzamosság körébe tartozó megoldandó problémák:

algoritmus, ami a párhuzamosságot vezérli,

közös erőforrások kezelése

védelem

várakozási sor kezelése

holtpont kezelés (amikor mindenki a másikra vár)

információcsere kérdése, szinkronizáció

Szemafor: Lényege, hogy a közös erőforrást legfeljebb egy eljárás alkalmazhassa. Megoldás, hogy a jelentkezők egy várakozási sorban várakoznak, ha felszabadul az erőforrás, akkor végrehajtódnak, majd ha végeztek, akkor szabaddá teszik az erőforrást. Mindezt két eljárással valósítja meg (s: logikai):

Várj(s): szabad jelre várakozik

Jelezz(s): szabadra állít

Példa: palacsintasütő-evő (közös a tányér)

Monitor

Olyan eljárás, amely magába gyűjti a közös erőforrásokat, nem megszakítható, így legfeljebb monitor működhet egyszerre. Programokat képes sorba állítani, ütemezni, rendezni. pl. Windows nyomtatásvezérlő

Probléma lehet, hogyha nem figyelünk arra, hogy ez egy monitor eljárás, akkor könnyen kialakulhat a holtpont.

Üzenetátadásos modell: Nincsenek közös eszközök, ha valakinek kell valami, azt le kell tárgyalnia a másikkal. Ennek két módszere ismeretes: randevú (ha találkoznak) és üzenő-tábla (ha nem találkoznak)

Két eljárása van: Küld(vkinek, vmit) és Vesz(vkitől, vmit)

Példa: Metró

6. tétel: Programozási technológia:

A programkészítés folyamata. Programkészítési elvek. Algoritmus leíró eszközök. Programok kódolása. A kód hatékonysága, a hatékonyság mérése. Tesztelési módszerek. Hibakeresési módszerek és eszközök. Dokumentálás.

PROGRAMKÉSZÍTÉS FOLYAMATA

Specifikáció: Mit kell megoldani?

Tervezés: Hogyan? –> Algoritmus

Kódolás: -> program

Tesztelés: Jó vagy rossz a program? -> helyességbiznyítás

Hibakeresés: Hol a hiba? -> hibajavítás

Hatékonyság: minőségvizsgálat és javítás

Dokumentálás: felhasználói, programfejlesztői

megjegyzések:

a tesztelés és a hibakeresés pontok ciklikusan követik egymást addig, amíg nem lesz a tesztelés eredménye kielégítő

A dokumentáció írása végigkíséri az egész folyamatot, nem csak a végén végezendő!

PROGRAMKÉSZÍTÉSI ELVEK

1. Stratégiai elvek:

"Oszd meg és uralkodj": felülről lefelé kifejtés, lépésenkénti finomítás -> ez a közkedveltebb: bármely program szétosztható 3 alapvető részre: beolvasás, feldolgozás, kiíratás

alulról felfelé építkezés

2. Taktikai elvek:

párhuzamos finomítás elve: Egy adott szint minden rész feladatát finomítsuk, ne szaladjunk előre egy könnyűnek vélt ágon!

Döntések elhalasztásának elve: Halasszuk későbbre azokat a döntéseket, amelyekhez még nincs elég ismeretünk!

Döntések nyilvántartása: Minden döntésünket jegyezzük fel, mert elfelejthetjük mit miért tettünk, és kódolásnál problémáink lehetnek.

Vissza az ősökhöz elv: Ha zsákutcába jutunk, lépjünk vissz egy szintet

Adatok elszigetelésének elve: Az egyes programrészeken belül alkalmazott adatokat ne vigyük be más programrészletekbe

Nyílt rendszerű felépítés elve: Ne egy adott feladathoz, hanem egy általánosabb feladatkörhöz készítsük el algoritmusunkat!

Párhuzamos ágak függetlenségének elve: egy szinten lévő eljárások egymást nem hívhatják, egymás változóit nem láthatják.

Szintenkénti teljes kifejtés tétele: A szint specifikációjának tartalmaznia kell a majdan alatta elhelyezkedő szintek leírását is.

3. Technológiai elvek: (program leírásához szükséges)

Algoritmus leírási szabályok: egyértelmű. A fő programeszközök (szekvencia, ciklus, elágazás) jól különüljenek el! Az eljárások, függvények megoldása.

Értelmes sorokra tördelés: Alapállás: minden utasítás külön sorba, de szervesen összefüggő utasítások egy sorba is kerülhetnek

Bekezdéses leírás: Az algoritmus szintekre tagolását a leírás formája is tükrözze

Összetett struktúrák zárójelezése: pl. ciklus, elágazás elejének, végének jelölése

Beszédes azonosítók használata: Használjunk olyan azonosító neveket, amelyek tükrözik a változó tartalmát.

4. Technikai elvek:

Barátságosság, udvariasság: tájékoztatás, segítségnyújtás a program teljes futása alatt

Biztonságosság: A felhasználó hibás adatbeírására, lehetőleg bármilyen hibalehetőségre fel kell készíteni a programot, és a hiba javítására lehetőséget kell adni a felhasználónak

Jól olvasható program: Kommentezés

Jól dokumentált program

5. Esztétikai elvek:

Lapkezelés: A képernyőlapok arányos kitöltése, időbeni váltása, azonos logikai szinthez tartozó programrészek egy képernyőlapon való kezelése, fontos részek kiemelése. Ne legyen túl giccses. Lapváltáskor várakozás!

Menütechnika: Bonyolult szolgáltatásokkal rendelkező programoknál elengedhetetlen. Egér használata megkönnyíti a felhasználást.

Ikontechnika: A szöveges megoldásnál sokkal átláthatóbb, használhatóbb, ha kis ábrák segítik a munkát.

Értelmezési tartomány kijelzése: Jelezzük ki a minimális és maximális adatot és a mértékegységet az adatok beolvasásakor

Tördelés: Nyelvtanilag helyes, esztétikus szövegkezelés

Következetesség: Vagy mindig Entert használjunk az adatbevitelkor lezárásként, vagy soha.!

Hibajelzés: írjuk ki a hiba okát, adjunk instrukciót a hiba javítására vonatkozóan. Legyen visszaállítható a hiba előtti képernyő.

Naplózás: A program elmentheti időnként a beállításait a későbbi vizsgálatok céljából

Funkcióbillentyűk: érdemes a program gyakran használt szolgáltatásaihoz egy billentyűkombinációt rendelni.

Ablaktechnika: Valamilyen logikai elkülönülő rész formailag is elkülönül

ALGORITMUSLEÍRÓ ESZKÖZÖK

Céljuk a megoldás menetének programozási nyelvtől független, szemléletes leírása.

1. Folyamatábra: Az egyik legrégebbi algoritmus leíró nyelv, amely a programot egy gráfként írja le. A programleíró gráf olyan gráf, amelynek egyetlen kiinduló és egyetlen befejező éle van. A kiinduló élből el lehet jutni bármely csomóponthoz és bármely csomópontból el lehet jutni a befejező élhez.

csomópontok fajtái: utasításcsomópont, döntéscsomópont, gyűjtőcsomópont

gráf elemei: szekvencia, elágazás, ciklus

START STOP értékadás elágazás beolvasás/kiírás előnye, hogy jól használható nyomkövetésre, hátránya, hogy nehézkes, áttekinthetetlen, struktúrája nem felel meg az algoritmus megírása során használt struktúrának.

2. Struktogram: Hasonló a folyamatábrához, csak a programgráfot élek nélkül ábrázolja. Az algoritmust téglelepba írjuk, melybe további téglalapokat illesztünk, és a végrehajtandó utasításokat ezekbe írjuk bele.

Elemei:

szekvencia: utasítás feltétel i h kétirányú elágazás: (többirányú hasonlóan) utasítás 1. utasítás 2.

ciklusmag ciklus feltétel hátultesztelősciklus ciklusmag ciklus feltétel előltesztelős ciklus

3. Mondatszerű leírás: A program lépéseit mondatszerűen leíró nyelv. Lehet sorszámozással, vagy bekezdésekkel tagolni.

PROGRAM KÓDOLÁSA:

A program kódolása, tulajdonképpen az algoritmus valamely programozási nyelvre való lefordítása.

algoritmus mélysége:

teljes részletességgel

programozási tételek mélységéig

modulspecifikáció mélységéig

A programozási nyelv kiválasztásának szempontjai:

lehetőségek

ismeret

dokumentáltság

alkalmazhatóság

hatékonyság

hordozhatóság

Kódolási szabályok, programtranszformációk:

nem megengedett értékadás kiküszöbölése

nem megengedett beolvasás, kiírás kiküszöbölése (pl. Pascalban nincsen tömb-beolvasás)

nem megengedett elágazás feltétel kiküszöbölése (logikai változó bevezetése)

nem létező különben ág kiküszöbölése (ha f …akkor …..: ha nem f akkor….)

nem létező sokfelé elágazás kiküszöbölése

szimmetrikus logikai művelet kiküszöbölése

ciklusok átírása, amennyiben nincsen valamilyen fajta

függvény helyettesítés változóval, amennyiben nem létezik függvény

nem megengedett függvényérték kiküszöbölése

A KÓD HATÉKONYSÁGA:

1. Végrehajtási idő csökkentése:

elvi tanácsok:

gyorsabb számolást lehetővé tevő adattípusok használata

gyors műveletek használata

összetett kifejezések egyszerűsítése

aritmetikai kifejezések egyszerűsítése

képlet transzformációk használata

konstans kifejezések előre kiszámítása

programtranszformációk:

összetett feltételek szétválasztása

elágazás felesleges feltételeinek elhszgyása

elágazások összevonása

ciklusok összevonása

ciklustól független utasítások kiszedése

Programozási nyelv szerepe:

értékadások speciális fajtái

speciális műveletek

háttértár kezelés

2. Helyfoglalás csökkentése

adatok méreteinek csökkentése:

indexek, változók csökkentése

hézagosan kitöltött struktúrák cseréje

programkód méretének csökkentése:

eljárások, függvények használata

adatok előfeldolgozása

HATÉKONYSÁG MÉRÉSE:

1. Végrehajtási idő mérése:

algoritmus alapján számítható jellemzők (utasítások, eljáráshívások száma)

futás közben

teljes programé

egyes részeké

2. Helyfoglalás mérése

algoritmus alapján számítható jellemzők (utasítások, eljáráshívások száma)

futás közben

operációs rendszer szolgáltatásai (memória, fileméret)

TESZTELÉSI MÓDSZEREK

A tesztelés célja minél több hibának a kiszűrése. Az összes hiba kiszűrésére, csak az összes lehetőség kipróbálásával lenne lehetőség.

fogalmak:

teszteset: A be és kimeneti adatok és feltételek megadása

próba: A tesztesetek azon halmaza, amelyekre a programot kipróbáltuk

ideális próba: a tesztesetek azon halmaza, amelyek kipróbálásával az összes hiba fellelhető

adott ε szinten megbízható próba: a tesztesetek azon halmaza, amellyel 1- ε valószínűséggel felfedhetjük az összes hibát.

Alapelvek:

Egy jó teszteset nagy valószínűséggel egy még fel nem fedezett hibát mutat ki.

A meg nem ismételhető tesztesetek kerülendők

A teszteseteket mind az érvényes mind az érvénytelen tesztesetekre kell elvégezni

Minden esetből lehetőleg minél több információt meg kell kapni

Ha valami nem jól működik, akkor a hiba forrását kell megkeresni

A program tesztelését csak "idegen kéz" tudja hatékonyan elvégezni

Módszerek:

Statikus tesztelési módszerek:

(a programot nem hajtjuk végre, csak a kódot vizsgáljuk)

kódellenőrzés (algoritmus kód összevetése)

formai ellenőrzés, kereszthivatkozási táblázat készítése (szintaktika)

tartalmi ellenőrzés (szemantikus ellenőrző kiszúrhatja)

felhasználatlan változók, objektumok keresése

érték nélküli változó

értéket nem változtató utasítás

azonosan igaz vagy hamis állítások

konstans értékű kifejezések

végtelen ciklus

érték nélküli vagy mellékhatással rendelkező függvény, vagy operátor

Dinamikus tesztelési módszerek:

(program futás közben)

fekete doboz módszer (a program belső szerkezete nem ismert)

ekvivalencia osztályok keresése

határeset elemzés

fehér doboz módszer

kipróbálási stratégiák (utasítások lefedésének elve, döntéslefedés elve, feltétellefedés elve)

teszteset generáló módszerek (arra keresi a választ, hogy mely adatokkal próbáljuk ki a programot)

HIBAKERESÉSI ESZKÖZÖK ÉS MÓDSZEREK:

Hibajelenségek:

szintaktikus hiba: értelmezés esetén jelentkezik a hiba

végrehajtási hiba: hibafigyelő rendszer által jelzett hiba (túlcsordulás, 0-val osztás)

végtelen ciklus

kiíratás nem megfelelő időben, nem megfelelő módon

hibás eredmény

Hibakeresés elvei:

programszövegben logikai hiba keresés

hiba javítás után az ebből következő hibák javítása

hibák száma és súlyossága a program méretével rohamosan növekszik

Hibajavítás alapelvei:

hibát kell javítani nem a tüneteket

hibajavítás után a tesztelés újra kezdése

annak valószínűsége, hogy a hibát jól kijavítottuk a program méretével arányosan csökken

a hibajavítás a program tervezési fázisáig visszanyúlhat

Hibakeresési módszerek:

indukció: jó és rossz esetek szétválasztása

dedukció: hibahelyek szűkítése

visszalépéses technika: hátulról haladunk visszafelé

Hibakeresési eszközök:

adatkiíratás

nyomkövetés

töréspontok

lépésenkénti végrehajtás

hiba helyének és okának kijelzése

állapotellenőrzés

DOKUMENTÁLÁS:

1. Fejlesztői dokumentáció: a programot esetlegesen továbbfejlesztő szakemberek részére készül

részei:

specifikáció, követelményanalízis

algoritmusok, és adatok leírása

választott programnyelv és annak verziószáma

programkód

tesztesetek

hatékonysági mérések

környezet leírás

fejlesztési lehetőségek

készítő adatai

2. Felhasználói dokumentáció: laikus felhasználók részére készül

részei:

rövid illetve részletes leírás

környezetleírás

használati leírás

mintaalkalmazás

hibaüzenetek és hibák esetleges okai

3. Programismertető: figyelemfelkeltés, reklám

a feladat és a program rövid leírása

minimális hardver és szoftver környezet

4. Installálási-, operátori kézikönyv: nagyobb programok esetén van jelentősége

A dokumentáció tulajdonságai:

se túl rövid, se túl hosszú

világosan tagolt

tömör, olvasható, pontos

van benne tartalomjegyzék

stílusa reklámszerű

18. tétel: A feladatreprezentáció állapotéren: A gráfreprezentáció. A megoldás vezérlési stratégiái. A visszalépéses keresés. A gráfkereső algoritmusok osztályai. Neminformált gráfkeresés (mélységi, szélességi, egyenletes). Heurisztikus gráfkereséséek (A, A*, monoton megszorításos)

Def: A mesterséges intelligencia célja olyan feladatok számítógépes megoldása, amelyek megoldásához intelligenciára van szükség.

Állapottér-reprezentáció: Azt az (A,M,s,T) négyest értjük rajta, ahol

A: lehetséges állapotok halmaza, M: Műveletek halmaza A->A

s: kezdőállapot (eleme A-nak), T: célállapotok halmaza (eleme A-nak)

Egy feladat megoldásán egy olyan műveletsorozatot értünk, amely a kezdőállapotból elvezet egy célállapotba.

Egy feladat optimális megoldásán a legkisebb költségű (legrövidebb) műveletsorozatot értjük. Az MI területén általában ezt tűzzük ki célul.

Vannak feladatok, amikor a célállapot előállítása a cél (4 királynő probléma) vannak esetek, amikor a célállapot ismert, csak az odavezető utat kell megkeresni.

GRÁFREPREZENTÁCIÓ: Az az (R,s,T) hármas, ahol R=(N,A) irányított gráf, ahol N a csúcsok halmaza, A az élek halmaza, s a startcsúcs, és T a célcsúcsok halmaza. A csúcsok állapotokat, az élek a műveleteket reprezentálják. δ-gráf: minden él hossza nagyobb δ-nál, és véges sok él indul ki minden csúcsból. Ez a tulajdonság biztosítja, hogy ha létezik út a startcsúcsból a célcsúcsok valamelyikébe, akkor létezik minimális költségű út is.

Produkciós vagy kereső rendszer: MI feladatok megoldásánál használt algoritmusosztály részei:

globális adatbázis: részgráf, amit már felderítettünk a gráfból

produkciós szabályok: műveletek a globális adatbázis elemein

kezdő adatbázis: startcsúcs

terminálási feltételek: célcsúcsok halmaza

vezérlési stratégiák: feladata az alkalmazásra kerülő szabály kiválasztása

fajtái: előrehaladó, visszafelé haladó, kétirányú

produkciós rendszer általános algoritmusa:

ADAT = kezdő adatbázis

ciklus amíg ADAT <> terminálási feltételek

választ szabályt a produkciós szabályokból : R

R(ADAT) (alkalmazom a szabályt)

ciklus vége

eljárás vége

heurisztika megadja, hogy milyen szabály alapján válasszunk a produkciós szabályok közül.

tulajdonságok:

lehetőleg az optimális megoldás megtalálása

algoritmus hatékonyság javítása

Megjegyzés: a nagyon erős heurisztika segít, hogy minél kevesebbet kellje próbálkozni, azonban lassítja a programot azzal, hogy ki kell gondolni melyikkel próbálkozzon. (pl. sakkprogram nagyon jókat lép, de lassan)

VEZÉRLÉSI STRATÉGIÁK:

csoportjai:

Nem módosítható vezérlési stratégiák: keresés közben egy már alkalmazott szabály visszavonására, azaz visszalépésre már nincs lehetőség.

Módosítható vezérlési stratégiák: ha egy alkalmazott szabály később helytelennek bizonyul, akkor lehetséges a visszalépés.

visszalépéses: 1 út van nyilvántartva, amin éppen haladunk, és onnan visszalépésekkel juthatunk el másik útra.

gráfkereső: egyszerre több út van nyilvántartva és a legkedvezőbbnek tűnőn haladunk tovább

heurisztika szempontjából csoportosítva: neminformált / heurisztikus

Nem módosítható vezérlési stratégiák:

A produkciós szabály alkalmazása visszavonhatatlan lépést jelent.

pl. Gradiens módszer: Leggyakrabban használt nem módosítható vezérlési stratégia, főleg függvények maximumának keresésére alkalmas. Lényege, hogy mindig azt a produkciós szabályt alkalmazza, amely a legnagyobb növekedéssel jár a függvényértékére vonatkozóan.

globális adatbázis: egy csúcs, az utolsó

produkciós szabályok: a csúcsból kiinduló élek

kezdő adatbázis: startcsúcs

terminálási feltételek: aktuális csúcs egy célcsúcs

vezérlési stratégiák: semmi nincs előírva (gradiens módszernél: a legnagyobb növekedést okozó)

Visszalépéses vezérélési stratégiák:

globális adatbázis: egy út, amelyben benne van a startcsúcs

produkciós szabályok: a globális ab.-ban található utat eggyel megnövelő, vagy eggyel lecsökkentő szabályok

kezdő adatbázis: startcsúcs, 0 hosszú út

terminálási feltételek: egy célcsúcs kerül az út végére, vagy visszajutunk a startcsúcshoz, és nincs hova tovább lépni

vezérlési stratégiák: mindent megnézek, ha nincs cél, akkor visszalépek. Ugyanazon csúcsba nem megyek kétszer.

visszalépés feltételei:

zsákutca (nincs tovább út)

adott csúcspontból már minden kivezető élet megvizsgáltunk

a meg nem vizsgált élekről látjuk, hogy nem vezetnek megoldáshoz (pl. vágások)

mélységi korlát elérése (mélységi korlát: d(s)=0, ha s a startcsúcs, d(m)=d(n)+1, ha n szülője m-nek)

körbe lépés esetén: az adott csúcsban már jártunk

előny: Körmentes gráfon mindig terminál, Kis memóriaigényű.

hátrány: Magas szinten hozott kedvezőtlen döntés, sok felesleges lépést okoz, nem feltétlenül az optimális megoldást találja meg

Gráf kereső vezérlési stratégia:

globális adatbázis: G kereső gráf. Minden felderített csúcs

produkciós szabályok: Γ kiterjesztések

kezdő adatbázis: startcsúcs

terminálási feltételek: aktuális csúcs egy célcsúcs, vagy NYILT(a még ki nem terjesztett csúcsok) halmaz üres

vezérlési stratégiák: semmi nincs előírva (kiértékelő függvények választanak a NYILT halmazból)

feszítő fa: Ha egy csúcshoz csak mindig a legrövidebb utat tartjuk nyilván. (visszafelé mutató pointerek)

költség függvény: (g(n)) az adott csúcshoz vezető legrövidebb utat megadó függvény. Amennyiben új csúcs g(n) értékéről van szó, az könnyen megkapható az új él és a már ismert csúcshoz vezető út összegéből. Azonban, ha már felderített csúcs g(n) értékét kell meghatározni, akkor meg kell vizsgálni, hogy kisebb értéket kaptunk-e az eddig ismertnél, ha igen, akkor az új csúcs őseire vonatkozóan is át kell állítani a költségeket, és a mutatókat.

kiértékelő függvény: kiterjesztésre választja ki a megfelelő csúcsot. Mindig a minimális kiértékelő függvény értékű csúcsot terjesztjük ki. jel: f(n)

Nem informált gráfkereső eljárások: (nincs heurisztika)

mélységi keresés: Itt a kiértékelő függvény mindig olyan csúcsot választ ki kiterjesztésre, amely a keresőfában a legmélyebben fekszik. f(n)=-d(n)

Tétel: mindig talál megoldást, ha van

szélességi keresés: Mindig a legmagasabban fekvő csúcsok közül választ ki egyet kiterjesztésre. Így egy szintet mindig kiterjeszt teljesen mielőtt tovább lépne. f(n)=d(n)

Tétel: mindig megtalálja az ideális megoldást, ha van megoldás

egyenletes keresés: mindig olyan csúcsot terjeszt ki amelyikhez vezető út a feszítőfában a legkisebb költségű.
f(n)=g(n).

Tétel: mindig megtalálja az ideális megoldást, ha van megoldás

Heurisztikus gráfkereső algoritmusok: Ezekben az algoritmusokban nem az csúcsok előélete játszik szerepet, mint a nem informált algoritmusok esetében, hanem az előrelátható út költsége is.

fogalmak: h*(n): a reprezentációs gráf tetszőleges n csúcsából egy célcsúcs eléréséhez szükséges út költsége.

h(n): a h*(n) függvény becslő függvénye

előretekintő keresés: Mindig olyan csúcsot terjeszt ki, amelyből várhatóan a legkisebb költséggel lehet célcsúcsba érni. f(n)=h(n)

Az algoritmus gyors, de nem biztos, hogy terminál, ha van megoldás.

Az A algoritmus: Olyan csúcsot választ ki kiterjesztésre, amelynek a várható összköltsége a minimális, azaz f(n)=g(n)+h(n)

Tétel: mindig talál megoldást, ha van megoldás

Az A* algoritmus: Olyan algoritmus, amelynek a heurisztikus függvénye mindig alulról becsüli a hátralévő út költségét. (h(n)<h*(n))

Tétel: mindig megtalálja az ideális megoldást, ha van megoldás

Ha egy A algoritmus heurisztikus függvénye bármelyik él mentén legfeljebb az él költségével csökken, akkor az algoritmust következetesnek vagy monoton megszorításosnak nevezzük. h(n)-h(m)<c(n,m)

Tétel: a monoton megszorításos algoritmus minden csúcsot legfeljebb egyszer terjeszt ki, és mindig az optimális megoldást találja meg, ha létezik.

10. tétel: Az informatika tantárgy felépítése az ismeretkörök alapján

Alapvető tananyag felépítési stratégiák és ezek alkalmazhatósága az informatikaoktatásban

lineáris: ismeretkörök valamilyen egymásutánját feltételezi, különböző tanévekhez különböző ismeretköröket rendel.

ciklikus: ismétlődő, azt feltételezi, hogy a főbb ismeretkörök valamilyen szinten már a tárgy alsóbb tanítási éveiben megjelentek és ezek a következő tanévekben fokozatosan mélyülnek.

A lineáris felépítés az informatika oktatásában nem alkalmazható jól, ezért érdemes a ciklikus módszert választani. Az egyes ismeretköröket nem azonos súllyal kell tanítani.

A tantárgy tanéven belüli felépítésének kérdése:

tartós ismeret: Az ismeretkör anyaga nagy blokkokban, folyamatosan tanítható (Algoritmizálás, adatmodellezés, programozási ismeretek illetve az Alkalmazói feladatok megoldása kész rendszerekkel ismeretkörök, amelyek akár váltakozva is előkerülhetnek az oktatás során)

rövid ismeret: 1-2 órás blokkban tanítható anyagrész (pl. szoftver-hardver eszközök működése, informatika matematikája, az informatika eszközei, ellenpélda: fél év DOS tanítás)

nagyon rövid ismeret: 5-10 perces órarészekben tanítható anyagrész (informatika történet, etikai kérdések, informatika és a társadalom témakör egész órán át unalmas lehet, de egy-egy rövid történet a tananyag közben még akár üdítő is lehet)

Két ismeretkör nem szerepelt a fenti felsorolásban, mivel ezek 16 éves életkorig nem ajánlottak: Programozás eszközei, Alkalmazói rendszerek.

Az informatika tantárgy utolsó két évében érdemes speciális oktatást tervezni.

Számítástechnikai szakmai vizsga letétele (bizonyítvány szerzése)

matematikus, programozó, műszaki továbbtanulóknak a programozási ismeretek kibővítése

tovább nem tanulók részére szakképesítés:

intelligens titkárnő (gépírás, levelezés, szövegszerkesztés, táblázatkezelés)

oktatás technikus (informatikai eszközök kezelése)

utazásszervező (Internet, levelezés, kiadványszerkesztés)

kiadványszerkesztő (Internet, grafika, nyomdai ismeretek)

speciális informatikai ismereteket igénylő szakközépiskolák:

műszaki (AUTOCAD)

közgazdasági, pénzügyi (EXCEL, könyvelő szoftverek)

egészségügyi (nyilvántartó programok)

Az informatika kialakításának szempontjai:

tanítható:

legyen hozzá tanár

feleljen meg az életkori sajátosságoknak

ne okozzon túlterhelést

tanulható:

ne legyen sok a lexikális ismeret

inkább gondolkodásfejlesztő, problémamegoldó gondolkodásra serkentsen

gyakorlatorientált:

ne legyen túlzottan elméleti

ne legyen játszadozás sem

önálló munkára ösztönözzön:

számonkérhető:

tudja a diák felmérni, hogy mennyi a tudása

érdekes

INFORMATIKA ÁLLAMVIZSGA

.

2002-06-08T09:26:00

Peter Szamoskozi