[[oktatas:programozás:programozás_elmélet|< Programozás elmélet]] ====== Programozás elmélet tananyag ====== * **Szerző:** Sallai András * Copyright (c) 2011, Sallai András * Szerkesztve: 2011, 2013, 2014, 2017 * Licenc: [[https://creativecommons.org/licenses/by-sa/4.0/|CC BY-SA 4.0]] * Web: https://szit.hu ===== Bevezetés ===== A programozás során felmerülő, nyelvtől független elméleti témák. A leírás jegyzet jellegű. Minden visszajelzést szívesen várok. A programozás egy olyan művészet, ahol folyamatosan megfogjuk a kódot és átgyúrjuk újra és újra. ===== A programozásról ===== ==== Fogalmak ==== Mit értünk programozás alatt? Hétköznapi és speciális feladatok modellezése a számítógépen. Cél: Célunk új program létrehozása, illetve a meglévők továbbfejlesztése. Mik a programozás eszközei? Folyamatleíró eszközök, fordítók, interpreterek és mesterséges programozási nyelvek, szerkesztők, hibakövetők. A következő ábrán jól látszik, hogy a nyelveknek két csoportja határozható meg. A természetese nyelvek és a mesterséges nyelvek. {{:oktatas:programozas:programozas_elmelet:programozasi-nyelvek.jpg|}} A mesterséges nyelvek feloszthatók formális és kommunikációra szánt nyelvre. Mi ebből a formális nyelvekkel foglalkozunk, az ábrán nem is bejelölve a kommunikációra szánt mesterséges nyelv. A formális mesterséges nyelvek közül nekünk a programozási nyelvek szükségesek egy program megíráshoz. A fejlettebb programok, ha adatbázishoz férnek hozzá, akkor azok használnak lekérdező nyelvet is, de ez már egy messzire mutató témakör. ==== Programozás szakaszai ==== Egy program elkészítésének menete hét elkülöníthető részre osztható, amelyet az alábbiakban láthatunk: * elemzés (analízis) * tervezés * kódolás * tesztelés * dokumentálás * terjesztés * karbantartás A következő fejezetekben ezeket a szakaszokat részletezzük. ==== Gyakorlat ==== * Mi a programozás? * Milyen szakaszokra osztható a programozás? * Hogyan csoportosíthatjuk a nyelveket? * Milyen eszközei vannak a programozásnak? ===== Elemzési szakasz ===== Mielőtt neki fogunk a program megírásához, illetve annak megtervezéséhez, meg kell vizsgálnunk a feladattal kapcsolatban néhány dolgot. Ezt a tevékenységet nevezzük elemzési szakasznak. Az elemzés során többféle felmérést végzünk. Megnézzük modellezhető-e a probléma számítógépen. Ha igen, milyen eszközök alkalmasak a megoldásra. Vannak-e esetleg más, már meglévő megoldások. A feltárt információkat dokumentáljuk. Az elemzési szakasz része, az bemenő és kimenő adatok meghatározása. A következő szempontok alapján vizsgáljuk az adatokat: * Bemenő adatok * típusok * mennyiségek * bevitel befejezése * feltételek * adatok közötti kapcsolatok * Kimenő adatok * típus * megjelenítendő * tárolandó ===== Tervezési szakasz ===== ==== A tervezési szakaszról ==== A tervezési szakaszban fokozatosan elemeire bontjuk a problémát, meghatározzuk a megoldás algoritmusát. Egy feladatot több kisebb egységre osztunk fel. Maximálisan annyi egységre osztjuk fel amit még képesek vagyunk átlátni. Van aki ezt maximálisan 7 egységben adja meg, van aki 30. Maximálisan 10 egységre való felbontást ajánlom. A felbontott egységeket újabb egységekre bonthatjuk. Eldöntjük milyen programozási nyelvet választunk. ==== Algoritmus ==== Az algoritmus egyértelműen előírt módon és sorrendben végrehajtandó tevékenységek véges sorozata Az algoritmusról tehát elmondhatjuk, hogy véges számú lépesben kell végrehajtani. Kapunk valamilyen eredményt. Az egyes lépések egyértelműek. Azonos jellegű feladatokra is használható. Determinisztikus, vagyis ugyanazokra a bemenő adatokra, ugyanazokat a kimenő adatokat kapjuk. A programok algoritmusokból állnak. Az algoritmusok tulajdonképpen matematikai minták. Az algoritmus szót egy arabul író perzsa tudós és matematikus nevéhez fűzzük: Abu Abdalláh Muhammad ibn Músza al-Hvárizmi (780 – 845), aki kidolgozta a matematikai algoritmus fogalmát. Az algoritmus szó tulajdonképpen az al-Hvárizmi név rossz fordítása. Az algoritmusok egyes lépéseit tevékenységként szoktuk emlegetni. A tevékenységet a következő ábra alapján osztályozhatjuk. {{:oktatas:programozas:programozas_elmelet:programozas-tevekenysegek.jpg|}} A szekvenciális tevékenység, az amikor egymás után hajtunk végre utasításokat. A szelekciós tevékenység estén bizonyos utasítások végrehajtását feltételhez kötjük. Ha feltétel teljesül, akkor végrehajtjuk az utasításhalmazt, ha nem akkor nem csinálunk semmit, vagy egy másik utasításhalmazt hajtunk végre. A szelekciós tevékenységet szokás még "elágazás" vagy "döntés" néven emlegetni. Az iteráció, másként ciklus vagy ismétlés. Egy adott lépést többször szeretnénk végrehajtani. A iterációk osztályozása: ^ Iteráció (ciklus) ^^ ^ Növekményes \\ (számláló; számláló-vezérelt; léptető) ^ Amíg típusú \\ (tesztelő; feltételes) ^ | Tudjuk hányszor ismétlünk | Nem tudjuk hányszor ismétlünk | Osztályozás másként: ^ Iteráció (ciklus; ismétlés) ^^ ^ Elől tesztelő ^ Hátul tesztelő ^ | előbb tesztelünk \\ utána hajtjuk végre az \\ utasításokat | egyszer végrehajtjuk az \\ utasításokat és csak utána \\ tesztelünk | | előbb tájékozódunk kell-e még\\ dolgoznunk ha igen, \\ dolgozunk \\ utána megint megnézzük | előbb dolgozunk, utána \\ tájékozódunk, kell-e még | A ciklus két részből áll: * ciklusmag - utasítások sorozata * vezérlő feltétel - valamilyen logikai kifejezés ==== Az utasítások szintjei ==== {{:oktatas:programozas:programozas_elmelet:utasitasok_szintjei.png|}} ==== Vezérlőtevékenységek ==== {{:oktatas:programozas:programozas_elmelet:vezerlotevekenysegek_konyhanyelven.png|}} ==== Algoritmizálás eszközei ==== Az algoritmizáláshoz használható eszközök felsorolását, az alábbiakban láthatjuk: * mondatszerű leírás * pszeudokód * folyamatábra * struktogram * Jackson-ábra A következő részekben, ezeket részletezzük. ==== Mondatszerű leírás ==== Röviden fogalmazva: Szövegesen leírom az algoritmust. Nincs megkötés, egyszerűen a saját nyelvemen leírom a tevékenység egyes lépéseit. Arra azonban ügyeljünk, hogy a tevékenységrészek egymástól jól elkülöníthetők legyenek, és egyértelműek. === Szekvenciális tevékenység === 2 szám összeadása: Program indul Bekérünk egy számot Bekérünk egy másik számot Összeadjuk az első és második számot, majd eltároljuk egy harmadik helyen Kiírjuk a harmadik hely értékét Program vége === Szelekciós tevékenység === Kisebb vagy nagyobb mint 10: Program indul Bekérünk egy számot A-ba Ha az "A" nagyobb akkor a következőt tesszük: Kiírjuk: „nagyobb” ellenkező esetben a következőt tesszük: Kiírjuk: „kisebb” Ha vége Program vége === Iterációs tevékenység === Összeadás 0 végjelig: Program indul A legyen egyenlő 1-gyel B legyen egyenlő 0-l ismétlés amíg A nem egyenlő 0-l bekérünk A helyre egy új számot Az A értékét B-hez adjuk, majd az összeget B-ben tároljuk ismétlés vége Kiírjuk B értékét Program vége === Iterációs tevékenység hátul tesztelve === Összeadás 0 végjelig: Program indul A legyen egyenlő 1-gyel B legyen egyenlő 0-l csináld bekérünk A helyre egy új számot Az A értékét B-hez adjuk, majd az összeget B-ben tároljuk ismétlés amíg A nem egyenlő 0 értékkel Kiírjuk B értékét Program vége ==== Pszeudokód ==== A pszeudokód esetén már nincs ilyen nagy szabadságunk. Mindig meg kell határoznunk, milyen utasításokat használunk. Létre kell hoznunk egy alap utasítás-, operátorlistát, ahol leírjuk, hogyan nézhetnek ki az egyes utasítások. Például: | a = 3 | értékadás | | ki a | változó kiíratás a képernyőre | | ki "szilva" | szöveg kiíratása a képernyőre | | be a | egy érték bekérése "a" változóba | | ha a < 100 \\ utasítás \\ ha vége | feltétel | | ciklus i = 1..5 \\ utasítások \\ ciklus vége | növekményes ciklus | | ciklus amíg a < 100 \\ utasítások \\ ciklus vége | elöl tesztelő amíg típusú ciklus | | ciklus \\ utasítások \\ ciklus amíg a < 100 | hátul tesztelő ciklus | | = | legyen egyenlő | | <> | nem egyenlő | | == | egyenlőség vizsgálat | | * | szorzás | | / | osztás | ||... | === Szekvenciális tevékenység === 2 szám összeadása: Start Be A Be B C = B + A Ki B Stop === Szelekciós tevékenység === Kisebb vagy nagyobb mint 10: Start Be A Ha A>10 akkor Ki „nagyobb” ellenben Ki „kisebb” Ha vége Stop === Iterációs tevékenység === Összeadás 0 végjelig: Start A=1 B=0 ismétlés (A <> 0) bekér A B=B+A ismétlés vége Kiír B Stop === Iterációs tevékenység hátul tesztelve === Összeadás 0 végjelig: Start A=1 B=0 csináld bekér A B=B+A ismétlés (A <> 0) Kiír B Stop ==== Folyamatábra ==== A folyamatábra még néhány ismert magyar és angol elnevezése: * blokkdiagram * végrehajtási gráf * Control Flow Graph (CFG) * flowchart [floucsát] A folyamatábra alakzatai: {{:oktatas:programozas:programozas_elmelet:folyamatabra-alakzatai.jpg|}} A folyamatábra alakzatainak felhasználása: {{:oktatas:programozas:programozas_elmelet:folyamatabra-alakzathasznalat.jpg|}} === Szekvenciális tevékenység === 2 szám összeadása: {{:oktatas:programozas:programozas_elmelet:folyamatabra-szekvencia.jpg|}} === Szelekciós tevékenység === Kisebb vagy nagyobb mint 10: {{:oktatas:programozas:programozas_elmelet:folyamatabra-szelekcio.jpg|}} === Iterációs tevékenység === Összeadás 0 végjelig: {{:oktatas:programozas:programozas_elmelet:folyamatabra-iteracio.jpg|}} === Alternatív alakzatok a folyamatábrákban === {{:oktatas:programozas:programozas_elmelet:folyamatabar-alakzat-alternativ.png|}} {{:oktatas:programozas:programozas_elmelet:folyamatabara-alternativalakzat2.png|}} === Folyamatábra példák === {{:oktatas:programozas:programozas_elmelet:folyamatabra_tovabbkepzes-folyamatabraja.png?500|}} {{:oktatas:programozas:programozas_elmelet:folyamatabar_minta_szakdolgozatkeszites-folyamatabraja.png?400|}} === Rekurzió folyamatábrával === {{:oktatas:programozas:programozas_elmelet:folyamatabrarekurzio.png|}} ==== Struktogram ==== A struktogram grafikus alapú algoritmus-ábrázolási módszer. 1972-ben **Isaac Nassi** és **Ben Shneiderman** tette először közzé. Nevük után Nassi-Shneiderman (NSD) ábra néven is ismert. 1974-ben **Chapin** is közé tette ezért chapin ábra (chapin chart) néven is ismert. Magyarországra a struktogram szó a német struktogramm szóból eredeztethető, amelyet struktúradiagramm néven szokás fordítani. Angol nyelvterületen inkább Nassi-Shneiderman diagram néven használják. Ha magyarosabban szeretnénk leírni, akkor talán a szerkezetrajz lenne a legjobb. Az oktatásban a struktogram szót használják. A leírása sajnos nem egységes. Egyesek "r" nélkül írják, mások két "m"-el a végén. A helyesírás ellenőrzők a három közül egyiket sem fogadják el. Felszokott még merülni a blokk diagram, de ezt nevet használják a folyamatábra jelölésére is. A struktogramban a folyamatok leírására téglalapot használunk. Van, aki a folyamatábrában szokásos ellipszissel jelöli a folyamat kezdetét, de ez nem elterjedted. Ellentétben a folyamatábrával, itt nem is szükséges jelölni, hogy hol kezdődnek a tevékenységek, mivel egyértelműen mindig felülről megyünk lefele. {{:oktatas:programozas:programozas_elmelet:struktogram01.png|}} === Szekvenciális tevékenység === Ez a legegyszerűbb, mert az egyes tevékenységeket egyszerűen felsorolom egymás alá. A következő ábrán erre látunk egy általános bemutatót. {{:oktatas:programozas:programozas_elmelet:struktogram02.png|}} === Szelekciós tevékenység === A szelekció esetében már feltételek is vannak, amit el kell helyeznünk valahol a téglalapban. Figyeljük meg a következő ábrát. {{:oktatas:programozas:programozas_elmelet:struktogram03_2.png|}} Jobbra fent egy kétágú szelekciót látunk, balra lent egy többágút. Egyes helyeken egyágú szelekciót ábrázolnak, csak éppen ezek használhatatlanok, mert a valóságban ilyen nincs. Attól ugyanis, hogy az egyik ágban nem csinálok semmit, attól még két választásom van, ezért kétágú szelekció. Az egyágú szelekció tulajdonképpen ellentmondásos kifejezés. Ha szelektálunk, akkor már egynél több ág van, legalább kettő. === Iterációs tevékenység === {{:oktatas:programozas:programozas_elmelet:struktogram04.png|}} === Szekvenciális tevékenység példa === Két szám összeadása: {{:oktatas:programozas:programozas_elmelet:struktogram05.png|}} === Szelekciós tevékenység példa === Kisebb vagy nagyobb mint 10 {{:oktatas:programozas:programozas_elmelet:struktogram06.png|}} === Iterációs tevékenység példa === Összeadás 0 végjelig: {{:oktatas:programozas:programozas_elmelet:struktogram07.png|}} ==== Jackson ábra ==== A Jackson ábrát Michael Anthony Jackson brit számítógéptudós találta ki, a nevét is róla kapta. Struktúra diagram néven is ismert, mivel egy program struktúráját ábrázoljuk vele. === Szekvenciális tevékenység === Szekvencia esetén a tevékenységeket mindig balról jobbra bontjuk ki. {{:oktatas:programozas:programozas_elmelet:jackson_szekvencia.png|}} === Szelekciós tevékenység === {{:oktatas:programozas:programozas_elmelet:jackson_szelekcio.png|}} === Iterációs tevékenység === {{:oktatas:programozas:programozas_elmelet:jackson_iteracio.png|}} ==== Programtervezési stratégiák ==== === Felülről lefele (top-down) tervezés === Lépésenként finomítjuk a programot. A programot előbb nagyobb egységere bontjuk, majd minden lépést finomítunk. Előnye: * A belső megoldások elrejthetők * Nem lehet hibázni === Alulról felfelé (down-top) tervezés === Téglánkénti építkezés elve. A legegyszerűbből kiindulva egyre bonyolultabb megoldást hozunk létre. Látszólagos előnyei: * Ugyanazt az elemet több helyen felhasználhatjuk. * Ha mégis hiányzik valami, még utólag meg lehet tervezni. ==== Gyakorlat ==== * Mit jelent a programozásban az elemzési szakasz? * Mi az algoritmius? * Milyen szakaszai vannak a programozásnak? * Mire jó folyamatábra? * Mi a különbség a mondatszerű leírás és a pszeudókód között? * Mik a programozás alaptevékenységei? * Mik a programozásban a vezérlőtevékenységek? * Magas szintű nyelveken nem ajánlott az ugróutasítás használata. Miért? * Milyen alakzattal ábrázoljuk a szelekció feltételét? ===== Kódolási szakasz ===== A kódolás számítógép számára érthető utasítások létrehozása. - Megfogalmazzuk a programot valamilyen programozási nyelven. - Gépi utasításokra fordítjuk a kódot. - Futtatjuk a kódot. ==== Programozói környezet ==== | Szövegszerkesztő | Fordító (compiler) | Összeszerkesztő (linker) | hibakövető (debugger) | | Programozói könyvtárak |||| | Operációs Rendszer |||| ==== IDE ==== Integrált Development Environment azaz IDE, magyarul Integrált Fejlesztői Környezet. Ez általában egy olyan speciális szövegszerkesztő, amely képes egyben a fordításra, összeszerkesztésre, hibakövetésre, esetleg sok más kényelmi szolgáltatást nyújt. ==== Vizuális Fejlesztőeszköz ==== Általában GUI (grafikus felhasználó felület) tervezésénél használható tervező eszköz, ahol a kinézetet nem a forráskódban állítjuk elő, hanem egér húzzással kattintással egy vizuális felületen. ==== Programozói könyvtárak ==== Előre elkészített programokban felhasználható komponensek. Úgy is mondhatnánk előre megírt utasítások, megvalósítások. ==== Debugger ==== Egy program, amelyet hibakövetésre, a szemantikai hibák felderítésére találtak ki. ^ Néhány debugger ^^ ^ Környezet ^ Debugger ^ | GCC | gdb | | Java | jdb | ==== Program ==== Utasítások sorozata a számítógép számára. Olyan mint a recept és a szakács. A recept utasítások sorozata, amit a szakács végrehajt. ==== Gépi kód ==== A gép számára végrehajtható utasítások sorozata. Ez az az eset, amikor a recept például magyarul íródott és a szakács is beszéli. A programozó ma már nem gépi kódban írja a programjait a kényelem előtérbe helyezése miatt. A programozó által használt nyelvet így le kell fordítani még gépi kódra. Ez az az eset, amikor a recept például kínai nyelven íródott, a szakács viszont csak magyarul tud. Valakinek le kell fordítani. A gépi kód elemi utasításokból áll, amelyek binárisan vannak kódolva, azaz 1 és 0-k sorozatából áll. ==== A program szó használata ==== === Szűkebb értelemben === Csak a gépi kód. === Tágabb értelemben === A gépi kód és a programozási nyelvben megfogalmazott utasítások. ==== A kódolás menete ==== * nyelv választás * gépelés (az algoritmus kódolása) * szintaktikai hibák javítása * futtatás * szemantikai hibák javítása (tesztelés) {{:oktatas:programozas:programozas_elmelet:kodolas01.png|}} ==== Ábécé ==== A nyelv jelkészlete A nyelvben használt betűk, számok, karakterek ==== Szintaxis ==== A mondatalkotási szabályok ==== Szemantika ==== Az a mód, ahogyan az utasításokhoz jelentést rendelünk ==== Hivatkozási nyelv ==== Egy magas szintű nyelv definíciója, leírása. A definíció általában szabvány. Nem konkrét megvalósítás. ==== Nyelv implementációja ==== Egy nyelv megvalósítása, bármilyen rendszerben. A hivatkozási nyelvvel nem szokott teljesen kompatibilis lenni. ==== Mi lehet programozási nyelv? ==== Bármilyen mesterséges nyelv, amely megfelelő eszközökkel rendelkezik az adatszerkezetek és az azokat kezelő, átalakító eljárások egyértelmű leírására. Programozási nyelvek mellett követelmény: * fordító vagy értelmező {{:oktatas:programozas:programozas_elmelet:kodolas02.png|}} ==== Alacsony szintű nyelvek ==== Gépközeli nyelvek Például: gépi kód, assembly ==== Magasszintű nyelvek ==== Hasonlítanak az emberi gondolkodásra, nagyobb az elvonatkoztatás (absztrakció) mértéke. Az nagyobb elvonatkoztatás következménye a platformfüggetlenség. Egy ilyen magas szintű nyelv létrehozásának célja a könnyebb és gyorsabb kódolás. Ha például a képernyőre akarok írni egy szöveget, nem kell nekem azt 4,5 vagy akár több utasítással megtennem, helyette egyetlen utasítást kell kiadnom. {{:oktatas:programozas:programozas_elmelet:kodolas03.png|}} ==== Imperatív nyelvek ==== * Utasításszerkezetűek * alapeszközei az utasítások és a * változók * minden utasítás mögött gépi kód áll * algoritmikus nyelvek * azt az algoritmust írom le, amelyet a gép végrehajt * a program a hatását a memóriában elhelyezett értékeken hajtja végre ==== Imperatív nyelvek osztályozása ==== ^ Eljárás orientált ^ Objektum orientált ^ | Fortran | C++ | | Cobol | Java | | C | Simula67 | | Ada | Eiffel | | Pascal | Smalltalk | | PL/1 | C# | | Algol60 | Az eljárás orientált nyelvek között vannak persze olyanok amelyeknek van objektum orientált megvalósításuk. Ilyen a C és Pascal nyelv. ==== Deklaratív nyelvek ==== * nem algoritmikusak * csak a problémát fogalmazzuk meg, a megoldást nem * nincs utasítás * az algoritmikus nyelvbe van építve * a programozó a memória értékeivel nem dolgozik ==== Deklaratív nyelvek osztályozása ==== ^ Funkcionális nyelvek ^ Logikai nyelvek ^ | Lisp | Prolog | ==== Lisp ==== Rekurzív függvények absztrakt ábrázolására tervezték. ==== Prolog ==== Alain Colmerauer fejlesztett ki 1972. A mesterséges intelligencia kutatás előszeretettel alkalmazza. ==== Más elvű nyelvek ==== Nem deklaratív és nem imperatív, azok elveit tagadja. ^ Más elvű nyelvek ^ | Apl | Matematikai problémák megoldására használjuk. ==== Nyelvek osztályozásának összefoglalása ==== {{:oktatas:programozas:programozas_elmelet:kodolas04.png|}} Ha precízebbek akarunk lenni akkor a mesterséges nyelveket feloszthatjuk még formális és beszélt nyelvre. A programozási nyelvek természetesen a formális nyelvekből eredeztethető. ==== A kódolás eszközei ==== * clear text szövegszerkesztő * programozói szövegszerkesztő * fejlesztői környezet * vizuális fejlesztői környezet === clear text szövegszerkesztő === Egy clear text szövegszerkesztő bármely nyelven való programozáshoz jók. Ilyenek lehetnek Windowson a Jegyzettömb, a Notepad2, Notpad++, stb. Linuxon mcedit, nano, gedit, stb. === programozói szövegszerkesztő === Általában olyan szövegszerkesztő, amelyet kifejezetten programozók számára készítettek. Sok olyan funkciót találunk benne, amely megkönnyíti a programok írását. Több platformos, sok nyelvet támogató ilyen szövegszerkesztő például a Scite. A Scite az útvonalba lévő fordítókat, interpreterekt felismeri, így azok azonnal használhatók. A programok fordítás után futtathatók. === Fejlesztői környezet === Általában valamely programozási nyelvhez tartozó olyan program, amely a programozói munkát a lehető legkönnyebbé igyekszik tenni. Általában tartalmaz hibakövető eszközöket. A fordítás és a futtatás néhány kattintással történik. * CodeBlock (C, C++, D, de bármely nyelv integrálható) * Dev-C++ * FreePascal IDE * stb. === Vizuális fejlesztői környezet === A program felületét vizuális eszközökkel tudjuk megtervezni, a felület egyes elemeihez eseményeket tudunk rendelni. * CodeBlock (wxWidget projektel) * MS Visual Studio xxxx * Delphi * Lazarus ==== Programkészítési technikák ==== === Fordító === Egy program készítése és használata három szakaszra osztható - A programot megfogalmazzuk egy programozási nyelven (Ez a forráskód) - Gépi kódú utasításra lefordítjuk - Futtatjuk A program futtatását az operációs rendszer végzi. Az ilyen programot szokás natív kódnak is nevezni. === Értelmező === Az implementált programozási nyelvek egy részéhez nem fordítót készítenek hanem értelmezőt. Az értelmező használata esetén a programot csak a futtatással egy időben fordítjuk le gépkódú utasítok sorozatára. Így magát a forráskódot futtatjuk. Az így előállított program természetéből adódóan lassabban fut, mivel előbb le kell azt fordítani. A program futtatásához kell egy értelemező az operációs rendszerre. === Bájtkód === A bájtkód előállításánál a **fordító** és az **értelmezős** technika **együtt** kerül alkalmazásra. A forráskódot lefordítjuk, de nem gépi kódra. Egy **köztes kódra** fordítjuk, melynek neve **bájtkód**. Ha futtatni akarjuk előbb az értelmezővel fordítjuk gépi kódra, ami elindul. Ez elvileg gyorsabb mint a szimpla értelmezős technika, mivel az eredeti forrást már előfordítottuk. ==== A fordítás lépései ==== A fordítás nem egy meneteben történik. Először egy ún. tárgykódot (objekt fájl) készítünk. Ez Windowsos rendszereken .obj, Linuxos rendszereken .o kiterjesztésű fájlt jelent. Ez után szerkesztővel elkészítjük a futtatható állományt. Ennek haszna több forrásfájlnál mutatkozik meg. Először minden forrásfájlt tárgykódú állománnyá fordítunk, majd ezeket összeszerkesztjük egyetlen futtatható állománnyá. A fordításhoz tehát két programra van szükség: * fordító * szerkesztő A fejlesztői környezetek, és ma már a legtöbb fordító parancs ezt a két műveletet egyben megcsinálja. {{:oktatas:programozas:programozas_elmelet:kodolas05.png|}} ==== Kódszöveg szerkesztése ==== === Karakter === A legelemibb alkotórész. Megjelenései az adott kódtáblától is függ. * Betűk * számjegyek * egyéb karakterek * pl.: * + @ _ # $ === A program lexikális egységei === * azonosítók * fenntartott szavak * címkék * elválasztó jelek * megjegyzések * változók * konstansok ==== Azonosítók ==== A programban saját objektumainknak valamilyen nevet adunk azonosítás céljából. Az azonosítók jellemzői: * betűvel kezdődik * betűvel vagy számmal folytatódhat * saját objektumaink megnevezésére használjuk ==== Fenntartott szavak ==== A nyelvben már valamilyen céllal felhasznált nevek * azonosító jellegű és felépítésű * a nyelv rendel hozzá jelentést * csak az adott célra használhatók ==== Címkék ==== * utasítások azonosítására használható * valahol számmal is kezdődhet * lehet azonosító jellege ==== Elválasztó jelek ==== * régen: egy sorba egy utasítás * szabad formátumú: utasítás szeparátor (elhatároló jelek): ; , : ( ) ==== Megjegyzés ==== A megjegyzések nem a fordítónak vagy az interpreternek szólnak, hanem a programozónak. Saját programjainkat gyakran látjuk el megjegyzésekkel, hogy később gyorsan kiderüljön mit is csinál az adott kód. Példák: PL/1, C, C++, C# /* több soros megjegyzés */ //megjegyzés Pascal { megjegyzés } Shell, Perl # megjegyzés Néhány programozási nyelvben csak egy soros megjegyzések alkalmazhatók, valamelyik több sorosat is megenged. ==== Változó ==== A változók olyan memóriaterületek, amelyeken valamilyen értéket tárolunk, de azok értékét bármikor megváltoztathatjuk. Egy változó felépítése * név * attribútum * cím * érték === Név === Egyedi azonosító === Attribútum === A tárolható érték típusa. Az attribútumok a következő módon határozhatók meg: * explicit deklaráció * programozó végzi * Pl.: char a; vagy var a : char; * C nyelvben * implicit deklaráció * programozó végzi * Pl.: ab Ha a-hoz már rendelve volt egy típus * A Fortran nyelvben van ilyen * automatikus * a fordító határozza meg a típust * Fortran, C nyelvben is van, stb. Lássunk egy példát implicit deklarációra Fortran nyelven. IMPLICIT REAL (c,g) Az állítás hatására, minden c és g betűvel kezdődő változó real. === Cím === A memória címe, ahol a változó van. Címhozzárendelés lehet: * statikus * Futás előtt rendelődik a változóhoz, majd állandó * dinamikus * futási időben kap hozzárendelést * futás közben változhat * a hozzárendelést a futtató rendszer végzi * kézi (programozó végzi) * abszolút * címet a változó nevéhez rendeljük * relatív * címet a változó nevéhez rendeljük, már a memóriában elhelyezett objektum címéhez képest * a futtató rendszert kérjük segítségül A C nyelv mind a hármat ismeri, de hangsúlyt kap a programozó által vezérelt címzés === Érték === * az adott memória helyen elhelyezett szám * a típus megadja, hány byte-on van tárolva ==== Konstansok ==== A konstans szintén egy a memóriában lefoglalt terület egy érték számára. A konstansok esetén a programozó azonban azt vállalja, hogy annak értékét a továbbiakban nem változtatja meg. === Osztályozás === * nevesített konstans * literál konstans === Nevesített konstansok felépítése === * név * típus * érték (címkomponens hiányában nem változtatható meg) === Literál konstansok felépítése === * típus * érték A literálkonstansnak tehát nincs neve. Az értéket egyszerűen leírjuk. A számokat általában önmagában, a karaktersorozatokat általában idézőjelek, vagy aposztrófok között. A literálkonstans önmagát deklarálja. A programba fix értékkel kerülnek. Például: 5 .5 4. "alma" A példa első sora egy egész típusú literális konstanst határoz meg. A második és a harmadik egy valós típusú konstanst. A negyedik egy karaktersorozat típusú konstanst. ==== Gyakorlat ==== * Mit jelent a szemantika? * Mit jelent a szintaktika? * Mi az a gépi kód? * Hogyan osztályozhatjuk a programozási nyelveket? * Hogyan osztályozhatjuk a magas szintű programozási nyelvek? * Mondjon példát deklaratív nyelvre. * Hogy épül fel egy változó? * Mi az a konstans? * Milyen részekből áll egy konstans? * Mi az a hivatkozási nyelv? * Sorolja fel a kódolás eszközeit. * Mit értünk fenntartott szavak alatt? * Mondjon példát a szemantikai hibára. ===== Tesztelési szakasz ===== A tesztelés biztosítja program minőségét. * fehérdobozos tesztelés * feketedobozos tesztelés A fehérdobozos tesztelés azért fehér mert a tesztelő a forráskóddal dolgozik. A feketedobozos tesztelés esetén a tesztelőnek nem áll rendelkezésre a forráskód. Szintaktikai tesztelést már a kódolási szakaszban is végzünk, hiszen e nélkül nem tudnánk továbbhaladni a program lekódolásában. Ugyanakkor tesztelnünk kell folyamatosan szemantikailag is, másként a program működése kétséges lesz. Ha a program elkészült ez után átadjuk a programot olyan felhasználóknak, akiket azért alkalmazunk, hogy teszteljék a programot. Az ilyen állapotban lévő programot szokás béta verziónak nevezni. A béta verziók még nem a végfelhasználók számára készült programok. A tesztelők feljegyzik a talált hibákat, majd elküldik azt a programozóknak. Egy program persze sosem készül el, így ha azt kiadjuk használatra a felhasználók is fognak hibajelzéseket visszaküldeni. {{:oktatas:programozas:programozas_elmelet:teszteles.png|}} ===== Dokumentálás szakasza ===== ==== Mit dokumentálunk? ==== Két fajta dokumentációt szokás készíteni. * fejlesztői * felhasználói ==== Fejlesztői dokumentáció ==== A kódolási szakaszban a programozó írhat megjegyzéseket a forráskódba és ez is a programozói dokumentáció része. Azonban a jó programozó olyan függvény és változó és más azonosító nevekkel dolgozik, amelyek önmagában, mindenféle megjegyzés nélkül olvashatóvá teszik a forráskódot. Ha nem ilyen a forráskódot, akkor valamit újra kell tervezni. A programozók számára készített dokumentáció azonban külön dokumentumok készítését is jelenti. Későbbi továbbfejlesztés esetére dokumentáljuk a programban alkalmazott függvényeket és eljárásokat, azok be és kimenő adatait, a fontos változókat. Leírjuk melyik fájlban mit találunk. Továbbfejlesztés során a dokumentáljuk a változásokat. {{:oktatas:programozas:programozas_elmelet:fejlesztoidokumentacio.png|}} ==== Felhasználói dokumentáció ==== Az adott program használatának leírása, segítség. A program a felületén milyen adatokat vár, mit fog előállítani. Szélső értékek. Hibalehetőségek, korlátozások. A program továbbfejlesztése vagy javítása esetén dokumentáljuk a változásokat, új funkciókat. Ez a változat leírás, angolosan Changelog. A változat leírásban egy dátum, alatt leírjuk a programunk melyik verziónál tart és felsoroljuk milyen változtatásokat hajtottunk végre a programban. A változatleírás egy program életében nagyon fontos, mert a legtöbb végfelhasználó ennek elolvasása után akarja a programunk következő verzióját beszerezni. {{:oktatas:programozas:programozas_elmelet:felhasznaloi_dokumentacio.png|}} ==== Gyakorlat ==== * Milyen dokumentációkat készítünk a programkészítés során? * A változatleírást milyen nevű fájlban szokás elkészíteni? ===== Terjesztés szakasza ===== ==== A terjesztésről ==== A terjesztés előtt át kell gondolnunk milyen engedéllyel szeretnénk terjeszteni az elkészített alkalmazásunkat. Ennek megfelelően meg kell írnunk a terjesztési engedélyt, azaz a licencet. Egyes programozók a licencet magában a programban is elhelyezik, ahol valamely menüpont meghívása után elolvashatjuk. Fontos jeleznünk a program szerzői jogi védelmét. Ennek módja a programban és annak forráskódjában elhelyezett védjegy, amelynek körülbelül így kell kinézni: Copyright (C) Nagy József, 2010 A fenti sorok azt mondják számunkra, hogy azt a művet amihez csatolva ezt olvassuk Nagy József birtokolja a szerzői jogait 2010-től. Választanunk kell egy terjesztési formát. Amely lehet forrás, vagy bináris a licenctől függően. A terjesztett állomány egyszerű tömörített állomány lesz vagy telepítő programba építjük, vagy egy adott operációs rendszer számára telepítőt készítünk. Mivel szoftverről van szó, amit terjeszteni fogunk az egy vagy több állomány lesz, attól függően a programot hogyan írtuk meg. A program kódja mellé minimális követelmény egy licenc nevű fájl, amiben a leírjuk a terjesztés licencét. Szokás még egy readme.txt vagy egy olvasd.txt fájl elhelyezése. Ebben leírhatjuk mit lehet tudni a programról. ==== Szokásos fájlok ==== Állományok terjesztésnél * programállomány vagy állományok * Licenc.txt * Readme.txt * Install.txt * ChangeLog * Todo.txt * Bug.txt A Licenc.txt fájlba értelemszerűen a felhasználás feltételei kerülnek. A Readme.txt fájlba a programról rövidebb, vagy hosszabb leírást adhatunk. Ki készítette, mire jó a program, hol érhető el az Interneten. De használati utasítás is ide kerülhet. Az Install.txt állományban leírjuk hogyan mik a telepítés feltételei, milyen osztott könyvtárak (.dll, .so) szükségesek a futtatáshoz. A ChangeLog fájlba írjuk le a változásokat, a változás dátumával, és mit változtattunk, mit javítottunk. A Todo.txt állományban leírjuk milyen tennivalók vannak még a továbbfejlesztés tekintetében. A Bug.txt fájlba írjuk le az ismert, de még nem javított hibákat. A fájlokat használhatjuk kiterjesztés nélkül is. Esetleg magyarítva. Szoktak például Readme.txt helyett readme vagy README, esetleg magyarosan olvasd.txt, vagy olvasd nevű fájlt használni. A következő példa az kisbetű nagybetű használatban más a fentiekkel szemben: * LICENC * README * INSTALL * TODO * BUG * USING Esetleg magyarosan: * licenc.txt * olvasd.txt * telepites.txt * tennivalo.txt * hibak.txt * hasznalat.txt Nagyobb terjedelmű használati útmutatót, amely több állományból áll célszerű külön könyvtárba tenni, amelyet "doc" néven hozunk létre. Unix alapú rendszerekben a parancsok számára úgynevezett "kézikönyvet" hozunk létre (manual, vagy röviden man). A kézikönyveknek speciális formátuma van, amit itt nem tárgyalunk. ==== Web ==== A program terjedését nagyban segíti egy weblap, amelyről letölthető a program, vagy annak demója, változásokat követhetünk. A weblapon elhelyezhetjük a program dokumentációit, segítséget és támogatást adhatunk a felhasználóknak. Esetleg fórumot hozhatunk létre, ahol a programal kapcsolatos problémákat a felhasználók megvitathatják. A weboldalba építhetünk hibakövető rendszert, vagy nyelvi fordító rendszert. ==== Gyakorlat ==== * Sorolja fel milyen állományokat szokás létrehozni a programállomány mellett, ha terjeszteni szeretnénk egy programot. * Mi a szerepe a Bug.txt fájlnak egy terjesztett program mellett? * Mit tartalmaz a Licenc.txt állomány? * Mit tartalmaz a Readme.txt állomány? * Mit szokás írni a Todo.txt állományba? * Mire használjuk a manualokat? * Írjon példát egy jogi nyilatkozat sorról. ===== Karbantartási szakasz ===== Hibátlan programot készíteni szinte lehetetlen. A jól megírt programok esetén is előjönnek előbb-utóbb hibák. A program élete során változhatnak a bemenő paraméterek. Esetleg más, vagy több kimenő paraméterre van szükség. A programot ilyenkor továbbfejlesztjük, és egy újabb verziószámon adjuk ki. A programozás ezen szakaszának legfontosabb része a változat leírás (ChangeLog) elkészítése, amiről fentebb szó volt. ===== Adatszerkezetek ===== ==== Adattípusok ==== * elemi * Nincs belső szerkezetük * összetett * Elemi adattípusokból épülnek fel ==== Elemi adattípusok ==== * egész * valós * logikai * karakteres ==== Összetett adatszerkezetek ==== * azonos típusból álló (homogén) * különböző típusból álló (heterogén) * alternatív adatszerkezetek ===== Összetett adatszerkezetek ===== * tömb * szöveg * verem (Last In First Out) * sor (First In First Out) * lista * szekvenciális állomány * direkt állomány * rekord * gráf * fa * halmaz Az összetett adatszerkezeteken elvégezhető műveletek * tetszőleges számú elem felhasználása, változtatása * a sorozat első elemének felhasználása, változtatása * a sorozat utolsó elemének felhasználása, változtatása * a sorozat következő elemének felhasználása, változtatása * a sorozat elemszámának meghatározása * új elem felvétel a sorozat elejére * új elem felvétel a sorozat végére * új elem felvétel a sorozat két adott elem közzé * a sorozat első elemének kivétel a sorozatból * a sorozat utolsó elemének kivétel a sorozatból * a sorozat adott elemének kivétel a sorozatból * a sorozat ürességének vizsgálata * a sorozat részhalmazának felhasználása vagy változtatása ==== Összetett adatszerkezetek szerkezet szerinti csoportosítása ==== Homogén adatszerkezetek (homogén) * struktúra nélkül * asszociatív adatszerkezet * szekvenciális adatszerkezet * hierarchikus adatszerkezet * hálós adatszerkezet Heterogén adatszerkezet * rekord ==== Memóriában történő helyfoglalása alapján csoportosítás ==== === Statikus adatszerkezet === * tömb * rekord * halmaz Véges számú adatelemből épül fel. Hosszuk nem változik csak az értékük. === Dinamikus adatszerkezet === * Lista * Fa * Gráf Az adatelemek száma tetszőleges és változhat Ha a dinamikus adatszerkezetek önmagára mutat, akkor rekurzívnak hívjuk. Ha több ilyen hivatkozás is van, akkor "nem lineáris". ==== Listák ==== * Láncolt * Gyűrűs * Kétirányú * Összetett (multi) === Listákról === A programozás során használt adatszerkezet. | fej | -> | elem1 | -> | elem2 | -> | NIL | Adott egy kezdő elem a "fej". Egy mutató mutat az "elem1"-re. Az első elemet egy újabb mutató követi, ami a második "elem2"-re mutat. Ha egy mutató nem mutat sehova (ezt a NIL-el jelezzük), akkor vége a láncnak. A példában egy láncolt listát látunk. A láncot az elemek közötti mutatók biztosítják. Láncolt lista esetén az elemek fizikailag lehetnek egészen más sorrendben, a mutatók biztosítják a számunkra kívánt rendezettséget. Ebből következik, hogy egy láncolt listából könnyebb törölnie egy tömbbel ellentétben, mivel csak át kell állítani a mutatót a törölt elemről, a törölt elem utáni elemre. Gyűrűs lehet egy lista, ha az utolsó elem a kezdőpontba mutat. | | <- <- <- <- <- <- <- <- ||||| | | | ||||| | | | fej | -> | elem1 | -> | elem2 | -> | NIL | A lista kétirányú, ha visszafele is lépkedhetek a listában, mert visszafele is mutat. | fej | <-> | elem1 | <-> | elem2 | <-> | NIL | Hogy egy adatszerkezetben megtaláljak egy elemet, vagy címezhető helyen kell legyen, vagy léteznie kell egy sornak, amelyen végig tudok menni. Ha tehát nem címezhetjük meg egy adott elem helyét, akkor csak úgy tudjuk tárolni, hogy fizikailag egymás után sorba rakom. Láthatjuk, hogy a láncolt lista használata előnyösebb a tömböknél. Ha egy tömb esetén törölünk egy elemet, a tömbben az elem helye ott marad üresen. Egy láncolt listában azonban nincs ilyen problémánk. ==== Fák ==== * bináris * nem bináris * kiegyensúlyozott * kereső === Bináris fa === Ha minden elemének legfeljebb két rákövetkező elem van. Egy bal és egy jobboldali részfa. Bináris fa: {{:oktatas:programozas:programozas_elmelet:binarisfa.png?direct&|}} === Nem bináris fa === Kettőnél több leágazásaik is lehetnek === Kiegyensúlyozott fa === Ha minden szintjén az egyes részfák magassága nem ingadozik többet egy szintnél. === Kereső fa === Definiálható egy rendezési sorrend. Minden csúcsra igaz: * balra a nála kisebb elemek helyezkednek el * jobbra a nagyobb elemek helyezkednek el === Speciális bináris fa === Speciális bináris fa a kupac. Ha a B csúcs fia az A csúcsnak és A nagyobb vagy egyenlő, mint B. ==== Gráf ==== Csomópontok és azok kapcsolatainak halmaza. Címkézett gráf: {{:oktatas:programozas:programozas_elmelet:cimkezettgraf.png?direct&|}} Irányított gráf: {{:oktatas:programozas:programozas_elmelet:iranyitottgraf.png?direct&|}} ==== Gyakorlat ==== * Mit értünk gráf adatszerkezet alatt? * Rajzoljon példát a nem bináris fára. * Rajzoljon egy bináris fát. ===== Alprogramok ===== ==== Az alprogramokról ==== Összetartozó programrészek, amelyeket blokkokba szervezünk. Szokásos elnevezések: * függvény * eljárás Objektum Orientált környezetben elnevezés: * metódus ==== Az alprogramok részei ==== * fejrész * törzs {{:oktatas:programozas:programozas_elmelet:alprogram_fuggveny.png?400|}} ==== A paraméterátadásról ==== A függvények az átadott értéket két módon kezelhetik. Vagy érték szerint veszik át vagy cím szerint. * érték szerint átvett (pass by value) * cím szerint átvett (pass by reference) A megértéshez tisztázzuk a formális paraméter és az aktuális paraméter fogalmát. Amikor meghívok egy függvényt a meghíváskor paraméterként megadott változók az aktuális változók. Azok a változók, amelyek egy függvényen belül paraméterként jelennek meg a formális változók. {{:oktatas:programozas:programozas_elmelet:alprogram_parameterek.png?400|}} ==== Érték szerint átvett paraméter ==== A formális paraméterváltozók új változóként jelennek meg a memória verem területén, ideiglenesen jönnek létre. A formális paraméterváltozó és az aktuális paraméterváltozó két különböző változó lesz. A formális paraméterváltozók értékének változtatása nincs hatással az aktuális paraméterváltozókra. ==== Cím szerint átvett paraméter ==== A függvényben a formális paraméter cím szerint veszi át az aktuális paraméter értékét. Vagyis nem jön létre új változó, ami azt is jelenti, hogy ha megváltoztatom a formális paraméterváltozó értékét, az az aktuális paraméterváltozóban is változik. Mindkét változó ugyanazt a memóriaterületet használja. ==== Alprogram példa ==== function dupla(var szam):Integer; begin dupla := szam*2; end; procedure nevjegy(); begin WriteLn('Nagy János'); end; function dupla(szam) { return szam*2; } function nevjegy() { console.log('Nagy János'); } public int dupla(int szam) { return szam*2; } public void nevjegy() { System.out.println('Nagy János'); } ==== Gyakorlat ==== * Milyen módon vehetünk át paramétereket függvényekben? * Mit értünk aktuális változó alatt? ===== Rekurzió ===== ==== A rekurzióról ==== Rekurzióról metódusok, függvények, illetve eljárások esetén beszélhetünk. Ha például egy metódus (vagy akár függvény és/vagy eljárás) önmagát hívja, akkor a metódus rekurzív. Rekurzív metódusok esetén gondoskodnunk kell a rekurzió megszakításáról, mert máskülönben végtelen ciklusba kerülünk. A következő C program 1-től -- 10-ig a képernyőre írja a számokat. Iterációt nem használunk benne, helyett rekurzívan oldottuk meg a feladatot. #include kiir(int a) { printf("%d\n", a); if(a < 10) { a++; kiir(a); } } main() { kiir(1); } Mivel egy rekurzív program önmagát hívja, ezért egy hurok keletkezik. Vagyis ciklust hoztunk létre ciklus utasítás nélkül. ==== Gyakorlat ==== * Mitől lesz egy metódus rekurzív? * Miről kell gondoskodnunk a rekurzív algoritmusok esetén?