Programozás alapjai (ANSI C) 1. Előadás vázlat A számítógép és programozása
Dr. Baksáné dr. Varga Erika adjunktus Miskolci Egyetem, Informatikai Intézet Általános Informatikai Intézeti Tanszék www.iit.uni-miskolc.hu
[email protected] 1
A számítógép és programozása Az előadás témakörei: 1. A számítógép komponensei, számábrázolás 2. A számítógép programozása: gépi kódú vs. magasszintű programozás 3. Programozási nyelvek: fejlődése, csoportosítása 4. A programkészítés menete: specifikáció, algoritmizálás, kódolás, tesztelés, dokumentálás 5. Az algoritmus: fogalma, követelményei 6. Algoritmusok leírási módszerei 7. Programozási tételek I. (számlálás, összegzés)
2
1. A számítógép A számítógép: univerzális, digitális, programvezérelt, automata számológép. Neumann-architektúra
3
1. A számítógép Komponensei: 1) hardver: fizikai alkotóelemek 2) szoftver: a számítógép működéséhez szükséges programok (tárolt program elv) A program: egy feladat megoldására szolgáló, a számítógép számára értelmezhető utasítássorozat. Adatok
Program
Eredmény 4
2. A számítógép programozása Minden program meghatározott feladatot végez. Ahhoz, hogy a (számító)gép azt tegye, amit mi várunk tőle, pontosan meg kell mondanunk, mi a feladat, és azt hogyan hajtsa végre. Feladat
Megoldó algoritmus
Gépikódú program
Forrásprogram
Fordító v. Értelmező 5
3. Programozási nyelvek Precízen definiált mesterséges nyelvek (szintaktika, nyelvtan, szemantika). Programnyelvek Hogyan hajtsa végre a programa feladatot?
Mit hajtson végre a program? Deklaratív
Imperatív
Procedurális
Objektum orientált
Logikai
Funkcionális
Algol, Fortran, Pascal, C
C++, Java, C#
Prolog
Lisp, Haskell, Clean, Erlang
6
4. A programkészítés menete 1. Probléma elemzése, feladat meghatározása 2. Program viselkedésének informális leírása 3. A program egyes részeinek megtervezése 4. A program elkészítése 5. Az optimális választások ellenőrzése (algoritmus, pr. nyelv stb.) - gyakran elmarad 6. A pr. kód helyességének vizsgálata (hibakeresés, javítás) 7. Felhasználói és fejlesztői dokumentáció készítése 8. Program telepítése, terjesztése, felhasználó betanítása a kezelésére 9. Garanciális javítások + a (HW, jogi, gazdasági) környezet megváltozása miatti módosítások/frissítések elvégzése
7
5. Algoritmus Algoritmus: jól meghatározott számítási eljárás, amelynek a bemenete egy érték v. értékhalmaz, és amely kimenetként létrehoz egy értéket v. értékhalmazt. A helyes algoritmus: ● ● ● ●
● ●
elvégezhető (megoldja az adott feladatot), véges számú lépés után megáll, egyértelmű (minden lépés pontosan definiált), determinisztikus (ugyanarra a bemenetre mindig ugyanazt az eredeményt szolgáltatja), hatékony (felesleges lépéseket nem tartalmaz), és minden azonos jellegű feladatra alkalmazható.
8
5. Algoritmus Az algoritmus építőelemei: ●
Adatok (bemeneti és kimeneti)
●
Műveletek: olyan átalakítás, amely az adatok aktuális értékét felhasználva előállítja az adatok új értékét
●
Vezérlő szerkezetek: a feladat műveletekre bontását és ezek végrehajtási sorrendjét írja le –
szekvencia (utasítások egymás utánisága)
–
iteráció/ciklus (utasítások ismétlése, amíg teljesül egy vizsgált feltétel)
–
szelekció (az algoritmus feltételtől függő elágaztatása) 9
6. Algoritmusok leírási módszerei ●
Szöveges leírás (nem exakt)
●
Pszeudokód (metanyelv)
●
Folyamatábra vagy blokkdiagram
●
●
Struktogram: Egyetlen téglalap tagolása, amely a teljes feladat részekre bontását jelenti. Felülről lefelé történő tervezés, strukturált programozási stílus. Jackson diagram vagy struktúra diagram: Szerkezeti ábra. A vezérlő szerkezeteteket ábrázoló téglalapok kifejtése külön téglalapokban történik. 10
6. Pszeudo kód elemei Beolvasó utasítás Kiíró utasítás Elemi utasítás (értékadás) Szelekció
Előltesztelő ciklus Hátultesztelő ciklus
Input: változók Output: változók változó := kifejezés HA feltétel AKKOR elemi utasítások EGYÉBKÉNT elemi utasítások FELÉTEL vége AMÍG feltétel ADDIG elemi utasítások CIKLUS vége CIKLUS elemi utasítások AMÍG feltétel
11
6. Folyamatábra elemei Algoritmus elejét ill. végét jelző határszimbólumok
START
STOP
igaz
hamis
Beolvasó és kiíró utasítás (input/output) Elemi utasítás Elágazás: a feladat végrehajtása a rombuszba írt feltétel igazságértékétől függően folytatódik Csatlakozási pont (elágazás előtt / után) A végrehajtási sorrendet kijelölő nyilak
12
Összefoglalás ●
●
●
●
Egy feladatot megoldó algoritmus kidolgozására nem létezik általánosan alkalmazható eljárás; azaz soha nem csak egy megoldás létezik! Vannak gyakran felhasznált általános algoritmusok: számlálás, összegzés, keresés, rendezés, stb. Programozáskor a számítógép számára értelmezhető nyelven (programozási nyelven) írjuk le a megoldó algoritmust. Ajánlott irodalom (több kötetes): Donald Knuth: A számítógépprogramozás művészete 13 (The Art of Computer Programming)
7. Programozási tételek I. Gyakran előforduló általános (generikus) algoritmusok. 1.Összegzés tétele: Adott egy számsorozat. Feladat az összes elem, vagy a T tulajdonsággal rendelkező elemek összegének (szorzatának, átlagának) kiszámítása. 2.Megszámlálás tétele: a feladat egy sorozat összes, vagy a T tulajdonsággal rendelkező elemeinek megszámlálása. 14
7.1 Összegzés tétele Adott egy számsorozat. Számoljuk ki az elemek összegét. Az algoritmus szöveges megfogalmazása: 1. Az összegző (akkumulátor) változót kinullázzuk. 2. Megnézem van-e még hozzáadatlan elem 3. Ha igen, akkor veszem a következő elemet és az összegző változó értékét megnövelem ezzel az elemmel, majd vissza a 2. pontra. 4. Ha nem, akkor vége a ciklusnak és az összegző változóm már tartalmazza az összes elem összegét. 15
7.1 Összegzés tétele Algoritmus:
összeg := 0
összeg:=0 AMÍG van még szám ADDIG szám := következő elem összeg := összeg+szám
van még szám?
nincs
igen szám:=köv.elem
CIKLUS VÉGE összeg:=összeg+szám
16
7.1 Összegzés tétele – variációk ●
●
●
●
Feladat egy számsorozat elemeinek összegét meghatározni. Például: 1-től 100-ig a számok összegzése. Feladat egy számsorozat elemeinek szorzatát meghatározni. Például: N faktoriálisa, 1-től N-ig a számok szorzata. Feladat egy számsorozat elemeinek számtani átlagát meghatározni. Például: 1-től 10-ig a számok összege, elosztva 10-el. Feladat egy számsorozat elemeinek mértani átlagát meghatározni. Például: 1-től 10-ig a számok szorzata, a 10-edik gyök alatt.
17
7.1 Összegzés tétele – szorzással Feladat: kiszámítani az első N egész szám szorzatát (N faktoriálisa) Megoldás:
Változók: i, szorzat, N BE: N szorzat := 1 i := 1 AMÍG i <= N ADDIG szorzat := szorzat * i i := i + 1 CIKLUS vége KI: szorzat
18
7.1 Feltételes összegzés Adott egy N elemű sorozat, és egy, a sorozat elemein értelmezett T tulajdonság. A feladat a T tulajdonsággal rendelkező elemek összegzése (szorzása, átlagolása). összeg:=0 AMÍG van még szám ADDIG szám := következő elem HA igaz a feltétel szám-ra AKKOR összeg := összeg+szám FELTÉTEL VÉGE CIKLUS VÉGE
összeg := 0
nincs Van még szám? igen szám:=köv.elem
hamis feltétel számra igaz összeg := összeg+szám 19
7.2 Számlálás tétele Adott egy N elemű sorozat, és egy, a sorozat elemein értelmezett T tulajdonság. A feladat a T tulajdonsággal rendelkező elemek megszámlálása. Az algoritmus szöveges megfogalmazása: 1. A számláló változó értékét nullára állítom 2. Megnézem van-e még megvizsgálatlan elem 3. Ha igen, akkor veszem a köv. elemet és megnézem eleget tesz-e a feltételnek 3.1 ha igen, akkor növelem a számláló változó értékét 1-el 3.2 ha nem, akkor vissza a 2. pontra 4. Ha nem, akkor vége a ciklusnak, és a számláló a végeredményt 20 tartalmazza
7.2 Számlálás tétele Algoritmus: db:=0 AMÍG van még szám ADDIG szám := következő elem
db := 0
Van még szám?
nincs
igen szám:=köv.elem
HA igaz a feltétel szám-ra AKKOR db := db+1 FELTÉTEL VÉGE CIKLUS VÉGE
hamis feltétel számra igaz db := db+1
21
Elgondolkodtató kérdések ● ●
Minden tevékenység/probléma algoritmizálható? Mit gondolnak milyen lesz a programozási nyelvek új generációja?
Házi feladat ●
●
Egy rendszeresen végzett házi (vagy házkörüli) munka algoritmusának leírása szövegesen, pszeudo kóddal és folyamatábrával. A programozási tételekre példák készítése szöveges és folyamatábra leírással. 22
