Bevezetés Alapfogalmak

Bevezetés Alapfogalmak C

Bevezetés Alapfogalmak A programozás alapjai I.

Hálózati Rendszerek és Szolgáltatások Tanszék Farkas Balázs, Fiala Péter, Vitéz András, Zsóka Zoltán

c Farkas B., Fiala P., Vitéz A., Zsóka Z.

2015. szeptember 7.

Bevezetés Alapfogalmak

2015. szeptember 7.

1 / 52


Tartalom

1

Az adat konstansok és

Bevezetés Bemutatkozás

változók

Mir®l lesz szó

Kifejezések

Követelmények

Programnyelvek

Ajánlott irodalom 2

3

Alapfogalmak

C nyelvi alapok Történet

Az imperatív programozási

Az els® program

paradigma

Változók

Az algoritmus

Beolvasás



2015. szeptember 7.

2 / 52



Bemutatkozás Mir®l lesz szó Követelmények Irodalom

1. fejezet Bevezetés


2015. szeptember 7.

3 / 52



Bemutatkozás BME Villamosmérnöki és Informatikai Kar Hálózati Rendszerek és Szolgáltatások Tanszék

Zsóka Zoltán tárgyfelel®s email: [email protected] szoba: IB123 Tel: 06 1 463 3279

Fiala Péter email: [email protected] szoba: IE430 Tel: 06 1 463 2543

A tárgy honlapja: www.hit.bme.hu/~zsoka/vihiaa01.php



2015. szeptember 7.

4 / 52



Tárgyunk a BSc képzésben

Informatika II

Informatika I

Digitális technika II

Digitális technika I


A programozás alapjai II

A programozás

A Számítás-

alapjai I

tudomány alapjai


2015. szeptember 7.

5 / 52



Mit tanulunk meg? Az algoritmikus gondolkodás és strukturált programszervezés alapjait START

p

−n >

H p

I k

I

p

←

←

f (k )

k

n +p 2


←

p +n 2

f (k )

>0

A

H

n

←

k

STOP

>0

−n >

p

←k

n

←k

k


2015. szeptember 7.

6 / 52



Mit tanulunk meg?

A C programozási nyelvet 1 2 3 4 5 6 7 8 9

/* Helloworld . c -- Az els ® program */ # include < stdio .h > /* printf - hez */ /* A f ® program */ int main () { printf ( " Szia , vil á g !\ n " ); /* Ki í r á s */ return 0; }



2015. szeptember 7.

7 / 52



Mit tanulunk meg?

Vektoralgoritmusokat Eldöntés Keresés Kiválasztás Rendezés



2015. szeptember 7.

8 / 52



Mit tanulunk meg?

A fájlkezelést



2015. szeptember 7.

9 / 52



Mit tanulunk meg? A rekurziót



2015. szeptember 7.

10 / 52



Mit tanulunk meg? gyökér

Dinamikus adatszerkezeteket Fák Listák

alma

körte

Vermek Prioritásos sorok

barack

0x1234 ?? 0x3456 0x????

0x3456 Alma 0x1245 0x1234

head 0x1234 c Farkas B., Fiala P., Vitéz A., Zsóka Z.

ribizli

0x1245 körte 0x4567 0x3456

0x4567 ?? 0x???? 0x1245

tail 0x4567 Bevezetés Alapfogalmak

2015. szeptember 7.

11 / 52



Mit tanulunk meg? Az állapotgépeket és az eseményvezérelt programozást 1,1,L

qb

0,1,L

start


qa

0,1,L 1,1,R

0,1,R

qc

0,1,L qd

1,1,R


2015. szeptember 7.

12 / 52



Mit tanulunk meg? A moduláris programozást egyik program

Megjelenítés I

Bináris fák

Fájlkezelés

Megjelenítés II

Rendezés

másik program



2015. szeptember 7.

13 / 52



Követelmények

1 Jelenlét El®adáson Tantermi gyakorlaton (70%) mi ellen®rizzük Laborgyakorlaton (70%) mi ellen®rizzük

2 Számonkérések hat (3

· 2)

kis ZH a tantermi gyakorlatokon

két nagy ZH beugrók a laborgyakorlatokon

3 Házi feladat



2015. szeptember 7.

14 / 52



Követelmények

Kis ZH-k (3

· 2)

kis ZH a tantermi gyakorlatokon, el®re meghirdetett

id®pontokban (1 2) (3 4) (5 6) mindegyiken 10 pont szerezhet®, páronként csak a jobb számít követelmény: páronként min. 4 pont

Nagy ZH-k 2 nagy ZH el®re meghirdetett id®pontokban papíron mindegyiken 40 pont szerezhet® követelmény: összesen min. 40 pont



2015. szeptember 7.

15 / 52



Követelmények Házi feladat Az ismeretek készségszint¶ megértését és alkalmazását el®segít® házi feladat, amely átfogja az adatszerkezet-tervezést, az algoritmizálást, az implementálást, a tesztelést és a dokumentálást. Beadás:

1 feladat pontosítása (6. hét) 2 adatszerkezet és algoritmusok (10. hét) 3 program és dokumentáció (13. hét) Értékelés: elfogadható/nem elfogadható Minimumkövetelmény: elfogadott megoldási terv (adatszerkezet és az algoritmusok) és m¶köd®képes program az el®írt dokumentációval.

Az elfogadott házi feladat el®feltétele a félévi jegy megszerzésének



2015. szeptember 7.

16 / 52



Ajánlott irodalom

Benk® Tiborné, Dr. Poppe András Együtt könnyebb a programozás C T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein Új algoritmusok Nemes Mihály Sebesség a számítástechnikában



2015. szeptember 7.

17 / 52



Imperatív Algoritmus Adat Kifejezések Programnyelvek

2. fejezet Alapfogalmak


2015. szeptember 7.

18 / 52



Programozás Hogy készítsek tojásrántottát?

Forr ó olajban pir í ts meg kev é s szalonn á t Ü ss bele h á rom toj á st ... Hogy pirítsak meg forró olajban kevés szalonnát?

V é gy egy serpeny ® t Tedd a t ¶ zhelyre Ö nts bele kev é s olajat Forrald fel T é gy bele kev é s szalonn á t V á rj , m í g megpirul Hogy forralom fel az olajat?

Gy ú jts al á V á rj kicsit Forr ó az olaj ? Ha nem , ugorj vissza a 2. sorra



2015. szeptember 7.

19 / 52



Az imperatív programozási paradigma Programozás Megmondjuk a gépnek, hogy mit csináljon

Programozási paradigmák Azok az elvek, amik alapján a programot elkészítjük Imperatív programozás

←

Ezt tanuljuk mi

Funkcionális programozás Objektum-orientált programozás stb. . .

Imperatív programozás Lépésr®l lépésre el®írjuk, hogy a gép mit csináljon egy algoritmus megfogalmazásával c Farkas B., Fiala P., Vitéz A., Zsóka Z.


2015. szeptember 7.

20 / 52



A programozás folyamata

A félév folyamán mindig ezt fogjuk csinálni:

1 Megfogalmazunk egy feladatot 2 A megoldáshoz kitalálunk egy algoritmust 3 Elkészítjük a programot kódoljuk az algoritmust



2015. szeptember 7.

21 / 52



A programozás folyamata

Ugyanaz kicsit b®vebben:

1 Megfogalmazunk egy feladatot 2 Megadjuk a pontos specikációt 3 Adatszerkezetet választunk a probléma modellezéséhez 4 A megoldáshoz kitalálunk egy algoritmust 5 Mi idén kizárólag C-ben programozunk 6 Kódoljuk az algoritmust 7 Teszteljük a programot



2015. szeptember 7.

22 / 52



Algoritmus

Algoritmus (módszer) Gépiesen végrehajtható lépések véges sorozata, amely elvezet a megoldáshoz Kódolás el®tt meggy®z®dünk róla, hogy helyes tényleg azt oldja meg, amit szeretnénk teljes minden lehetséges esetben megoldja véges véges sok lépésben befejez®dik

Nem elég kipróbálni, bizonyítani is kell!



2015. szeptember 7.

23 / 52



Algoritmusok példák

Feladat: Határozzuk meg az Megoldás: Osszuk el

n-et

n

szám köbgyökét!

néggyel!

Tesztek:

1 n = 8, n/4 = 2, 2 · 2 · 2 = 8 2 n = −8, n/4 = −2, (−2) · (−2) · (−2) = −8 3 n = 64, n/4 = 16, 16 · 16 · 16 = 4092 6= 64 Az algoritmus nem teljes



2015. szeptember 7.

24 / 52



Algoritmusok Feladat: Meneküljünk ki a sötét labirintusból Megoldás: Bal vállunkat a falnak nyomva haladjunk, míg ki nem érünk.


21 20

19 22

13 18 23

12 24

11 25

10 26

14 17 16 15

27 9 28 8

1

29 7

2

30 6

3

4


31

5

2015. szeptember 7.

25 / 52



Algoritmusok Feladat: Meneküljünk ki a sötét labirintusból Megoldás: Bal vállunkat a falnak nyomva haladjunk, míg ki nem érünk.


10

9

20 8

19 7

11 12

18 6 17 5

13 1

14 2

15 3

16 4


2015. szeptember 7.

26 / 52



Algoritmusok példák

Attól, mert az algoritmus helyes, teljes és véges, még nem biztos, hogy kezelhet® Fontos, hogy gyakorlatilag is véges legyen, vagyis kivárható id® alatt lefusson ésszer¶ mennyiség¶ adattal dolgozzon



2015. szeptember 7.

27 / 52



Algoritmusok példák Isten algoritmusa Adjuk meg tetsz®leges kezd®állapothoz a legkisebb lépésszámú forgatássorozatot, amivel a Rubik-kocka kirakható.

21 626 001 637 244 900 000 feldolgozandó állapot Ha másodpercenként 1 000 000-t dolgozunk fel, 685 756 évig tart. Az emberiség eddigi története < 10 000 év c Farkas B., Fiala P., Vitéz A., Zsóka Z.


2015. szeptember 7.

28 / 52



Algoritmusok leírása Algoritmusok nyelvfüggetlen leírási módja a pszeudokód (álkód) természetes nyelven, de precízen megfogalmazott utasítássorozat

V é gy egy serpeny ® t Tedd a t ¶ zhelyre Ö nts bele kev é s olajat Gy ú jts al á V á rj kicsit Forr ó az olaj ? Ha nem , ugorj vissza az 5. sorra T é gy bele kev é s szalonn á t V á rj , m í g megpirul Ü ss bele h á rom toj á st



2015. szeptember 7.

29 / 52



Algoritmusok leírása Algoritmusok grakus ábrázolásának eszköze a folyamatábra Egybemenet¶ és egykimenet¶ program folyamatábrája START és STOP elemek között helyezkedik el START

STOP

A folyamatábra az alábbi elemekb®l épül fel I Tevékenység

Feltétel H

tevékenység c Farkas B., Fiala P., Vitéz A., Zsóka Z.

feltételes elágazás Bevezetés Alapfogalmak

becsatlakozás 2015. szeptember 7.

30 / 52



Folyamatábra példa

Adjuk meg a forralás algoritmusának folyamatábráját START Gyújts alá

Várj kicsit H

Forr? I STOP



2015. szeptember 7.

31 / 52



Folyamatábra példa Hogyan dobunk be három tojást? START Dobj be egy tojást Dobj be egy tojást Dobj be egy tojást

STOP



2015. szeptember 7.

32 / 52



Folyamatábra példa Hogyan dobunk be 12 tojást? Jelölje

t

a már bedobott tojások számát!


START t

←

0

Dobj be egy tojást t

I

←

t

t

+1

< 12? H

STOP Bevezetés Alapfogalmak

2015. szeptember 7.

33 / 52



Az adat fogalma

Az algoritmus adatokon, adatokkal dolgozik

Adat Az adat minden, amit a külvilágból számítógépünkben leképezve tárolunk Az adatnak van típusa (szám, bet¶, szín, . . . ) értéke

A típus meghatározza az adat értékkészletét és az adaton végezhet® m¶veleteket



2015. szeptember 7.

34 / 52



Típusok példák

típus

értékek

m¶veletek

szám

0, −1, e, π, . . .

összeadás,

kivonás,

...,

összehasonlítás, rendezés bet¶ logikai

a, A, b,

γ,

...

{igaz, hamis}

összehasonlítás, rendezés tagadás,

konjunkció (ÉS),

diszjunkció (VAGY) szín

piros, kék, . . .

h®mérséklet

hideg, meleg, forró, . . .


összehasonlítás összehasonlítás, rendezés


2015. szeptember 7.

35 / 52



Állandók és változók Az algoritmusban betöltött szerepe szerint az adat lehet állandó (konstans) értéke nem változik az algoritmus futása során pl. a fenti példában

12

(a bedobandó tojások száma)

változó azonosítóval jelöljük (pl.

t)

értéke m¶veletekben felhasználható (olvasás), pl értéke frissíthet® (értékadás, írás), pl.

t←0

t < 12?

Az állandó típusa a megjelenési formából kiderül A változó típusát mindig külön meg kell adni (deklaráció). pl. Jelölje

t

a bedobott tojások számát



2015. szeptember 7.

36 / 52



Kifejezések Kifejezés Állandókból és változókból a megfelel® m¶veletek (operációk) alkalmazásával kifejezések képezhet®ek A kifejezés kiértékelhet®, típusa és értéke van. A m¶veleteket operátorok határozzák meg, melyek az operandusokon dolgoznak Kifejezés példák kifejezés 2

+3

−a 2

∗ (a − 2)

igaz ÉS hamis


típus

érték

szám

5

szám

−3

ha

a=3

szám

2

ha

a=3

logikai

hamis


megjegyzés

2015. szeptember 7.

37 / 52



Kifejezések Kifejezések típusa nem feltétlenül egyezik meg az operandusok (összetev®k) típusával. Vegyes kifejezések:

kifejezés

típus

érték

<3 (a − 2) 6= 8

logikai

igaz

logikai

igaz

2

megjegyzés ha

a=3

A kifejezések képzésének szigorú szabályai (szintaxis) vannak. Hibás (értelmezhetetlen) kifejezések:

kifejezés 3/ piros

hiba bináris operátor (/) egy operandussal

<2

· meleg (2 < 3) + 5 3


szín < szám szám

· h®mérséklet

logikai + szám


2015. szeptember 7.

38 / 52



Programnyelvek

Programozási nyelv Számítógéppel értelmezhet® matematikai formalizmus

Hasonlít a beszélt nyelvekhez, hogy könnyen érthet® legyen, és egyszer¶en tudjunk fogalmazni Sz¶k szókincs, szigorú nyelvtan (szintaxis)



2015. szeptember 7.

39 / 52



Szintaktika és szemantika

Szintaktikai (nyelvtani) hiba (syntax error) helytelenül használjuk a programnyelv szabályait, a program értelmezhetetlen, végrehajthatatlan A szintaktikai hiba hamar kiderül általában egyszer¶en, gyorsan javítható.

Szemantikai (értelmezési) hiba (semantic error) A program végrehajtható, lefut, de nem azt csinálja, amit specikáltunk A szemantikai hiba sokszor nehezen érhet® tetten, nehezen reprodukálható, nehéz javítani. A programtesztelés szakma.



2015. szeptember 7.

40 / 52



Történet helloworld Változók Beolvasás

3. fejezet C nyelvi alapok


2015. szeptember 7.

41 / 52



A C nyelv rövid története 1972: Fejlesztés kezdete az AT&T Bell Labsban UNIX kernel nagy része C-ben készült 1978: K&R C Brian Kernigham, Dennis Ritchie: The C Programming Language 1989: Szabványosítás: ANSI X3.159-1989 1999: C99-szabvány: új adattípusok (komplex) nemzetközi karakterkódolás változó méret¶ tömbök ... 2007: C1X szabvány, 2011-ben C11 C++ kompatibilitás többszálú programok ... c Farkas B., Fiala P., Vitéz A., Zsóka Z.


2015. szeptember 7.

42 / 52



A C f®bb tulajdonságai

fordított nyelv forráskód

fordító, linker

program.c

futtatható fájl program.exe

kis nyelv: kevés (10) utasítás, rengeteg (>50) operátor tömör szintaktika nehezen olvasható (ha nem gyelünk oda) könny¶ hibát véteni nehéz megtalálni

jól optimalizálható, gyors kódot eredményez jól hordozható



2015. szeptember 7.

43 / 52



Az els® C program A minimálprogram forráskódja 1 2 3 4 5 6

/* first . c -- Az els ® program */ int main () { return 0; }

link

A program elindul, majd befejezi a futást

/* és */ között komment, a programozónak szól int main() Így kezd®dik minden C-program int Main()

Nem így. A C case sensitive

{ } blokk, a programtörzset zárja return 0; A program végét jelzi


közre


2015. szeptember 7.

44 / 52



Az els® C program . . . ami már csinál is valamit 1 2 3 4 5 6 7 8 9

/* Helloworld . c -- Az els ® program */ # include < stdio .h > /* printf - hez */ /* A f ® program */ int main () { printf ( " Szia , vil á g !\ n " ); /* Ki í r á s */ return 0; }

link

Fordítás és futtatás után a kimenet:

Szia, világ!

#include más C programrészek printf kiírás, \n soremelés


beillesztése


2015. szeptember 7.

45 / 52



Eggyel bonyolultabb

Egymás után kiadott utasítások 1 2 3 4 5 6 7 8 9

/* football . c -- szurkol ó program */ # include < stdio .h > int main () { printf ( " Sz ó d á s ü veget " ); /* nincs ú jsor */ printf ( " a b í r ó nak ,\ n " ); /* itt van */ printf ( " hajr á , Fradi !" ); return 0; }

link

Szódásüveget a bírónak, hajrá, Fradi!



2015. szeptember 7.

46 / 52



Változó értékének kiírása 1 2 3 4 5 6 7 8 9 10

# include < stdio .h > int main () { int n; /* n nev ¶ eg é sz v á ltoz ó dekl . */ n = 2; /* n <- 2 é rt é kad á s */ printf ( " A sz á m é rt é ke : % d \ n " , n ); /* ki í r á s */ n = -5; /* n <- -5 é rt é kad á s */ printf ( " A sz á m é rt é ke : % d \ n " , n ); /* ki í r á s */ return 0; }

A szám értéke: A szám értéke:

link

2 -5

int n változódeklaráció. int (integer, egész) a típus, n az azonosító n = 2 értékadás, n változó felveszi a 2 kifejezés értékét printf(, <mit>) <mit> kifejezés értékének kiírása formában %d

decimális (tízes számrendszer)



2015. szeptember 7.

47 / 52



Blokk és deklaráció Blokk szerkezete

{ } 1

{

2 3 4 5 6 7 8

}

<deklarációk>

/* deklar á ci ó k */ int n; /* utas í t á sok */ n = 2; printf ( " % d \ n " , n );



2015. szeptember 7.

48 / 52



Blokk és deklaráció

Deklaráció szerkezete

[ = ]opt ; 1 2

int n; int number_of_dogs = 2;

/* inicializ á latlan */ /* inicializ á lt */

n értéke kezdetben memóriaszemét number_of_dogs értéke kezdetben 2



2015. szeptember 7.

49 / 52



Adat beolvasása 1 2 3 4 5 6 7 8 9 10 11

/* square . c -- sz á m n é gyzetreemel é se */ # include < stdio .h > int main () { int num ; /* eg é sz v á ltoz ó dekl . */ printf ( " Adj meg egy eg é sz sz á mot : " ); /* info */ scanf ( " % d " , & num ); /* beolvas á s */ /* k é t kifejez é s é rt é k é nek ki í r á sa */ printf ( " % d n é gyzete : % d \ n " , num , num * num ); return 0; } link

Adj meg egy egész számot: 8 8 négyzete: 64

scanf(, &) formátumú adat beolvasása c Farkas B., Fiala P., Vitéz A., Zsóka Z.


a

változóba

2015. szeptember 7.

50 / 52



Adat beolvasása

Így is lehet, az eredmény ugyanaz. 1 2 3 4 5 6

# include < stdio .h > int main (){ int num ; printf ( " Adj meg egy eg é sz sz á mot : " ); scanf ( " % d " , & num ); printf ( " % d n é gyzete : % d \n " , num , num * num ); return 0;}

link

Persze gondoljunk az utókorra is!



2015. szeptember 7.

51 / 52




Köszönöm a gyelmet.


2015. szeptember 7.

52 / 52

Bevezetés Alapfogalmak

Recommend Documents