Programme of colloquia with abstracts for the Spring 2006 semester

21 February 2006

Doc. RNDr. Luboš Brim, CSc., FIMU, Brno

Detection of cycles in dense graphs

Abstract: Massive graphs occur naturally in many applications. Examples include graphs used to model the World Wide Web, graphical information systems or telecommunications networks. These graphs cannot fit into the main memory of a single ‘standard’ computer, and graph algorithms for their analysis require access to external memory. Currently, there is intensive research into the possibility of using either external storage devices or the distributed main memory of multiple interconnected computers as additional memory. In both cases, however, it is generally not possible to use standard sequential graph algorithms, and it is necessary to design entirely new algorithms, which in many cases differ fundamentally from them.

In this lecture, the latest results for distributed-memory environments will be demonstrated using a specific graph problem as an example. Basic methods and techniques for detecting accepting cycles will be outlined, the key ideas behind individual algorithms will be presented, and the advantages and disadvantages of these algorithms will be discussed.

28 February 2006

Assoc. Prof. Dr. Ing. Petr Hanáček, FIT, Brno University of Technology

Information System Security and Design Flaws – Can We Prevent Them?

Abstract: To ensure the security of information systems, there are standardised procedures for secure design, development and testing, as well as sophisticated criteria for assessing the security of these systems. Nevertheless, even when these procedures are followed, security flaws appear in real-world systems that these procedures have failed to prevent. In this lecture, the author will attempt to analyse whether today’s modern methods for designing secure systems must indeed result in the designed system being secure, and what role standards, formal procedures and informal intuition play in this.

7 March 2006

Doc. RNDr. Roman Barták, Ph.D., Faculty of Mathematics and Physics, Charles University, Prague

Modelling unary resources using constraints -- Constraint Models for Unary Resources

Abstract: Scheduling with constraints is one of the most successful applications of constraint satisfaction technology. It is based on the idea of describing the scheduling problem as a problem of satisfying constraints, i.e. using variables, their domains (sets of possible values) and relations/conditions between variables. This talk describes our latest results in the field of modelling unary (sometimes also referred to as disjunctive) resources, i.e. resources that, at any given time, can process at most one activity. The focus will be on describing new incremental filtering algorithms that reduce the search space by shrinking the time windows of activities and deriving new precedence relationships between activities.

Constraint-based scheduling represents one of the successes of constraint satisfaction technology. It is based on the idea of modelling the scheduling problem as a constraint satisfaction problem, that is, in terms of problem variables, their domains (possible values), and constraints between the variables. The talk describes our recent results in modelling unary (also known as disjunctive) resources, where at most one activity can be processed at any given time. The emphasis is placed on describing new incremental filtering algorithms that prune the search space by reducing the time windows of activities and deduce new precedence relations between the activities.

14 March 2006

Prof. RNDr. Jozef Kelemen, DrSc., Silesian University in Opava

85 Years of Robots

Abstract: In this lecture, accompanied by a wealth of (perhaps interesting) images, we shall outline some of the paths that led to the 1921 premiere of Karel Čapek’s play R. U. R., we will say something (perhaps surprising) about the play’s fate, about what the author (probably) intended to convey in it, and about the subsequent fates of his robots and how they came to be portrayed in literature, philosophy, science and engineering.

21 March 2006

Prof. Ing. Jiří Jan, CSc., Faculty of Electrical Engineering and Computer Science, Brno University of Technology, Brno

MRI signal model and its conversion to image data

Abstract: A generalised model of the MRI signal, based on the spatial distribution of transverse magnetisation, encompasses all cases of initiation, not just the usual static case, and allows the procedure for converting the measurement signal into image data to be derived transparently via a multidimensional Fourier transform. Explanation from the perspective of signal and image data processing.

28 March 2006

RNDr. Tomáš Kaiser, Dr., KMA, University of West Bohemia, Plzeň

Graph Search

Abstract: In this lecture, we shall provide an overview of the main results and issues relating to the graph search problem. One formulation of this problem involves a group of ‘policemen’ and a ‘robber’, positioned at the vertices of a given graph G. The robber and the policemen move in turn, always between neighbouring vertices. The aim of the policemen is to apprehend the robber; the robber’s aim, on the other hand, is to avoid being apprehended. The fundamental question is which side has a winning strategy in graph G, or, alternatively, how many policemen are needed for their side to have such a strategy. We shall show how the answers to these questions depend on other parameters of graph G.

PhD Seminar

How a young scientist is made, with guest speaker Mgr. Tomáš Brázdil

Topics for discussion:

• Introduction to the new seminar and its future focus.
• How to actually get into RESEARCH and how to choose a supervisor.
• The initial challenges of doctoral life and how to tackle them.
• How to successfully work your way through to a completed doctoral thesis...

4 April 2006

Doc. RNDr. Luděk Matyska, CSc., FIMU, Brno

Multipoint videoconference in uncompressed High Definition quality (theory and technology behind the scenes) -- Multipoint videoconference in uncompressed HD quality (theory and technology behind the scenes)

Abstract: Preparing and successfully running a multipoint HD videoconference over a long distance via the current Internet is akin to putting together a jigsaw puzzle. Its individual pieces are the network, the capture and display of the HD stream, IP encapsulation of the video stream, and the multipoint distribution itself. We will use examples of multipoint HD videoconferences we conducted during the second half of 2005 to illustrate these puzzle pieces—the theory and technology used to construct them—and also to discuss what knowledge is required to actually assemble the entire puzzle. Furthermore, a combination with a visualisation system utilising the same underlying transport and display principles will be demonstrated. Videoconferencing systems are merely one part of the complete collaborative environment, and the lecture will conclude with a brief vision of the collaborative environments of the future that these experiments are helping to define.

11 April 2006

Gelasio Salazar, PhD., IICO-UASLP, Mexico

The crossing number problem

Abstract (pdf)

Abstract: The crossing number cr (G) of a graph G is a measure of the non-planarity of G. It is well understood exactly under which circumstances a graph can be drawn in the plane without any crossings of edges. When this is not possible, one is interested in finding an optimal drawing, that is, a drawing with the minimum possible number of crossings of edges, or at least a drawing close to optimal. Questions concerning the crossing number were first raised by Turán in the mid-1940s. In addition to their intrinsic theoretical interest, they have important applications, most notably in the field of VLSI layout.

Turán’s original problem was the calculation of the crossing number cr (_Km,n ) of the complete bipartite graph_Km,n . There are natural drawings of_Km,n with exactly_Zm,n crossings, where _Zm,n := [(m-1)/2] [m/2] [(n-1)/2] [n/2]. No drawing of_Km,n with fewer crossings has ever been found, and so it has long been conjectured that cr (_Km,n )_=Zm,n . This has been verified only for m< 7 (and arbitrary n). The exact value of cr (_K₆,n ) implies the best general bound known prior to our work, namelycr (_Km,n ) ≥ 0._8Zm,n .

In this talk, we will report on some recent research into this problem. We tackled the problem of estimating cr (_K₇,n ) for large values of n. We analysed the combinatorial and topological properties of drawings of_K₇,n , and formulated a quadratic programming problem whose solution provides a lower bound for cr (_K₇,n ).

The quadratic programming problem we originally obtained is quite large (the associated matrix is of size720 × 720). To solve this problem, we used state-of-the-art quadratic programming techniques, combined with some invariant theory of permutation groups. As a result, we were finally able to provide the improved boundcr (_K7,n ) ≥ 2.^1796n² – 4.5n, which is quite close to _{Z₇,ₙ = 2} .25^{n² +} O (n). Our bound for cr (_K₇,ₙ ) implies that, for each fixed m> 8,limₙ→∞ cr (_{K_m,ₙ} )/Z (m,ₙ) ≥ 0.83m/ (m-1). We also obtained, as a by-product, an improved bound for the crossing number of the complete graph_{\(K_n\)} .

18 April 2006

Prof. Zdeněk Strakoš, DrSc., Institute of Computer Science, Czech Academy of Sciences

Bidiagonalisation as a fundamental decomposition of data in linear approximation problems

Abstract (pdf)

25 April 2006

Mgr. Filip Procházka, RNDr. Zdenko Staníček, Ph.D., FIMU, Brno

Universal information robot – principles and applications

Abstract: The problem of working effectively with knowledge is becoming increasingly pressing as cyberspace expands. Most knowledge and data already exists in cyberspace, but is not easily accessible. This presentation will illustrate how this problem can be addressed using a virtual assistant in the form of a Universal Information Robot (UIR). It will describe how, with its help, a so-called virtual knowledge network can be created from existing data sources. The solution to this problem will also be illustrated using examples from the UIRON project – the use of the UIR in cancer research – carried out under an Academy of Sciences grant by a research consortium comprising UVT MU, CBA MU and the Masaryk Memorial Cancer Institute. A brief demonstration of the functioning system will be presented and the basic principles on which it is based will be explained.

2 May 2006

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

Scalable and distributed similarity search structures

Abstract: Due to the increasing complexity of current digital data, similarity search has become a fundamental computational task in a variety of applications, and many similarity search structures have been proposed in the literature. Unfortunately, computational costs remain high, and the linear scalability of single-computer implementations prevents efficient searching of large data volumes. In this talk, we briefly describe four very recent scalable, distributed similarity search techniques and study the performance of their implementations on the same cluster of peer computers executing queries on three different datasets. Although all the methods utilise parallelism to speed up query execution, experiments have identified different advantages for different objectives.

PhD Seminar

Bibliographic Citations and Citation Ethics with guest speaker Jiří Kratochvíl from the Central Library of the Faculty of Science, Masaryk University

• Principles of citation ethics.
• The issue of plagiarism (explanation of the term, examples of high-profile cases in the media).
• Creating bibliographic citations for the most commonly cited types of documents.
• Further details

9 May 2006

Prof. RNDr. Jiří Rosický, DrSc., Faculty of Science, Masaryk University, Brno

Homotopy and Concurrency

Abstract: The aim of this lecture is to show that methods from algebraic topology (in particular, homotopy theory) can be useful for the theory of parallelism. The exposition will be elementary and, amongst other things, will demonstrate a ‘discrete’ approach to homotopy theory using simplicial sets (i.e. infinite-dimensional graphs). It will provide a natural perspective on bisimulations (induced by open maps) and on their connection with homotopies. So-called weak factorisation systems will be used as the basic formal tool.

PhD seminar

Citation databases and electronic resources, with guests Jiří Kratochvíl from the Faculty of Science, Masaryk University, and Miroslav Bartošek from the University Computing Centre, Masaryk University

• An introduction to the Web of Science databases and the index for the evaluation of scientific journals.
• Programme and Projects 1N.
• Principles and options for using licensed electronic information resources.
• Brief introduction to resources: IEEE Computer Society Digital Library, ACM Digital Library, LNCS Online, and other resources.

16 May 2006

Assoc. Prof. Zdeněk Kotásek, CSc., FIT, Brno University of Technology

Principles of testing digital systems

Abstract: The fundamental principles of the synthesis and design of digital systems with regard to their testability (synthesis/design for testability) will be described, along with the principles of testing based on the application of these principles. Furthermore, the following concepts and techniques will be explained: controllability/observability of internal points of the circuit under test, autonomous testing methods, structured design methods, connection testing, and the application of these methods in the construction of computing systems. The results of research carried out in the field of diagnostics and testing of digital circuits at the Faculty of Information Technology, Brno University of Technology, will be mentioned.

23 May 2006

Doc. Ing. Jiří Sochor, CSc., FIMU, Brno

Interaction Tools and Techniques in Virtual Environments

Abstract: In May 2000, we presented an introductory talk entitled ‘Human Computer Interaction in Virtual Environments”, in which we set out the main objectives of specific research in VR: interaction in 3D space should enable users to interact freely with virtual objects. Six years later, we shall briefly summarise developments in this field and present the contributions made by the HCI Laboratory at Masaryk University.