1. alszekció a helyezések megjelölésével
Számítástudomány
Bárány Vince
Feltörhető kifejezések a lambda‑kalkulusban
Eötvös Loránd Tudományegyetem
Témavezető: dr. Csörnyei Zoltán
A lambda-kalkulus az egyik legegyszerűbb formalizmus, amely számítási modellként is szolgál. Szemantikájának központi fogalma a megoldhatóság, illetve a megoldhatatlanság, amely számos „szép” tulajdonsága folytán alkalmas a jelentéstelenség definiálására. A megoldhatatlanság ezen tulajdonságai több kutatót arra késztettek, hogy általánosabb környezetben is vizsgálják a jelentéstelenség problémáját.
Engem elsősorban az érdekel, hogy hogyan lehet a lambda-kifejezések megoldható – megoldhatatlan osztályozását tovább finomítani. Kiindulásként azt a kérdést tettem fel, hogy mennyire megoldható egy kifejezés. A kérdés értelmezésének egy módja, ha azt vizsgáljuk, legkevesebb hány argumentumra van szükség egy kifejezés megoldásához. Azt találtam, hogy a megoldható kifejezések két csoportba sorolhatók aszerint, hogy van-e megoldásuk a triviálisnál eggyel kevesebb argumentummal, vagy sem. Az előbbieket feltörhetőnek (breakable), a megoldásukat a triviálisnál eggyel kevesebb argumentummal feltörésnek nevezem, utalva ezzel egy ilyen megoldás megtalálásának tapasztalt nehézségére. Dolgozatomban a feltörés mint probléma nehézségét vizsgálom. A feltörhetőségnek a különböző szintaktikai átalakítások alatti invarianciáját, valamint a kapcsolatát a Böhm-fákkal vizsgálva adódik néhány szerény eredmény, de a feltörhető kifejezések teljes szintaktikus karakterizációja további kutatást igényel.
Belényesi Viktor – Németh Cs. Dávid
d-bonyolultság meghatározása
Eötvös Loránd Tudományegyetem
Témavezető: dr. Iványi Antal
Adott ábécé feletti szavak egyik gyakran vizsgált bonyolultsági mértéke - melyet M. Heinz vezetett be - a különböző részszavak száma. Egy másik lehetőség a különböző részsorozatok száma. Mindkét definíció származtatható a d-bonyolultságból, melyben azokat a különböző részsorozatokat vizsgáljuk, melyek szomszédos betűi a vizsgált szóban legfeljebb d távolságra vannak egymástól. Ez a fogalom 1987-ben, az Annales/Sectio Computatorica egyik cikkében jelent meg. A fogalom alapja a természetben szereplő „szavak” térbeli szerkezete: a d paraméter értéke a szóból elhagyható hurkok maximális hossza.
Donald E. Knuth A programozás művészete című könyvsorozatának negyedik kötetében (a kötet kézirata a szerző honlapjáról letölthető) részletesen tárgyalja a témánkhoz szorosan kapcsolódó - tökéletes sorozatokkal és a tökéletes kétdimenziós mátrixokkal kapcsolatos - eredményeket.
Az általános esetben még az is nyitott kérdés, hogy mennyi időre van szükség adott szó d-bonyolultságának meghatározásához.
A dolgozat ennek a problémának a megoldására javasol két algoritmust: az egyik minden esetben alkalmazható, míg a másik csak a részsorozat-bonyolultság meghatározására. A dolgozatban leírt algoritmusok a gyakorlatban is megvalósíthatók és az előadáshoz kapcsolódó bemutatóban nagy szerephez jutnak.
Ezen programok lényeges segítséget jelentettek például a következő probléma vizsgálatában: milyen kapcsolat van adott hosszúságú szivárványszavak (ezek minden betűje különböző), maximális bonyolultságú bináris szavak és véletlen bináris szavak bonyolultságai között?
Kertész-Farkas Attila
Véges nyelvek tömör reprezentációja nemdeterminisztikus automatákkal
Szegedi Tudományegyetem
Témavezetők: dr. Fülöp Zoltán, Kocsor András
Az automaták széles körű elterjedésének egyik legfontosabb okát a könnyű implementálhatóságuk jelenti. Egy véges nyelv eldönthetőségére több, egymással ekvivalens automata konstruálható, de a gyakorlatban használt rendszerek esetén a szűkös memóriakorlátok miatt a lehető legkisebb méretű automatát célszerű megkonstruálni.
Ebben a dolgozatban véges nyelveket reprezentáló automaták tömörítési algoritmusaival foglalkozunk. Automata tömörítési algoritmuson egy olyan algoritmust értünk, amelyik egy A (nem feltétlenül determinisztikus) automatából kiindulva megkonstruál egy A-val ekvivalens nem feltétlenül determinisztikus, de kisebb helyen tárolható automatát.
Az automatákat reprezentálhatjuk pointerekkel, szomszédsági mátrixokkal, továbbá átmenetmátrixokkal is. A legkisebb méretű adatszerkezetet akkor kapjuk, ha az állapotokat és az azokhoz tartozó átmeneteket vektorokkal tároljuk. Ezek mérete egyenesen arányos az átmenetek és állapotok számával (George Anton Kiraz, 1999). Ha a tömörítés az állapotok és az átmenetek számát is figyelembe veszi, akkor kisebb méretű ekvivalens automatát kapunk.
Amilhastre és Janssen (1999) egy olyan automatát tömörítő algoritmust javasol, amely csak olyan automatákon működik, amelyek csupa azonos hosszú szavakból álló véges nyelveket ismernek fel. Az ilyen automaták gráfján szintek határozhatók meg. Megadnak egy technikát a k és a k+1-edik szint által meghatározott páros részgráf biklikk lefedésére, amely alapján állapotok összevonása végezhető. Jelentős hátránya azonban, hogy bizonyos esetekben az állapotok összevonásakor további élek is keletkezhetnek, így számos esetben a tömörített nemdeterminisztikus automata mérete nagyobb lett, mint a vele ekvivalens minimális determinisztikus automatáé.
A dolgozatban saját eredményként bemutatunk egy olyan újszerű tömörítési algoritmust, amely kiterjeszti az előző módszert úgy, hogy tetszőleges véges nyelvet felismerő automatán működik. Az algoritmus az állapotok és átmenetek összegének száma szerint tömörít, és garantálja, hogy az eredmény mérete nem lesz nagyobb, mint a minimális determinisztikus automatáé, sőt a teszteredmények szerint 10-25%-os méretbeli csökkenés volt elérhető.
III. helyezett: Kovács Annamária
Fuzzy csoportosítási eredmények megjelenítése módosított Sammon-leképezéssel
Veszprémi Egyetem
Témavezető: dr. Abonyi János
Napjainkban rohamosan növekszik a rendelkezésre álló adatok mennyisége, ezért gyakran nagy dimenziójú adatsorokat kell csoportosítani. Ebben az esetben a csoportosítás eredménye is sokdimenziós, amiből nehéz következtetéseket levonni, illetve elemezni azt. A csoportérvényességet jellemző számítások egy lehetőséget adnak ezen probléma megoldására, viszont ezek alkalmazása a nagy adatsort jellemző és a csoportok paramétereit hordozó információkat egyetlen számértékbe csökkenti. A csoportok kis dimenziójú megjelenítése ennél jóval több információt nyújthat, ezért munkánkban egy – a csoportosítási eredmények ábrázolására szolgáló – új eszközt szeretnénk bemutatni.
A kidolgozott módszer az adatelemzésben széles körben alkalmazott változó transzformációs módszeren, a Sammon-leképezésen alapul. Ez a nemlineáris leképező algoritmus az eredeti változókat kevesebb változóba vetíti le, miközben megőrzi az adatok belső struktúráját. Ezt úgy valósítja meg, hogy – az eredeti nagy ( n)-dimenziójú adatokat N pontba leképezve az alacsonyabb (q)-dimenziós térbe – megőrzi az adatpontok közötti távolságot. Célja tehát az, hogy az adott pontok közötti távolság a (q )-dimenziós térben a legjobban közelítse az ugyanazon pontok közötti távolságot az (n)-dimenziójú térben. Ebből következően az algoritmusnak nagy számítási igénye van, minden iterációs lépésben N (N−1)/2 távolságot kell kiszámolni. Nagy számú adatpontra ( N) ezért a Sammon-leképezés alkalmazása nem hatékony. Ezen probléma elkerüléséhez módosítottuk a Sammon-projekciót. A fuzzy csoportosítási módszerek alaptulajdonságait felhasználva az új eszköz a csoportközéppontokat és az adatpontokat képezi le úgy, hogy a csoportok és az adatpontok közötti távolságot őrzi meg. Az iteratív leképezés során az algoritmus az adatok tagsági értékeit használja fel és a csoportosítási algoritmus célfüggvényét minimalizálja. Ezzel a módszerrel megfelelő csoportformákat kapunk eredményül, és az eredeti Sammon-leképezéssel összehasonlítva a számítási igény is jelentősen lecsökken. A kidolgozott eszköz alkalmazását számos adatsoron bemutatva látható, hogy kiváló eredményeket ad a lineáris leképezési módszerrel (főkomponens elemzés) és a klasszikus Sammon-leképezéssel szemben.
Kovács Gábor Zsolt – Pataki Norbert
Rangsorolási algoritmusok
Eötvös Loránd Tudományegyetem
Témavezető: dr. Iványi Antal
Dolgozatunkban a rendezés egy lehetséges általánosítását vizsgáljuk: adott n darab objektum és ezeket szeretnénk rangsorolni. Az objektumokat páronként összehasonlítjuk, és a kapott pontszámok összege alapján rangsoroljuk.
A témakörnek nagyon gazdag irodalma van abban az esetben, ha az összehasonlítás lehetséges eredményeinek halmaza S = {1:0, 0:1}. Ebben az esetben az eredmények ábrázolhatók egy irányított teljes gráffal (tournament). Az eredmények egy része átvihető a k-teljes esetre, amikor S = {0:k, 1:k-1, 2:k-2, …, k:0}, valamint az (a, b)-teljes esetre, amikor a kiosztott pontszámok összege minden összehasonlításnál a és b közé esik, és minden kiosztás megengedett.
Dolgozatunkban a probléma egyik, úgynevezett hiányos esetét vizsgáljuk, amelyben S = {0:3, 1:1, 3:0,}, ami megfelel a fociban használt módszernek.
A dolgozat három fő részből áll: sorozatok ellenőrzése, helyreállítása és leszámlálási problémák. Az ellenőrzési részben a feladat annak eldöntése, hogy adott sorozat lehet-e a fenti rangsorolás eredménye. A helyreállítás során a cél legalább egy, a jó sorozatokhoz tartozó pontmátrix megtalálása. A leszámlálási részben a vizsgált halmazok elemszámát határozzuk meg.
Fő eredményeink:
· ellenőrző, helyreállító és leszámláló algoritmusok futási idejének elemzése;
· algoritmusok megvalósítása (Delphi és MatLab);
· az elméleti úton kapott leszámlálási eredmények és a szimulációs eredmények együttes elemzése.
Lengyel Zoltán
Logikai normálformákat előállító algoritmusok
Debreceni Egyetem
Témavezető: dr. Várterész Magda
Az 1950-es években az elektronikai alkalmazások kapcsán került a logikai normálformák előállításának és egyszerűsítésének problémája előtérbe. Az 1950–70-es években az elektronikus berendezések tervezése funkcionálisan teljes művelethalmazokat realizáló funkcionális elemek segítségével történt.
Napjainkban az informatika több kutatási területén is szükség van a logikai formulákat normálformákká alakító algoritmusokra. Vannak informatikai problémák, melyek formulákkal megfogalmazva logikai eszközökkel jól kezelhetőek, és vannak, melyek tárgyalásához elengedhetetlen valamely normálforma használata. Ilyen területek például a kriptográfia, az automatikus tételbizonyítás, logikai programozás, szakértői rendszerek.
A tanulmányban logikai normálformákat egyszerűsítő módszereket és ezekhez kapcsolódó algoritmusokat gyűjtöttem össze. Ezek a következők:
· Logikai formulát konjunktív, illetve diszjunktív normálformára alakító eljárás, amely elengedhetetlen a további algoritmusok működéséhez.
· Triviális algoritmus: a legegyszerűbb algoritmus, ugyanakkor hatékonyságát tekintve a gyakorlatban használhatatlan. Ennek ellenére fontos megemlíteni, mert a többi eljárás erre építkezik.
· Az egyszerűsített diszjunktív normálformák fontos szerepet töltenek be a diszjunktív normálformák minimalizálása során, ezért az ilyen normálformákat kialakító algoritmusok közül kettőt is elemeztem: a Blake-módszert, amely tetszőleges diszjunktív normálformára alkalmazható, illetve a McCluskey-féle algoritmust, amely csak speciális normálformákat tud kezelni.
· A diszjunktív normálformákat egyszerűsítő algoritmusok közül kettőt ismertetek, melyek tetszőleges diszjunktív normálformákra alkalmazhatóak, de általában egyszerűsített diszjunktív normálformákra alkalmazzuk.
A hatékonyságvizsgálatok során gyűjtött tapasztalatok azt mutatják, hogy minél később kerül sor a lehetséges normálformák végigpróbálgatására, annál hatékonyabb az algoritmus. Ez a lépés azonban nem küszöbölhető ki teljes mértékben, bizonyos leszűkítés mellett már sokkal hatékonyabb a próbálgatás, mint a további szűkítés.
I. helyezett: Muzamel Lóránd
Termek feletti felismerhető-reducibilis relációk
Szegedi Tudományegyetem Természettudományi Kar
Témavezető: dr. Fülöp Zoltán
A dolgozatban termátíró rendszerekre és átcímkéző fatranszformátorokra vonatkozó eldönthetőségi kérdésekkel foglalkozunk. M. Dauchet és S. Tison The Theory of Ground Rewrite Systems is Decidable című munkáját követve ismertetjük a felismerhető-reducibilis reláció (RR-reláció) fogalmát. Az RR-relációk valamely Σ rangolt ábécé feletti termek feletti relációk.
Megmutatjuk, hogy az RR-relációk jó zártsági és eldönthetőségi tulajdonságokkal rendelkeznek, majd ezt felhasználva megmutatjuk, hogy az RR-relációk valamennyi olyan tulajdonsága eldönthető, amely leírható elsőrendű logikai formulával. Megmutatjuk, hogy minden R ground termátíró rendszer esetén mind az egylépéses Þ R, mind ennek a Þ *R reflexív tranzitív lezártja RR2-reláció. Ebből következik, hogy tetszőleges ground termátíró rendszerről eldönthető, hogy konfluens-e, mivel ezen tulajdonság közismert módon leírható egy elsőrendű formulával. Ezen munka során pontosítjuk a fent idézett cikkben bevezetett fogalmakat, kiegészítjük és példákkal látjuk el a konstrukciókat és a bizonyításokat.
A dolgozat második, inkább önálló munkának tekinthető részében olyan további t fatranszformációkat találunk, melyek RR-relációk. Ehhez először kiterjesztettük az RR-reláció fogalmát különböző rangolt ábécék feletti GRR-relációkká. Megállapítottuk, hogy GRR-relációkra ugyanúgy építhető logika, mint RR-relációkra, feltéve, ha típusolt (heterogén) logikát alkalmazunk. Igazoltuk, hogy tetszőleges F GRR-formula és A GRR-struktúra esetén eldönthető, hogy A kielégíti-e F-et. Megmutattuk, hogy minden M=(Q, S, D,F,R) átcímkéző fatraszformátor átmeneti relációja GRR reláció . Ezen eredményből következik, hogy az átcímkéző fatranszformációk (fatranszformátorok) minden elsőrendű logikai formulával kifejezhető tulajdonsága eldönthető. Többek között effektíven eldönthető az átcímkézők ekvivalencia problémája, vagyis, hogy tetszőleges M1 és M2 átcímkéző fatranszformátorok ugyanazt a fatranszformációt indukálják-e, mivel ez a tulajdonság leírható egy heterogén elsőrendű formulával.
Észrevesszük, hogy ugyanez mondható el az alakmegőrző felszálló fatranszformációk elsőrendű logikai formulával kifejezhető tulajdonságairól is, mert Fülöp Zoltán és Gazdag Zsolt [FG02]-ben bebizonyította, hogy az alakmegőrző felszálló fatranszformációk osztálya megegyezik az átcímkéző fatranszformációk osztályával..
Végül a lineáris, permutáció mentes, betű-betű leszálló fatranszformátorokat és azoknak egy módosítását vizsgáljuk, amelyek az átcímkézőknél valamivel többet tudnak és bebizonyítjuk, hogy a módosított lineáris, permutáció mentes, betű-betű fatranszformációk is GRR-ben vannak, azaz bármely elsőrendű tulajdonságaik effektíven eldönthető.
Roszik János
Visszatérő igényeket tartalmazó számítógéprendszerek matematikai modellezése
Debreceni Egyetem
Témavezetők: dr. Almási Béla, dr. Sztrik János
A visszatérő igényeket tartalmazó véges forrású sorban állási rendszerek vizsgálatát a gyakorlati életbeli problémák tették szükségessé pl.: CSMA/CD protokoll alapú helyi hálózatok, mágneslemezes memóriák, celluláris mobil rendszerek.
A dolgozat célja a már többek által vizsgált homogén modell általánosítása heterogén forrásokra, vagyis amikor minden igényt saját intenzitások jellemeznek. A szokásos rendszerjellemzők megadásához a rendszer működését leíró Markov-lánc stacionárius eloszlására van szükségünk, melyet egy már létező programcsomag alkalmazásával nyerünk.
A dolgozatban a matematikai modell megadása után bemutatásra kerül az Erlangeni Egyetemen kifejlesztett MOSEL nyelv és a hozzá tartozó programcsomag, amihez az általam elkészített szoftver ad egy magasabb szintű felületet ilyen típusú rendszerek modellezésére. Bemutatom, hogyan kaphatjuk meg e szoftver segítségével a vizsgált rendszer jellemzőit, valamint azt, hogy hogyan vizsgálhatjuk meg az egyes paraméterek változásának a rendszerre gyakorolt hatását. Ezek a vizsgálatok az analitikus eredményeken alapuló, grafikonon történő ábrázolás segítségével jól elemezhetőek.
A dolgozat újdonsága a heterogén, több kiszolgálós, visszatérő igényeket tartalmazó sorban állási rendszer modellezése. A feladat nehézsége abban rejlik, hogy a leíró nyelv segítségével meg tudjuk fogalmazni a rendszer működését. Ezt követően a heterogén rendszerekre fel kell írni a rendszerjellemzőkre érvényes összefüggéseket. Végül a grafikus megjelenítéseket a program megfelelő moduljának felhasználásával hajtjuk végre.
zsűri dicséret: Sárközi Norbert
Univerzális számítógépes eszközök hálózatszintézis feladatok megfogalmazásához és folyamatstruktúráinak generálásához
Veszprémi Egyetem
Témavezető: Bertók Botond
A folyamathálózatok szintézisére számos módszer áll rendelkezésünkre. Noha ezek a módszerek szisztematikusak vagy akár algoritmikusak is, különféle feltevésekkel élnek a feladat megfogalmazása és/vagy megoldása során, ami e módszerek használhatóságát nagyban korlátozza.
Jelen munkánkban egy univerzális nyelvet vezetünk be folyamatszintézis feladatok formális megfogalmazásához. Ezen felül, egy általános keretalgoritmust is ajánlunk a feladatokat kielégítő folyamatok lehetséges struktúráinak kimerítő és algoritmikus generálására, amelyben semmilyen feltevéssel nem élünk.
Kezdetben, a folyamatban szereplő anyagáramok releváns tulajdonságait adjuk meg, mint például hőmérséklet, nyomás stb. Ennek eredményeképp az anyagáramok egyedi, többdimenziós ábrázolását kapjuk. A vizsgált folyamat be- és kimeneteit, tehát a nyersanyagokat és termékeket, valamint a lehetséges műveleti egységek be- és kimeneteit a tulajdonságaik megengedett értékeinek tartományával határozzuk meg, mint például az összetételek halmazával, hőmérséklet- vagy nyomásintervallumokkal. Ez teszi lehetővé a különböző típusú lehetséges műveleti egységek szisztematikus azonosítását a be- és kimeneteik tulajdonságainak megengedett tartománya szerint, valamint gyorsan és automatikusan annak a meghatározását, hogy egy bizonyos típusú műveleti egység kimenete lehet‑e egy másik bemenete. Végül algoritmikusan generáljuk az összes olyan folyamatstruktúrát, amely lehetséges a nyersanyagokkal, termékekkel és a műveleti egységek megengedett be- és kimeneteivel szemben támasztott követelmények, valamint a feladat definíciójában szereplő feltevések alapján. Példaként különböző szintézisfeladatok újrafogalmazása szolgál.
A javasolt módszertan a folyamatszintézis feladatok mélységében történő megértését eredményezi. A bevezetett általános célú számítógépes eszközök a szintézis kezdeti lépésében alkalmazhatóak matematikai programozási feladatok felírása helyett, és a speciális megoldó algoritmusok kifejlesztését és valamely nyelven történő implementációját megelőzően.
I. helyezett: Szita István – Takács Bálint
WP-DYNA: Tervezés és megerősítéses tanulás jól tervezhető környezetekben
Eötvös Loránd Tudományegyetem
Témavezető: Lőrincz András
A megerősítéses tanulás elmélete azzal a problémával foglalkozik, hogy hogyan lehet jó döntéssorozatokat hozni bizonytalan környezetekben. A probléma megoldására sokfajta, elméletileg is jól megalapozott algoritmust dolgoztak ki. Általános hiányosságuk, hogy a gyakorlatban elfogadhatatlanul lassúak lehetnek, mivel viszonylag lassú az állapotok értékei közötti információáramlás. Sok módszer létezik a tanulás gyorsítására. Legsikeresebbnek a modellt használó tervező módszerek bizonyultak.
A dolgozatunkban bemutatott WP-Dyna algoritmusban két tervezési módszert ötvözünk. Módszerünk azt az elvet használja ki, hogy a tervezést érdemes azokra a régiókra koncentrálni, ahol a cselekvések következményei megbízhatóan jósolhatók, itt viszont már egy egyszerű modell is elegendően pontos – ebben az egyszerű modellben pedig gyorsan lehet tanulni. Téziseink:
· A WP-Dyna algoritmus specifikációja. Specifikáljuk a WP-Dyna algoritmust, amely a megerősítéses tanulást a modell alapján történő tervezéssel egészíti ki, és ötvözi a Dynát és a makrókereső módszereket.
· A WP-Dyna algoritmus közel-optimalitásának bizonyítása. Megmutatjuk, hogy a WP-Dyna tervező része által talált makrók közel optimálisak, és korlátot adunk értéküknek az optimálistól való eltérésére.
· Matematikai háttér a bizonyításhoz (e-MDP-k). Bemutatjuk az e-MDP modellt, ami egy kismértékben perturbált Markov döntési folyamat. Ezt felhasználva belátjuk a WP-Dyna közel-optimalitását.
· Módosított WP-Dyna, amely optimális politikához konvergál. Megadjuk algoritmusunknak egy olyan módosítását, amelyről bebizonyítjuk, hogy az optimális értékelőfüggvényhez konvergál.
· A WP-Dyna teljesítményének kísérleti vizsgálata. Számítógépes szimulációkkal igazoljuk, hogy a WP-Dyna tervezési módszere jól használható megerősítéses tanulási problémák megoldására.