Program kolokvií s abstrakty pro semestr Jaro 2009
- 24. 2. 2009
- Dr. Markus Chimani, Technical University of Dortmund
- How many crossings do I need to draw a graph? - Exact Optimization of NP-hard Problems
- Abstrakt:
In traditional combinatorics, we often classify problems as either
polynomially solvable or as NP-hard. In the latter case, one is tempted to concentrate on the development of heuristics or approximation algorithms, since exact algorithms would require exponential time (if P!=NP). Yet, the recent progress in
mathematical programming and computer hardware allows for algorithms
which -- eventhough theoretically exponential in the worst case -- can solve real-world instances of NP-hard problems in reasonable time to provable optimality.
In this talk we will discuss methods to solve the "crossing number problem" to provable optimality. Thereby we ask for the minimum number of edge crossings required when drawing a given graph on the plane. Although this NP-hard problem originated over 60 years ago and has seen livid research activity during that time, we still do not know much about this non-planarity measure. Even the exact crossing number for seemingly simple graphs -- like complete graphs -- are unknown. In graph drawing applications, the crossing number also often plays a central role: multiple strong heuristics have been developed, but we do not even know whether the measure is approximable for general graphs.
Despite the above, we will consider exact approaches based on linear programs, which are able to solve real-world instances to provable optimality within reasonable time bounds.
- 3. 3. 2009
- doc. Ing. Petr Sosík, Ph.D., Slezská univerzita v Opavě
- DNA Computing: Quo Vadis?
- Abstrakt: DNA Computing has moved significantly since the time of the famous Adleman's experiment in 1994. Nowadays the most prominent part of the research can be characterized by the keywords biomolecular self-organization, bionanodevices, synthetic biology. The programable molecular recognition properties of DNA is used to build nanostructures by self-assembly and to construct artificial nanomachines, biosensors etc. We give an overview of current trends and results in this interdisciplinary field.
- 10. 3. 2009
- prof. Ing. Ivo Serba, CSc., FIMU, Brno
- Math Art
- Abstrakt:
- Matematické umění jako součást Computer Artu.
- Computer Art jako produkt kybernetické éry.
- Výtvarné formy a informatika.
- Hlavní témata matematického umění – ukázky.
- 17. 3. 2009
- Mgr. Radek Pelánek, Ph.D., FIMU, Brno
- Škola hrou ve 21. století
- Abstrakt: Jakou roli mohou mít hry a soutěže ve výuce? Nad touto otázkou se zamyslíme v obecné metodické rovině, ovšem pouze stručně, protože od 17. století se na obecných metodických principech zas tak moc nezměnilo. Zaměříme se tedy především na rozbor konkrétních aktivit s důrazem na novinky, které nám umožnily informační technologie 21. století. Zmíníme jak aktivity s přímým vztahem k FI, což jsou soutěže pro středoškoláky (korespondenční semináře, Intersob, zážitkové soustředění) a vysokoškoláky (FIbot, ACM ICPC, SVOČ), tak i šifrovací hry pro veřejnost, a to české (Tmou, Sendvič) i zahraniční (MIT mystery hunt, Microsoft puzzle hunt). Na základě zkušeností z těchto aktivit se zamyslíme se nad tím, jak může FI využít soutěžní aktivity pro svoji propagaci a zpestření výuky.
- 24. 3. 2009
- RNDr. Jan Bouda, Ph.D., FIMU, Brno
- Aktuální trendy kvantové kryptografie
- Abstrakt:
V první části přednášky bude promítnut propagační film o kvantové síti
SECOQC (5 uzlů, jednotlivá spojení v délce desítek kilometrů) sestavené
ve Vídni na základě spolupráce desítek výzkumných a průmyslových skupin
z celé Evropy zahrnující několik kvantových spojení založených na
různých fyzikálních technologiích (optické vlákno, signál přenášený
vzduchem, ...).
Druhá část přednášky bude prezentovat definici a konstrukci klasických a kvantových non-malleabilních kryptosystémů:
Klasický one-time pad zajišťuje absolutní utajení zašifrované zprávy, bohužel však umožňuje útočníkovi modifikovat (neznámou) zprávu předvídatelným způsobem. Negace libovolného bitu kryptotextu způsobí bez ohledu na klíč negaci odpovídajícího bitu zprávy. Non-malleabilní kryptosystém zabraňuje cílené modifikaci zprávy, tj. je konstruován tak, aby útočník nebyl schopen předpovědět jaký důsledek má konkrétní modifikace kryptotextu.
V přednášce bude prezentována optimální (z hlediska délky klíče) konstrukce bezpodmínečně non-malleabilních klasických i kvantový kryptosystémů a demonstrováno, že non-malleabilita implikuje absolutní utajení zašifrováné zprávy.
Koncept non-malleability je aplikovatelný i v případě že délka zprávy a kryptotextu je shodná. Pokud uvažujeme kryptotext obecně větší délky než je zpráva, je autentizace speciálním případem non-malleability.
- 31. 3. 2009
- doc. Mgr. Tomáš Tyc, Ph.D., PřF MU, Brno
- Transformační optika - cesta k neviditelnosti a geometrické interpretaci optiky i mechaniky
- Abstrakt: Transformační optika je velmi mladým oborem optiky, nabízí však jak pozoruhodné aplikace (například neviditelnost), tak i velmi netradiční pohledy na dávno dobře probádané oblasti fyziky, především na optiku a mechaniku. V přednášce budou vyloženy principy transformační optiky a nového návrhu neviditelného pláště, ale i nový, geometrický pohled na zákony optiky a mechaniky.
- 7. 4. 2009
- RNDr. Daniel Kráľ, Ph.D., ITI MFF UK, Praha
- Removal Lemma for systems of linear equations
- Abstrakt:
Daniel Kral (joint work with Oriol Serra and Lluis Vena)
We are interested in analagous of the famous Removal Lemma for graphs for other mathematical objects. Vaguely speaking, the lemma says that if a given graph does not contain too many subgraphs of a given kind, then all the subgraphs of this kind can be destroyed by removing few edges. During the talk, we first provide a brief but self-contained introduction to this recently largely developed area of graph theory and we then present a proof of the following conjecture of Green:
For every k x m integral matrix A with rank k and every eps>0, there exists delta>0 such that the following holds for every N and every subset S of {1,...N}: if the number of solutions of A x = 0 with x \in S^m is at most delta N^{m-k}, then it is possible to destroy all solutions x \in S^m of A x = 0 by removing at most eps N elements from the set S.
Independently of us, Shapira obtained the same result using a different reduction to the colored version of hypergraph Removal Lemma.
- 14. 4. 2009
- doc. Dr. Ing. Pavel Zemčík, UPGM FIT VUT, Brno
- Syntéza hologramů a akcelerace jejich výpočtu
- Abstrakt:
Pavel Zemčík a Ivo Hanák
Přehled principů užívaných v holografii, optický hologram a syntéza hologramu, vztah optického pole a hologramu, výpočet optického pole, optické pole a zobrazovací metody počítačové grafiky, akcelerace výpočtů optického pole.
- 21. 4. 2009
- doc. MUDr. Josef Feit, CSc., Ústav patologie LF MU, Brno
- Hypertextové atlasy patologie
- Abstrakt:
Patologie se především zabývá hodnocením vzhledu buněk a tkání
pro diagnostické účely. Obrazové sbírky mají zásadní význam,
jak pro účely výukové, tak i referenční.
Atlasy patologie jsou na webu již přes 10 let (první veřejná verze Atlasu Dermatopatologie byla zpřístupněna v roce 1997). Jedná se o postupně narůstající sbírku obrazů různého typu (makroskopické snímky, snímky z různých zobrazovacích metod a snímky histologické). Cílem atlasů je výuka a usnadnění diagnostiky. Nejedná se tedy jen o krátkými texty doplněné obrazy, ale atlasy mají některé méně obvyklé vlastnosti:
- anotace obrazů (s možností aktivace šipek na důležité diagnostické znaky)
- expertní systémy (ve formě klíče pro některé typy kožních tumorů a ve formě popisy porovnávajícího expertního systému pro nenádorové kožní choroby)
- virtuální mikroskop pro přístup k obrazům o velmi vysokém rozlišení (desítky tisíc obrazových bodů na stranu ve více rovinách)
V přednášce bude popsán vývoj atlasů až po současný stav a Některé problémy, které jsme při vývoji atlasu řešili.
- 28. 4. 2009
- Dr. Calin A. Belta, Boston University
- Scalable algorithms for analysis of gene and metabolic networks
- Abstrakt:
Bacteria continuously respond to environmental changes through a
complicated mechanism consisting of an interplay between metabolic
and gene networks. Through hundreds of chemical reactions, the
metabolic network converts nutrients from the environment to
elements necessary for growth and survival of the cell. Most of
these chemical reactions are regulated by enzymes produced by a
gene network. In turn, the expression of the genes from the gene
network is regulated by its own products and metabolites produced
by the metabolic network.
In the first part of the talk, I will show how a quasi-steady state assumption on the dynamics of the metabolic network, combined with tools from convex analysis and in vivo survivability data, can lead to predictions such as essentiality of metabolites, nutrients, and chemical reactions. In the second part of the talk, I will focus on gene networks. I will show how a particular approach to modelling, together with discrete abstractions and model checking, can be used to tune and analyze gene networks from qualitative specifications given as arbitrary temporal and logic statements over species concentrations. I will exemplify the methods on the metabolism of E.coli and on a four-gene synthetic transcriptional cascade.
- 5. 5. 2009
- Richard Clayton, Ph.D., University of Cambridge
- What we now know about phishing websites
- Abstrakt: We have been studying phishing websites, that impersonate banks and other firms, for more than two years. We know how long it is before they're removed and have gathered all sort of other statistics about them. We can now explain why our lifetime measures exceed what industry expected; we understand how some of the vulnerable sites are found by the attackers -- and why the same sites are re-compromised again and again. We can compare takedown times for phishing with how long other types of illegal site remain available, and use security economics to explain the results. We can even demonstrate weaknesses in various community approaches to dealing with phishing. There's an awful lot we still don't understand, and we're still re-interpreting what we thought we knew last year! But this talk will get you up to speed on what (we think) we know in 2009.
- 12. 5. 2009
- Prof. Willy Zwaenepoel, Swiss Federal Institute of Technology, Lausanne
- TwinDrivers: Deriving Fast and Safe Hypervisor Drivers from Guest OS Drivers
- Abstrakt:
In a virtualized environment, device drivers are often run inside a virtual machine (VM) rather than in the hypervisor, for reasons of safety and reduction in software engineering effort. Unfortunately, this approach results in poor performance for I/O-intensive devices such as network cards. The alternative approach of running device drivers directly in the hypervisor yields better performance, but results in the loss of safety guarantees for the hypervisor and incurs additional software engineering costs.
In this paper we present TwinDrivers, a framework which allows us to create safe and efficient hypervisor drivers from guest OS drivers. The hypervisor driver runs directly in the hypervisor, but its data resides completely in the driver VM address space. A Software Virtual Memory mechanism allows the driver to access its VM data efficiently from the hypervisor running in any guest context, and also protects the hypervisor from invalid memory accesses from the driver. An upcall mechanism allows the hypervisor to largely reuse the driver support infrastructure present in the VM. The TwinDriver system thus combines most of the performance benefits of hypervisor-based driver approaches with the safety and software engineering benefits of VM-based driver approaches.
Using the TwinDrivers hypervisor driver, we are able to improve the guest domain networking throughput in Xen by a factor of 2.4 for transmit workloads, and 2.1 for receive workloads, both in CPU-scaled units, and achieve close to 64-67% of native Linux throughput.
This is joint work with Aravind Menon and Simon Schubert of EPFL.
- 19. 5. 2009
- prof. Ing. Miroslav Švéda, CSc., UIFS FIT VUT, Brno
- Real-Time Software-Intensive Systems Engineering Curricula Development: An International Perspective
- Abstrakt: This lecture provides an overview and a comparison of several international projects that focus on research and development of international computing curricula. The projects address computer based systems in general and more specifically the area of real-time software intensive embedded systems. Issues related to the analysis, design, implementation and assessment in international contexts of such curricula are discussed.