A számítógép fekete doboz modellje
A számítógéppel történő feladatmegoldás során a számítógépet gyakran egy fekete doboznak tekintjük, amelynek nem szükséges pontosan ismernünk a felépítését.
- bemeneti adatok; input (amelyet a digitális számítógépek rendszerint bináris formára alakítanak át)
- az adatokon végrehajtandó utasítássorozat, algoritmus
- az utasítások végrehajtása során képződött részeredmények ("rövid távú memória")
- a számítógépben tárolt adatok, törzsadatok (pl. egy adatbázis; "hosszú távú memória")
- kimeneti adatok, eredmények; output (a működés során előállított bináris adatokat a digitális számítógépek rendszerint az emberi kommunikáció által megszokott formára alakítanak át)
Az algoritmus fogalma
Kiindulásképpen adjunk egy rövid meghatározást az algoritmus fogalmára.
Az algoritmus több azonos jellegű, egymástól csak a kiinduló adatokban különböző feladat megoldására szolgáló eljárás, amelynek során előre meghatározott, véges számú lépést adott sorrendben végrehajtva jutunk el a feladat megoldásához.Példák algoritmusokra:
- egy ételrecept alapján egy étel elkészítése
- információ-visszakeresés egy adatbázisból (pl. a Google, a DEENK katalógusa stb.)
- egy SQL nyelven megadott lekérdezés végrehajtása egy relációs adatbázisban⇒
- select: a relációs adatbázis tábláinak milyen oszlopait ("mezőit") kell kiíratni?
- from: a relációs adatbázis melyik tábláit kell használni a lekérdezésben?
- where: a relációs adatbázis megadott tábláinak melyek azok a sorai ("rekordjai"), amelyeket a kiírásban figyelembe kell venni?
- cim like "* informatika *" and targyszo="NAT": a 'cim' mezőben milyen keresést kell végrehajtanunk? (itt: forduljanak elő benne az 'informatika' és a NAT tárgyszavak)
- order by: a kiírandó sorokat milyen mező(k) szerint rendezzük?
- egy matematikai eljárás végrehajtása (pl. egész számok összeadása, szorzása stb.; különböző számrendszerekben megadott számok átváltása; a legnagyobb közös osztó meghatározása stb.)
- egy izgalmas informatikai gyakorló feladat ügyes végrehajtása :-)
Az algoritmus működése (példa: az első 'n' egész szám kiíratása, ld. a lenti folyamatábrát)
Egy algoritmus rendszerint a következő elemekből tevődik össze:
- bemeneti adatok meghatározása (input)
- a kijelölt műveletek vagy a végrehajtási sorrendet vezérlő utasítások (pl. ciklus, szelekció) végrehajtása véges számú lépésben (program)
- lépések végrehajtása egymás után (szekvencia)
- start;
- n←10;
- i←1;
- (ciklus végrehajtása)
- stop;
- meghatározott lépések ismételt végrehajtása (ciklus)
- ismételd, amíg i≤n teljesül
- i kiírása;
- i←i+1; (i értékének növelése 1-gyel)
- adott feltételtől függően különböző utasítások végrehajtása (szelekció)
- ha i≤n teljesül, akkor
- a ciklus folytatása
- egyébként (azaz ha i≤n nem teljesül)
- kilépés a ciklusból
- kimenő adatok, eredmények meghatározása (output)
Példa egy algoritmusra (az első 'N' egész szám kiíratása):
// az első 'n' szám kiíratása var n=10; var i=1; while(i<=n) { writeln(i); i=i+1; } writeln("_____________");A fenti JavaScript nyelven írt program ki is próbálható.⇒
A "jó" algoritmusok alapvető jellemzői
- végesség (az algoritmus egyszer biztosan befejeződik)
- az algoritmus véges számú lépésből áll
- nincs az algorimusban "végtelenszer" ismétlődő utasítássorozat (azaz nincs benne "végtelen ciklus")
- egyértelműség (mindig tudjuk, hogyan kell folytatnunk az algoritmust)
- az algoritmus minden lépése után egyértelműen meghatározható a következő lépés
- teljesség (minden esetben eljutunk az algoritmus végéig)
- minden lehetséges lépésre van rákövetkező, kivéve az utolsó, befejező lépést
- az algoritmusban a szokatlan (ritka, váratlan, rendkívüli stb.) esetek, az ún. "kivételek" is megfelelően kezelve vannak (pl. a nullával való osztás, négyzetgyökvonás negatív értékből stb.)
- determinisztikusság vagy meghatározottság (de: a determinisztikusságot nem mindig követeljük meg; nem determinisztikus algoritmus pl. a statisztikai fizikai folyamatok számítógépes modellezése vagy "szimulációja" stb.)
- adott bemenő adatok mindig ugyanazokat a kimenő adatokat fogják szolgáltatni
- ún. "véletlen" vagy "rejtett" paraméterek nem fordulnak elő az algoritmusban
általánosság:
Az algoritmus rendszerint nem egy egyedi probléma megoldására szolgál, hanem több, egymáshoz valamilyen szempontból hasonló probléma megoldására (amelyek csak a bemenő adatokban különböznek egymástól).
Az algoritmusok néhány megadási módja
- természetes nyelven (pl. egy ételrecept esetében)
- függvénnyel
- felsorolással, táblázattal (pl. függvénytáblázatban megadva)
- grafikusan, függvénydiagram segítségével (pl. koordináta-rendszerben ábrázolva)
- képlettel, "kiszámítási szabállyal" (visszavezetve elemi műveletekre)
- pszeudokóddal (a természetes nyelv formalizálásával)
- ábrázolva, grafikusan (pl. folyamatábrával)
- programozási nyelv segítségével (pl. a Pascal programozási nyelv eredetileg épp erre a célra készült)
- (absztrakt, matematikai) automatákkal (pl. egy Turing-gép programja segítségével⇒)
Az algoritmus több azonos jellegű, egymástól csak a kiinduló adatokban különböző feladat (pl. matematikai számítás: összeadás, szorzás stb.) megoldására szolgáló eljárás, amelynek során előre meghatározott, véges számú lépést adott sorrendben végrehajtva jutunk el a feladat megoldásához.
0. példa algorimusra: egy ételrecept alapján egy étel elkészítése
1. példa algorimusra: információ-visszakeresés egy adatbázisból
SELECT szerz,cim,kiadev
FROM konyvtar.konyv
WHERE cim LIKE "* informatika *" and targyszo="NAT"
ORDER BY kiadev DESC;
RAKTJ | SZERZ | CIM | KIADHELY | KIADO | KIADEV |
---|---|---|---|---|---|
... | ... | ... | ... | ... | ... |
123456 | Kőfalvi Tamás | Informatikai alapismeretek a tanári mesterségre készülők számára | Budapest | Nemzeti Tankönyvk. | 2006 |
188224 | Holczer József | Informatika szóbeli érettségi közép- és emelt szinten | Budapest | Jedlik Oktatási Stúdió | 2013 |
234114 | Herdon Miklós et al. | Informatika | Debrecen | DE AMTC AVK | 2007 |
... | ... | ... | ... | ... | ... |
2. példa algoritmusra: egy matematikai függvény vagy művelet értékének kiszámítása (pl. egy kör kerületének vagy területének kiszámítása; két szám összeadása, kivonása, szorzása vagy osztása; a másodfokú egyenlet gyökeinek meghatározása; egy bináris vagy hexadecimális szám átváltása tízes számrendszerbe stb.)
példa: egy henger térfogatának kiszámítása; legyen a henger alapkörének sugara r=3 cm, magassága m=15 cm
további információk:
Algoritmus (Wikipédia) (2016-11-08)
Az adatbázis fogalma (Sulinet) (2016-11-08)
Adatbázis (Sulinet) (2016-11-08)
Az algoritmusok néhány megadási módja:
további információk:
Algoritmus (Sulinet) (2018-05-08)
Az algoritmusok (Tankönyvtár) (2018-05-08)
Az algoritmusok jellemzői (Tankönyvtár) (2018-05-08)
Algoritmus (Wikipédia) (2018-05-08)
Turing-gép (2018-05-08)
egyszerű algoritmusok
további algoritmusok
(1) A korábban létrehozott szocikkek nevű mappában hozzon létre egy új, recept nevű mappát, és ebben dolgozzon!
(2) Keressen egy ételreceptet az interneten. Az alábbi példában egy tyúkhúsleves receptjét fogjuk használni a Gasztroangyal webportálról:
(3) Készítsen az IrfanView-ban egy új, üres képet 640x480-as felbontásban, tetszőleges háttérszínnel! A képet mentse el a recept mappában alap.bmp néven, BMP formátumban. (Emlékeztető: a mentés CTRL S billentyűkombinációval a legegyszerűbb!)
A továbbiakban ezt a képet fogjuk alapként használni. A választott recept minden hozzávalójához készítünk egy diát az alap.bmp képfájl felhasználásával.
(4.1) Elsőként az ételrecept címdiáját készítsük el! Nyissuk meg az alap.bmp képfájlt, és középre írjuk be megfelelő betűnagysággal (betűszínnel, betűtípussal stb.) a választott étel nevét! Ha elégedettek vagyunk, mentsük el a képet a recept mappában BMP formátumban, dia01.bmp néven.
(4.2) Ezután következnek az ételreceptben szereplő "hozzávalók" diái, egyenként. Az általunk választott Tyúkhúsleves recept szerint az első hozzávaló 1 db konyhakész tyúk. Ehhez keressünk az interneten egy képet, és kicsinyítsük le 400 képpont szélességűre. Jegyezzük meg a lekicsinyített kép magasságát, és másoljuk a képet vágólapra (CTRL C). Nyissuk meg az alap.bmp képfájlt, és hozzunk létre egy Speciális kijelölést (SHIFT C) a következő beállításokkal:
A vágólapra másolt képet így torzítás nélkül tudjuk beilleszteni (CTRL V) az alap.bmp képfájlba. Írjuk be a diába a hozzávaló nevét is ("konyhakész tyúk"), majd mentsük el a képet a recept mappában BMP formátumban, dia02.bmp néven. A következő diához hasonlót kell kapnunk:
(4.3) Készítsünk az előző diához hasonló diákat a többi hozzávalóhoz is úgy, hogy összesen legalább 10 diánk készüljön el. A Tyúkhúsleves következő hozzávalójának (1 kg sárgarépa) a diája például a következő lehet:
(4.4) Ha megvan a címdiánk és a hozzávalókhoz készített 10 diánk, akkor keressünk egy szép képet a választott ételreceptnek megfelelő, elkészült ételről. Az utolsó (dia12.bmp) diánk ezt tartalmazza, például a következőképpen:
(5) Most fűzzük össze az elkészült diákat, és készítsünk egy animált gif videót belőlük. Ehhez először nyissuk meg a VirtualDub alkalmazást. A File/Open video file... menüponthoz tartozó ablakban keressük meg a recept mappában a dia01.bmp fájlt, és állítsuk be az ablak Fájltípus opciójában az Image sequence típust:
Ha mindent jól csináltunk, a VirtualDub betölti az elkészített 12 diát külön képkockákként:
Állítsunk be másodpercenként 1 képkockát a VirtualDub Video/Frame rate... menüpontjában úgy, hogy a Change frame rate to (fps): opció után 1 értéket írunk be:
Végül mentsük a videót úgy, hogy a File menü Export menüpontjában az Animated gif... opciót választjuk ki:
A célkönyvtár beállítása után a videónak adjuk a recept.gif nevet.
Az eredményül kapott animációt megnézhetjük, ha az alábbi címdiára kattintunk:
A feladatok elvégzése után kapott recept.gif animált videót küldje el e-mail csatolmányként.
(1) A korábban létrehozott szocikkek nevű mappában hozzon létre egy új, csillagok nevű mappát, és ebben dolgozzon!
(2) Keressen egy csillagokat tartalmazó képet az interneten (ez ne az a kép legyen, amit most a feladat bemutatásakor használni fogunk!). Az alábbiakban a következő képet fogjuk használni a csillagaszat.hu webhelyről:
(3) Nevezzük át a képet csillagok.jpg névre. (Ha nem 'jpg' típusú fájlt töltött le, az IrfanView segítségével konvertálja át 'jpg' típussá.) Készítsen az IrfanView-ban egy új, üres képet 640x480-as felbontásban, tetszőleges háttérszínnel. A kép jobb alsó sarkába írja be a nevét, és alá a "csillag animáció" feliratot. A képet mentse el a csillagok mappában alap.bmp néven, BMP formátumban.
A továbbiakban ezt a képet fogjuk alapként használni. Most készítsük elő a csillag animációt megvalósító képet a letöltött csillagok.jpg képből. Az általunk letöltött kép 534x462 felbontású (ez értelemszerűen képenként változhat). A szélesség és a magasság közül válasszuk ki a kisebbet (ez itt a magasság, amely 462 képpont), és ennek megfelelően jelöljünk ki a képben egy 462x462 négyzetet a kép bal felső sarkában a Szerkesztés/Speciális kijelölés-készítés (SHIFT C) menüpont kiválasztásával:
A kijelölés után vágjuk ki a kijelölt részt a Szerkesztés/Kijelölt rész a kép (CTRL Y) menüpont kiválasztásával. Eredményül egy 462x462 méretű képrészletet kapunk. Ezt kicsinyítsük le 300x300-as méretre és mentsük el csillag01.jpg néven.
(4) Ezek után elkészítjük az animáció első diáját.
Nyissuk meg a csillag01.jpg képet, és másoljuk vágólapra (CTRL C). Majd nyissuk meg az alap.bmp fájlt és az előző lépésben is használt Szerkesztés/Speciális kijelölés-készítés (SHIFT C) funkcióval jelöljünk ki egy 300x300-as négyzetet úgy, hogy a kijelölés a kép tetejétől és bal szélétől egyaránt 30 képpont távolságban legyen:
Ezután másoljuk be az előbb vágólapra helyezett csillag01.jpg képet. Az így kapott képet mentsük el 'bmp' típusú képként, dia01.bmp néven:
(5) Most készítsük el a második diát.
Elsőként a csillag01.jpg képet fogjuk átalakítani.
(5.1) Először levágjuk a kép 10 képpont szélességű és magasságú külső szegélyét. Jelöljünk ki a kép közepén egy 280x280-as négyzetet az előző lépésben is használt Szerkesztés/Speciális kijelölés-készítés (SHIFT C) funkcióval úgy, hogy a kijelölés a kép tetejétől és bal szélétől egyaránt 10 képpont távolságban legyen:
A kijelölés után vágjuk ki a kijelölt részt a Szerkesztés/Kijelölt rész a kép (CTRL Y) menüpont kiválasztásával. Eredményül egy 280x280 méretű képrészletet kapunk. Ezt nagyítsuk fel 300x300-as méretre és mentsük el csillag02.jpg néven.
Most bemásoljuk a csillag02.jpg képet a (4) ponthoz teljesen hasonló módon az alap.bmp képbe.
(5.2) Nyissuk meg a csillag02.jpg képet, és másoljuk vágólapra (CTRL C). Majd nyissuk meg az alap.bmp fájlt és az előző lépésben is használt Szerkesztés/Speciális kijelölés-készítés (SHIFT C) funkcióval jelöljünk ki egy 300x300-as négyzetet úgy, hogy a kijelölés a kép tetejétől és bal szélétől egyaránt 30 képpont távolságban legyen:
Ezután másoljuk be az előbb vágólapra helyezett csillag02.jpg képet. Az így kapott képet mentsük el 'bmp' típusú képként, dia02.bmp néven:
(6) Az előző lépéseket megismételve készítsük el az animáció további 8 diáját. Ennek végeztével összesen 10 diánk lesz. Az animáció lényege, hogy az egyes diákon a csillagokat mutató képrészlet közepén levő csillagok egyre nagyobbak lesznek, a szélen levő csillagok pedig egymás után "kifutnak" a képből ("nagyítás").
Az utolsó dia (dia10.bmp) például a következő lesz:
(7) Most készítsük el az animációt a VirtualDub segítségével. Először töltsük be képszekvenciaként az elkészült dia01.bmp, dia02.bmp, ..., dia10.bmp képeket a korábban elkészített ételrecept animáció során megtanult módon. Ha mindent jól csináltunk, a VirtualDub betölti az elkészített 10 diát külön képkockákként:
Állítsunk be másodpercenként 5 képkockát a VirtualDub Video/Frame rate... menüpontjában úgy, hogy a Change frame rate to (fps): opció után 15 értéket írunk be:
Végül mentsük a videót animált gif típusú fájlként a File menü Export menüpontjának Animated gif... opciója segítségével. Legyen a videó neve csillagok_animacio.gif.
Az eredményül kapott animációt megnézhetjük, ha az alábbi címdiára kattintunk:
A feladatok elvégzése után kapott csillagok_animacio.gif animált videót küldje el e-mail csatolmányként.