Program kolokvií s abstrakty pro semestr Podzim 2007

18. 9. 2007

prof. Ranieri Baraglia, ISTI - Institute of the Italian National Research Council Pisa, Italy

A Job Scheduling Framework for Large Heterogeneous Computing Farms

Abstrakt:

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

A major effort has been devoted to understand job scheduling problems in scientific literature. Job scheduling algorithms can be divided into two classes: on-line and offline. On-line scheduling are those that have to take decisions for arriving jobs while other jobs are running. Examples of on-line algorithms are: First-Come-First-Serve, Backfilling, List Scheduling. Offline algorithms know all the jobs before taking scheduling decisions. Examples of offline algorithms are: SMART, Preemptive-Smith-Ratio-Scheduling, 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 exploits a set of heuristics that guide the scheduler in making decisions. Each heuristics manages a specific problem constraint, and contributes to carry out a priority value that measures the degree of matching between a job and a machine. The scheduler aims to schedule arriving jobs respecting their deadline requirements, and optimizing the utilization of hw resources as well as the sw resources. It permits to carry out a job-scheduling plan on the basis of the current status of the system (i.e. resource availability, executing jobs), and information related to jobs waiting for execution.

25. 9. 2007

doc. RNDr. Michal Kozubek, Ph.D., FIMU, Brno

Simulace degradace obrazu v optické mikroskopii

Abstrakt:

Studium chování algotitmů zpracování obrazu z mikroskopu a srovnání kvality výsledků algoritmů mezi sebou vyžaduje dostupnost tzv. ground truth informace neboli správného (pravdivého) výsledku. Míru kvality výsledku daného algoritmu pak můžeme definovat jako velikost odchylky od této pravdy. Bohužel v drtivé většině aplikací v optické mikroskopii není tato pravda dostupná nebo je nahrazena jejím odhadem expertem (biologem či lékařem). Často mají ale různí experti různé názory na to, co je pravda. Kvalita výsledku algoritmu je pak odhadována subjektivně.

Za účelem objektivního hodnocení kvality výsledku jsme vyvinuli simulátor skutečných biologických objektů (buněk a jejich částí) a simulátor degradace obrazu při průchodu optickou soustavou a při vyčítání a převodu do digitální podoby. Obraz simulovaného objektu je podroben virtuálnímu průchodu optickou soustavou a virtuálnímu snímání do paměti počítače. Na takto zkreslený a zašuměný obraz jsou pak aplikovány algoritmy, které se snaží zrestaurovat původní obraz nebo provést nad objekty v obraze měření. Výsledky algoritmů jsou pak porovnány s pravdou, která je v tomto případě dostupná.

2. 10. 2007

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

Evoluční návrh obvodů: Principy, aplikace, důsledky

Abstrakt:

V přednášce bude uvedena problematika evolučního návrhu obvodů. Po shrnutí relevantních poznatků z oblasti evolučních algoritmů a rekonfigurovatelných zařízení budou prezentovány příklady evolučně navržených obvodů, které v některých ohledech vykazují vlastnosti nedosažitelné konvenčními návrhovými technikami. Závěrem budou diskutovány důsledky používání evolučního návrhu z pohledu tzv. "problému implementace", který se snaží ozřejmit vztah mezi abstraktním a fyzickým počítáním.

9. 10. 2007

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

Dynamic Scheduling

Abstrakt:

Scheduling represents a wide area of problems with many different aspects given by practical applications and studied by various theoretical approaches. Complete information necessary for scheduling is sometimes available before the problem is solved. However, the problem often changes as time goes, scheduler must react on the changed state of the problem and dynamic schedule updates are needed. Revised schedule should often take into account the existing solution not to generate too many undesirable changes.

This talk will describe the general scheduling problem from the point of view of static and dynamic/changing problems. Methodologies based on local search methods will be presented and their applicability for dynamic problem solving will be discussed. Two case studies will demonstrate the use of dynamic scheduling in practical real-life problems. Main features of the scheduling system for the large scale timetabling problem at Purdue University will be presented. Local search based algorithm allows solving variety of timetabling problems for different scheduling units at Purdue University where the largest problem has 800 courses and 55 classrooms. The second study is concentrated on scheduling of jobs in the Grid environment. A novel incremental use of local search algorithms allows to construct better solutions in a reasonable time.

16. 10. 2007

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

Enaktivní robotika - Enactive robotics

Abstrakt:

Podle jednoho směru bádání v kognitivní vědě je (lidská) kognice založena na předpokladu vtěleného subjektu v přirozeném prostředí. Agent získává znalosti o okolním světě a o svých schopnostech do něj zasahovat na principu senzomotorické interakce, v níž mizí tradiční rozlišování percepce od akce. Tento tzv. enaktivní přístup je založen na pracích F. Varely a dalších. V přednášce se pokusím naznačit, jak by se podobný přístup mohl uplatnit v robotice. V této souvislosti se zmíním o některých nedávných úvahách o strojovém vědomí (MC = machine consciousness) – někteří autoři považují enaktivní kognici za základ subjektivního vědomí sebe sama.

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

The current scene in cognitive science is characterized 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 characterized as belonging to embodied, situated agents. In the contribution I will discuss possible implications of the enactive approach for future robotic systems. In particular, the enactive approach in perception would lead to robots whose ability to perceive not only depends on, but is constituted by, their posession of certain sensorimotor skills (Noë, 2004). The proposed enactive scheme may consist of six successive procedures: (1) to register data from proprioception, kinesthesis, and touch; (2) to associate these data with coincident low-level visual inputs; (3) to store salient combinations; (4) to infer, store and actualize laws of sesorimotor contingencies; using these laws (5) to execute pertinent bodily movements in order to supplement missing data, verify hypotheses, and resolve ambiguities ("action for perception") and (6) continuously to categorize and recategorize 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. 10. 2007

prof. RNDr. Jana Musilová, CSc., PřF MU, Brno

Variační teorie ve fyzice a jejich současný matematický aparát

Abstrakt:

Odhlédneme-li od problémů, které byly postupně formulovány již od starověku a jsou z hlediska dnešní klasifikace úlohami typicky variačními, lze za první variační úlohu cíleně takto formulovanou považovat úlohu o brachistochroně (Johann Bernoulli – 1697). Většina současných klíčových fyzikálních teorií jsou tzv. teorie variační. Znamená to, že jejich pohybové rovnice (obyčejné diferenciální rovnice v mechanice, parciální diferenciální rovnice v teoriích pole) jsou odvoditelné z variačního principu. Lze tedy říci, že základní potřeba rozvoje variačního počtu vzchází z fyziky. I proto je variační počet jednou z intenzivně rozvíjených oblastí matematické fyziky.

Přednáška, koncipovaná pro informatické kolokvium, se po krátké historické expozici a uvedení typických příkladů zaměří na formulaci variačního principu, jeho význam ve fyzikálních teoriích, orientační přehled o současném matematickém aparátu variačních teorií a jeho použití při řešení základních obecných problémů spjatých s variačním principem. Patří k nim zejména řešení tzv. triviálního variačního problému (vede k identicky nulovým levým stranám pohybových rovnic) a inverzního variačního problému (možnost rozhodnout, zda dané pohybové rovnice vznikly z variačního principu). Přednáška bude doplněna příklady.

30. 10. 2007

Geraint Price, Royal Holloway, University of London

The Emporer's New Clothes: the danger of relying on "strong" authentication

Abstrakt:

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. To many in the security research community weaker notions of authentication are to be dismissed without further thought when proposing security designs. We will argue that building supposedly "secure" protocols on a 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 which centres on the notion that, for some applications and security mechanisms, security researchers need to embrace other forms of achieving their goals than is currently the accepted gospel.

6. 11. 2007

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

Voronoi diagrams and zone diagrams

Abstrakt:

First we recall the classical and widely applied concept of Voronoi diagram. Then we discuss a new variation of this concept called 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 nonempty 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 convergence of a natural iterative algorithm for computing it. Many challenging questions remain open, some of them already 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. 11. 2007

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

Language equations as a model of syntax

Abstrakt:

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 conjunction of syntactic conditions, and Boolean grammars, which are further equipped with negation. Their extended expressive power and the intuitive clarity of their descriptive means make them a more powerful tool for language specification than the context-free grammars. At the same time, the main context-free parsing algorithms, such as the Cocke-Kasami-Younger, the recursive descent and the generalized LR, can be extended to Boolean grammars without an increase in computational complexity, and have been implemented in software. These results will be surveyed in the talk, leading to the thesis of Boolean grammars' being "better context-free grammars".

20. 11. 2007

Prof. Irina Perfiljeva, CSc., Ostravská univerzita

Snadné a efektivní zpracování dat na základě fuzzy transformace

Abstrakt:

V klasické matematice se používá řada speciálních transformací (Fourierova, Laplaceova, integrální, wavelety) ke konstrukci aproximačních modelů, které jsou pak aplikovány v různých oblastech. Hlavní myšlenkou těchto technik je převést daná data do speciálního prostoru, v němž jsou výpočty jednodušší. Následná transformace zpět do původního prostoru dává přibližný model nebo přibližné řešení.

V přednášce ukážeme vztah mezi známými metodami a metodami konstrukce fuzzy aproximačních modelů. Zavedeme obecnou metodu fuzzy transformace, která zahrnuje jak klasické metody tak i aproximační metody, které jsou založeny na zpracování fuzzy IF-THEN pravidel studovaných ve fuzzy modelování.

Fuzzy transformace má řadu dobrých vlastností, které jsou zajímavé pro aplikace v nejrůznějších oborech. V této přednášce se zaměříme na její použití při zpracování dat, a to filtrování signálu, kompresi a dekompresi obrázků, fúzi obrázků a dolování asociací z numerických dat. Všechny výsledky budeme demonstrovat na praktických ukázkách.

27. 11. 2007

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

Nonlinear problems in analysis of Krylov subspace methods

Abstrakt:

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 in the linear iterative methods based on the idea of splitting of A, the Krylov subspace methods, which are used in computational kernels of various optimization techniques, look for some optimal approximate solution x^n in the subspaces K_n (A, b) = { b, Ab, ..., A^{n-1}b}, n = 1, 2,... (here we assume, with no loss of generality, x^0 = 0). As a consequence, though 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, and from the point of view of Krylov subspace methods uninteresting cases, it cannot be meaningfully characterized by an asymptotic rate of convergence. In Krylov subspace methods such as the conjugate gradient method (CG) or the generalized minimal residual method (GMRES), the optimality at each step over Krylov subspaces of increasing dimensionality makes any linearized description inadequate.

CG applied to Ax = b with a symmetric positive definite A can be viewed as a method for numerical minimization the quadratic functional 1/2 (Ax, x) - (b,x). In order to reveal its nonlinear character, we consider CG a matrix formulation of the Gauss-Christoffel quadrature, and show that it essentially solves the classical Stieltjes moment problem. Moreover, though the CG behaviour is fully determined by the spectral decomposition of the problem, the relationship between convergence and spectral information is nothing but simple. We will explain several phenomena where an intuitive commonly used argumentation can lead to wrong conclusions, which can be found in the literature. We also show that rounding error analysis of CG brings fundamental understanding of seemingly unrelated problems in convergence analysis and in theory of the Gauss-Christoffel quadrature.

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

Pdf version

4. 12. 2007

Ing. Miroslav Karásek, DrSc., Ústav fyzikální elektroniky AV ČR

Vláknové zesilovače pro optické komunikace

Abstrakt:

V přednášce bude stručně shrnut vývoj vláknových zesilovačů a jejich význam pro optické komunikace. Budou popsány fyzikální principy nejčastěji používaných typů zesilovačů na bázi vláken dopovaných prvky vzácných zemin, ramanovských vláknových zesilovačů (RFA) a parametrických vláknových zesilovačů (PFA). Pozornost bude soustředěna na erbiem dopované vláknové zesilovače (EDFA) a bude vysvětlen rozdíl v návrhu EDFA pro pásmo C (1530-1560 nm) a pásmo L (165-162nm).

Pro tento typ vláknových zesilovačů budou odvozeny soustavy parciálních diferenciálních rovnic popisujících základní fyzikální procesy důležité pro popis jejich činnosti a ukázány numerické metody vhodné pro jejich řešení. V případě RFA a PFA budou prezentovány rovnice popisující šíření vln čerpání, signálu a zesílené spontánní emise a numerické modely obou typů těchto vláknových zesilovačů.

Pozornost bude věnovány přechodovým jevům ve vláknových zesilovačích vznikajících při změně počtu přenášených kanálů v rekonfigurovatelných WDM sítích a možnostem jejich potlačení.

Uvedeme některé příklady atypického použití všech typů vláknových zesilovačů v experimentální síti CzechLight.

11. 12. 2007

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

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

Abstrakt:

Speech is the most important modality in human to human communication. Even in face-to-face communication, it might contain more than 80% of the information and in case of a telephone conversation, this proportion goes up to 100%. Speech is omni-present in many electronic media (land-line and mobile networks, IP telephony, dedicated channels, ...).

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

Automatic speech search techniques} can help to find the requested information - the ``needle in a haystack'' - in reasonable time and without extensive human labor. However, they should not be considered almighty - they are not able to replace qualified personnel that will always have to do the final analysis and decisions. They are able to automate some processing steps and ``limit 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 textual transcription of speech. The best performing LVCSR systems are based on complex acoustic models trained on thousands 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 best suited to find the information in speech - as it is constrained by recognition vocabulary, it is hard to find rare information such as new proper names (companies, politicians, geographical). In this case, it is necessary to use PHONETIC SEARCH that operates not on the output of word recognizer, but rather on oriented graphs containing smaller units - phonemes.

As important as the contents of speech is the information ``who said it'' - this is addressed by SPEAKER RECOGNITION. We speak about speaker identification if the task is to choose one out of a set of N speakers, or about speaker verification, where it s necessary to confirm the claimed identity of a speaker.

Last but not least, LANGUAGE IDENTIFICATION is needed in speech search to be used as search criterion itself or for routing speech segments to appropriate language-dependent recognizer.

This talk will deal mainly with the first two mentioned topics - LVCSR and phonetic search, jointly called SPOKEN TERM DETECTION, mainly in light of first edition of NIST Spoken term detection (STD) evaluations and development of STD system in our research group - Speech@FIT. We will also briefly mention our work in speaker recognition and language identification.

18. 12. 2007

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

Translations between Timed Automata and Petri Nets with Time

Abstrakt:

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 of real-time systems. Unfortunately, there is no tool support for the verification of such nets yet. In this talk I will describe mutual translations between the timed extension of Petri nets and the model of timed automata as used e.g. in the verification tool UPPAAL. A prototype tool with GUI translating Petri net verification questions to UPPAAL-ready timed automata will be presented, including some preliminary experimental results.