Algoritmusok


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.

A számítógép mint fekete doboz

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:

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:

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ó.

Az első 'N' egész szám kiíratása

A "jó" algoritmusok alapvető jellemzői

á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


Algoritmusok

az algoritmus fogalma és megadási módjai

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

Egy Google keresés eredménye (2016.11.08) Google:
NAT informatika
Egy Google keresés eredménye (2016.11.08) DEENK:
Cím: informatika
Tárgyszó: Nemzeti Alaptanterv
SQL:
SELECT szerz,cim,kiadev
FROM konyvtar.konyv
WHERE cim LIKE "* informatika *" and targyszo="NAT"
ORDER BY kiadev DESC;
1. táblázat: a konyv tábla lehetséges sorai a konyvtar adatbázisból
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)


A "jó" algoritmusok alapvető jellemzői

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)


példák algoritmusokra

egyszerű algoritmusok

első 'n' szám kiíratása folyamatábrával

további algoritmusok


Gyakorlati feladat (ételrecept animáció)

(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: A 'Tyúkhúsleves - Gasztroangyal | Magyarország finom' képernyőképe

(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!)

Mentés másként BMP formátumban

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.

Tyúkhúsleves címdia képe

(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:

Ha ez utóbbi pl. 289, akkor a menüablakot a következőképpen kell beállítanunk:

Speciális kijelölés-készítés

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:

Második dia képe

(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:

Harmadik dia képe

(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:

Utolsó dia képe

(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:

A diák megnyitása képszekvenciaként a VirtualDub alkalmazásban

Ha mindent jól csináltunk, a VirtualDub betölti az elkészített 12 diát külön képkockákként:

A megnyitott diák a VirtualDub alkalmazásban

Á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:

A video lejátszási sebességének beállítása

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 video exportálása animált gif videóként

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:

Az ételrecept alapján készített animált gif videó

A feladatok elvégzése után kapott recept.gif animált videót küldje el e-mail csatolmányként.


Gyakorlati feladat (csillagok animáció)

(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: Egy csillagokat mutató kép

(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.

Az animáció alapja: alap.bmp

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:

Speciális kijelölés-készítés

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:

Speciális kijelölés-készítés

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:

Az animáció első diája

(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:

Speciális kijelölés-készítés

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:

Speciális kijelölés-készítés

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:

Az animáció második diája

(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:

Az animáció utolsó diája

(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:

A megnyitott diák a VirtualDub alkalmazásban

Á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:

A video lejátszási sebességének beállítása

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:

Az ételrecept alapján készített animált gif videó

A feladatok elvégzése után kapott csillagok_animacio.gif animált videót küldje el e-mail csatolmányként.


Tartalom
Boda István, 2020.