Programme of colloquia with abstracts for the Autumn 2007 semester

18 September 2007

Prof. Ranieri Baraglia, ISTI – Institute of the Italian National Research Council, Pisa, Italy

A Job Scheduling Framework for Large Heterogeneous Computing Farms

Abstract:

A computing farm can integrate heterogeneous hardware and software resources such as workstations, parallel systems, servers, storage arrays, and software licences. Such infrastructure requires appropriate scheduling mechanisms in order to meet application performance requirements (QoS) and optimise resource utilisation. In such an environment, users should be able to submit their computational requests without necessarily knowing on which computational resources these will be executed.

A great deal of effort has been devoted to understanding job scheduling problems in the scientific literature. Job scheduling algorithms can be divided into two classes: on-line and off-line. On-line scheduling refers to algorithms that must make decisions regarding incoming jobs whilst other jobs are running. Examples of on-line algorithms include: First-Come-First-Serve, Backfilling and List Scheduling. Offline algorithms have full knowledge of all jobs before making scheduling decisions. Examples of offline algorithms include: SMART, Preemptive-Smith-Ratio-Scheduling and Longest Reference First.

The talk describes a new framework, called Convergent Scheduling (CS), for scheduling a continuous stream of batch jobs on the machines of large-scale heterogeneous computing farms. The proposed solution utilises a set of heuristics that guide the scheduler in making decisions. Each heuristic addresses a specific problem constraint and contributes to the calculation of a priority value that measures the degree of match between a job and a machine. The scheduler aims to schedule arriving jobs whilst respecting their deadline requirements and optimising the utilisation of both hardware and software resources. It enables a job-scheduling plan to be drawn up on the basis of the current state of the system (i.e. resource availability, jobs currently running), and information relating to jobs awaiting execution.

25 September 2007

Assoc. Prof. RNDr. Michal Kozubek, Ph.D., FIMU, Brno

Simulation of image degradation in optical microscopy

Abstract:

Studying the behaviour of algorithms for processing microscope images and comparing the quality of the results produced by these algorithms requires access to so-called ‘ground truth’ information, i.e. the correct (true) result. We can then define the quality of a given algorithm’s result as the magnitude of the deviation from this ‘truth’. Unfortunately, in the vast majority of applications in optical microscopy, this ‘truth’ is not available or is replaced by an expert’s estimate (by a biologist or doctor). However, different experts often have differing views on what constitutes the truth. The quality of the algorithm’s result is then assessed subjectively.

In order to evaluate the quality of the result objectively, we have developed a simulator of real biological objects (cells and their parts) and a simulator of image degradation as the image passes through the optical system and during detection and conversion into digital form. The image of the simulated object undergoes virtual passage through an optical system and virtual capture into computer memory. Algorithms are then applied to this distorted and noisy image, which attempt to restore the original image or perform measurements on the objects within the image. The results of the algorithms are then compared with the ground truth, which is available in this case.

2 October 2007

Doc. Ing. Lukáš Sekanina, Ph.D., FIT VUT, Brno

Evolutionary circuit design: Principles, applications, implications

Abstract:

This lecture will address the topic of evolutionary circuit design. Following a summary of relevant findings in the field of evolutionary algorithms and reconfigurable devices, examples of evolutionarily designed circuits will be presented which, in certain respects, exhibit properties unattainable by conventional design techniques. Finally, the implications of using evolutionary design will be discussed from the perspective of the so-called ‘implementation problem’, which seeks to clarify the relationship between abstract and physical computation.

9 October 2007

Mgr. Hana Rudová, Ph.D., FIMU, Brno

Dynamic Scheduling

Abstract:

Scheduling encompasses a broad range of problems with many different aspects arising from practical applications and studied through various theoretical approaches. The complete information required for scheduling is sometimes available before the problem is solved. However, the problem often changes over time, so the scheduler must respond to the changed state of the problem, and dynamic schedule updates are required. The revised schedule should often take into account the existing solution to avoid generating too many undesirable changes.

This talk will describe the general scheduling problem from the perspective of static and dynamic/changing problems. Methodologies based on local search methods will be presented, and their applicability to dynamic problem-solving will be discussed. Two case studies will demonstrate the use of dynamic scheduling in practical, real-life problems. The main features of the scheduling system for the large-scale timetable-making problem at Purdue University will be presented. A local search-based algorithm enables the solution of a variety of timetable-making problems for different scheduling units at Purdue University, where the largest problem comprises 800 courses and 55 classrooms. The second study focuses on the scheduling of jobs in a Grid environment. A novel, incremental approach to the use of local search algorithms enables the construction of better solutions within a reasonable timeframe.

16 October 2007

Doc. Ing. Ivan M. Havel, CSc., Ph.D., CTS, Prague

Enactive robotics

Abstract:

According to one school of thought in cognitive science, (human) cognition is based on the premise of an embodied agent in a natural environment. An agent acquires knowledge about the surrounding world and about its ability to interact with it through sensorimotor interaction, in which the traditional distinction between perception and action disappears. This so-called enactive approach is based on the work of F. Varela and others. In this lecture, I shall attempt to outline how a similar approach might be applied in robotics. In this context, I shall mention some recent reflections on machine consciousness (MC) – some authors regard enactive cognition as the basis of subjective self-awareness.

Chella, A., Manzotti, R. (Eds): Artificial Consciousness. Imprint Academic, Exeter 2007.

The current landscape in cognitive science is characterised by a growing interest in the ecological-embodied-enactive approach (Varela et al., 1991; Gallagher and Varela, 2001). According to this view, cognition is best characterised as belonging to embodied, situated agents. In this paper, I will discuss the possible implications of the enactive approach for future robotic systems. In particular, the enactive approach to perception would lead to robots whose ability to perceive not only depends on, but is constituted by, their possession of certain sensorimotor skills (Noë, 2004). The proposed enactive scheme may consist of six successive procedures: (1) to register data from proprioception, kinesthesia and touch; (2) to associate these data with coincident low-level visual inputs; (3) to store salient combinations; (4) to infer, store and actualise laws of sensorimotor contingencies; (5) using these laws to execute relevant bodily movements in order to supplement missing data, verify hypotheses and resolve ambiguities (‘action for perception’); and (6) continuously categorising and recategorising various higher-level objects situated in the environment.

Varela, F. J., Thompson, E., & Rosch, E. (1991): The Embodied Mind: Cognitive Science and Human Experience. The MIT Press, Cambridge, Mass.

S. Gallagher and F. Varela (2001): ‘Redrawing the map and resetting the time’. In: S. Crowell et al. (eds), *The Reach of Reflection: Issues for Phenomenology’s Second Century* (www.electronpress.com).

A. Noë (2004): Action in Perception. The MIT Press, Cambridge, Mass.

23 October 2007

Prof. RNDr. Jana Musilová, CSc., Faculty of Science, Masaryk University, Brno

Variational Theories in Physics and Their Current Mathematical Framework

Abstract:

Leaving aside the problems that have been gradually formulated since antiquity and which, from the perspective of today’s classification, are typically variational problems, the problem of the brachistochrone (Johann Bernoulli – 1697). Most of today’s key physical theories are so-called variational theories. This means that their equations of motion (ordinary differential equations in mechanics, partial differential equations in field theories) can be derived from the variational principle. It can therefore be said that the fundamental need for the development of the calculus of variations arises from physics. This is one of the reasons why the calculus of variations is one of the most intensively developed areas of mathematical physics.

This lecture, designed for a computer science colloquium, will, following a brief historical overview and the presentation of typical examples, focus on the formulation of the variational principle, its significance in physical theories, a general overview of the current mathematical apparatus of variational theories, and its application in solving fundamental general problems associated with the variational principle. These include, in particular, the solution to the so-called trivial variational problem (which leads to left-hand sides of the equations of motion that are all zero) and the inverse variational problem (the ability to determine whether given equations of motion arise from the variational principle). The lecture will be illustrated with examples.

30 October 2007

Geraint Price, Royal Holloway, University of London

The Emperor’s New Clothes: the danger of relying on “strong” authentication

Abstract:

In this talk, we will outline some of the difficulties faced by those implementing security protocols in distributed systems. Many designers of cryptographic primitives assume the pre-existence of a cryptographic means of bootstrapping the authentication phase of a protocol. In real-world distributed systems, this is not always feasible. For many in the security research community, weaker notions of authentication are to be dismissed out of hand when proposing security designs. We will argue that building supposedly ‘secure’ protocols on the false assumption of a non-existent strong authentication mechanism is just as dangerous, if not more so, as using a weak authentication primitive. In presenting our case, we hope to stimulate a debate centred on the notion that, for some applications and security mechanisms, security researchers need to embrace alternative approaches to achieving their goals rather than adhering to the currently accepted orthodoxy.

6 November 2007

Prof. RNDr. Jiří Matoušek, DrSc., KAM UK, Prague

Voronoi diagrams and zone diagrams

Abstract:

First, we recall the classical and widely applied concept of the Voronoi diagram. We then discuss a new variation of this concept known as the zone diagram. Given points (sites) p_1,...,p_n in the plane, each p_i is assigned a region R_i, but in contrast to the ordinary Voronoi diagrams, the union of the R_i has a non-empty complement, the neutral zone. The defining property is that each R_i consists of all points that lie closer (non-strictly) to p_i than to the union of all the other R_j. Thus, the zone diagram is defined implicitly, by a fixed-point property, and neither its existence nor its uniqueness seem obvious. We prove both, as well as the convergence of a natural iterative algorithm for computing it. Many challenging questions remain open, some of them even for the case of two points (where the regions are bounded by an apparently new and interesting planar curve).

Joint work with Tetsuo Asano and Takeshi Tokuyama.

13 November 2007

Alexander Okhotin, Ph.D., University of Turku, Finland

Language equations as a model of syntax

Abstract:

The basic model of syntax is a context-free grammar, which can be naturally regarded as a system of language equations using the operations of union and concatenation. More general families of language equations lead to more expressive kinds of formal grammars. This talk is about two such families obtained by adding the missing Boolean operations. The resulting families of grammars are conjunctive grammars, which can express the conjunction of syntactic conditions, and Boolean grammars, which are further equipped with negation. Their extended expressive power and the intuitive clarity of their descriptive methods make them a more powerful tool for language specification than context-free grammars. At the same time, the main context-free parsing algorithms, such as the Cocke–Kasami–Younger algorithm, the recursive descent algorithm and the generalised LR algorithm, can be extended to Boolean grammars without an increase in computational complexity, and have been implemented in software. These results will be reviewed in the talk, leading to the thesis that Boolean grammars are ‘better context-free grammars’.

20 November 2007

Prof. Irina Perfiljeva, CSc., University of Ostrava

Simple and efficient data processing based on fuzzy transformation

Abstract:

In classical mathematics, a number of special transforms (Fourier, Laplace, integral and wavelet transforms) are used to construct approximate models, which are then applied in various fields. The main idea behind these techniques is to transform the given data into a special space, in which calculations are simpler. The subsequent transformation back into the original space yields an approximate model or an approximate solution.

In this lecture, we will demonstrate the relationship between well-known methods and methods for constructing fuzzy approximation models. We shall introduce a general method of fuzzy transformation, which encompasses both classical methods and approximation methods based on the processing of fuzzy IF-THEN rules studied in fuzzy modelling.

Fuzzy transformation has a number of beneficial properties that are of interest for applications in a wide variety of fields. In this lecture, we will focus on its use in data processing, namely signal filtering, image compression and decompression, image fusion and association mining from numerical data. We will demonstrate all the results using practical examples.

27 November 2007

Prof. Ing. Zdeněk Strakoš, DrSc., UI CAV, Prague

Nonlinear problems in the analysis of Krylov subspace methods

Abstract:

Consider a system of linear algebraic equations A x = b where A is an n by n real matrix and b a real vector of length n. Unlike the linear iterative methods based on the idea of splitting A, the Krylov subspace methods, which are used in computational kernels of various optimisation techniques, seek an optimal approximate solution x^n in the subspaces K_n (A, b) = { b, Ab, …, A^{n-1}b}, n = 1, 2, … (here we assume, without loss of generality, that x^0 = 0). Consequently, although the problem A x = b is linear, Krylov subspace methods are not. Their convergence behaviour cannot be viewed as an (unimportant) initial transient stage followed by the subsequent convergence stage. Apart from very simple cases—which, from the point of view of Krylov subspace methods, are uninteresting— it cannot be meaningfully characterised by an asymptotic rate of convergence. In Krylov subspace methods such as the conjugate gradient method (CG) or the generalised minimal residual method (GMRES), the optimality at each step across Krylov subspaces of increasing dimensionality renders any linearised description inadequate.

CG applied to Ax = b with a symmetric positive-definite matrix A can be viewed as a method for the numerical minimisation of the quadratic functional 1/2 (Ax, x) – (b, x). In order to reveal its non-linear nature, we regard CG as a matrix formulation of the Gauss–Christoffel quadrature, and show that it essentially solves the classical Stieltjes moment problem. Moreover, although the behaviour of CG is fully determined by the spectral decomposition of the problem, the relationship between convergence and spectral information is by no means simple. We shall explain several phenomena where an intuitive, commonly used line of reasoning can lead to incorrect conclusions, as found in the literature. We also show that rounding error analysis of CG provides a fundamental understanding of seemingly unrelated problems in convergence analysis and in the theory of Gauss–Christoffel quadrature.

In the remaining time, we shall demonstrate that, in the unsymmetric case, the spectral information is not generally sufficient to describe the behaviour of Krylov subspace methods. In particular, given an arbitrarily prescribed convergence history of GMRES and an arbitrarily prescribed spectrum of the system matrix, there always exists a system Ax=b such that GMRES follows the prescribed convergence whilst A has the prescribed spectrum.

PDF version

4 December 2007

Ing. Miroslav Karásek, DrSc., Institute of Physical Electronics, Czech Academy of Sciences

Fibre amplifiers for optical communications

Abstract:

This lecture will briefly summarise the development of fibre amplifiers and their significance for optical communications. The physical principles of the most commonly used types of amplifiers – those based on rare-earth-doped fibres, Raman fibre amplifiers (RFAs) and parametric fibre amplifiers (PFAs) – will be described. The focus will be on erbium-doped fibre amplifiers (EDFAs), and the difference in the design of EDFAs for the C-band (1530–1560 nm) and the L-band (165–162 nm) will be explained.

For this type of fibre amplifier, systems of partial differential equations describing the fundamental physical processes relevant to their operation will be derived, and numerical methods suitable for solving them will be demonstrated. In the case of RFAs and PFAs, equations describing the propagation of pump, signal and amplified spontaneous emission waves will be presented, along with numerical models for both types of these fibre amplifiers.

Attention will be paid to transient phenomena in fibre amplifiers arising when the number of transmitted channels changes in reconfigurable WDM networks, and to ways of suppressing them.

We shall present some examples of non-standard applications of all types of fibre amplifiers in the CzechLight experimental network.

11 December 2007

Doc. Dr. Ing. Jan Černocký, FIT VUT, Brno

Search in speech, language identification and speaker recognition in speech@fit

Abstract:

Speech is the most important modality in human-to-human communication. Even in face-to-face communication, it may account for more than 80 per cent of the information, and in the case of a telephone conversation, this proportion rises to 100 per cent. Speech is ubiquitous in many electronic media (landline and mobile networks, IP telephony, dedicated channels, etc.).

In many applications (e-learning, meeting recognition, audio archive search), the problem is usually not to obtain the speech but to efficiently process thousands of hours of speech recordings. Typically, speech is processed by human experts, but this processing capacity is always limited: by a lack of qualified personnel, a lack of budget, insufficient knowledge of foreign languages, insufficient security clearances (for security applications), or a combination of the above.

Automatic speech search techniques can help to find the requested information – the ‘needle in a haystack’ – within a reasonable time and without extensive human labour. However, they should not be regarded as all-powerful – they are not capable of replacing qualified personnel who will always have to carry out the final analysis and make the final decisions. They are capable of automating certain processing steps and ‘narrowing the search space’ for humans.

Let us first define the categories of speech search:

The task of Large Vocabulary Continuous Speech Recognition (LVCSR) is to determine ‘what was said’ or to provide a textual transcription of speech. The best-performing LVCSR systems are based on complex acoustic models trained on thousands of hours of transcribed speech and on language models trained on gigabytes of text. The biggest challenge in LVCSR is processing spontaneous data for which developers lack speech and language resources.

In some situations, LVCSR is not the most suitable method for finding information in speech – as it is constrained by the recognition vocabulary, it is difficult to find rare information such as new proper names (companies, politicians, geographical names). In this case, it is necessary to use PHONETIC SEARCH, which operates not on the output of the word recogniser, but rather on directed graphs containing smaller units – phonemes.

Just as important as the content of speech is the information ‘who said it’ – this is addressed by SPEAKER RECOGNITION. We refer to speaker identification when the task is to select one speaker from a set of N speakers, or to speaker verification, where it is necessary to confirm the claimed identity of a speaker.

Last but not least, LANGUAGE IDENTIFICATION is required in speech search, either to be used as a search criterion in its own right or to route speech segments to the appropriate language-dependent recogniser.

This talk will focus primarily on the first two topics mentioned – LVCSR and phonetic search, collectively referred to as SPOKEN TERM DETECTION, primarily in the context of the first edition of the NIST Spoken Term Detection (STD) evaluations and the development of the STD system within our research group – Speech@FIT. We will also briefly mention our work in speaker recognition and language identification.

18 December 2007

Doc. Mgr. Jiří Srba, Ph.D., University of Aalborg, Denmark

Translations between Timed Automata and Petri Nets with Time

Abstract:

A timed extension of Petri nets, where every token has an associated age from the domain of real numbers, is a well-studied formalism for modelling real-time systems. Unfortunately, there is as yet no tool support for the verification of such nets. In this talk, I shall describe mutual translations between the timed extension of Petri nets and the model of timed automata as used, for example, in the verification tool UPPAAL. A prototype tool with a graphical user interface (GUI) that translates Petri net verification queries into UPPAAL-ready timed automata will be presented, including some preliminary experimental results.