Informatika2-2013/Eloadas

A MathWikiből
A lap korábbi változatát látod, amilyen Rpalovics (vitalap | szerkesztései) 2013. február 26., 17:56-kor történt szerkesztése után volt.

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.
  • A C nyelv alapvető adattípusai:
    • char egyetlen bájt, a gépi karakterkészlet egy elemét tárolja,
    • int egész szám,
    • float egyszeres pontosságú lebegőpontos szám,
    • double kétszeres pontosságú lebegőpontos szám.
  • lebegőpontos számokról
  • Minősítők:
    • Egész számokhoz (int):
      • short int általában 16 bites
      • long int általában 32 bites
    • char és bármilyen egész szám esetén:
      • signed és unsigned minősítések
    • A long double típus növelt pontosságú lebegőpontos számot jelöl.
    • Az egyes egész és lebegőpontos számok mérete gépfüggő.

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.
  • C++-ban már létezik bool, azaz logikai igaz/hamis típus.

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

do
   utasítás 
while (kifejezés);
  • Hasonló a while ciklushoz, csak hátul, a ciklusmag után teszteli a kifejezést.
  • Ez esteben tehát a ciklusmag garantáltan egyszer le fog futni.

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é.
for(...)
   for(...) {
      ...
      if (zavar)
         goto hiba;
   }
   ...
hiba:
  • 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

  • Először gondoljuk végig a függvények fogalmát. A függvényeket részletesebben alább tárgyaljuk.
  • Operátorokra helyes definíciót nehéz adni.
  • Néhány állítás:
    • Az operátorok szintakszisa eltér a függvényekétől
    • Az operátorok mindig operandusokon végeznek el műveleteket, és valamilyen értéket adnak vissza.
    • Az operátorok szintakszisa rögzített az adott nyelvben.
    • Az operátorokat kifejezésekben használjuk.
  • Az operátorokat tulajdonságaik alapján csoportosíthatjuk. Lényeges tulajdonságok:
    • operandusok típusa és száma
    • az operátor álltal visszaadott eredmény
    • az operandusok kiértékelési sorrendje (pl. asszociativitás összeadás esetén)
    • az egyes operátorok egymáshoz való viszonya (precedencia)
    • történik-e, ha igyen milyen automatikus típuskonverzió az operátor meghívásakor?
  • A alábbi táblázat összefoglalja a C nyelv operátorait:
Precedencia Operátor Rövid leírás Asszociativitás Jelölés Túlterhelhető
1 ()
[]
->
.
++
--
Csoportosítás
Tömb-elérés
Mutatón keresztüli tag-elérés
Objektumon keresztüli tag-elérés
Posztfix növelés
Posztfix csökkentés
Bal (a)
a[]
ptr->b()
a.b()
a++
a--
Nem
Igen
Igen
Nem
Igen
Igen
2  !
~
++
--
-
+
*
&
(típus)
sizeof
Logikai tagadás
Bitenkénti negálás
Prefix növelés
Prefix csökkentés
Előjel -
Előjel +
Dereferálás
Objektum címe
Konverzió típusra
Méret
Jobb  !a
~a
++a
--a
-a
+a
*ptr
&a
(b)a
sizeof(a)
Igen
Igen
Igen
Igen
Igen
Igen
Igen
Igen
Igen
Nem
3 *
/
 %
Szorzás
Osztás
Maradékszámítás
Bal Infix Igen
4 +
-
Összeadás
Kivonás
Bal Infix Igen
5 <<
>>
Bitenkénti eltolás balra
Bitenkénti eltolás jobbra
Bal Infix Igen
6 <
<=
>
>=
Kisebb
Kisebb-egyenlő
Nagyobb
Nagyobb-egyenlő
Bal Infix Igen
7 ==
 !=
Egyenlő
Nemegyenlő
Bal Infix Igen
8 & Bitenkénti ÉS Bal Infix Igen
9 ^ Bitenkénti kizáró VAGY Bal Infix Igen
10 | Bitenkénti megengedő VAGY Bal Infix Igen
11 && Logikai ÉS Bal Infix Nem Igen
12 || Logikai(megengedő) VAGY Bal Infix Igen
13  ? : if-then-else operátor Jobb logikai-kif ? kifejezés : kifejezés Nem
14 =
+=
-=
*=
/=
 %=
&=
^=
|=
<<=
>>=
Értékadás
Összeadás és értékadás
Kivonás és értékadás
Szorzás és értékadás
Osztás és értékadás
Maradékképzés és értékadás
Bitenkénti ÉS és értékadás
Bitenkénti kizáró VAGY és értékadás
Bitenkénti megengedő VAGY és értékadás
Eltolás balra és értékadás
Eltolás jobbra és értékadás
Jobb Infix Igen
15 , Szekvencia operátor Bal a, b Igen


Kulcsszavak

Memória lefoglalás, pointerek és tömbök

Paraméterek, argumentumok

File I/O

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

Struktúrák

Személyes eszközök