Informatika2-2013/Eloadas

A MathWikiből
(Változatok közti eltérés)
270. sor: 270. sor:
 
* A default ág opcionális.
 
* A default ág opcionális.
 
==== for ciklus ====
 
==== for ciklus ====
 +
<C>
 +
for (1. kifejezés; 2. kifejezés; 3. kifejezés)
  
 +
  utasítás
 +
</C>
 +
* Szintaktikailag a for utasítás mindhárom komponense kifejezés.
 +
* Leggyakrabban az 1. és 3. kifejezés értékadás vagy függvényhívás, és a 2. kifejezés egy relációs kifejezés.
 +
<C>
 +
for (ii=0; ii<100; ii++)
 +
  utasítás
 +
</C>
 +
* A három komponens bármelyike hiányozhat, de az őket lezáró pontosvessző kiírása ekkor is kötelező.
 +
* Ha az 1. vagy 3. kifejezés hiányzik, akkor azokat egyszerűen elhagyjuk a for utasítást követő zárójelből.
 +
* Ha a 2. (vizsgáló) kifejezés is hiányzik, akkor azt a gép úgy tekinti, hogy az állandóan igaz, és ezért a program végtelen ciklusba fordul.
 
==== while ciklus ====
 
==== while ciklus ====
 
<C>
 
<C>

A lap 2013. február 20., 10:12-kori változata

Tartalomjegyzék

Bevezetés

Gyakran egy matematikai probléma megoldását, vagy a megoldás egy lépését számítógép segítségével határozhatjuk meg. A probléma megfogalmazása után először a megoldáshoz vezető algoritmust kell megadnunk. Ezután következik az algoritmus implementálása, beprogramozása a számítógépbe.

Algoritmusok

Az algoritmusnak nincs egységesen elfogadott definíciója, így az alábbi megfogalmazás sem definícióként értendő.

Algoritmus: (Cormen, T., Leiserson, C. E., Rivest, R. L., Stein, C. Introduction to Algorithms) Bármely jól meghatározott számítási eljárás, amelynek bemenete egy bizonyos érték vagy értékhalmaz, és amely létrehoz valamilyen értéket vagy értékhalmazt kimenetként.

Egy algoritmust sokféleképp jellemezhetünk. Knuth könyvében az alábbi, 5 fontos tulajdonságot emeli ki: (Knuth, D. E. - The Art of Computer Programming)

  • Végesség: Az algoritmus véges sok lépés után befejeződik.
  • Meghatározottság: Az algoritmus minden lépése pontosan definiált.
  • Bemenet (Input): Az algoritmus igényelhet olyan értékhalmazt (adatokat), amiket elindítása előtt meg kell adnunk.
  • Kimenet (Output): Az algoritmushoz tartozhat olyan kimeneti értékhalmaz, mely meghatározott kapcsolatban van a bemenettel.
  • Elvégezhetőség: Elvárjuk, hogy az algoritmust végre lehessen hajtani

Számítási módszernek nevezünk egy olyan eljárást, mely a végességet leszámítva teljesíti a fenti feltételeket.

Egy példa algoritmusra - Euklideszi algoritmus:

  • A feladat: Adott két pozitív egész szám, m és n, keresendő legnagyobb közös osztójuk.
  • Az Euklideszi algoritmus lépései:
    • E0 Ha m < n , akkor cseréljük meg a két számot:  m \leftrightarrow n
    • E1 Osszuk el m-et n-nel, legyen a maradék r.
    • E2 Ha r = 0, akkor az algoritmus véget ért, az eredmény n.
    • E3 Legyen  m \leftarrow n és  n \leftarrow r és menjünk vissza E1 lépésre.

Programozás, programozási nyelvek

Célunk algoritmusok beprogramozása a számítógépbe. Ehhez először a számítógép fogalmát kell megértenünk. A mai számítógépek Neumann János 1946-ban kidolgozott elvei szerint működnek. Felépítésük az ún. Neumann és Harvard architektúrák felépítését követi. Leegyszerűsített felépítésük a következő:

  • Processzor (CPU): beolvassa a memóriából az utasításokat és az adatokat, az utasítások alapján műveleteket végez, az eredményt visszaírja a memóriába; valamint vezérli a perifériákat - adatokat olvas belőlük, és ír ki
  • Memória: általános tároló, mely utasításokat és adatokat tartalmaz
  • Perifériák: háttértárolók, beviteli eszközök, monitor, ...

Egy algoritmust programozási nyelv használatával adjuk meg a számítógépnek.

  • Egy programozási nyelvvel képesek vagyunk vezérelni, utasítások sorozatát előírni a számítógép processzorának.
  • Az egyes nyelvek között compiler-ek fordítják át az utasításokat.
  • Gépi kódnak nevezzük azon nyelvet, mellyel a számítógép processzora közvetlenül vezérelhető.

Egy algoritmus programozásakor a választott programozási nyelvvel képesnek kell lennünk:

  • az algoritmus álltal használt adatok tárolására/kezelésére.
  • az algoritmus utasítás sorozatának megadására.

Példák programozási nyelvekre: Assembly, C, C++, Java, Python, ...

A C programozási nyelv

Bevezetés

A C programozási nyelv egy általános célú nyelv, melyet eredetileg Dennis Ritchie fejlesztett az AT&T Bell laboratóriumában 1969-1973 között. A nyelv néhány tulajdonsága:

  • Gépi kódra fordul
  • Hordozható
  • Hatékony programok írására alkalmas
  • Egyszerű nyelv, tömör szintaktika
  • Előfeldolgozó
  • Szabványos könyvtári függvények
  • Nagyon sok nyelv "alapja"

A nyelv lényeges részei

A nyelv lényeges részei, melyekről részletesebben lesz szó:

  • Adatok (változók, konstansok)
  • Adattípusok
  • Operátorok
  • Vezérlő struktúrák
  • Paraméterek, argumentumok
  • Pointerek és tömbök
  • Függvények, függvény könyvtárak
  • Kulcsszavak
  • Láthatóság
  • Struktúrák

Kódolás, fordítás a gyakorlatban

Forráskód

A nyelv részletes elemzése előtt érdemes tanulmányozni a "Hello World!" program C-ben írt forráskódját.

#include <stdio.h>
 
int main(void){
   printf("Hello world!\n");
   return 0;
}
  • A program első sora egy #include utasítás, hatására az előfeldolgozó erre a helyre bemásolja a megnevezett állomány tartalmát. Ez most az stdio.h állomány.
  • Az első sorban a "<>" jelek arra utalnak, hogy az stdio.h állomány a fordító részére megadott ún. „include path” által definiált helyen van.
  • A következő nem üres sor a main függvény definíciója. A main függvény egy speciális függvény a C programokban, amely a program indításakor legelőször hívódik meg.
  • Az int megadja, hogy a „main” függvény egy egész szám típusú adatot ad vissza.
  • A void azt jelenti, hogy a függvény nem vár paramétereket vagy adatokat az őt meghívó rutintól.
  • A kapcsos zárójel a függvény törzsének kezdetét jelzi.
  • A következő sor futtatja a printf függvényt. Az stdio.h tartalmazza a printf függvény meghívásának leírását (prototípusát, deklarációját).
  • Ebben az esetben, a printf függvényt mindössze egyetlen paraméterrel hívjuk meg, mégpedig egy fix szöveggel: „Helló, világ!\n”, ahol \n új sort jelent.
  • A printf függvény ugyan ad vissza értéket (a kiírt karakterek számát), de ezt most nem használjuk ki.
  • A return utasítás jelenti a kilépést az aktuális függvényből (ami ebben az esetben a main), és megadja a hívónak visszaadandó értéket-Ez az esetünkben 0, ami a program hibátlan lefutását jelzi.
  • Végül a záró kapcsos zárójellel jelezzük a „main” függvénytörzs végét.

Fordítás

  • Egy egyszerű szövegszerkesztőben is megírható C forráskódot compiler-el fordíthatunk le gépi kódra. Az így kapott fájl már futtatható lesz.
  • Itt most a linux-on, gcc-vel való fordítást mutatjuk be.
  • A GCC a GNU Compiler Collection rövidítése. Kezdetben GNU C Compilert, tehát GNU C fordítót jelentett. Mára a GCC kiegészült egyéb nyelvek fordítóival is. Elsősorban linux és BSD rendszereken használják, de Windows-on is elérhető.
  • A fordítás legegyszerűbb esetben, ha a forrásunk a hello.c file:
gcc hello.c
  • Ekkor a futtatható file-unk az "a.out" lesz.
  • Előfordulhat, hogy a megírt forráskódunk a nyelv szerint hibás részt tartalmaz. Ekkor a kód nem fordul le, a fordító pedig hibaüzeneteket küld a felhasználónak, például:
hello.c: In function ‘main’:
hello.c:3:1: error: expected ‘,’ or ‘;’ before ‘}’ token
hello.c:3:1: error: expected declaration or statement at end of input

Kapcsolók

  • A fordítás folyamatát különböző kapcsolókkal befolyásolhatjuk.
  • Sokféle akpcsoló létezik: gcc command options
  • Néhány fontos kapcsoló:
    • -o a létrejövő futtatható file nevét állíthatjuk be. Az alábbi példában a hello file lesz a futtatható file.
gcc hello.c -o hello
    • -W a legfontosabb figyelmeztető üzeneteket (warning) bekapcsolja
    • -Wall még néhány fontos figyelmeztető üzenetet bekapcsol
    • -s felesleges részeket (pl. nyomkövetési információk és szimbólumok) eltávolítja kimenetből
    • -g hibakereső információk hozzáadása a kimenethez
    • -gdb gdb (lsd. később) futtatásakor használt információk hozzáadása a kódhoz
    • -O1 (vagy -O), -O2, -O3' különböző szintű optimalizálások bekapcsolása. Magasabb szám magasabb szintű optimalizálást jelent. Ez hosszabb fordítási idővel, nagyobb memóriahasználattal, azonban csökkentett futtatási idővel és kisebb kódmérettel jár.
    • -Os kódméretre való optimalizálás
    • további optimalizálási kapcsolók


Linking and Compiling

  • Eddig fordításnak (compiling) neveztük azt a folyamatot, amikor a forráskódból a fordító (gcc) futtatható (gépi) kódot hozott létre. A fordítás folyamata azonban nem mindig ilyen "egyszerű". Ez történik, ha a programunk egyes részei különböző forrás file-okban találhatóak:
    • helyesen inkább "build"-nek kéne nevezni azt a folyamatot, mely során a forráskódból futtatható file-t állítunk elő.
    • compile folyamat során minden egyes forrásfájlból ún. object (.o) file-ok keletkeznek
    • linking alatt pedig azt a folyamatot értjük, amikor az object file-okból egyetlen, végső futtatható file jön létre. A fordítónak az object file-okból kell összeraknia a végső futtatható file-t.
  • A forráskódtól a futtatható file-ig tehát a compile és linking folyamatok vezetnek.
  • Ezt azért érdemes tudni, mert ha egy program nem fordul, akkor ennek oka
    • lehet a forráskódban lévő hiba miatt,
    • de az is elképzelhető, hogy a fordító a "linking" során nem talál egy forrásfájlt, amire egy másik hivatkozik.
  • Ne feledkezzünk meg a C preprocesszorról, ami a fordítás és linkelés előtt fut le. Célja, hogy a "compiler"-nek csak a tényleges fordítással kelljen foglalkoznia. Feladatai:
    • optimalizálja a whitespace karaktereket
    • végrehajtja a kódban "#"-gal jelölt preprocesszor utasításokat
    • eltávolítja a megjegyzéseket a kódból

Hibakeresés (Debugging)

  • Előfordulhat, hogy a megírt programunk hibás. Ennek oka lehet
    • szintaktikai hiba: ekkor a nyelvi hibát vétünk, a kód nem fordul le, a fordító álltal küldött hibaüzenetekből tájékozódhatunk a hiba forrásáról.
    • szemantikai hiba: ekkor a kód ugyan lefordul, de a futás nem úgy történik, ahogy azt elvárnánk (például végtelen cikulsba fordul a programunk, vagy összeomlik). Ennek forrásáról először a fordító álltal adott "warning" figyelmeztetések adhatnak információt. Ha ez sem segít, akkor hibakereső programok használatára van szükségünk.
  • A gdb (GNU Project debugger) egy ilyen hibakereső program. Néhány hasznos tudnivaló a gdb-ről (fejlesztés alatt, mivel itt sok fogalom tisztázatlan még, ez itt csak egy terv):
  • Használatához először fordítsuk le az adott kódot:
 gcc hello.c -gdb -Wall -o hello
  • Ezután hívjuk meg a gdb-t az adott kóddal:
  gdb hello
  • Később lesz szó argumentumokról. ezeket a következőképp adhatjuk meg:
  set args argumentum1 argumentum2 ...
  • Ha ezzel is megvagyunk, akkor futtathatjuk a kódot
run
  • ha a kódunk összeomlott, akkor visszakérhetjük, hogy pontosan milyen hívás okozta ezt:
backtrace

...

Fejlesztői környezetek

  • Fejlesztői környezetek célja egy program fejlesztési folyamatának, egy programozó munkájának a megkönnyítése.
  • Egy fejlesztői környezet nagyon sokoldalú lehet. Az alábbiak csak példák arra, hogy milyen funkciókat tartalmazhat:
    • forráskód szerkesztés,
    • "syntax highlighting" (adott nyelv forráskódjának színezése),
    • automatikus kiegészítés,
    • forráskód automatikus formázása,
    • hibakeresés segítése, egyszerűsítése,
    • több forrásfájlból álló, bonyolult kód hatékony kezelése ...
  • Példák fejlesztői környezetekre:
    • Code::Blocks
    • CodeLite
    • Eclipse
    • NetBeans
    • Visual Studio ...

A nyelv (fontosabb) részei

Adatok (Változók, konstansok) és típusaik

Deklarálás, inicializálás, konstansok definiálása

  • Változók és az állandók alkotják a programban feldolgozott alapvető adatobjektumokat.
  • Ha egy adat értéke változhat a futtatás során, akkor változó, ha nem, akkor konstans.
  • Egy változót deklarálunk, ha megadjuk annak típusát és azt a nevet, mellyel hivatkozunk rá a kódban:
int sum;
  • Az előző példában az int a változó típusára utal, melyről a továbbiakban lesz szó.
  • Egy változót inicializálunk, ha a deklarálás után megadjuk annak kezdeti értékét:
int sum = 0;
  • Egy változót konstansnak definiálunk a következő módon:
const int valasz=42;

Röviden a változók láthatóságról

  • Egy változó láthatóságán azt értjük, hogy a programkód mely részeiből érhető el, hol használható.
  • Az egyszerű szabály az, hogy a változó azon a blokkon belül érhető el, ahol deklaráltuk.
  • Blokknak számít egyrészt maga a teljes C forrásfájl, másrészt minden kapcsos zárójelek közötti rész egy-egy újabb blokk.
  • A zárójeleken belül lokális változóink lesznek. Lokális változók csak az adott blokkon belül látszódnak.
  • A zárójeleken kívül, a C forrásban deklarált változók globális változók. A globális változók a kód minden részéből láthatóak.

Típusok

  • Most kitérünk az adatok lehetséges típusaira.

Egész számok logikai értelmezése

  • A C nyelvben az egész számoknak logikai jelentése van: ha a szám nem nulla, az IGAZ-at jelent, ha nulla, az HAMIS-at.
  • A logikai műveletek eredménye egész számként használható. A logikai művelet eredménye 0, ha HAMIS és 1, ha IGAZ.

Vezérlési szerkezetek

Utasítások

  • Mindent, aminek értéke van kifejezésnek hívunk.
  • Tetszőleges kifejezés (pl. x = 0) utasítássá válik, ha egy pontosvesszőt írunk utána.
  • A C nyelvben a pontosvessző az utasításlezáró jel (terminátor).
  • A {} kapcsos zárójelekkel deklarációkat és utasításokat fogunk össze egyetlen összetett utasításba vagy blokkba, ami szintaktikailag egyenértékű egyetlen utasítással.

if/else szerkezet

if (kifejezés)
   1. utasítás
else
   2. utasítás
  • Ha az if utáni kifejezés igaz, akkor az 1. utasítást hajtjuk végre.
  • Ha az if utáni kifejezés hamis, akkor az else utáni utasítást hajtjuk végre.
  • Az else utasítás opcionális.

else if szerkezet

if (kifejezés)
   utasítás
else if (kifejezés)
   utasítás
else if (kifejezés)
   utasítás
else if (kifejezés)
   utasítás
.
.
.
else
   utasítás
  • Ha az if utáni kifejezés hamis, akkor egymás után sorra megvizsgáljuk az egyes else if utáni kifejezéseket, és csak ezután lépünk az else utáni utasításra.
  • Ha egy else if utáni kifejezés igaz, akkor az utána következő utasításokat végrehajtjuk és kilépünk a vizsgáló láncból. Az ezutáni if else kifejezéseket tehát nem vizsgáljuk meg.

switch szerkezet

switch (kifejezés) {
   case állandó kifejezés: utasítások
   case állandó kifejezés: utasítások
   .
   .
   .
   default: utasítások
}
  • Az egyes, mindig case után szereplő állandó értékű kifejezések értékét hasonlítjük össze a switch után szereplő kifejezéssel.
  • Az összehasonlítandó állandól egész típusú értékek kell legyenek.
  • Az utolsó, default ág akkor hajtódik végre, ha egyetlen case ághoz tartozó feltétel sem teljesült.
  • A default ág opcionális.

for ciklus

for (1. kifejezés; 2. kifejezés; 3. kifejezés)
 
   utasítás
  • Szintaktikailag a for utasítás mindhárom komponense kifejezés.
  • Leggyakrabban az 1. és 3. kifejezés értékadás vagy függvényhívás, és a 2. kifejezés egy relációs kifejezés.
for (ii=0; ii<100; ii++)
   utasítás
  • A három komponens bármelyike hiányozhat, de az őket lezáró pontosvessző kiírása ekkor is kötelező.
  • Ha az 1. vagy 3. kifejezés hiányzik, akkor azokat egyszerűen elhagyjuk a for utasítást követő zárójelből.
  • Ha a 2. (vizsgáló) kifejezés is hiányzik, akkor azt a gép úgy tekinti, hogy az állandóan igaz, és ezért a program végtelen ciklusba fordul.

while ciklus

while (kifejezés)
   utasítás
  • A program kiértékeli a while után szereplő kifejezést
  • Ha értéke igaz, tehát nem nulla, akkor végrehajtja a while utáni utasítást, majd újra kiértékeli a kifejezést.
  • Ha a kifejezés értéke hamis, akkor kilép a ciklusból.

do while ciklus

Ciklusokról általában

  • A ciklusok ismétlődő (azonos vagy hasonló) tevékenységek megvalósítására szolgálnak.
  • Megkülönböztetünk feltételes és számlálós típusokat.
  • A feltételesen belül megkülönböztetünk elől és hátultesztelős ciklusokat.

Egyéb (ugró) utasítások

  • a break utasítás hatására a legbelső ciklus vagy a teljes switch utasítás fejeződik be.
  • a continue utasítás hatására azonnal (a ciklusmagból még hátralévő utasításokat figyelmen kívül hagyva) megkezdődik a következő iterációs lépés.
  • a goto címkékkel a programkód adott részeire való ugrást tesz lehetővé.
  • a return parancs egy függvény (lsd. később) visszatérési értékét adja meg.
  • Ne használjuk a goto utasítást, és amennyiben lehetséges, kerüljük a break és continue parancsokat.
  • Szintén kerüljük a switch utasítást.

Operátorok

Kulcsszavak

Paraméterek, argumentumok

Pointerek és tömbök

Függvények, függvény könyvtárak

Struktúrák

Személyes eszközök