Elméleti alapozás
Az algoritmus fogalma
A számítógép-vezérelt technológia című fejezetben meghatároztuk a számítógép működési elvét. Ismételjük meg ezt a nagyon fontos felismerést:
A számítógépek nem tesznek mást, mint érzékelők vagy más, a külvilággal kommunikáló egységek segítségével mintát vesznek a valóság egy adott szeletéről és ezt a beléjük táplált program szerint feldolgozzák. Valójában a bemeneti adatokat egy adott program utasításai szerint kimeneti adatokká alakítják át (Turing-elv).
Bemeneti adatok → Program → Kimeneti adatok
Az algoritmus fogalma ehhez a meghatározáshoz kapcsolódik.
Az algoritmus egy magasabb szintű probléma megoldására alkotott, véges lépésekből álló programsorozat, amely lépéseket számítások és döntések befolyásolnak. Az algoritmus mindig tartalmazza mindhárom programozási komponenst, azaz a bemeneti adatokat, a programot és a kimeneti adatokat.
Belátom, ez így eléggé érthetetlen meghatározás...
Ha jobban belegondolunk, valójában hétköznapjainkat legtöbbször egyszerű, de néha bonyolulttá váló algoritmusok szerint éljük le. Másképpen fogalmazva: nem kaotikusan, hanem rendezett életvitelben. Bizonyítsuk be ezt az állítást egy hétköznapi példán keresztül!
Nézzük meg Ági titkárnő átlagos, hétköznapi életrendjét algoritmikusan megfogalmazva! Felvázolásához a Java-nyelv szintaktikai jellegzetességeit használom fel, de ebben a formában az algoritmus természetesen nem lesz futtatható. Megjegyzem, programozók gyakran dolgoznak mindenféle álkódokkal, úgy is hívják őket, hogy pszeudokódok. Szeretném azonban hangsúlyozni, hogy megfelelő bemeneti adatok birtokában és a kódot átírva az algoritmus alapjában véve működőképessé tehető (mondjuk egy Sims-játékban).
Forrás - Source: www.wikihow.com
HA (nap = „Hétfő” VAGY „Kedd” VAGY „Szerda” VAGY „Csütörtök” VAGY „Péntek”){
Ági.alvás(23h, 7h);
Ági.ébredés(7.10h);
Ági.reggeliTeendők(zuhanyzás(), fogmosás(), öltözés(), reggelizés());
Ági.utazás(busz(32), villamos(6));
Ági.munka(9h, 17h);
Ági.utazás(busz(32),villamos(6));
Ági.bevásárlás(Tesco);
Ági.főzés(víz, paradicsom, tészta);
Ági.TVnézés(RTL, M1, StoryTV);
}
Sokan állíthatják: Ági élete nem lehet ennyire algoritmikus, de az igazság az, hogy lényegét tekintve igen. A bemeneti paraméterek például akár naponta változhatnak, például Ági másnap nem RTL Klubot néz, hanem TV2-t, azaz:
Ági.TVnézés(TV2, M1, StoryTV))
...de Ági abban az időben mégiscsak a TV előtt ül.
Másik példa: Ági garantáltan nem 7.10-kor, hanem 6 órakor fog kelni, ha a főnöke hívja:
HA (főnökHívás == TRUE){
Ági.ébredés(6h);
}
Láthatjuk azonban, hogy ez a bemeneti adat (a főnöki hívás) az életvitel alapstruktúráját nem fogja megváltoztatni, csakis akkor, ha speciális kérést tartalmaz, mondjuk Ági utazzon főnökével néhány napra külföldre. Az utazás után Ági megszokott életvitele visszatér az eredeti algoritmusba, kivéve persze, ha főnöke külföldön megkéri a kezét. Ekkor Ági élete egy új algoritmust fog felvenni, de továbbra is mindenképpen rendezett és algoritmikus lesz.
Jól tudják mindezt a hálózattudomány szakemberei is, akik szerint éppen ezen algoritmikus életvitel miatt az átlagemberek 90%-ának (!) jövő hete 100%-os valószínűséggel megjósolható.
Ez azonban már nem jóslás, hanem jövőbelátás!
Azt is láthatjuk, hogy nagyobb algoritmusok kisebb algoritmusokból épülhetnek fel. Ági reggeliTeendői() például reggelizést is tartalmaz, amely nagy valószínűséggel szintén nem lesz kaotikus, hanem algoritmikusan elrendezett (azaz Ági nagy valószínűséggel minden nap ugyanazt reggelizi és ugyanolyan sorrendben):
Reggeli(){
kávéFogyasztás(kávé, cukor, kiskanál);
péksüteményVajazás(zsemle, kés, vaj);
húsFogyasztás(„Pick”, szeletelés());
}
Az algoritmus tehát nem egy légből kapott matematikai ötlet, hanem az emberi életet nagyon mélyen meghatározó rendezési elv.
Az algoritmus fogalmához kapcsolódik egy további fontos felismerés, amely 2 olasz matematikus, Corrado Böhm és Giuseppe Jacopini nevéhez fűzödik:
Az 1966-ban alkotott Böhm-Jacopini-tétel szerint minden algoritmus megvalósítható a 3 programozási alapszerkezet, a szekvencia, iteráció és szelekció segítségével.
A későbbiekben mindhármat részletesen megtárgyaljuk. A tétel azonban több okból is rendkívül fontos:
-
Mivel a számítógép mindhárom szerkezetet képes végrehajtani, minden algoritmus végrehajtható számítógéppel, azaz minden algoritmus végrehajtása gépesíthető.
-
Ha pedig az algoritmus a való élet egy kiragadott szeletét írja le, valamint ez a szelet egyáltalán matematikailag leírható, akkor a számítógép ezt szintén képes megjeleníteni. Magyarán: a számítógép képes a való világot szimulálni.
Ha jobban belegondolunk, akkor az 1 + 1 = 2 matematikai művelet is a való élet egy bizonyos szeletének szimulációja, hiszen 1 alma + 1 alma az valóban = 2 almával.
Vegyünk egy másik, bonyolultabb példát!
A kör kerületének (K = 2r * pi) és területének (T = r2 * pi) kiszámításához 1 db bemeneti adatra van szükség, a körsugárra (r), ettől függetlenül a kézi számolás nem lesz gyors. Egy előre megírt program segítségével azonban gépesíthető és villámgyorsan végrehajtható. Az alábbi Java-kód már futtatható:
import java.math.*;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
final double PI = 3.1415926535;
Scanner in = new Scanner(System.in);
System.out.println("Kérem, hogy adja meg a sugárhosszt
(r)!");
String sugar = in.nextLine();
int r = Integer.parseInt(sugar);
double kerulet = 2 * r * PI;
double terulet = Math.pow(r, 2) * PI;
System.out.println("A(z) " + r + " egységnyi sugarú kör
kerülete: " + kerulet);
System.out.println("A(z) " + r + " egységnyi sugarú kör
területe: " + terulet);
}
}
Végeredmény:
Kérem, hogy adja meg a sugárhosszt (r)!
10
A(z) 10 egységnyi sugarú kör kerülete: 62.83185307
A(z) 10 egységnyi sugarú kör területe: 314.15926535
Köztudott, hogy a körkerület és körátmérő aránya adja ki a PI értékét. Az állítás bizonyításaként írjunk 1 olyan programot, amely ezt ellenőrzi le 1 és 10 között! (Valójában nem ellenőrzi le, csak kiírja és mindig ugyanaz lesz a végeredmény.) Az alábbi Java-kód már futtatható:
public class Main {
public static void main(String[] args) {
final double PI = 3.1415926535;
for(int r = 1; r <= 10; r++){
double kerulet = 2 * r * PI;
System.out.println("A(z) " + r +
" egységnyi sugarú kör kerület és
átmérőaránya (PI): " + kerulet / (2 * r));
}
}
}
Végeredmény:
A(z) 1 egységnyi sugarú kör kerület és
átmérőaránya (PI): 3.1415926535
A(z) 2 egységnyi sugarú kör kerület és átmérőaránya (PI): 3.1415926535
A(z) 3 egységnyi sugarú kör kerület és átmérőaránya (PI): 3.1415926535
A(z) 4 egységnyi sugarú kör kerület és átmérőaránya (PI): 3.1415926535
A(z) 5 egységnyi sugarú kör kerület és átmérőaránya (PI): 3.1415926535
A(z) 6 egységnyi sugarú kör kerület és átmérőaránya (PI): 3.1415926535
A(z) 7 egységnyi sugarú kör kerület és átmérőaránya (PI): 3.1415926535000005
A(z) 8 egységnyi sugarú kör kerület és átmérőaránya (PI): 3.1415926535
A(z) 9 egységnyi sugarú kör kerület és átmérőaránya (PI): 3.1415926535
A(z) 10 egységnyi sugarú kör kerület és átmérőaránya (PI): 3.1415926535
Aki mindezt megértette, az megértett minden lényegeset a számítógéppel kapcsolatban, a többi részletkérdés…☺
Pénzes László