Háromszögdiagrammal definiált feladatok megoldásstruktúráinak generálását támogató szoftver fejlesztése Szerző: Éles András, Mérnökinformatikus Mesterszak, II. évfolyam Témavezető: Dr. Bertók Botond, egyetemi docens Munka helyszíne: PE-MIK, Rendszer- és Számítástudományi Tanszék A gyakorlatban találkozhatunk olyan problémákkal, melyek lényege háromkomponensű elegyek megfelelő arányú keverése és szétválasztása. Ide tartozik például az azeotrópos desztilláció egy lehetséges megvalósítása is. Ilyen feladatokban egy háromszögdiagramot használhatunk a gyártás során előforduló anyagösszetételek és technológiai lépések reprezentációjára. Ez egy geometriailag is értelmezhető, egyszerre diszkrét és folytonos jellegű matematikai problémához vezet, melyben a végső cél a technológiai lépések, berendezések összekapcsolásának új, eddig ismeretlen módjait, megoldásstruktúrákat felfedezni. Elkészült egy szoftver, mely kellően általános választ ad a feladatra. Két fő részből áll: egy beágyazott
MILP
(Kevert
Egészértékű
Lineáris
Programozási)
modellből
és
egy
megoldásstruktúra-generáló keretalgoritmusból. A MILP modell egy GNU MathProg nyelven írt kód, mely akár önmagában is alkalmas bizonyos megoldások keresésére. Megfogalmazza a technológiai lépések során az anyagok összetételére tett algebrai korlátozásokat, az anyagáramok működését és a berendezések összekapcsolását egy linearizált modellben. A keretalgoritmus egy egyedi eljárást implementáló, Qt platformon készült C++ program, melynek feladata, hogy az összes lehetséges struktúrát egymás után, szisztematikusan előállítsa és ellenőrizze azok helyességét a MILP modell segítségével. A talált megoldásokat a szoftver képes jól átlátható vizuális formában is megjeleníteni. Két esettanulmány készült az eredmények demonstrációjára, mindkettő víz és etanol elegyének szétválasztása tiszta komponenseire az azeotrópos desztilláció módszerével, egyik esetben toluol, másik esetben benzol, mint harmadik komponens hozzáadásával. Kulcsszavak: háromszögdiagram, azeotrópos desztilláció, MILP modell, struktúra-generálás, GNU MathProg, C++
Megoldó algoritmus készítése egy japán logikai játékhoz Szerző: Kun Laura, Farkas Máté, Baranyai Márk, elsőéves BSc hallgatók Témavezető: Orosz Ákos, PhD hallgató Munka helyszíne: Jedlik Ányos Szakkollégium Napjainkban rengeteg olyan logikai játékkal találkozhatunk, amelyek Ázsiából származnak. Ezeknek a logikai játékoknak különböző nehézségi fokozataik léteznek, melyek közül a nehezebbek megoldása a tapasztalt fejtők számára is fejtörést okoz.
Az ismertebb
feladványok számítógépes úton történő megoldása már nem ismeretlen feladat a programozók számára. A Japánból származó, fillomino nevet viselő játék a kevésbé ismert feladatok körébe tartozik. A játék lényege, hogy bizonyos szabályok alapján teljesen feltöltsünk egy négyzethálót, melyben néhány helyen előre megadott számok vannak elhelyezve általában 1-től 9-ig. A különböző, egymással szomszédos számok vonallal vannak elválasztva, amelyek a megfejtésben kis szigeteket alkotnak. Egy sziget négyzeteibe írt szám azt mutatja, hogy mennyi négyzetből áll. Szakmai munkánk célja egy, a fillomino rejtvények megoldására képes algoritmus megtervezése és megvalósítása. Az első lépés a feladat megismerése és a stratégiák megalkotása. A stratégiákat értékeltük, figyelembe véve, hogy a megvalósításuk mennyire komplex. A másik szempont a várható hatékonyság volt a megoldási folyamatban. Ezek a stratégiák különböző információkat tudnak meghatározni a megoldásról, ezért az iteratív használatuk jó eséllyel megoldja a közepes nehézségű pályákat is. Természetesen az ügyes stratégiák nem tudnak minden feladványt megoldani önmagukban. A megoldás hiányzó részének meghatározásához próbálgatást kell alkalmazni az ilyen feladatoknál már ismert backtrack algoritmus segítségével. Ez biztosítja, hogy megoldható rejtvényekre mindig találjunk megoldást. Kulcsszavak: fillomino, logikai játék, backtrack, megoldó algoritmus, következtetések
A hitel és pénz körforgásának szimulálása Szerző: Rozmán Ádám, Mérnökinformatikus B.Sc. III. évfolyam Témavezető: Dr. Heckl István, egyetemi Docens Munka helyszíne: PE-MIK, Rendszer és Számítástudományi Tanszék Munkám célja az volt, hogy megvizsgáljam egy gazdasági szimulációs szoftver megalkotásának lehetőségét, mely a pénz és a hitel körforgásának szimulálásával foglalkozik. A feladat elvégzése során 2 hallgatótársammal együtt elkészítettünk egy demóprogramot, amely bemutatja egy kezdetleges modellező programtól elvárt funkciókat, illetve a programhoz tartozó dokumentációt és a szoftver kezeléséhez szükséges útmutatót. A szimulációs segédprogram emberek, cégek és a bankrendszer kapcsolatát mutatja be egyszerű matematikai háttérszámításokkal és az eredményeket egy modern grafikus kezelőfelületen reprezentálja a felhasználónak. A szoftver havi bontásban képes szimulálni tranzakciókat az egyes entitások között és lehetőséget biztosít a felhasználó számára, hogy mentse vagy személyre szabja a szimulációs profilokat vagy exportálja széles körben felhasználható fájlformátumba a nyers adatokat későbbi vizsgálat céljából. A szoftver elkészítéséhez Java technológiákat használtunk fel, melyek jelentőségét részletesen bemutatom szakmai munkámban. A dolgozatomban bemutatásra kerülnek irodalmi példák kifejezetten gazdasági szimulációval foglalkozó szoftverekről és szoftverbővítményekről, valamint programokról melyek működésük során alkalmaznak szimulált gazdasági rendszert. Munkámban kifejtem milyen megközelítéssel lehetne széles körben használhatóvá tenni a létrehozott szimulációs demoprogramot . Kulcsszavak: Szimuláció, Java, GUI
Elosztott mozgásdetektálás és analízis szenzorhálózati eszközökön Szerző: Orbán Gyula (programtervező informatikus BSc. III. évfolyam) Témavezető: Zachár Gergely, PHD hallgató Munka helyszíne: PE Műszaki Informatikai Kar, Rendszer- és Számítástudományi Tanszék A szenzorhálózatok térnyerése az informatikai eszközök méretbeli és fogyasztásbeli csökkenésével együtt valósult meg. Napjainkban széles körben használják őket az okos házaktól kezdve az egészségügyön át az űrkutatásig. A szenzorhálózatokat több eszköz, un. mote alkotja. Ezek az önálló működésre képes, egymással rádiófrekvencián kommunikáló mikroszámítógépek különféle szenzorokat (például hőmérséklet, páratartalom, fényerősség, gyorsulás) tartalmaznak. Több eszköz együttműködésével, és ezáltal több érzékelő segítségével nem csak redundáns, hanem összetettebb mérések is elvégezhetőek. Tudományos munkámban a beltérben különböző pontokra elhelyezett szenzorhálózati eszközöket és az azokon található fényérzékelőket használom, melyek segítségével lehetőség nyílik az összetett mozgásdetektálásra, valamint a világítási viszonyok folyamatos megfigyelésére. A kapott adatok segítségével például intelligens- és előreprogramozott eszközökkel rendelkező házak energiafogyasztása optimalizálható. A dolgozatban először ismertetem a szükséges irodalmi hátteret, majd az elkészült mérőrendszert, végül bemutatom a mért adatokat alapján mozgásdetektálásra alkalmas szoftvert valamint annak felépítését. Kulcsszavak: szenzorhálózatok, jelfeldolgozás, mozgásdetektálás
Virtuális múzeumok színhelyességének vizsgálata Szerző: Barta Éva Anna, Hajgató Anita Gabriella, Hruby Dániel Témavezető: Szücs Veronika, PhD. hallgató Munka helyszíne: Pannon Egyetem, Villamosmérnöki és Információs Rendszerek Tanszék, Alkalmazott Multimédia Laboratórium A tapasztalat azt mutatja, hogy a valóságos műalkotások és virtuális másuk gyakorlatban erőteljesen eltér egymástól. Munkánk célja ennek a különbségnek a feltérképezése. Ennek érdekében különböző méréssorozatokat terveztünk és végeztünk el a kiválasztott műalkotásokon és digitális reprodukcióikon. Valós képek jellegzetes színeinek, képrészleteinek spektrális elemzését végeztük el. Különböző böngészőkben megjelenített digitális reprodukciókon hajtottunk végre egy méréssorozatot, valamint nyomtatott és eredeti festményeken végeztük el a színtani méréseket. A méréseket Photo Research PR-705 SpectraScan System’s spektro-koloriméterével végeztük el, 2 nanométeres lépésközzel 380 nanométer és 780 nanométer közötti hullámhossz tartományban. A mérési adatok feldolgozását követően beigazolódott a kezdeti feltevésünk, amelyben azt állítottuk, hogy a böngészők különböző módon jelenítik meg a műalkotások digitális reprodukcióit. Távolabbi célunk egy olyan algoritmus kidolgozása, mely a virtuális világ színhelyes megjelenítését, színminőségi jellemzőit javítja. Ehhez szintén a mérések kiértékelése során szerzett tapasztalatainkat használjuk fel. Kulcsszavak: virtuális múzeumok, műalkotások, internet, színhelyes megjelenítés
Nyílt forráskódú lineáris optimalizáló kernelek teljesítményanalízise Szerző: Böröcz Péter, Mérnökinformatikus Msc. I. évfolyam Témavezető: Dr. Maros István, professor emeritus Munka helyszíne: PE-MIK, Rendszer és Számítástudományi Tanszék Napjainkban már megbízható algoritmusok állnak rendelkezésre nagyméretű lineáris programozási problémák megoldására, de futási sebességük még mindig kulcsfontosságú tényező. A megoldók hatékonyságát jelentősen befolyásolják a használt adatszerkezetek. A megfelelő adatszerkezetek implementációja nem triviális. Mivel nagy mennyiségű lineáris algebrai művelet kerül elvégzésre a megoldás során, így a rendelkezésre álló adatszerkezetek teljesítményanalízise értékes segítséget nyújthat a hatékonyság növeléséhez. Munkánk
során
összehasonlítottuk
ritkás
adatszerkezetek
több
nyílt
forráskódú
implementációját, illetve saját kernelünket a Blazemark rendszerre épülő saját fejlesztésű elemzőszoftverünk segítségével. Célunk azon kulcsfontosságú tényezők feltárása, amelyek döntő szerepet játszanak az implementációk különböző műveleteinek teljesítményében. Ismertetjük a ritkás lineáris algebrai adatszerkezeteket és műveleteket, valamint azok tulajdonságait és sajátosságait. Kitérünk továbbá ezek hagyományos, sűrű adatszerkezeti változataiktól való különbségére is. Bemutatjuk a Blazemark felépítését, amely lehetővé teszi különböző lineáris algebrai könyvtárak műveleteinek hatékonyság szempontjából való összehasonlítását. Bemutatjuk saját szoftverünk, a BlazemarkAnalyser felületét és működését, kiemelve az adatszerkezetek elemzésére, valamint műveleteinek profilozására szolgáló funkciókat. Ismertetjük, hogy méréseink alapján mik azok a kulcsfontosságú tényezők, amelyek döntő szerepet játszanak az implementációk hatékonyágában, mint például a cache, vagy a processzor speciális utasításainak kihasználásra. Prezentáljuk eredményeinket és az ezekből levont
következtetéseinket,
illetve
az
ezek
felhasználásával
kifejlesztett
saját
adatszerkezeteinket. Végül összehasonlítjuk új kernelünk teljesítményét más nyílt forráskódú lineáris optimalizáló szoftverek kerneljeinek teljesítményével. Kulcsszavak: Lineáris programozás, lineáris algebra, ritkás adatszerkezetek, szimplex algoritmus
A Bloch-gömb általánosítása q-tritekre és egyéb többállapotú rendszerekre Szerző: Mód Barnabás, Villamosmérnöki B.Sc. III. évfolyam Témavezető: Dr. Gurin Péter, adjunktus Munka helyszíne: PE-MK, Fizika- és Mechatronika Intézet A kvantuminformatika alapegységét kétállapotú rendszerek – úgynevezett qbitek – képezik. Ha egy kvantumfizikai rendszer zárt, leírható a hullámfüggvényével, ha azonban kölcsönhatásba léphet a környezetével, esetleg össze is tud fonódni vele, akkor nem
lehet
a
hullámfüggvényt
alkalmazni,
ehelyett
a
sűrűségoperátorukkal
jellemezhetőek ezen nyílt rendszerek. Egy qbit sűrűségoperátora reprezentálható az úgynevezett Bloch-gömb pontjaival. Szakmai munkám a Bloch-gömb három-, illetve többállapotú rendszerekre történő általánosításával foglakozik. A munkám során megvizsgáltam, hogy a Bloch-gömb által reprezentált sűrűségoperátor kifejezésében található Pauli-mátrixok együtthatóinak milyen követelményeknek kellett eleget tenniük, melyek a Bloch-gömb szokásos definíciójához vezetnek. Ezen követelményeket alapul véve meghatároztam, hogy a 3, illetve az n állapotú rendszerek sűrűségoperátorai esetében az SU(3), illetve SU(n) csoportok generátorait alkotó mátrixokat bázisnak választva, ezen mátrixok együtthatóira milyen megszorítások vonatkoznak. Ezek után megállapítottam, hogy a 3, illetve több dimenziós rendszerek sűrűségoperátorai milyen matematikai objektumokkal reprezentálhatóak és ezen objektumok milyen tulajdonságokkal rendelkeznek. Kulcsszavak: Sűrűségoperátor, Bloch-gömb, qbit
A szimplex algoritmus degeneráció-kezelésének vizsgálata Szerző: Stágel Bálint Marcell, mérnökinformatikus MSc I. évf. Témavezető: Dr. Maros István, Rendszer és Számítástudományi Tanszék Konzulens: Tar Péter, Rendszer és Számítástudományi Tanszék Munka helyszíne: PE-MIK, Operációkutatási Kutatólaboratórium A lineáris programozás(LP) az optimalizálás kiemelkedő jelentőségű területe, mind önmagában, mind más nem-lineáris feladatok megoldása során gyakran alkalmazott módszer. Lineáris programozási feladatok megoldására két algoritmus-család létezik: a belsőpontos módszerek, illetve a pivotalgoritmusok. Mi munkánk során ez utóbbiba tartozó szimplex módszerrel foglalkoztunk. Ezen iteratív eljárás szomszédos bázisokon halad keresztül az n dimenziós térben az optimum megtalálásáig. Minden iterációban szükséges egy pivotelem meghatározása, amely kritikus szerepet tölt be az algoritmusban, nagyban befolyásolja az optimális megoldás megtalálásához szükséges iterációszámot és megoldási időt, valamint az algoritmus konvergenciáját. A pivotválasztás egy szofisztikált szabályrendszer alapján történik, amelyben az alapvető előrehaladást biztosító feltételek mellett egyéb szempontokat is figyelembe vehetünk, így egy nagyon komplex pivotalgoritmust kapunk. Munkánk során a szimplex algoritmus primál és duál változatát mind elméleti, mind implementációs szinten megvizsgáltuk, fókuszban a különböző numerikus kihívásoknak ellenálló, hatékony pivotalgoritmus megalkotásával. Kiemelt figyelmet fordítottunk a degeneráció kezelésére, mivel az jelentős mértékben hátráltathatja a megoldást. Az általunk megvizsgált eljárásokra általában jellemző, hogy nagyon érzékenyek az implementációra, így kis változtatások magasabb szinten teljesen más bázisokhoz vezethetnek. Ebből következően ezen technikák szakszerű vizsgálata a hatékony megvalósítása érdekében elengedhetetlen. A különböző eljárások kombinálhatósága újabb kérdéseket vet fel, nagyon körültekintőnek kell lennünk ezek együttes alkalmazása során. Jelen dolgozatban bemutatjuk az általunk megvalósított technikákat, a megvalósítás körülményeit, végül pedig a megvalósítás validálására elvégzett számítási vizsgálat eredményeit. Kulcsszavak: Lineáris programozás, szimplex algoritmus, degeneráció
