G-raph.com, avagy avagy a változatosság gyönyörködtet

XII. Erdélyi Tudományos Diákköri Konferencia – Kolozsvár, 2009. május 15–17.

G-raph.com, avagy avagy a változatosság gyönyörködtet

Szerző: Nyulas Károly-Róbert Sapientia EMTE Marosvásárhely Informatika III. év

Tudományos vezető: Dr. Kátai Zoltán Sapientia EMTE Marosvásárhely Matematika-Informatika tanszék

„Az őrültség nem más, mint ugyanazt tenni újra és újra, és várni, hogy az eredmény más legyen.” Albert Einstein

I. Bevezető Ebben a dolgozatban arra keressük a választ, hogy érdemes lenne-e az iskolákban tanultakhoz egy a szórakoztatóiparban helytálló verziót is mellékelni, ezzel elkerülendő, hogy az esetleges könnyebb út választása ne jelentse egyúttal az általános butulást. Az oktatás1 arról szól-e, hogy mit tanulunk, vagy csak arról, hogy hogyan? A témával azért kezdtem el foglalkozni, mert a tizenöt iskolapadban töltött év alatt rengeteget unatkoztam. Elemiben az óráknál érdekesebbek voltak a szünetek, általánosban alig vártuk, hogy végre mehessünk focizni, középiskolában mindig volt valami fontos, amit meg kellett beszélni, egyetemen pedig nem egyszer találtam magam kis böngészős játékok utolsó pályáján. Bizonyosságképpen, hogy nem velem van a baj, végeztem egy informális felmérést a környezetemben, de sem volt diákot, sem jelenlegi tanárt nem találtam, aki ne érezte volna így magát időnként. Lehetséges azonban, hogy ez a probléma egy regionális, vagy éppen kulturális jelenség, de ettől függetlenül még megoldásra vár, legfeljebb a megoldás is „csak” regionális, illetve kulturális lesz. Vizsgált területnek azért választottam a gráfelméletet, mert ez a tudományág rendelkezik egy jól elkülöníthető elméleti résszel, melynek az elsajátítása az elsőszámú cél, annak ellenére, hogy a tantárgyat legtöbbször egy programozási nyelv gyakorlásával kapcsolva tanítják. A továbbiakban tisztázunk néhány olyan alapfogalmat, mint a tanulás, tanítás, szórakoztatás, megvizsgáljuk az oktatás szerepét az egyének életében, bemutatjuk részletesebben, hogy mi is az a gráfelmélet és mire jó, majd végezetül megvizsgáljuk, hogy a javasolt megoldásunk milyen hatékonysággal lesz képes pótolni a hiányosságokat.  ϭ



njŽŬƚĂƚĄƐĂůĂƚƚŵŝŶĚǀĠŐŝŐĂŚĂŐLJŽŵĄŶLJŽƐĂƚĠƌƚũƺŬ͕ĐƐĂŬƐĞŵŵŝĂůƚĞƌŶĂƚşǀ

ϭ

II. Oktatás: a tanítás, tanulás és számonkérés keveréke 1. Tanítás Az a szemlélet, hogy a tanár tud valamit, a tanuló nem, az iskola pedig az a hely, ahol a tanár átadja a tudását a tanulónak, nagyon sokáig (gyakorlatilag a kezdetektől egészen a XX. század második feléig) tartotta magát. Ennek a hosszú pályafutásnak pedig az volt a titka, hogy hatékonyan modellezte a valóságot. Az életben való boldogulás nagyban függött az információ birtoklásától, ezért logikus volt az iskolák intézményét is erre az elvre szervezni. Fontos megjegyezni azonban, hogy nem az elv alakította ki az iskolákat, hanem az adott földrajzi és gazdasági konjunktúra tette ilyenné őket az idők folyamán. Ha a középkorban mindenki megfelelő minőségű saját könyvtárral rendelkezett volna, teljesen más oktatási rendszerben tevékenykednénk éppen. A postaszolgálat bizonyosan fejlettebb lenne. Telt-múlt az idő, és a számítógépek valamint az internet rohamos elterjedésének köszönhetően az áhított világ2, melyben minden információ karnyújtásnyira van, bizonyos értelemben elérkezni látszik. Az új világ azonban új kihívásokat rejteget, s mivel ez az eddig leggyorsabb ismert világunk, villámgyors reakciókra van szükség. Az egyik ilyen nagy kihívás az oktatás aktualizálása. Olyan dolgokat kell tanítani, amelyeknek hasznát lehet venni az iskolán kívül is. Én személy szerint támogatnám egy a keresőmotorok működését bemutató tantárgy bevezetését még általános iskolás szinten. Egy olyan környezetben, ahol a leírtak bármikor előhívhatóak, vagy legalábbis potenciálisan előhívhatóak lesznek, a hagyományos célja egy képlet, algoritmus, évszám stb. felírásának a táblára vagy füzetbe, megszűnik. Előtérbe kerül viszont a dolgok közti összefüggések ismerésének a fontossága, és a hatalmas információáradatban hatékonyan való keresés képességének a birtoklása. Lássuk hogyan változott eközben a tanuláshoz való viszonyulás.

 Ϯ

ELJŝůǀĄŶŶŝŶĐƐŵĞŐŵŝŶĚĞŶŬŝŶĞŬĞnjĂůĞŚĞƚƅƐĠŐĞ͕ĂƚŽǀĄďďŝĂŬĂͣĨĞůƐƅŵĄƐĨĠůŵŝůůŝĄƌĚƌĂ͟ǀŽŶĂƚŬŽnjŶĂŬ͕ĂŬŝŬŶĞŬǀĂŶ ŝŶƚĞƌŶĞƚŬĂƉĐƐŽůĂƚƵŬ͕ůĄƐĚĂnjŚƚƚƉ͗ͬͬǁǁǁ͘ŝŶƚĞƌŶĞƚǁŽƌůĚƐƚĂƚƐ͘ĐŽŵͬƐƚĂƚƐ͘ŚƚŵƐƚĂƚŝƐnjƚŝŬĄũĄƚϮϬϬϵŵĄƌĐŝƵƐĄďĂŶ



Ϯ

2. Tanulás Ha a mesterséges intelligenciában használatos meghatározásból indulunk ki, a tanulás nem más, mint osztályokba sorolás. Az emberek esetében ez csak a kezdetekben ennyire triviális (lásd ingerekben gazdag környezet fontossága a gyerekek fejlődésében), de a későbbi komplex folyamatokban is gyakran visszatérő motívum lesz: ennek segítségével ismerünk fel minden látottat, és ennek segítségével kapcsoljuk a már meglévőkhöz az újakat. Következésképpen, egy adott tananyag elsajátításában nagy szerepe van a több oldalról való megvilágításának. Ahogy a karakterfelismerő programról is annál inkább elmondható, hogy tudja, milyen az „A” betű, úgy a kisiskolás diákról is elmondható, hogy minél többet gyakorolta, annál, jobban tudja már az összeadást. Gyakorlatilag ez a tanár szerepe: különböző példákon keresztül bemutassa a tanulnivalót, és biztosítsa azt, hogy a hallgatósága a megfelelő következtetéseket vonja le, valamint a megfelelő tudással gazdagodik. Kellemetlen érzés, mikor valamilyen elvont elmélet tanulmányozása közben arra kell rájönnünk, hogy gyakorlatilag minden publikációban ugyanaz a, egyébként nagyon didaktikus és frappáns, példa található, amelyet az első szerző honosított meg. Ilyenkor, ha szerencsések vagyunk, vannak egyéb, független könyvek a témában, de sokszor jól jönne egy valamilyen felület, ahol kipróbálhatnánk a kérdéseinket. Végül említsük meg, hogy néha épp a radikálisan más nézetek segíthetnek megérteni egy adott problémát, a teljesen új szemszögekből való vizsgálódás új tereket nyithat meg, amelyek a hagyományos példákban fel sem tűntek volna (erre kiváló példa dr. Kátai Zoltán könyve a programozási technikákról), de a legfontosabb tanulság, hogy egyik vagy másik módszer sem segített önmagában, hanem csakis egymás mellett alkalmazva.

3. Az ismeretek felmérése Azok vagyunk, amit mérünk, szokás mondani, inkább csak viccelődésből, de az igazság az, hogy ez igaz. Burger (2007) dolgozatában részletekbe menően tárgyalja a különböző tesztek kialakulásának és használhatóságának történetét, konkrét megoldásokat is javasolva néhány



ϯ

elméleti és több hatékonysági problémára, ami a gráfelméleti ismeretek felmérését illeti. Hogy miért nem használják sehol az ötleteit, arra a későbbiekben még visszatérünk. Nem csak Burger következtetései, de az általános tendencia is azt mutatja, hogy a tesztek világában mindenki törekedik két nagy irányvonal tartására. Az egyik, hogy minél igazságosabb és átverhetetlenebb tesztek készüljenek. Itt ugyancsak két ideológia vetekszik egymással: az egyik, főleg memóriát is tesztelő esetekben a külvilág kizárása (zárt termek, internet nélküli gépek stb), a másik pedig az olyan feladatok megalkotása, ahol nem elégséges valamit lemásolni a sikeres teljesítéshez. Az utóbbi hűbben tükrözi a valóságot, hiszen nem sok embernek kell majd egy üres osztályteremben megoldania a felmerülő problémáit, de nehezebb a tesztet megalkotni, míg az előző esetben könnyű a tesztet elkészíteni és kijavítani, viszont vitatható az egész hasznossága. A másik irányvonal, hogy az olyan dolgokat, amelyek javításához illetve kiértékeléséhez nem szükséges emberi intelligencia, azt mielőbb tegyék át elektronikus változatba. Ez a lehető legészszerűbb dolog, hiszen jobb, ha egyszer írja meg egy programozó a rácstesztelő alkalmazást, minthogy minden vizsgánál emberek százai ellenőrizzék és számolgassák a válaszokat. A közös cél tehát: gyorsabban és egyszerűbben felmérni a leadott anyag hatását.

III. Egyetemi oktatás vs. Szórakoztatóipar A rengeteg különbség mellett, most elsősorban néhány hasonlóságra szeretném felhívni a figyelmet, amelyek elsősorban az internet elterjedésének és még inkább az egyetemi oktatás széleskörű elterjedésének köszönhető. Általában az egyetemi előadásokon a hallgatóság két részre osztható: akiket érdekel az előadás, és akiket nem annyira. Ez fizikailag az első két-három sort, illetve a terem többi részét jelenti, nyilván tele termekkel számolva. Köztük a diplomájuk nem fog különbséget tenni (feltéve persze, hogy mindannyian elvégzik), de a tudásuk igen. A megszokott válasz erre az, hogy a



ϰ

felsőoktatás nem kötelező, de ennek van egy hatalmas hátránya. Az a két első sor az egész teremből kerül ki, így aztán a többiekre is szükség van. Maga a rendszer azonban jól ki van találva: az egész infrastruktúra és az első két sor ellátása meg van oldva a többiektől beszedett tandíjból is, így senki sem potyázik, aki ügyes az kapja a jutalmakat, és úgy egyáltalán, minden a legnagyobb rendben. A tanáron és az előadásán esetleg annyi múlik, hogy nem csak két sor fog elől ülni, hanem három. Ötven százalékos növekedés, de a teljes létszámhoz képest nem nagy dobás. Mi történik akkor, ha egyre több ilyen intézmény nyitja meg a kapuit? Egy nagyon jó dolog, méghozzá az, hogy egyre több ember fog jelentkezni, így nő az esélye, hogy egyre jobb minőségű kutatókat és szakembereket neveljen ki az intézmény. Ez eddig szép és jó, csak nem szabad elfelejteni, hogy a másik kategóriában is ugyanez történik: egyre gyengébb képességű hallgatók fognak ülni a hátsó sorokban. Egy oktató előtt most két lehetőség áll: vagy folytatja tovább a munkát örülve a jobb érdeklődőknek, vagy megpróbál mindenkit bevonni, azaz csökkenteni a színvonalat, ezzel megtartva az intézmény működéséhez szükséges emberanyagot, de hátráltatva a tehetségesebbek fejlődését. Nem könnyű feladat megtalálnia az egyensúlyt. Az MIT által 2001ben elindított kezdeményezés, hogy a lehető legtöbb kurzus ingyenesen elérhető legyen az interneten, hatalmas sikernek számít, hiszen megadta a „szünet”, „előre” és „vissza” gombokat azokhoz a videókhoz, amelyeket hallgatók ezrei nézték évekig „youtube minőségben”3 a hátsó sorokból. Az alapvető problémát viszont nem oldotta meg, hisz ezeket az oldalakat is azok fogják látogatni, akiket érdekel a téma, akiket nem, azok továbbra is maradnak például a South Park-nál4. És akkor itt is vagyunk a szórakoztatóipar kellős közepén. Csupa móka és kacagás az egész, a lényeg, hogy érezd jól magad, ne gondolkozz sokat, esetleg vásárolj ezt-azt, de mindenképpen sokkal egyszerűbb, mint tanulni, vagy esetleg gondolkodni. Még mielőtt a szokásos „mennyire rossz a mai média” szövegbe csapna át az egész, szeretném leszögezni, hogy ez csak a két világ összehasonlításánál tűnik így, ahogy mondani szokták, nem azzal van baj aki hülyít, hanem aki  ϯ ϰ



ϯϮϬdžϮϰϬƉŝdžĞů͕Ăǁǁǁ͘LJŽƵƚƵďĞ͘ĐŽŵǀŝĚĞſŵĞŐŽƐnjƚſƵƚĄŶŝĞůŶĞǀĞnjĠƐ ŚƚƚƉ͗ͬͬĞŶ͘ǁŝŬŝƉĞĚŝĂ͘ŽƌŐͬǁŝŬŝͬ^ŽƵƚŚͺWĂƌŬ

ϱ

hagyja magát. Nő az ingerküszöb, egyre agresszívebb reklámokra, kampányokra van szükség ugyannak a hatásnak az eléréséhez. Mindeközben mi történik az oktatáson belül? Nem sok, úgy teszünk, mintha nem tudnánk arról, ami odakint, az egyetem, iskola falain kívül található. Nem jobb lenne, ha a panaszkodás helyett, hogy a tanulókat nem érdekli az óra, olyan órákat tartanának, ami érdekelné őket? Elvileg a legjobbak tanítanak az egyetemeken, nem kéne gond legyen a szórakoztatóipar kifejezési formáival is elmondaniuk a mondanivalóikat.

IV. Gráfelmélet A wikipédia „Gráf” szócikke szerint a gráf „dolgok (csomópontok, csúcsok) és rajtuk értelmezett összeköttetések (élek) halmaza. Egy gráfot megadhatunk csúcsainak és éleinek felsorolásával, vagy szemléletesebben egy diagram formájában, ahol a pontok felelnek meg a gráf csúcsainak, az őket összekötő ívek pedig az éleknek. A két megadási mód ekvivalens, azaz a gráf pusztán egy struktúra, semmilyen megjelenítési információt nem tartalmaz.” Az ezek közti összefüggéseket, és az ezeken alkalmazható algoritmusokat vizsgálja a gráfelmélet, mint tudományág. Most nem célunk, ennél mélyebbre kalandozni a témában, megtette ezt Burger (2007) és megteheti bárki Kátai (2008) Gráf algoritmusok könyvét lapozva. Azért esett a választás pont erre a tantárgyra, mert ez rendelkezik egy jól elkülöníthető (programozási nyelvtől független) elmélettel, amelynek ismerete azonban kulcsfontosságú a különböző témával kapcsolatos fejlesztéseknél. A gráfelmélet informatikai vonatkozásait természetesen nehéz, és aránylag értelmetlen, lenne programozás nélkül tanítani, de mint tantárgy, az elsődleges cél, oktatásról lévén szó, az elméleti tudás átadása. Végeztünk egy érdekes kísérletet ezzel kapcsolatban, a Sapientia másodéves számítás-technika és a harmadéves informatika szakos tanulók körében. A gráfelmélet tantárgy pótvizsgáján, akiknek nem sikerült megírnia a kért programot a kért időintervallumon belül, az átmenő jegyért a következő feladatot kellett megoldaniuk: egy tíz csomópontból álló gráfnak kellett felírniuk a mélységi, illetve szélességi bejárás utáni csomópontok sorrendjét. Az elgondolás az volt, hogy az



ϲ

esetlegesen programozási nehézségekkel küzdő hallgatóknak is értékelni lehessen a gráfelméleti ismereteiket. Az eredmény megdöbbentő volt: tizenegyből kettőnek sikerült. Hogy szemléletesebbé tegyük a példát: van 9 olyan hallgató, akinek gyakorlatilag szinte semmi nem maradt az egész tantárgyból, és tudjuk, hogy a két szakon összesen 90 helyet (50 informatika és 40 számítás-technika) hirdetnek meg. Ez 10 százalék. Magas aránynak tűnik, de ha visszagondolunk a dolgozat elején említett előadástermes példára, már nem is olyan vészes: a hátsó sorokban, soronként egy ember, ennyi veszteséggel számolni kell. Tulajdonképpen ez a kísérlet fogalmazta meg először, hogy ezzel a 10 százalékkal is kezdeni kell valamit, mert ahogy azt a dolgozatom elején kifejtettem, ez az arány már nem lesz kevesebb, csak több.

V. A megoldás Egy olyan felületre lenne szükség, ami felkelti az érdeklődést, esetleg fent is tartja azt, és garantálja, hogy a megtanulandó dolgok fognak megmaradni a felhasználónak. Burger (2007) dolgozata tökéletes megoldása az utóbbinak, és tökéletesen bemutatja, hogy hogyan ne próbáljuk az előbbit. Ő ugyanis elkészített egy alkalmazást, amely segítségével a felhasználók gráfokat szerkeszthettek, végignézhették a különböző algoritmusok animációit, és le is tesztelhették magukat, hogy mennyire értették meg őket. A baj csak az, hogy ehhez még kapcsolt néhány teljesen más témájú tesztet ( mert a tesztekről szólt a dolgozat), olyan technikai megoldást választott, hogy nehézkes legyen az alkalmazás használata és terjesztése egyaránt (külön szerver részt kellett indítani minden egyes használatkor), majd sikeresen elrejtette egy pincében5. Mint már többször hangsúlyoztuk, alkalmazásunknak a lehető legkönnyebben elérhető helyen kell lennie, mert gyakorlatilag a legtürelmetlenebb közönségnek szól. És hol lehetne valami közelebb, mint az interneten?  ϱ



^ĂƉŝĞŶƚŝĂDdŵĂƌŽƐǀĄƐĄƌŚĞůLJŝŬƂŶLJǀƚĄƌĂ

ϳ

VI. A weboldal 1. Felhasználása: •

Gráfok importálása és exportálása szöveges fájlokba szomszédsági mátrixként.

•

Algoritmusok animálásának megtekintése, akár lépésenként.

•

Gráfok szerkesztése

•

„Vizsgázás” a gráfok kért algoritmusok szerinti végigjárásával az egérrel (időre, vagy nehézségi szintek szerint)

2. A látvány: Hosszas fontolgatás után végül két okból döntöttünk a minimális grafika és inkább kidolgozott szöveg mellett. Az egyik, hogy a grafikai dolgok nagyon hamar öregednek, ami idén még menőnek számít, két év múlva már biztos nem lesz az, de egy vállalt minimál grafika nem kelti az elhanyagolt honlap látszatát. A másik ok, hogy a szöveg aránylag egyszerűbben cserélhető elem, amennyiben időnként az aktualizálás mellett döntünk. A honlap tematikája szintén nagy kihívás volt, hiszen olyat kellett választani, amely elég humoros és megragadó a figyelemfelkeltéshez, de elég tiszta ahhoz, hogy használható legyen. Végül a szavanna mellett döntöttünk, egész konkrétan egy zsiráf foltjai lesznek a gráfok csomópontjai. Az angol név szinte már adta magát: a gráf angolul „graph”, de ha Graph-ra módosítjuk, akkor ugyanúgy hangzik, mint a „giraffe”, ami zsiráfot jelent. Mivel a célunk nem a puszta szórakoztatás, hanem a gondolkodásra késztetés is, több apró geg-et rejtettünk el a honlapon (főleg ironikus hangvételűeket), de gondosan ügyelve arra, hogy ne zavarják a gráfos rész használata közben a felhasználót, hanem inkább az elkalandozások idején tereljék vissza a figyelmét.



ϴ

1.ábra: A honlap látványtervének a vázlata

3. A nyelv Nem meglepő módon az angol nyelvet választottam a weblap elkészítéséhez. Informatikai témáról lévén szó, nyilvánvalóan az angol nyelv az, amelyik a legnagyobb közönséget megszólíthatja. Nagy siker esetén lesznek majd fordítások, az újabb piac felkutatása érdekében, de igazából ez lesz az utolsó dolog, amiről szó lesz esetleges fejlesztések és javítások során.

4. Fenntarthatóság A fent említett türelmi okokból kifolyólag, nem lenne szerencsés ötlet ezt a honlapot valamelyik egyetem szerverének egyik sarkában tartani, főleg ami a domain-nevét illeti. Az



ϵ

eredeti elképzelés, hogy www.g-raph.com néven szerepeljen, (a fejlesztés egyelőre a www.graph.co.cc címen követhető) és az egyik legfontosabb terv a továbbiakra egy erős keresőoptimalizálás az olyan kulcsszavakra mint például gráfelmélet, mélységi bejárás, szélességi bejárás, satöbbi. Elvileg néhány oktatási intézmény megengedhetné magának, hogy fenntartsa, de mivel kéregetni csúnya dolog, ezért a reklámozás mellett döntöttünk. Nem szeretnénk azonban olyan szánalmas honlapot, ahol a két rész (reklám és tartalom) szinte teljesen szétválik, ezért egy ritkább és különlegesebb módszert vezettünk be, ami a reklámokat illeti. Néhány szöveg úgy lett megírva, hogy egyes részei kicserélhetőek legyenek bármire. Például a felhő, ahol „Monsieur Godot” messenger státusa látható, átírható lesz. Ha jön majd egy „Pepsi” rajongó, és látja, hogy a világ jövendőbeli informatikusai nap mint nap azt látják ott, hogy „addig is igyál Coca Cola-t”, egy bizonyos összegért cserében átírhatja azt. Mindenképpen érdekes kísérlet lesz, miután elkezdenek érkezni a látogatók, hogy milyen összegig mennek majd fel a reklámokkal. A terv az, hogy az első átírás egy dollárba fog kerülni, a következők pedig mindig eggyel többe. Hogy az előbbi példánál maradjunk, a „Coca Cola” a két dolláros „Pepsi” feliratot három dollárért cserélheti le, majd az övét valaki más négyért. A befolyt összeg természetesen a szerverekre, domain-névre, kereső optimalizálásra, további fejlesztésekre és a rászoruló zsiráfokra lesz költve.

VII. Következtetések, további tervek Úgy gondoljuk, hogy ez a honlap egyaránt nyújt majd segítséget és szórakozási lehetőséget azoknak, akik valamilyen formában szeretnének jobban megismerkedni a gráfelmélet szépségeivel. Bár sikerült lefedni minden alapdolgot a tantárgy elsajátításához, az alkalmazás használata inkább csak segédeszközként ajánlott, mert megkönnyíti ugyan a látottak megértését és felfogását, de nem helyettesíthet egy tanárt, hisz még a kérdéseidre sem tud válaszolni.



ϭϬ

VIII. Könyvészet [1] Kátai Zoltán: Gráfelméleti algoritmusok (Algoritmica grafurilor), Editura Scientia, ClujNapoca, 2008, ISBN 978-973-7953-95-7, [2] Kátai Zoltán: Algoritmusok felülnézetből (Algoritmi – o proiecţie orizontală), Editura Scientia, Cluj-Napoca, 2007, ISBN 978-973-7953-74-2, [3] Tóth László: Algo-ritmika, 2008, Sapientia EMTE

[4] Burger Szilárd: Didaktikai kiértékelés egy informatizált világban, 2007, Sapientia EMTE



ϭϭ