Programme of colloquia with abstracts for the Spring 2008 semester

19 February 2008

Assoc. Prof. RNDr. Petr Hliněný, Ph.D., FIMU, Brno

On the surprising problem of the intersection number of a graph

Abstract: The problem of determining the intersection number of a graph (or drawing a graph with the smallest possible number of edge crossings) is not only theoretically interesting, but also has useful practical applications, for example in VLSI design or in graph visualisation. In general, this is an NP-complete problem, and even in terms of approximations or heuristics, no particularly satisfactory results are known. It is only in the last few years that attention has turned to a surprising sub-problem – how to determine the crossing number of a graph formed by adding a single edge to a planar graph? Despite the apparent triviality of this question, we still do not know its solution, and there are even opinions amongst experts that this sub-problem may be NP-complete. In this talk, we will take a detailed look at recent developments concerning this sub-problem.

The lecture will be bilingual, in Czech and English.

26 February 2008

Doc. Mgr. Tomáš Tyc, Ph.D., Faculty of Science, Masaryk University, Brno

Metamaterials, invisibility and conformal mapping

Abstract: We are currently witnessing the creation of unique materials whose properties can be tailored to our specific needs. An example of this are so-called metamaterials, in which the desired properties arise from their microscopic structure, rather than their chemical composition. Metamaterials offer possibilities that were unimaginable until recently – achieving a negative refractive index, superluminal speeds, optical imaging without any defects, and so on. One application of metamaterials is the achievement of invisibility, whereby a metamaterial cloak directs light round an object and back into its original direction, so that the object cannot be seen. For microwaves, invisibility has already been experimentally achieved in this way; for visible light, however, this has not yet been the case. In the theory of invisibility, geometric mappings play a significant role alongside metamaterials, and amongst these, conformal mappings in particular. The lecture will touch upon the theory of metamaterials, explain the principles behind achieving invisibility as well as the difficulties involved, and present some new findings from this fascinating field.

4 March 2008

Jan Obdržálek, MSc, PhD, FIMU, Brno

Gendarmes, a Thief and Graph Theory

Abstract: It is a well-known fact that many interesting and important algorithmic problems on graphs are NP-complete. However, if we restrict the class of graphs under consideration (for example, to graphs defined by structural decomposition), the complexity of the problem can decrease significantly. The best-known, and highly significant, class of such graphs are those with bounded tree-width, for which many NP-complete problems can be solved in linear time.

Closely related to tree decomposition is a certain type of game on graphs known as ‘cops and robbers’ games. A significant and non-trivial result is an alternative characterisation of the tree-width of graphs using precisely these games. In this talk, we shall examine various versions of the ‘cops and robbers’ games and the relationships between them. We shall also mention new results, in particular the adaptation of these games to directed graphs.

11 March 2008

Doc. Mgr. Jiří Damborský, Dr., Loschmidt Laboratories, Masaryk University, Brno

Structural Bioinformatics and Computer-Assisted Engineering of Proteins

Abstract: Bioinformatics is the application of information technology to the management and analysis of biological data. Structural bioinformatics is the branch of bioinformatics dealing with data from the structural analysis of proteins, nucleic acids and their complexes. Analysis of the three-dimensional structures of biomolecules, experimentally determined to atomic resolution, provides insight into the function of living organisms at the lowest organisational level and generates essential knowledge for the design and optimisation of biomolecules for industrial applications.

A number of computational tools have been developed in recent years for the storage and analysis of biomolecular structures. New tools are still required to predict changes in structure that will lead to functional modifications in a controlled manner. Predicted changes, known as mutations, can be routinely introduced into the structures using molecular biology techniques.

The lecture will describe the usefulness of structural bioinformatics for the design and construction of proteins with novel properties. A general concept of computer-assisted protein engineering will be presented, along with two in-house programmes, CAVER and HOTSPOT WIZARD, developed for the prediction of mutations. Examples will be given from the engineering of proteins for the synthesis of fine chemicals and the detoxification of hazardous chemical substances.

18 March 2008

Prof. Ing. Pavel Zezula, CSc., FIMU, Brno

Metric similarity search in theory and practice

Abstract: Similarity search methods based on the principle of metric postulates have experienced an unprecedented boom over the last ten years. The main reason is that the number of datasets comprising objects that can only be compared on the basis of similarity is growing – the volume of such data is increasing exponentially. The aim of this lecture is to present the basic concepts of metric search and to outline methods for scalable index structures capable of processing large volumes of data.

The capabilities of this technology will be demonstrated using the MUFIN (Multi Feature Indexing Network) system to search a collection of 10 million images indexed by five basic MPEG-7 descriptors for colour, contours and texture.

25 March 2008

Ing. Přemysl Kršek, Ph.D., FIT VUT, Brno

3D Geometric Modelling in Medicine and its Clinical Applications

Abstract: This lecture focuses on the creation of 3D geometric models of human tissues based on medical imaging data from computed tomography and magnetic resonance imaging. The emphasis is on the application of the created models back in clinical practice to improve the treatment of specific patients. This is in line with the current global trend in medicine, which focuses on individualised patient care (‘tailor-made surgery’).

During the lecture, the characteristics of the processed CT/MRI data will be described. The complete procedure for creating 3D tissue models will be analysed, comprising: tissue segmentation, vectorisation of tissue models, smoothing and decimation of vector models. The presentation will also cover the topic of a virtual networked collaborative environment for the consultation, correction and verification of 3D tissue models.

Finally, a range of applications for the created models in clinical practice across various medical disciplines will be presented: plastic and cosmetic surgery, dentistry, orthopaedics and neurosurgery. To date, over 30 operations on specific real patients have been carried out in our country with the support of the techniques described.

1 April 2008

Doc. RNDr. Jiří Sgall, DrSc., Institute of Mathematics, Czech Academy of Sciences, Prague

Approximation algorithms for scheduling

Abstract: Scheduling algorithms constitute a classic area of research at the interface between combinatorial optimisation and operational research. Many problems are NP-hard, and in such cases we investigate approximation algorithms, i.e. algorithms that guarantee at least a certain quality of solution compared to the optimum. In this lecture, we shall present several related problems and algorithms from this field, with an emphasis on methods using linear programming. The lecture is based (largely) on the article T. Ebenlendr, M. Krčál, J. Sgall: Graph balancing: A special case of scheduling unrelated parallel machines Proc. of the 10th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), ACM-SIAM, 2008.

8 April 2008

RNDr. Libor Škarvada, FIMU, Brno

Polymorphic and dependent types

Abstract: We shall examine type systems with high expressiveness, their relationship to logical calculi, and their potential applications in practical programming. In particular, we shall focus on type systems with parametric polymorphism, type constructors and value-dependent types. Whilst polymorphic types and type constructors have long found application in functional languages, value-dependent types are used mainly only in experimental languages and have not found their way into practical use. The reasons are both trivial (unfamiliarity and cumbersomeness) and fundamental (undecidability of type checking). Our aim will be to overcome the first obstacle and to work around the second.

15 April 2008

Ing., Dipl.-Ing. Martin Drahanský, Ph.D., FIT VUT, Brno

Biometric systems

Abstract: The lecture will begin with an overview of existing biometric systems, highlighting their strengths and weaknesses. The subsequent topic will be biometric systems based on fingerprint recognition, where I will focus on testing the quality of image data in fingerprints. The lecture will conclude with a discussion of methods for testing liveness in biometric systems and current research at FIT VUT in Brno.

22 April 2008

Prof. RNDr. Jiří Zlatuška, CSc., FIMU, Brno

Research evaluation, science policy – a problem specific to computer science or a general issue?

Abstract: The lecture will address certain conceptual and practical issues relating to the reform of research, development and innovation in the Czech Republic. Criticism of the evaluation system has already emerged from computer science departments in the Czech Republic. We shall examine the broader aspects of the issue and assess the extent to which the problems highlighted by computer science are specific to that field alone, and to what extent they are of a more general nature.

29 April 2008

RNDr. Věra Kůrková, DrSc., Institute of Computer Science, Czech Academy of Sciences, Prague

Training neural networks with the capacity for generalisation as an inverse problem

Abstract: The training of neural networks, modelled as the minimisation of error functionals, can be formulated as an inverse problem using appropriate operators. Inverse problems were developed to solve physical problems (these include, for example, computed tomography). Various regularisation methods designed to increase the stability of solutions to inverse problems can also be used to model generalisation, i.e. the ability of neural networks to satisfactorily process data that was not used during training. In this way, network learning algorithms can incorporate not only empirical data (the training set) but also knowledge about certain qualitative properties of the sought-after solutions. Mathematical methods developed by generations of mathematicians for solving physics problems can be used to design alternative neural network learning algorithms based on solving systems of linear equations.

6 May 2008

Doc. RNDr. Viliam Geffert, CSc., Faculty of Science, P. J. Šafárik University, Košice

State hierarchy of finite automata

Abstract: A more detailed analysis of the relationship between the number of states of a classical unidirectional deterministic finite automaton (DFA) and its non-deterministic equivalent (NFA) will be presented. Although the exponential relationship is generally known, the exact magnitude has not yet received much attention.

We shall show that for every natural number d, and every n in the interval log(d)...d, there exists a regular language for which the optimal DFA uses EXACTLY d states, whilst every optimal NFA uses EXACTLY n states. Thus, the state hierarchy of non-deterministic NFAs for languages recognised by d-state DFAs is connected and contains no ‘magic’ holes.

If we focus on BINARY regular languages, the above result has been proven for all values of n in the range from Omega(log(d)^3/loglog(d)^2) to d.

Conversely, for UNARY regular languages, this state hierarchy is not connected. There are ‘gaps’ in the hierarchy, i.e. magic values between values that are not magic. In fact, the overwhelming majority of values of n smaller than d are magical for d (i.e., for almost all values of n smaller than any sufficiently large given d, it holds that NO optimal d-state DFA recognising a unary language has an equivalent optimal NFA that would use exactly n states).

Keywords: descriptive complexity, finite automata, regular languages

13 May 2008

Assoc. Prof. RNDr. Václav Matyáš, M.Sc., Ph.D., Mgr. Petr Švenda, FIMU, Brno

Cryptographic Protocols in Sensor Networks

Abstract: This lecture will introduce the technology of wireless sensor networks, with particular emphasis on their security. This relatively new technology began to develop alongside advances in the miniaturisation of electronic devices, their falling costs and the widespread adoption of wireless communication. Data collected by miniature devices in the field (temperature, pressure, movement) is processed locally and then transmitted to the end user, who is thus able to monitor a selected area in detail and continuously. Applications range from medical patient monitoring, through uses in agriculture and industry, to early-warning systems for emergency situations and, last but not least, military applications, from which this technology originated.

The aim will be not only to demonstrate the underlying technology and the range of open research questions arising from the differences between this new technology and existing ‘classic’ networks, but also to convince the audience of the need for the timely implementation of security measures commensurate with the intended use of the network. The area of designing protocols for key distribution and establishment that are resistant to partial compromise will be covered in detail, including their automated design based on evolutionary algorithms, as well as the reverse approach – the automated search for attacker strategies.

20 May 2008

RNDr. Petr Sojka, Ph.D., FIMU, Brno

From Pixels and Minds to the Mathematical Knowledge in a Digital Library

Abstract: Experience in establishing a workflow for converting scanned images of mathematical papers into a fully-fledged mathematical library is described using the example of the Czech Digital Mathematics Library (DML-CZ) project. The entire process is described, with particular attention paid to the details of all production stages.