Program kolokvií s abstrakty pro semestr Jaro 2008

19. 2. 2008

doc. RNDr. Petr Hliněný, Ph.D., FIMU, Brno

O překvapivém problému průsečíkového čísla grafu

Abstrakt: Problematika určení průsečíkového čísla grafu (neboli nakreslení grafu s co nejmenším počtem křížení hran) je nejen teoreticky zajímavá, ale má i užitečné praktické aplikace třeba ve VLSI designu nebo ve vizualizaci grafů. Obecně se jedná o problém NP-úplný a ani po stránce aproximací či heuristik nejsou známy příliš uspokojivé výsledky. Teprve v posledních pár letech se dostalo pozornosti i jedné překvapivé podotázce - jak určit průsečíkové číslo grafu, který vznikne z rovinného přidáním jediné hrany? Navzdory zdánlivé trivialitě této otázky stále neznáme její řešení a dokonce se mezi odborníky vyskytují názory, že i tento fragment může být NP-úplný. Na přednášce se podíváme podrobně na nedávný vývoj okolo této podotázky.

Přednáška bude dvojjazyčná, česko-anglická.

26. 2. 2008

doc. Mgr. Tomáš Tyc, Ph.D., PřF MU, Brno

Metamateriály, neviditelnost a konformní zobrazení

Abstrakt: V současnosti jsme svědky konstrukce unikátních materiálů, jejichž vlastnosti lze připravit na míru pro účel, který potřebujeme. Příkladem jsou tzv. metamateriály, u nichž požadované vlastnosti vytváří jejich mikroskopická struktura, nikoli chemické složení. Metamateriály poskytují možnosti, které byly ještě v nedávné době nepředstavitelné - dosažení záporného indexu lomu, nadsvětelných rychlostí, optického zobrazení bez jakýchkoli vad apod. Jednou z aplikací metamateriálů je i dosažení neviditelnosti, kdy se pomocí pláště z metamateriálu světlo vede kolem předmětu a vrátí se do svého původního směru, takže předmět není vidět. Pro mikrovlny byla již neviditelnost tímto způsobem experimentálně realizována, pro viditelné světlo dosud nikoliv. V teorii neviditelnosti hrají kromě metamateriálů významnou roli geometrická zobrazení a mezi nimi zvláště zobrazení konformní. Přednáška se dotkne teorie metamateriálů, vysvětlí principy dosažení neviditelnosti i obtíže, které to přináší, a představí některé nové výsledky z tohoto zajímavého oboru.

4. 3. 2008

Mgr. Jan Obdržálek, PhD., FIMU, Brno

Četníci, zloděj a teorie grafů

Abstrakt: Je známých faktem, že mnohé zajímavé a důležité algoritmické problémy na grafech jsou NP-úplné. Pokud ovšem omezíme třídu uvažovaných grafů (například na grafy definované pomocí strukturální dekompozice), složitost problému může výrazně klesnout. Nejznámnější, a velmi významnou třídou takovýchto grafů jsou grafy s omezenou stromovou šířkou (tree-width), pro které jsou mnohé NP-úplné problémy řešitelné v lineárním čase.

Se stromovou dekompozicí úzce souvisí jistý typ her na grafech, nazývaných hry na četníky a zloděje. Významným a netriviálním výsledkem je alternativní charakterizace stromové šířky grafů právě pomocí těchto her. V přednášce se podíváme různé verze her na četníky a zloděje a na vztahy mezi nimi. Zmíníme i nové výledky, především adaptaci těchto her na orientované grafy.

11. 3. 2008

doc. Mgr. Jiří Damborský, Dr., Loschmidt Laboratories, MU Brno

Structural Bioinformatics and Computer-Assisted Engineering of Proteins

Abstrakt: Bioinformatics is the information technology applied to the management and analysis of biological data. Structural bioinformatics is the branch of bioinformatics dealing with the data from structural analysis of proteins, nucleic acids and their complexes. Analysis of the three-dimensional structures of biomolecules experimentally determined to the atomic resolution provides insight into the function of living organisms at the lowest organizational level and generates essential knowledge for design and optimization of biomolecules for industrial applications.

A number of computational tools have been developed for storage and analysis of biomolecular structures in recent years. New tools are still needed for prediction of changes in a structure that will bring modification in function in a controlled manner. Predicted changes, called mutations, can be routinely introduced into the structures by the molecular biology techniques.

The lecture will describe the usefulness of structural bioinformatics for design and construction of proteins with novel properties. Presented will be a general concept of computer-assisted engineering of proteins as well as two in-house programs CAVER and HOTSPOT WIZARD developed for prediction of mutations. Examples will be given from engineering of proteins for synthesis of fine chemicals and detoxification of dangerous chemical substances.

18. 3. 2008

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

Metrické podobnostní hledání v teorii a praxi

Abstrakt: Metody podobnostního hledání založené na principu metrických postulátů dosáhly v posledních desíti letech nebývalého rozmachu. Hlavním důvodem je fakt, že počet datových množin objektů pouze porovnatelných na základě podobnosti roste - nárust objemu těchto dat je exponenciální. Cílem prednášky je představit základní koncepty metrického hledání a nastínit metody škálovatelných indexových struktur, schopných zpracovaní velkých objemů dat.

Možnosti této technologie budou demonstrovány pomocí systému MUFIN (Multi Feature Indexing Network) na vyhledávání v kolekci 10 miliónů obrázků indexovaných pěti základními MPEG7 deskriptory barev, kontur a textury.

25. 3. 2008

Ing. Přemysl Kršek, Ph.D., FIT VUT, Brno

3D geometrické modelování v medicíně a jeho klinické aplikace

Abstrakt: Přednáška je věnována problematice tvorby 3D geometrických modelů lidských tkání na základě medicínských obrazových dat z Počítačové tomografie a Magnetické rezonance. Důraz je při tom kladen na aplikaci vytvořených modelů zpět v klinické praxi pro zkvalitnění ošetření konkrétních pacientů. To odpovídá současnému světovému trendu v medicíně, který se orientuje na individuální ošetření pacientů (Tailor surgery).

Během přednášky budou popsány vlastnosti zpracovávaných CT/MR dat. Bude rozebrán kompletní postup tvorby 3D modelů tkání, který se skládá ze: segmentace tkání, vektorizace modelů tkání, vyhlazení a decimace vektorových modelů. Součástí bude také problematika Virtuální síťové kolaborativní prostředí pro konzultace, korekce a verifikace 3D modelů tkání.

Na konci bude prezentována skupina aplikací vytvořených modelů v klinické praxi lékařských oborů: plastická a estetická chirurgie, stomatologie, ortopedie a neurochirurgie. Dosud bylo u nás s podporou popisovaných technik realizováno přes 30 operací konkrétních reálných pacientů.

1. 4. 2008

doc. RNDr. Jiří Sgall, DrSc., Matematický ústav AV ČR, Praha

Aproximační algoritmy pro rozvrhování

Abstrakt: Algoritmy pro rozvrhování je klasická oblast výzkumu na pomezí kombinatorické optimalizace a operačního výzkumu. Řada problémů je NP-těžkých, a v takovém případě zkoumáme aproximační algoritmy, tj. takové algoritmy, které zaručí alespoň jistou kvalitu řešení v porovnání s optimem. V této přednášce předvedeme několik souvisejících problémů a algoritmů z této oblasti, s důrazem na metody používající lineární programování. Přednáška vychází (z velké části) z článku T. Ebenlendr, M. Krčál, J. Sgall: Graph balancing: A special case of scheduling unrelated parallel machines Proc. of the 10th Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), ACM-SIAM, 2008.

8. 4. 2008

RNDr. Libor Škarvada, FIMU, Brno

Polymorfní a závislé typy

Abstrakt: Ukážeme si typové systémy s vysokou vyjadřovací schopností, jejich vztah k logickým kalkulům i možnosti jejich použití v praktickém programování. Jde zejména o typové systémy s parametrickým polymorfismem, typovými konstruktory a s hodnotově závislými typy. Zatímco polymorfní typy a typové konstruktory dávno našly uplatnění ve funkcionálních jazycích, hodnotově závislé typy se používají spíše jen v experimentálních jazycích a do praxe nepronikly. Důvody jsou triviální (nezvyklost a těžkopádnost) i fundamentální (nerozhodnutelnost otypování). Naším cílem bude první překážku překonat a druhou obejít.

15. 4. 2008

Ing., Dipl.-Ing. Martin Drahanský, Ph.D., FIT VUT, Brno

Biometrické systémy

Abstrakt: V úvodu přednášky bude poskytnut přehled stávajících biometrických systémů, s uvedením jejich silných míst a slabin. Navazujícím tématem budou biometrické systémy založené na rozpoznávání otisků prstů, kde se zameřím na testování kvality obrazové informace v otiscích prstů. Na závěr přednášky budou rozebrány metody testování živosti v biometrických systémech a současný výzkum na FIT VUT v Brně.

22. 4. 2008

prof. RNDr. Jiří Zlatuška, CSc., FIMU, Brno

Hodnocení výzkumu, vědní politika - problém informatiky nebo problém obecný?

Abstrakt: Přednáška se bude týkat některých koncepčních a realizačních problémů souvisejících reformou výzkumu, vývoje a inovací v ČR. Z informatických pracovišť v ČR se již objevila kritika systému hodnocení. Podíváme se na širší aspekty problému a toho, nakolik jsou problémy, na které upozorňuje informatika specifické pouze informatice, a nakolik se jedná o problémy obecnějšího rázu.

29. 4. 2008

RNDr. Věra Kůrková, DrSc., Ústav informatiky AV ČR, Praha

Učení neuronových sítí se schopností generalizace jako inverzní úloha

Abstrakt: Učení neuronových sítí modelované jako minimalizace chybových funkcionálů lze pomocí vhodných operátorů formulovat jako inverzní úlohu. Inverzní úlohy byly vyvinuty k řešení fyzikálních úloh (patří mezi ně např. počítačová tomografie). Různé metody regularizace určené ke zvýšení stability řešení inverzních úloh lze využít i k modelování generalizace, tj. schopnosti neuronových sítí uspokojivě zpracovávat i data, která nebyla použita při učení. Tak lze do algoritmů učení sítí zahrnout kromě empirických dat (trénovací množina) též znalosti o určitých kvalitativních vlastnostech hledaných řešení. Matematické metody vyvíjené generacemi matematiků pro řešení fyzikálních úloh lze využít k návrhu alternativních algoritmů učení neuronových sítí založených na řešení soustav lineárních rovnic.

6. 5. 2008

doc. RNDr. Viliam Geffert, CSc., PřF, Univerzita P. J. Šafárika, Košice

Stavová hierarchia konečných automatov

Abstrakt: Bude predstavená detailnejšia analýza vzťahu medzi počtom stavov klasického jednosmerného deterministic konečného automatu (DFA) a jeho nedeterministického ekvivalentu (NFA). Hoci je všeobecne známy exponenciálny vzťah, presná veľkosť sa zatiaľ do povedomia až tak nedostala.

Ukážeme, že pre každé prirodzené číslo d, a každé n v intervale log(d)...d, existuje taký regulárny jazyk, pre ktorý optimálny DFA používa PRESNE d stavov, zatiaľ čo každý optimálny NFA PRESNE n stavov. Teda stavová hierachia nedeterministických NFA, pre jazyky rozpoznávané pomocou d-stavových DFA je súvislá, neobsahuje žiadne "magické" diery.

Pokiaľ sa sústredíme na BINÁRNE regulárne jazyky, uvedený výsledok sa podarilo dokázať pre všetky hodnoty n v rozsahu od Omega(log(d)^3/loglog(d)^2) po d.

Naopak, pre UNÁRNE regulárne jazyky táto stavová hierarchia súvislá nie je. V hierarchii sú "diery", t.j. magické hodnoty medzi hodnotami ktoré magické nie sú. V skutočnosti drvivá väčšina hodnôt n menších ako d je magická pre d (t.j., pre skoro všetky hodnoty n menšie ako ľubovoľné dostatočne veľké dané d platí, že ŽIADNY optimálny d-stavový DFA rozpoznávajúci unárny jazyk nemá ekvivalentný optimálny NFA ktorý by používal presne n stavov).

Kĺúčové slová: popisná zložitosť, konečné automaty, regulárne jazyky

13. 5. 2008

doc. RNDr. Václav Matyáš, M.Sc., Ph.D., Mgr. Petr Švenda, FIMU, Brno

Kryptografické protokoly v senzorových sítích

Abstrakt: Přednáška uvede technologii bezdrátových senzorových sítí, se zvláštním zřetelem na jejich bezpečnost. Tato relativně mladá technologie se začala vyvíjet spolu s pokrokem v oblasti miniaturizace elektronických zařízení, jejich klesající ceně a všeobecným rozšířením bezdrátové komunikace. Data snímaná miniaturními zařízeními v terénu (teplota, tlak, pohyb) jsou lokálně zpracovávána a následně přenášena koncovému uživateli, který tak získá možnost detailního kontinuálního monitorování vybrané oblasti. Uplatnění začíná od medicínského monitorování pacientů přes využití v zemědělství a průmyslu po systémy včasné detekce havarijních situací a v neposlední řadě i vojenského využití, odkud počátky této technologie pocházejí.

Cílem bude nejen ukázat základní technologii a paletu otevřených výzkumných otázek pramenících z rozdílu nové technologie oproti stávajícím "klasickým" sítím, ale zároveň přesvědčit posluchače o potřebnosti včasné implementace úrovní bezpečnosti odpovídající zamýšlenému využití sítě. Detailněji bude pokryta oblast návrhu protokolů pro distribuci a ustavení klíče odolných proti částečné kompromitaci, jejich automatizovaný navrh založený na evolučních algoritmech ale i opačný směr - automatizované hledání útočníkových strategií.

20. 5. 2008

RNDr. Petr Sojka, Ph.D., FIMU, Brno

From Pixels and Minds to the Mathematical Knowledge in Digital Library

Abstrakt: Experience in setting up a workflow from scanned images of mathematical papers into fully fledged mathematical library is described on the example of the project Czech Digital Mathematics Library DML-CZ. The whole process is described, with attention given to details of all production steps.