A programozók rengeteg matekot tanulnak (sokszor többet is, mint szeretnének), és általában a hétköznapi gondolkodásban a programozási tudást valahogy a matektudással kötjük össze. Olyat is hallottam már, hogy valaki azért nem akar hallani sem a programozásról, mert „nem volt jó matekból”. Annyi biztos, hogy a programozásnak sok köze van a matekhoz, de az vitatható, hogy minden programozónak nagy matekosnak kellene lennie.

A lényeg: a modell

Először is tisztázzuk, hogy a matematika a modellalkotás, az absztrakció (elvonatkoztatás) tudománya. Ezért olyan nehéz besorolni a tudományok hagyományos osztályaiba, mert nem a természetről, nem is az emberről, nem is a társadalomról szól, hanem minden olyan jelenségnek, amivel a tudomány bármelyik területe foglalkozik, a modellezéséről. (Ezért sok egyetemen a matematikát külön karon, illetve karok fölötti intézetekben tanítják.) Modellezésen (ahogy a hétköznapi életben is, mondjuk a repülő- és vasútmodelleknél) olyasmit értünk, hogy egy nagyon bonyolult, összetett jelenséget úgy ragadunk meg, hogy csak a (valamilyen szempontból) jellegzetes vonásait tartjuk meg, az illető szempontból lényegtelenektől eltekintünk (elvonatkoztatunk).

A modellalkotásnak persze az az értelme, hogy a leegyszerűsítve ábrázolt jelenséget jobban tudjuk vizsgálni, mint az eredeti bonyolultat, mert eltekintettünk a bonyodalmaktól, így tudunk rá olyan ismereteket alkalmazni, amiket az egyszerűbb objektumról már tudunk. Ezért használhatjuk szinonimaként a modellalkotást és az absztrakciót (sőt, még a metaforát is, hiszen egy bonyolult dolgot egy egyszerűbbhöz hasonlítunk). Például a Földet sok szempontból tekinthetjük gömbnek (és alkalmazhatjuk rá mindazt, amit a gömbről, mint elég egyszerű matematikai fogalomról egészen biztosan tudunk, bizonyítani tudunk), pedig egyáltalán nem gömb alakú. Csak arra kell vigyáznunk, hogy olyan esetekben, amikor számít a Föld és a gömbök különbsége (például az, hogy a Föld picit „lapított”, meg hogy van domborzata), akkor ne ezt a modellt használjuk, hanem másmilyet. De valamilyen modell használata nélkül szinte semmit sem tudunk róla mondani, legalábbis tudományosat nem (nem mintha lebecsülném az irodalmi szövegeket, de azért azokat különböztessük meg a tudományosaktól).

A mindennapi életből is ismerős például az, hogy sok mindent modellálunk egész számokkal (iskolai osztályok, emeletek stb.). Olyan dolgokra szoktuk ezt a modellt használni, amiknek van egy természetes sorrendezésük, mert az egész számokra is jellemző ez (a matematikában úgy mondják ezt, hogy az egész számok lineárisan rendezve vannak, ennek a definíciójától itt eltekintek). Az emeleteknél azt szoktuk nagyobb számmal jelölni, amelyik magasabban van (sőt, az egyre mélyebb pinceszinteket negatív számokkal szokták jelölni), és így tovább. A számok használatával eltekintünk attól, hogy a rendezés magasságbeli, csak magát a rendezést tartjuk meg. Építészeti szempontból ez nyilván nagyon hiányos modell (túl sok mindentől tekint el, túl elvont), mert ott még az egyes emeletek magassága és még számtalan más tulajdonságuk fontos: ők gazdagabb modellt, kevesebb leegyszerűsítést fognak használni.

Mi köze a mateknak a programozáshoz?

Ennek a sorozatnak a legelején abból indultam ki, hogy programozáskor egy virtuális világot teremtünk, és abban mozgunk. Világos, hogy az ilyen virtuális világ valójában modellnek tekinthető. Amikor a francia kártya lapjait számpárokkal ábrázoltuk, akkor egy nagyon egyszerű modellt használtunk, nem is kellett hozzá sok matek, mert nem bonyolultak az összefüggések a kártyalapok, színek, lapértékek között. Ennyi matekot mindenki kibír. Nyilván többre lenne szükség, ha például a programunkkal mindenfélét rajzolni szeretnénk (ismerni kellene a geometriát), pláne ha háromdimenziós tárgyak kétdimenziós (képernyőre rajzolható) vetületeit szeretnénk rajzolni, és még inkább, ha mondjuk azt akarnánk, hogy ezek árnyékolva is legyenek, és forogjanak is. Nyilvánvaló, hogy az ilyesmi egész bonyolult számításokat igényelhet, amit persze majd a számítógép fog elvégezni, de nekünk kell előírni, hogy mit számoljon ki. Persze annak is igaza van, aki ezt nem a programozás részének tekinti: tervezze meg valaki más, hogy mit kell kiszámolni, mi meg megírjuk a programot. Csak nem mindig találunk valaki mást, aki helyettünk megtervezi.

És ne felejtsük el, hogy a program virtuális világában nemcsak dolgok (tárgyak) modelljeivel van dolgunk, hanem folyamatok modelljeivel is, mert a dolgokkal mindenfélék történnek. A történéseket eljárásokkal, algoritmusokkal modelláljuk, és persze ezeknek is megvan a matematikájuk. Az eddigi példáinkban az algoritmusok is nagyon egyszerűek voltak, de bonyolultabb adatok esetében az algoritmusok is bonyolultak lehetnek, és nagyon fontos, hogy milyen algoritmust használunk. Ezen múlhat, hogy ki tudjuk-e várni, míg lefut a programunk, vagy hogy egyáltalán lefut-e valaha.

Vegyünk például egy klasszikus problémát, az ún. utazó ügynök problémáját. Arról van szó, hogy az ügynöknek el kell utaznia egy csomó városba, úgy, hogy a végén visszaérjen a kiinduló helyére, és hogy a lehető legkisebb távolságot tegye meg. Tudnunk kell, hogy melyik városból melyikbe vezet út, és ismerjük az utak hosszát. Másra viszont nincs szükségünk: nemcsak a valóságos régiót egyszerűsítjük le egy térképre, de még a térképet is annyira leegyszerűsítjük, hogy például teljesen érdektelen, hogy melyik város milyen irányban van más városoktól. Szóval amire szükségünk van, az egyáltalán nem hasonlít igazi térképre.

Ezt a fajta leegyszerűsített modellt, „térképet”, amin csak „helyek” és köztük vezető „utak” vannak, a matematikában gráfoknak nevezik. A helyeket csúcsoknak, az utakat éleknek hívják. Ha az utak „egyirányúak” is lehetnek, akkor irányított élekről (és irányított gráfról) beszélünk. A városok távolságának ábrázolásához az élekhez címkéket kell társítanunk (elég gyakori, hogy a gráfokhoz tartozik címkézés, az éleket és a csúcsokat is lehet persze címkézni). A programozónak abban kell jónak lennie, hogy ezt a modellt hogyan ábrázolja a virtuális világban. (Bár még ebben sem feltétlenül, hiszen a gráfok ábrázolását már előtte rengetegen elvégezték, ezért jó esélye van rá, hogy készen le tud venni a polcról egy jó kis programkönyvtárat, amit használhat.)

Ilyen tehát az utazó ügynök problémájában maguknak az adatoknak a modellje. De milyen folyamattal találhatja meg az ügynök a megfelelő útvonalat? Ennek a folyamatnak a modelljei különböző algoritmusok, amikhez egyébként mindenféle további adat-modelleket is kell használni (például az ügynök számontartja, hogy hova kell még mennie, mennyi utat tett meg eddig, és így tovább). Ezeknek az algoritmusoknak a matematikája igen bonyolult, különösen nehéz kérdés, hogy melyik mennyire hatékony, még bonyolultabb, hogy úgy általában van-e egyáltalán hatékony algoritmus, hogy a nem hatékonyak milyen tulajdonságúak, és így tovább.

Megint azt tudom mondani, hogy az algoritmusok matematikáját a programozónak nem kell feltétlenül ismernie. Ami fontos a számunkra, azt könnyen megtalálhatjuk a neten. Például rengeteg mindent tudunk a gráfokról, és magáról az utazó ügynök problémájáról is. Ha utánanézünk, rövid úton rá fogunk jönni, hogy bizonyítható: nincs hatékony megoldása. Ez azt jelenti, hogy nincs olyan algoritmus, ami annyi lépésben biztosan eredményt ad, amennyit (a városok és utak számának függvényében) egy algebrai polinommal leírhatunk. Elég ennyit tudni (a programozónak nem kell például magát a bizonyítást ismernie). De ha ilyen problémával kerülünk szembe, akkor ne próbáljunk olyan programot írni, amelyik ténylegesen a legjobb megoldást találja meg. Inkább olyan algoritmust keressünk és használjunk, amelyik nem biztos, hogy a legeslegrövidebb utat találja meg, de legalább viszonylag gyorsan lefut.

Az algoritmusok hatékonyságának persze többféle mérőszáma van. A legfontosabb, amit az előbb említettem, a szükséges lépések száma. Ilyenkor az elemi lépéseket kell számolni. Akár hiszi az olvasó, akár nem, csak háromféle elemi lépés létezik, ezekből bármilyen program összeállítható: értékadás (a memóriában tárolt számokon valamilyen számtani művelet végrehajtása, és az eredmény tárolása valahol); feltételes utasítás (egy feltétel megvizsgálása, és ha teljesül, az egyik irányba megyünk tovább, ha nem, akkor a másikba); és ismétlés (ciklus) (egy utasítássor végéről újra az elejére ugrás). És van egy másik fontos szempont: a számításhoz használt munkamemória mérete. Igaz, hogy manapság óriási (és gyors) a számítógépek munkamemóriája, azért mégiscsak véges, és rengeteg plusz adminisztrációt és időt jelent annak a helyzetnek a kezelése, amikor nagyon megterheljük (ennek a részleteibe itt nem megyek bele).

Egy algoritmus: rakjuk sorrendbe a lapokat!

Ha már az algoritmusoknál tartunk, legutóbb egy 52 lapos francia kártya lapjait négy egyenlő részre („kézre”) osztottuk, de kihagytuk azt, hogy az egyes kezek lapjait sorbarakjuk. Ha a sorbarakást sajátkezűleg akarjuk megoldani, akkor gyorsan megkeressük a legfontosabb sorbarendező algoritmusokat, és valamelyiket alkalmazzuk. Az egyes algoritmusoknál meg fogjuk találni, hogy milyen esetekben érdemes használni őket, és hogy mennyire bonyolultak. Ez azt jelenti, hogy a sorbarendezendő dolgok számától (esetünkben 13 lapról van szó) milyen nagyságrendű a várhatóan szükséges lépések száma (külön meg szokták mondani, hogy mennyi az átlagosan várható, és mennyi a legrosszabb esetben várható lépésszám). Például itt van egy algoritmus, programban leírva, ami nem a lehető legjobb, O(n²) lépés kell hozzá átlagosan is, meg a legrosszabb esetben is, ami azt jelenti, hogy a lépések számának a nagyságrendje a lapok számának négyzete.

// Ehhez a 13 leosztott lapot egy 'kez' nevű tömbbe tegyük.

public static void sorbarak( Lap[] kez )

{

// Mindig egy lapot helyezünk el a sorban,

// valahol a jelenlegi helye ('i') előtt, ahol a már

// sorbarakottak vannak.

int i; // ezt a lapot helyezzük el legközelebb a sorban

for ( i = 1; i < 13; ++i )

{

Lap lap = kez[i];

int j; // ezzel végigmegyünk 0-tól addig, amíg meg nem

// találjuk a lap helyét valahol az 'i'-edik

// hely előtt:

for ( j = 0; j < i; ++j )

{

Lap masikLap = kez[j];

// A 'nagyobb' függvény majd legyen a 'Lap' osztály

// nyilvános tagja (módszere):

if ( masikLap.nagyobb( lap ) ) // ez elé kell tenni:

{

// A 'beilleszt' függvényt még meg kell adnunk!

beilleszt( lap, kez, j, i );

break; // ez azt jelenti, hogy megszakítjuk a ciklust

}

}

// Ha nem tudtuk beilleszteni a lapot, mert nem volt nála

// nagyobb, akkor marad a helyén!

}

}

// ennek nem kell nyilvánosnak lennie:

static void beilleszt( Lap lap, Lap[] kez, int j, int i )

{

// A 'j'-edik lap elé illesztjük be, és onnan az 'i'-edik

// lapig minden lapot eggyel jobbra tolunk.

// Először az eggyel eltolást végezzük el,

// a jobb szélsőtől indulva:

int k;

for ( k = i; k > j; --k )

{

kez[k] = kez[k - 1];

}

// Így már felszabadult a 'j'-edik hely:

kez[j] = lap;

}

// A 'Lap' osztályt pedig így egészítsük ki:

public static class Lap

{

private int szin;

private int ertek;

public Lap( int sz, int e )

{

szin = sz;

ertek = e;

}

// Az értéke igazságérték (igaz vagy hamis),

// ezt 'boolean'-nak nevezik:

public boolean nagyobb( Lap masik )

{

if ( szin > masik.szin )

{

// ha a színe nagyobb, akkor nagyobb:

return( true );

}

else if ( masik.szin > szin )

{

// ha pedig kisebb a színe, akkor kisebb:

return( false );

}

else // ha egyforma a színük:

{

return( ertek > masik.ertek );

}

}

}

A szerző nyelvész, az MTA Nyelvtudományi Intézetének főmunkatársa.

link Forrás