Program kolokvií s abstrakty pro semestr Jaro 1999

2. 3. 1999: Prof. Vladimir Buzek, DrSc, SAV, Bratislava; Secret life of qubits; Abstract: In the first part of my talk I briefly review basic concepts and ideas of quantum information processing. I introduce definitions of the qubit, the superposition principle, and the entanglement. These notions are necessary for explanation of the effects such as quantum dense coding, quantum teleportation and quantum cloning. Having these tools available I show how they can be used in quantum cryptography (quantum key distribution) and quantum computing. I conclude the review part of the talk with comments on physical realizability, decoherence and quantum error correction schemes.
The second part of the talk is devoted to the description of optimal manipulations with qubits.
9. 3. 1999: Prof. Eduard Groeller, University of Technology, Viena; Interactive visualisation applications; Abstract: Visualization techniques are often quite time-consuming. Interactivity, however, is highly desireable in many applications to facilitate insight and visual analysis. Therefore the investigation of interactivity issues is quite an important research field in scientific visualization.
In the first part of my talk I will give a brief overview on recent visualization projects of our group (http://www.cg.tuwien.ac.at/research/vis/).
In the second part I will discuss some of the projects in more detail: fast maximum-intensity projection, fast surface rendering for volumetric data, multimodal volume visualization, and oriented line integral convolution. Special emphasis will be on real-time techniques for 3D flow visualization.
16. 3. 1999: Mgr. Rudolf Ruzicka, Brno; Computer music --- pocitacove hudobne umeni; Abstract: Strucne dejiny vyuziti pocitacu v hudebni vede a pri vytvareni hudebnich skladeb (Hiller, Isaacson, "Illiac Suite" pro smyccove kvarteto z srpna 1956 a dal.
Computerova elektroakusticka hudba jako autonomni umelecka tvorba. Pro hudebni vedu je prinosem analyza hudebnich del, pocitace se pouzivaji pro ziskavani poznatku o hudebnim stylu a dalsich aspektech analyzovanych skladeb.
Seznameni s pocitacovymi programy pro vznik artificialnich hudebnich del, jejich automaticke notace a zvukove realizace. Syntetizery napodobujici hudebni nastroje a lidske hlasy.
Zvukove ukazky nase a zhranicni pocitacove hudby.
23. 3. 1999: Prof. Jaroslav Nesetril DrSc, MFF KU PRaha; Morfismove schema kombinatoricke optimalizace; Abstract: V prednasce bude uvedeno schema, ktere je vhodne k vyjkadreni dobrych charakteristik (tj. prislusnosti ke tride NP a coNP) pro ulohy kombinatoricke optimalizace a pro polynomialni resitelne pripady takovych uloh. To souvisi s teorii dobrych quasiusporadani na strane jedne a s tzv. vetami o hom-dualite. Uvedeme charakteristiku techto vet pro obecne relacni systemy (coz bylo nedavno dokazano autorem spolu s C. Tardifem).
30. 3. 1999: Doc. Libor Polak, CSc, PF MU Brno; Unifikace v tridach pologrup; Abstract: Dve hlavni oblasti aplikaci (ekvacionalni) unifikace v computer science a umele inteligenci jsou dedukcni systemy a prepisovani termu. Problematika unifikace neni nic jineho nez reseni rovnic ve volnych algebrach. Zakladni otazky jsou existence reseni a v kladnem pripade popis vsech reseni napr. pomoci tzv. ``nejobecnejsich'' reseni. V informatice mluvime o rozhodnutelnosti, unifikacnim typu, unifikacnich algoritmech a unifikacnich procedurach. Unifikacni typ je dan strukturou mnozin vsech reseni (= unifikatoru) resitelnych rovnic. Ten muze byt unitarni, konecny, nekonecni nebo nula v zavislosti na mohutnosti mnoziny nejobecnejsich reseni (= minimalnich unifikatoru). Typ nula znamena, ze takova mnozina vobec neexistuje. Unifikacni algoritmus/procedura (pro konecny/nekonecny typ) dava mnozinu vsech minimalnich unifikatoru. My se zamerime na nektere tridy (unarnich) pologrup a to obvykle s konstantami. Pripomeneme zname vysledky tykajici se variet vsech pologrup, komutativnich pologrup, polosvazu, uplne regularnich pologrup, grup a komutativnich grup. Nastinime autorovy vysledky tykajici se rozhodnutelnosti pro uplne jednoduche a uplne regularni pologrupy a vsimneme si mnoziny vsech reseni nekterych rovnic, napr. $ xy = yx$ nebo $ p x^n q = r$, napr. v inverznich pologrupach.
6. 4. 1999: Dr Jozef Vyskoc, Bratislava; Pocitacova steganografie; Abstract: Ochranu udajov, prenasanych verejnymi (otvorenymi) kanalmi, je mozne riesit v podstate dvomi sposobmi, V prvom pripade sa sprava pred prenosom transformuje s cielom dosiahnut, aby vysledok bol "zrozumitelni" iba pre opravneneho adresata. Druhy sposob je zalozeny na transformacii spravy s cielom dosiahnut, aby neopravnena osoba nedokazala v prenasanych udajoch detekovat, resp. extrahovat z nich, povodnu spravu. V prvom pripade hovorime o kryptografii, druhy pristup je znamy pod menom steganografia.
Zatial co v kryptografii sa za roky jej existencie podarilo vybudovat solidny teoreticky aparat, steganografia bola az donedavna znama hlavne v suvislosti s neviditelnymi atramentami, mikrobodkami a podobnymi technologicky orientovanymi (a tazko formalizovatelnymi) sposobmi utajenia. V poslednych rokoch vsak mozno zaznamenat prudky rast zaujmu o vyuzitie steganografickych principov aj v prostredi, ktore vytvaraju moderne informacne technologie.
Cielom prednasky bude poskytnut zakladnu orientaciu v tejto zaujimavej oblasti informacnej bezpecnosti. Prednaska bude orientovana na nasledovne oblasti: strucni historicki prehlad steganografie; metody pocitacovej steganografie; taxonomia steganografickych algoritmov; vztah steganografie a kryptografie
13. 4. 1999: Doc. Jiri Matousek, DrSc, MFF, KU Praha; Combinatorial algorithms for linear programming; Abstract: The number of arithmetic operations performed by known polynomial time algorithms for linear programming depends on the number of digits of the coefficients. We consider ``combinatorial'' algorithms, where the number of arithmetic operations only depends on the dimension $d$ and the number of constraints $n$ (working with the model of computation which is usual in computational geometry). In this setting, no polynomial time algorithm is known.
We survey some developments in this area from last years (most of them up to 5 years old), including a randomized algorithm with a subexponential expected running time.
20. 4. 1999: Dr. Patrick Hanks, Oxford University Press, Oxford; On preparation of the New Oxford Dictionary of English; Abstract: Talk concentrates on discussion of the process how the largest and newest dictionary of contemporary English has been prepared and compiled. The resourses (British National Corpus) and the techniques of building this monumental volume will be discussed and analysed.
27. 4. 1999: Prof. Nicola Leone, Technical University, Viena; Representing and solving problems in the DIV System; Abstract: The advanced logic-based KR languages developed in the last two decades allow to represent problems in a natural, declarative way, using principles of common sense reasoning. These languages are highly expressive; for instance, nonmonotonic languages like Default Logic, Autoepistemic Logic, and Disjunctive Logic Programming allow to encode very hard problems (even SigmaP2-complete problems) in a simple fashion. Nevertheless, such languages are hardly used in practice, and their exploitation in concrete application domains has been very limited. This is mainly due to the lack of efficient implementations of nonmonotonic languages, whose development is a difficult task because the higher is the expressive power, the higher is the computational complexity of the language.
The dlv system -- under development at the Technical University of Vienna -- has the ambitious goal to eliminate this deficiency, providing an efficient implementation of a highly expressive nonmonotonic language which may serve as a tool for the development of advanced knowledge based applications. The kernel language of dlv is full disjunctive Datalog under stable model semantics (dlv stands for DataLog with 'v', i.e., DataLog with disjunction) extended with strong negation (a' la Gelfond and Lifschitz), integrity constraints, and finite integers along with arithmetic operators and comparison predicates; front-ends to other advanced KR formalisms are also offered by dlv. Smart algorithms and sophisticated optimization techniques are implemented in dlv in order to achieve efficient programs evaluation. This talk shows the use of dlv as an "implementation engine" for KR purposes. In particular, we illustrate how complex problems from several application domains can be naturally encoded in the dlv language in a declarative and easy-to-understand fashion. We also report some benchmarks showing that instances of reasonable size of even hard problems are solved rather quickly by dlv. These benchmarks are contrasted to the dlv evaluation times reported at KR'98, and highlight the tremendous speed-up obtained during the last year, which make us very optimistic on the possibility to reach the ultimate dlv goal.
29. 4. 1999 Thursday: Prof. Mark Hillery, Hunter College, City University New York; Quantum secret sharing; Abstract: Secret sharing is a procedure for splitting a message into several parts so that no subset of parts is sufficient to read the message, but the entire set is. We show how this procedure can be implemented using quantum GHZ states. In the quantum case the presence of an eavesdropper will introduce errors so that his presence can be detected. We also show how GHZ states can be used to split quantum information into two parts so that both parts are necessary to reconstruct the original qubit.
4. 5. 1999: Ing. Vladimir Benko, Jazykovedny ustav L. Stura, SAV, Bratislava; Lexikografia, pocitace a "lacne riesenia"; Abstract: Jednou z uloh pocitacovej lexikografie je informatizacia procesu tvorby slovnikov. V prvom kroku ide najma o vyber vhodneho softveroveho prostredia a vytvorenie nastrojov a metod zefektivnujucich pracu lexikografov vo vsetkych etapach zivotneho cyklu lexikografickeho diela. Vzhladom na pomerne maly trh a specificke potreby jednotlivych lexikografickych projektov doposial prakticky neexistuju komercne programove nastroje, ktore by uspokojivo pokryvali aspon hlavne cinnosti pri tvorbe slovnika. A neda sa ani ocakavat, ze by sa tato situacia v blizkej buducnosti zmenila. Vacsina projektov je preto odkazana na pouzivanie nastrojov povodne urcenych na ine ucely, pricom tvorbu nastrojov "usitych mieru" si mozu dovolit len vo velmi malom rozsahu. V prednaske sa na priklade niekolkych lexikografickych projektov poukazuje na potrebu a moznosti tzv. "lacnych rieseni", ktore sa daju uplatnit najma v oblasti validacie textu slovnika (ide predovsetkym o lokalizaciu chyb a zvysovanie konzistencie a integrity udajov, pricom za mieru uspesnosti riesenia povazujeme pomer "ceny" u mnozstva programatorskej prace u k poctu najdenych chyb). Prezentuje sa jedna z moznosti reprezentacie slovnikovych dat v pocitaci a subor nastrojov pouzivanych na nasich pracoviskach na ich spracovanie.
11. 5. 1999: Dr. Thomas Worsch, Fachbereich Informatik, Universitaet Karlsruhe; Cellular automata with dynamically reconfigurable buses; Abstract: Motivated by advances in FPGA technology and optical computing, there is an increasing interest in dynamically reconfigurable architectures. In the talk we will consider an extension of the very simple model of one-dimensional cellular automata. Even in this case the addition of reconfigurable buses already leads to a seemingly very powerful model (RCA) on which one can solve all PSPACE problems in polynomial time. Partially building on Rothstein's work on bus automata we give a characterization of RCA time complexity in terms of Turing machines.
18. 5. 1999: Prof. Jiri Zlatuska, MU, Brno; Globalization of Academic Discipline; Abstract: Trendy nastupu informacni spolecnosti vytvareji zmenene prostredi pro vyzkumnou praci a meni jeji charakter, zpusoby spoluprace i zpusoby mereni vysledku.
Informatika zde posobi jednak jako katalyzacni prostredk, ve kterem se tyto zmeny odehravaji jako dusledek obecnejsich procesu, jednak jako novy prvek v konstrukci infrastruktury pro tyto discipliny.
Vymena informace v symbolickem tvaru vytvari prostupni prostredi odpovidajici "globalizaci" v ciste podobe nebo prototypu "znalostni" spolecnosti.
25. 5. 1999: Dr. Wolfgang Slany, Technical University, Vienna; Ramsey games; Abstract: We study combinatorial games based on graph Ramsey theory: Given two graphs G and A, two players, Red and Green, alternate in coloring the edges of G in their respective colors. Aim is to avoid (achieve) to build a monochromatic subgraph isomorphic to A. We determine the complexity of finding winning strategies for several variants of these games and ultra-strongly solve some small instances.
A Java applet that improves its strategy by playing over the Internet and that allows to play some small but non-trivial instances can be challenged at http://www.dbai.tuwien.ac.at /proj/ramsey/.
Please try it out! In case you win, you will be able to leave your name in our hall-of-fame.
8. 6. 1999: Shun Ha Sylvia Wong, BSc, University of Birmingham; An investigation into the use of Argument Structure and Lexical Mapping Theory in LFG for Machine Translation; Abstract: Lexical Functional Grammar (LFG) has been quite widely used as the linguistic backbone for recent Machine Translation (MT) systems. The relative order-free functional structure (f-structure) in LFG is believed to provide a suitable medium for performing source-to-target language transfer in a transfer-based MT system. However, the linguistic information captured by traditional f-structure is syntax-based , which makes it relatively language-dependent and thus inadequate to handle the mapping between different languages. Problem are found in the lexical selection and in the transfer from some English passive sentences to Chinese. The recent development of the relatively language-independent argument structure (a-structure) and the lexical mapping theory in the LFG formalism seems to provide a solution to these problems. In the light of the study carried out on the application of the a-structure and the lexical mapping in the different tasks of the translation from English sentences to Chinese, this talk will discuss how this method can be used to improve the structural disambiguation process of various combinations of verbs and prepositions as well as how to improve the lexical selection process of verbs. This talk will also illustrate how the use of a-structure and the lexical mapping theory can overcome the problem in transferring some passive sentences from English to Chinese. A brief evaluations on the effectiveness of the use of a-structure and the lexical mapping theory for MT will also be given in this talk.