Programme of colloquia with abstracts for the Spring 2000 semester

29 February 2000: Prof. RNDr Jozef Gruska DrSC, Faculty of Informatics, Masaryk University, Brno; Quantum automata; Abstract: An attempt to understand the power of quantum computing, as an important new paradigm in computing, has recently drawn researchers’ attention to various quantum models of automata. The main focus has so far been on various natural quantum versions of classical automata, such as finite automata, Turing machines and cellular automata. The recognition power and succinctness of these models have been investigated. In addition, a new direction appears to be the investigation of different models of quantum automata. Results obtained so far are largely based on expertise gained during the study of classical automata, particularly probabilistic automata and reversible automata. However, new methods are also emerging. The talk will provide an overview of recent results and the methods used, with a focus on open problems.
7 March 2000: Prof. RNDr Jaroslav Kral DrSC, Prague; Beyond object orientation; Abstract: The implications of the fact that software is a technical artefact. Wide-area information systems (WAIS), examples. Crucial properties of WAIS. Networks of autonomous components (NAC) as the only known feasible architecture for WAIS. Properties of autonomous components not covered by object-oriented methodology. Middleware-oriented systems. Autonomous components in small systems. How to model NAC? The role of XML and the Internet. An overview of the differences between NAC and object orientation. Open problems concerning middleware orientation and autonomous components. Why they have not been used until now. The threat posed by the new paradigm. Consequences of NAC for the software industry and software professionals.
14 March 2000: Prof. Ing. Ivo Serba, DrSC, Brno; Image perception and communicative computer graphics; Abstract: Image interpretation as an ill-defined problem – implications. The mechanism of perceiving planar and spatial scenes. Information throughput of the screen (window). Graphical encoding of commands and feedback. Principles of proper compositional and colour design of windows.
21 March 2000: Hans Hagen, PRAGMA ADE, The Netherlands; The Future of Documents and Documentation; Abstract: There will be some major changes in the way we deal with documents and documentation in the next few years. High-quality online viewing will begin to replace paper. Instead of ever-changing word processor formats, open formal document encoding formats will take the lead.
The characteristics of electronic documents compared to their paper predecessors will be demonstrated and discussed: we should not ignore hundreds of years of typographic tradition.
Aspects of source encoding in XML, transformations using XSL, processing with TeX, and document distribution in PDF will be discussed and illustrated with examples.
28 March 2000: Prof. RNDr Petr Hajek DrSC, UIVT CAV Prague; What is soft computing?; Abstract: Soft computing is a new computing paradigm based on the creative integration of techniques such as fuzzy computing, neural networks and genetic algorithms, etc., characterised by dealing with uncertainty, vagueness, imprecision and sub-optimality, and inspired by human problem-solving. It involves solving problems for which the use of classical mathematical methods is difficult or impossible due to the excessive volume of data or a lack of theoretical background. In this lecture, I intend to discuss the subject of soft computing in more detail, focusing in particular on the logical background of fuzzy controllers, the relationship between fuzzy controllers and neural networks, and the possibilities for combining them.
4 April 2000: Doc. Mojmir Kretinsky CSc; Projects on Concurrency at the Faculty of Informatics, Masaryk University; Abstract: We provide an overview of various research projects in the field of concurrent process systems that have been carried out or are currently underway at the Department of Computer Science, Faculty of Informatics, Masaryk University, Brno. We outline their research directions and objectives, and summarise some of the results achieved. We also briefly report on the current status and discuss some prospective research directions and targets to be met.
11 April 2000: Dr Franz Wotawa, Vienna University of Technology; Model-Based Reasoning and its Application to Software Debugging; Abstract: Model-based reasoning deals with logical models of technical or physical systems for solving problems, such as diagnosis, configuration and others. When compared with other approaches, such as rule-based expert systems, model-based diagnosis offers several advantages. Firstly, it allows for reasoning using direct representations of a system. Changing small parts of a system does not usually require modifying the entire model. Model fragments can be reused to describe parts of other systems. Finally, adopting a component-oriented modelling approach facilitates the development and maintenance of models for large systems. Model-based diagnosis has been successfully applied in several fields, including the automotive industry for diagnosing vehicles, space exploration (NASA, Deep Space One), the environmental sector, software debugging, and others.
In the first part of my talk, I will give a brief introduction to model-based diagnosis, including basic definitions, algorithms and modelling principles. I will then present applications of model-based diagnosis developed at research institutes, companies and the Vienna University of Technology. In the second part of my talk, I will demonstrate how model-based diagnosis can be used for software debugging, the advantages and results of these methods, and the further research required.
18 April 2000: Prof. Jaroslav Nesetril DrSc, Charles University, Prague; The Idea of Universality in Mathematics and Computer Science; Abstract: The universal object is one of the fundamental concepts that appears in many forms in mathematics and computer science. In this lecture, we shall present several examples that illustrate this concept from the perspective of online algorithms and structural combinatorics.
25 April 2000: Dr Peter Rossmanith, Technical University of Munich; Exact algorithms for NP-complete problems; Abstract: NP-hard problems have long been described as ‘intractable’. However, there are now highly efficient methods for solving many of these problems. Although their worst-case running time remains exponential, they can be used to solve real-world problems. This talk surveys some of these new and established algorithms, covering topics such as logical and graph algorithms.
27 April 2000: Prof. Juraj Hromkovic, University of Aachen; On the computational power of Las Vegas finite automata; Abstract: One of the central themes of complexity theory is the study of the computational power of probabilistic algorithms. Given that no separation has been proven for polynomial time between deterministic, non-deterministic and probabilistic Turing machines in polynomial time, efforts are being made to investigate the power of stochastic computations, at least for limited computational models. In this lecture, we shall focus on Las Vegas probabilistic computations, which are highly practical as they never lead to an incorrect result. I shall present some results describing the computational power of Las Vegas finite automata (both unidirectional and bidirectional) and formulate open problems related to this topic.
2 May 2000: Doc. Vladimir Petkevic, Faculty of Arts, Charles University, Prague; Karel Oliva, Saarland University; Milena Hnatkova, Faculty of Arts, Charles University, Prague; Pavel Kveton, Faculty of Arts, Charles University, Prague; Automatic morphological disambiguation of Czech texts; Abstract: The topic of this lecture is one of the main problems in one of the most cutting-edge branches of mathematical and computational linguistics: the automatic disambiguation of morphologically tagged texts in language corpora, in our case Czech corpora. This involves the automatic resolution of morphological homonymy based on syntactic rules: after a morphological analyser has assigned all possible morphological interpretations to each word occurrence in a text included in the corpus, another programme, known as a tagger or disambiguator, selects the appropriate interpretation from all the options based on the context in which the word form appears. The lecture has two main parts: - a critique of existing methods for morphological disambiguation using statistical methods - a rule-based approach to disambiguation, with examples of certain rules and the current status of the work? - the relationship between disambiguation and the grammatical checker for Czech texts, and their syntactic analysis. The lecturer emphasises that this problem is extremely difficult and that, with very few exceptions, it has not yet been – satisfactorily resolved for the Czech language.
9 May 2000: Prof. Charles Wuetrich, University of Aachen; TBA
16 May 2000: Doc. Jiri Sochor CSc; Human-Computer Interaction in Virtual Environments; Abstract: Interaction in 3D space should enable users to interact freely with virtual objects. Direct manipulation of virtual objects presents new challenges. Upcoming virtual environment applications require efficient techniques for faster and more natural 3D interaction. We will present a brief review of interaction techniques used in virtual environment (VE) applications. We will then outline the objectives of our research into 3D interaction and explain the user interfaces employed in such applications. We will also discuss experiments carried out in our HCI laboratory.
23 May 2000: Doc. J. Psutka CSc, Plzeň; Recognition of Spoken Czech; Abstract: The aim of this lecture is to provide a brief overview of the fundamental tasks that must be addressed when designing a system for the recognition of continuous spoken Czech. The lecture will discuss the issues involved in processing the acoustic speech signal, including the derivation of suitable parameterisation. For the purposes of acoustic modelling, a methodology based on triphen HMMs, the creation of phonetic decision trees, etc., will be mentioned. In the section dealing with language modelling, the issues surrounding the creation of statistical language models for spoken Czech will be discussed. Finally, the results of some experiments on continuous Czech speech recognition carried out at the Centre for Cybernetic Systems Research at the University of Technology in Plzeň will be presented.
30 May 2000: Mgr. Antonín Kučera, Dr.; Verification of Concurrent Systems: Theory and Practice (Habilitation lecture); Abstract: The problem of verifying concurrent, distributed and non-terminating systems is a major challenge in modern computer science.
Due to the high degree of non-determinism and unpredictability of such systems, ad hoc verification techniques (such as testing) are unusable and even dangerous. In this context, the proper use of rigorous formal methods is essential, and a substantial amount of work has been invested in making them as efficient as possible.
In this talk, we discuss both the theoretical foundations and the practical applicability of the two main ‘verification paradigms’: equivalence-checking and model-checking. In the equivalence-checking approach, one formally defines the specification (i.e. the intended behaviour) of a system and the actual implementation in a higher-level language with well-defined semantics, and then demonstrates that the two descriptions are equivalent. In the model-checking approach, the correctness requirements are expressed as a formula in a certain temporal logic, and it is then demonstrated that the implementation satisfies the formula. Of course, computers can support these activities, and a natural question is where the corresponding decidability and complexity bounds lie. From a practical point of view, the main limiting factor is the size (i.e., the number of states) of the implementation. Even a single hardware chip can have more than 10^150 states, and it is not possible to represent all of them explicitly. However, there are ways to overcome this fundamental difficulty (also known as the ‘state-space explosion problem’). Existing approaches can be divided (roughly) into two groups: abstraction techniques and techniques for symbolic state-space representation. The idea is that one can either attempt to reduce the number of states by abstracting the implementation into something smaller (retaining only the ‘important’ information), or develop a ‘symbolic’ description language which allows for compact definitions of a large state space by exploiting some form of regularity inherent in the structure of the states. Based on our current understanding, it appears that abstraction is more suitable for the verification of software (concurrent and distributed algorithms), whilst the main industrial applications of the symbolic approach lie in the field of hardware verification (integrated circuits). We shall discuss the advantages and future prospects of both methods in detail, providing some concrete examples of how they actually work in practice.
27 June 2000: Prof. Jay Anderson, Lancaster, USA; Algorithm visualisation with QuickTime movies: new techniques to enhance student learning; Abstract: The use of algorithm visualisation and animation in the classroom to teach computer science (informatics) dates back about fifteen years, with the introduction of innovative yet simple techniques for portraying sorting algorithms, amongst others. However, recent studies indicate that a picture alone – even a moving one – does little to help students learn about an algorithm.
Instead, studies show that students learn best if the animation is (1) accompanied by a textual explanation; (2) the student has the opportunity to pause, rewind, and move forwards and backwards through the animation; (3) the animation can be automatically paused to ask the student a question; and (4) the student can select inputs or parameters for the algorithm being animated.
QuickTime® Movies provide ways to achieve the first three objectives. Movies can be embedded in web pages, streamed from a server, or delivered on physical media such as CD-ROMs. QuickTime movies can be developed on either Windows or Macintosh platforms and played on either platform. The talk will include examples drawn from the author’s experience at Franklin & Marshall College, Masaryk University and TU Wien between 1994 and 2000.