Zdieľanie spoločných nákladov
Martin Pál, Cornell University, Ithaca
Utorok, 17. decembra 2002, 13:20-14:00 (Informatika I.)
Majme množinu potenciálnych užívateľov U nejakej služby (napr. pripojenie k Internetu). Pre danú podmnožinu J užívateľov označme c(J) náklady na poskytnutie tejto služby užívateľom v J. Napríklad, c(J) môže byť cena najlacnejšieho Steinerovho stromu, ktorý pripojí každého užívateľa v J k centrálnemu uzlu s.
Predpokladáme, že každý užívateľ i si cení pripojenie na hodnotu ui. Od každého pripojeného užívateľa chceme vybrať poplatok pi tak, aby súčet vybraných poplatkov približne pokryl náklady na poskytnutie služby. Našim cieľom je teda vybrať množinu užívateľov J, ktorí dostanú pripojenie a vypočítať výšku poplatku pi pre každého užívateľa. Problém je, že hodnota ui je tajná a pozná ju iba užívateľ i. Užívateľ môže udať nepravdivú hodnotu u'i, ak tým zvýši svoj celkový úžitok (úžitok užívateľa i je rovný ui-pi ak je pripojený a 0 ak nie je). Našim cieľom je navrhnúť taký mechanizmus na výber množiny J a výpočet poplatkov pi, aby optimálna stratégia každého užívateľa bola prezradiť pravdivú hodnotu ui.
Broadcastové systémy vyšších rádov
Karol Ostrovský, Chalmers University of Technology, Gothenburg
Utorok, 17. decembra 2002, 14:00-14:40 (Informatika I.)
Siete Ethernetového typu sú veľmi populárnym komunikačným médiom. V takýchto sietach prebieha všetka komunikácia po jedinom bezmennom komunikačnom kanáli. Predchádzajúce práce modelujúce takéto systémy využívali kalkulus CBS. V tejto práci prezentujeme nový kalkulus HOBS. V porovnaní s CBS, 1) HOBS je kalkulus vyššieho rádu, kým CBS je kalkulus prvého rádu, 2) HOBS umožňuje dynamickú rekonfiguráciu subsytémov, kým CBS rekonfiguráciu neumožňuje, a 3) HOBS nevyžaduje žiadny pomocný jazyk, aby mal výpočtové schopnosti Turingovho stroja. Fakt, že HOBS je kalkulom vyššieho rádu, je kľúčovým pre zvýšenie výpočtových schopností a elimináciu pomocného jazyka. Zároveň ale kalkulus vyššieho rádu vyžaduje komplikovanejšie dôkazové techniky na overenie základných vlastností daného kalkulu. V tejto práci prezentujeme základnú teóriu rovnosti pre HOBS spolu s niekoľkými príkladmi, ktoré ilustrujú programovanie v tomto kalkule. Hlavným technickým prínosom tejto práce je adaptácia Howeovej metódy pre HOBS a dôkaz, že bisimulácia je kongruencia. Pomocou tohoto výsledku následne dokážeme, že CBN lambda-kalkulus je sub-kalkulom HOBS, a zároveň poukážeme na čiastocnú reprezentáciu pi-kalkulu a bPi-kalkulu v HOBS.
Karol Ostrovský študoval na fakulte v rokoch 1993-1998 odbor informatika, špecializácia umelá inteligencia. Jeho vedúci diplomovej práce bol Damas Gruska. Po skončení magisterského štúdia pôsobil na fakulte ako doktorand a od roku 1999 je doktorandom na Chalmers University of Technology v odbore informatika. Medzi jeho vedecké záujmy patria programovacie jazyky, funkcionálne programovacie jazyky, konkurentné programovacie jazyky, teória konkurencie, typové systémy a statická analýza programov.
Architektúra pre systémy reálneho času na báze reaktívnych agentov
Andrej Lúčny, Microstep-MIS Bratislava
Streda, 18. decembra 2002, 13:20-14:00 (Informatika II.)
Počas uplynulého desaťročia bol vedúcou platformou v oblasti systémov reálneho času QNX4. Jeho dominantnou vlastnosťou je architektúra na báze mikrokernelu a blokujúceho message passingu. Výrobcom odporúčaná architektúra aplikačného systému je tzv. pyramidálna client-server architektúra. Jej nevýhody sa prekonávajú použitím tzv. message queue. My sme použili iný princíp zavedenia neblokujúceho message passingu na báze reaktívnych agentov komunikujúcich nepriamo cez tzv. space. Týmto krokom sa zvyšuje škálovateľnosť systému a jeho povaha sa približuje biologickým systémom, čo sa prejavuje na schopnosti modelovať živé systémy.
RNDr. Andrej Lúčny absolvoval MFF UK v roku 1994 v odbore Informatika, zameranie umelá inteligencia. Vedúcim jeho diplomovej práce na tému "Emergentné správanie v kolóniách agentov" bol prof. RNDr. Jozef Kelemen, DrSc. Po ukončení štúdia pracoval v MicroStep-HDO ako programátor zaoberajúci sa monitorovaním v reálnom čase. Od roku 1997 pôsobí na Ústave informatiky ako externý vyučujúci. Od roku 2000 pracuje v MicroStep-MIS ako vedúci oddelenia QNX, kde je zároveň spoločníkom a konateľom. Podieľa sa na vývoji monitorovacích a informačných systémov v aplikačných oblastiach: meterológia, seizmológia, životné prostredie a letecká doprava. Pracuje hlavne pre zákazníkov z krajín blízkeho a stredného východu. Jeho záujmy v oblasti výskumu sa koncentrujú na softwarové architektúry založené na multiagentových systémoch.
Analýza aktivity neurónových kultúr pomocou multielektródovych polí
Miroslav Dudík, Princeton University
Streda, 18. decembra 2002, 14:00-14:40 (Informatika II.)
Skupina Steva Pottera (pôvodne na California Institute of Technology, v súčasnosti na Georgia Intitute of Technology) študuje proces učenia na kultúrach živých neurónov. Populácie 500-2000 neurónov prežívajú v Petriho miskách niekoľko mesiacov, preukazujú spontánnu aktivitu a reagujú na elektrickú stimuláciu. Multielektródové polia umožňujú spojenie neurónových kultúr s počítačom, ktorý simuluje ich interakciu s virtuálnym prostredím. Na vytvorenie zmysluplnej simulácie treba vyvinúť softwarové nástroje, ktoré by boli schopné rozpoznať koordinovanú neurónovú aktivitu a odpovedať stimulom pochopiteľným pre neurónovú kultúru. V súčasnej fáze projektu treba vymedziť, čo je to koordinovaná aktivita a aké sú vhodné typy stimulácie. So skupinou Steva Pottera som pracoval v lete 2001 na analýze spontánnej aktivity neurónových kultúr zaznamenanej počas dvoch pozorovaní: 28-dňového pozorovania s 15-minutovým záznamom aktivity každý deň a 24-hodinového pozorovania s nepretržitým záznamom. Korelácie aktivity na dvojiciach a trojiciach elektród boli použité na určenie funkčných závislostí v rámci kultúry. Pochopenie rýchlosti spontánneho vývoja aktivity v neurónových kultúrach je dôležité na pochopenie výsledkov dlhodobých experimentov a typy prirodzených závislostí v neurónovej kultúre by mohli slúžiť ako báza pre zmysluplnú simuláciu. Vo svojom príspevku zhrniem výsledky svojho výskumu a priblížim niektoré matematické, fyzikálne a informatické problémy v tejto oblasti.
Miroslav Dudík študoval informatiku na MFF UK v rokoch 1997-1999 a na California Institute of Technology v rokoch 1999-2002. Od septembra 2002 je doktorandom v oblasti teoretickej informatiky na Princeton University, kde sa plánuje zaoberať teóriou zložitosti, teóriou učenia a aproximačnými algoritmami.