T��de� absolventov matfyzu 2002

Abstrakty - Informatika


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.