Program kolokvií s abstrakty pro semestr Jaro 2006

21. 2. 2006
doc. RNDr. Luboš Brim, CSc., FIMU, Brno
Detekce cyklů v masivních grafech
Abstrakt: Masivní grafy se přirozeně objevují v mnoha aplikacích. Příkladem mohou být grafy pro modelování webu, grafických informačních systémů či telekomunikačních sítí. Tyto grafy nelze umístit do operační paměti jednoho "běžného" počítače a grafové algoritmy pro jejich analýzu vyžadují přístup k externí paměti. V současné době jsou intenzívně zkoumány možnosti využít jako dodatečnou pamě» buď externí disky nebo distribuovanou operační pamě» více vzájemně propojených počítačů. V obou případech však zpravidla není možné použít standardní sekvenční grafové algoritmy a je nezbytné navrhnout zcela nové algoritmy, které se od nich v mnoha případech zásadně liší.

V přednášce budou na příkladu specifického grafového problému demonstrovány nejnovější výsledky pro prostředí s distribuovanou pamětí. Budou uvedeny základní metody a techniky pro detekci akceptujících cyklů, představeny klíčové myšlenky jednotlivých algoritmů a diskutovány výhody a nevýhody těchto algoritmů.

28. 2. 2006
doc. Dr. Ing. Petr Hanáček, FIT VUT, Brno
Bezpečnost informačních systémů a chyby při návrhu - jsme schopni jim zabránit?
Abstrakt: Pro zajištění bezpečnosti informačních systémů existují standardizované postupy bezpečného návrhu, vývoje a testování a propracovaná kritéria pro hodnocení bezpečnosti těchto systémů. Přesto se i při dodržení těchto postupů v reálných systémech objevují bezpečnostní chyby, kterým tyto postupy nedokázaly zabránit. V přednášce se autor pokusí analyzovat, zda dnešní moderní metody návrhu bezpečných systémů musí skutečně vést k tomu, že navržený systém je bezpečný a jakou roli v tom hrají standardy, formální postupy a neformální intuice.
7. 3. 2006
doc. RNDr. Roman Barták, Ph.D., MFF UK, Praha
Modelování unárních zdrojů pomocí podmínek -- Constraint Models for Unary Resources
Abstrakt: Rozvrhování s omezujícími podmínkami patří k nejúspěšnějším aplikacím technologie splňování podmínek. Je založeno na myšlence popisu rozvrhovacího problému jako problému splňování omezujících podmínek, tedy pomocí proměnných, jejich domén (množin možných hodnot) a relací/podmínek mezi proměnnými. Přednáška popisuje naše poslední výsledky na poli modelování unárních (někdy také nazývaných disjunktivních) zdrojů, tj. zdrojů, které v libovolném čase mohou zpracovávat maximálně jednu aktivitu. Důraz bude kladen na popis nových inkrementálních filtračních algoritmů, které omezují prohledávaný prostor zmenšováním časových oken aktivit a odvozováním nových precedenčních vztahů mezi aktivitami.

Constraint-based scheduling represents one of the successes of constraint satisfaction technology. It is based on 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 called disjunctive) resources where at most one activity can be processed at a given time. The emphasis is put on description of new incremental filtering algorithms that prune the search space by shrinking time windows of activities and deduce new precedence relations between the activities.

14. 3. 2006
prof. RNDr. Jozef Kelemen, DrSc., Slezká univerzita v Opavě
85 let robotů
Abstrakt: V přednášce doprovázené množstvím (možná zajímavých) obrázků nastíníme některé z cest, které přivedly v roce 1921 ke premiéře hry Karla Čapka R. U. R., povíme něco (možná překvapivé) o osudu hry, o tom, oč v ní autorovi (asi) šlo, a o tom, jaké osudy pak měli jeho roboti a jak se z nich stali roboty v literatuře, ve filozofii, ve vědě i v inženýrství.
21. 3. 2006
prof. Ing. Jiří Jan, CSc., FEKT VUT, Brno
Model MRI signálu a jeho konverze na obrazová data
Abstrakt: Zobecněný model MRI signálu, vycházející z prostorové distribuce příčné magnetizace zahrnuje všechny případy iniciace, nikoli jen obvyklý statický případ a umožňuje transparentně odvodit postup konverze měřicího signálu na obrazová data prostřednictvím vícerozměrné Fourierovy transformace. Výklad z hlediska zpracování signálových a obrazových dat.
28. 3. 2006
RNDr. Tomáš Kaiser, Dr., KMA ZČU, Plzeň
Prohledávání grafů
Abstrakt: V přednášce podáme přehled hlavních výsledků a otázek se vztahem k problému prohledávání grafu. Jedna z formulací tohoto problému zahrnuje skupinu "četníků" a "lupiče", umístěné ve vrcholech určitého grafu G. Lupič a četníci se pohybují střídavě, a to vždy mezi sousedními vrcholy. Cílem četníků je zadržet lupiče, jeho cílem je naopak se zadržení vyhnout. Základní otázkou je, která ze stran má v grafu G vyhrávající strategii, případně kolik četníků je potřeba k tomu, aby takovou strategii měla jejich strana. Ukážeme, jak odpovědi na tyto otázky závisejí na dalších parametrech grafu G.

Doktorandský seminář
Kterak se zrodí mladý vědec s hostem Mgr. Tomášem Brázdilem
Témata k povídání a diskuzi:
  • Uvedení nového semináře a jeho zaměření do budoucna.
  • Kde se vlastně dostat k VĚDĚ a jak si vybrat školitele.
  • První problémy doktorandského života a jejich řešení.
  • Jak se úspěšně dopracovat až k hotové dizertaci...
4. 4. 2006
doc. RNDr. Luděk Matyska, CSc., FIMU, Brno
Vícebodová videokonference v nekomprimované High Definition kvalitě (teorie i technologie v pozadí) -- Multipoint videoconference in uncompressed HD quality (theory and technology behind the scene)
Abstrakt: To prepare and successfully run a multipoint HD videoconference over a large distance in the current Internet resembles a puzzle composition. Its individual pieces are the network, 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 performed during the second half of 2005 to show these puzzle pieces---the theory and technology used to construct them---and also to discuss what knowledge is necessary to actually build the whole puzzle. Also, a combination with a visualization system using the same underlying transport and display principles will be demonstrated. Videoconferencing systems are just a part of the complete collaborative environment, and the lecture will be concluded with a brief vision of the collaborative environments of the future these experiments are helping to define.
11. 4. 2006
Gelasio Salazar, PhD., IICO-UASLP, Mexico
The crossing number problem
Abstrakt (pdf)
Abstrakt: The crossing number cr(G) of a graph G is a measure of the nonplanarity 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. Crossing number questions were first raised by Turán in the mid 1940's. Besides their intrinsical theoretical interest, they have important applications, most importantly in the area 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 been long conjectured that cr(Km,n)=Zm,n. This has been verified only for m<7 (and arbitrary n). The exact knowledge of cr(K6,n) implies the best general bound known previous to our work, namely cr(Km,n)>=0.8Zm,n.

In this talk we will report on some recent research on this problem. We attacked the problem of estimating cr(K7,n) for large values of n. We analyzed combinatorial and topological properties of drawings of K7,n, and came up with a quadratic programming problem whose solution gives a lower bound for cr(K7,n).

The quadratic programming problem we originally obtained is quite large (the associated matrix is of size 720 x 720). To solve this problem, we used state-of-the-art quadratic programming techniques, combined with a bit of invariant theory of permutation groups. As a result, we were finally able to give the improved bound cr(K7,n)>=2.1796n2 - 4.5n, quite close to Z7,n=2.25 n2+ O(n). Our bound for cr(K7,n) implies that, for each fixed m>8, limn->∞cr(Km,n)/Z(m,n)>=0.83m/(m-1). We also obtained as a by-product an improved bound for the crossing number of the complete graph Kn.

18. 4. 2006
prof. Zdeněk Strakoš, DrSc., Ústav informatiky AV ČR
Bidiagonalization as a fundamental decomposition of data in linear approximation problems
Abstrakt (pdf)
25. 4. 2006
Mgr. Filip Procházka, RNDr. Zdenko Staníček, Ph.D., FIMU, Brno
Universální informační robot - principy a aplikace
Abstrakt: Problém efektivní práce se znalostmi je s rozpínáním se kyberprostoru stále aktuálnější. Většina znalostí a dat již v kyberprostoru je přítomna, není ale snadno dostupná. V presentaci bude ilustrováno, jak lze tento problém řešit pomocí virtuálního asistenta v podobě Universálního Informačního Robota (UIR). Bude popsáno, jak lze pomocí něj vytvořit tzv. virtual knowledge network z existujících datových zdrojů. Řešení tohoto problému bude ilustrováno také na příkladech z projektu UIRON - využití UIR v onkologickém výzkumu - řešeném v rámci grantu AV řešitelským konsorciem UVT MU, CBA MU a Masarykův onkologický ústav. Bude předvedana krátká ukázka fungujícího systému a vysvětleny základní principy na kterých je postaven.
2. 5. 2006
prof. Ing. Pavel Zezula, CSc., FIMU, Brno
Scalable and distributed similarity search structures
Abstrakt: Due to the increasing complexity of current digital data, similarity search has become the fundamental computational task in a variety of applications and many similarity search structures have been proposed in the literature. Unfortunately, computational costs are still high and the linear scalability of single computer implementations prevents from efficient searching of large data volumes. In the talk, we shortly describe four very recent scalable distributed similarity search techniques and study performance of their implementations on the same cluster of peer computers executing queries on three different datasets. Though all the methods employ parallelism to speed up query execution, different advantages for different objectives have been identified by experiments.

Doktorandský seminář
Bibliografické citace a citační etika s hostem Jiřím Kratochvílem z Ústřední knihovny PřF MU
  • Zásady citační etiky.
  • Problematika plagiátorství (vysvětlení pojmu, příklady mediálně známých kauz).
  • Tvorba bibliografických citací nejčastěji citovaných typů dokumentů.
  • Další podrobnosti
9. 5. 2006
prof. RNDr. Jiří Rosický, DrSc., PřF MU, Brno
Homotopie a souběžnost
Abstrakt: Cílem přednášky je ukázat, že metody algebraické topologie (zejména teorie homotopií) mohou být užitečné pro teorii souběžnosti. Výklad bude elementární a mimo jiné předvede "diskrétní" přístup k teorii homotopií pomocí simpliciálních množin ( = nekonečně-dimenzionální grafy). Poskytne přirozený pohled na bisimulace (zaváděné otevřenými zobrazeními) a na jejich souvislost s homotopiemi. Jako základní formální nástroj budou použity tzv. slabé faktorizační systémy.

Doktorandský seminář
Citační databáze a elektronické zdroje s hosty Jiřím Kratochvílem z PřF MU a Miroslavem Bartoškem z ÚVT MU
  • Seznámení s databázemi Web of science, rejstřík pro hodnocení vědeckých časopisů.
  • Program a projekty 1N.
  • Zásady a možnosti používání licencovaných elektronických informačních zdrojů.
  • Stručné představení zdrojů: IEEE Computer Society Digital Library, ACM Digital Library, LNCS Online, další zdroje.
16. 5. 2006
doc. Zdeněk Kotásek, CSc., FIT VUT, Brno
Principy testování číslicových systémů
Abstrakt: Budou popsány základní principy syntézy/návrhu číslicových systémů s ohledem na jejich testovatelnost (synthesis/design for testability) a principy testování založené na uplatnění těchto principů. Dále budou vysvětleny tyto pojmy a techniky: řiditelnost/pozorovatelnost vnitřních bodů testovaného obvodu, metody autonomního testování, metody strukturovaného návrhu, testování spojů, využití těchto metod v konstrukci výpočetních systémů. Budou zmíněny výsledky výzkumu realizovaného v oblasti diagnostiky a testování číslicových obvodů na FIT VUT v Brně.
23. 5. 2006
doc. Ing. Jiří Sochor, CSc., FIMU, Brno
Interaction Tools and Techniques in Virtual Environments
Abstrakt: In May 2000 we presented an introductory talk "Human Computer Interaction in Virtual Environment", where we stated the main goals of specific research in VR: Interaction in 3D space should enable users to interact freely with virtual objects. 6 years later, we will briefly summarize the development in this field and present the contributions achieved in HCI Laboratory at Masaryk University.