Program kolokvií s abstrakty pro semestr Podzim 2009

29. 9. 2009

Dr. Paul Leyland, CEPIA Technologies, United Kingdom

RSA Security and Integer Factorization: The Thirty Years War from 1990 to 2020

Abstrakt: The RSA public key cryptosystem was invented in 1977. It was put into widespread use about ten years later. The security of RSA depends critically on integer factorization being a difficult problem in practice. Those who factor integers have been working very hard to reduce the practical difficulty of factoring, not always to the approval of those who use RSA to protect valuable information. This talk covers the history of the tension between these two communities over the last twenty years, and suggests that a resolution should be forthcoming in the next decade.

6. 10. 2009

RNDr. Radka Svobodová Vařeková, Ph.D., Národní Centrum pro Výzkum Biomolekul, Siemens Corpotate Technology & Research

R&D projekty a jejich realizace ve firmách

Abstrakt: Oblast průmyslového výzkumu a inovačních projektů je v současnosti velmi často diskutovaným tématem. Jedním z důvodů je zvýšení dotační podpory R&D projektů ve srovnání s minulými lety. Dalším je vzrůstající nutnost inovací, které se pro firmy postupně stávají nezbytnou podmínkou pro udržení jejich konkurenceschopnosti. Příkladem jsou i aktivity v připravovaném projektu CERIT. V rámci své přednášky se zaměřím právě na průmyslový výzkum a na praktické zkušenosti z této oblasti. Nejdříve popíši motivaci zahájení výzkumného projektu a iniciační fázi projektu. Poté uvedu zkušenosti z oblasti realizace grantových projektů v rámci firmy a z oblasti spolupráce s univerzitami. V druhé části přednášky popíši příklady dvou výzkumných projektů a informace o nich.

13. 10. 2009

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

Syntéza polymorfních logických sítí

Abstrakt: V přednášce bude představena oblast polymorfní elektroniky, která vychází z existence tzv. polymorfních hradel. Bude popsáno polymorfní hradlo NAND/NOR vyvinuté na FIT VUT v Brně, které mění svoji logickou funkci v závislosti na úrovni napájecího napětí. Hlavní část přednášky bude věnována problému syntézy polymorfních logických sítí. Budou diskutovány algoritmy syntézy založené na konvenčních metodách i evolučním přístupu. V závěru budou demonstrovány vybrané aplikace polymorfní elektroniky.

20. 10. 2009

Dr. Sang-il Oum, KAIST, Daejeon, Korea

Maximum number of complete subgraphs in a certain graph

Abstrakt: A clique of a graph is a set of pairwise adjacent vertices. We are interested in the maximum possible number of cliques in a graph. In general a graph with n vertices can have at most 2^n cliques obviously. We will show that if we restrict to a graph with no K_r- minor, then such a graph can have at most O(n) cliques. Indeed this result is not new; several researchers already discovered the same bound. Previous best bound was 2^(c r sqrt(log r)) n. We improved this to 2^(c log log r) n. We also looked at other classes of graphs. As a corollary, we obtained a hypergraph generalization of the theorem of Thomason and Kostochka (independently) on the maximum number of edges in a graph with no K_r minor. This talk is based on a joint work with Fedor Fomin and Dimitrios Thilikos for relating tree-width and rank- width for planar graphs and H-minor-free graphs.

27. 10. 2009

doc. Damas Gruska, Ph.D., Fakulta matematiky, fyziky a informatiky, KU, Bratislava

Informačný tok a bezpečnosť informatických systémov

Abstrakt: Otázka bezpečnosť hardvérových a softvérových systémov má niekoľko rozmerov. Od návrhu algoritmov, ktorých prelomenie je dokázateľne ťažké, cez implementačné problémy až po údržbu a ľudský faktor. Špecifickým rizikom bezpečnosti je existencia informačných toku medzi privátnymi a verejnými dátami či akciami. Útoky využívajúce takýto informačný tok sa ukazujú ako mimoriadne účinné a pomocou nich možno nabúrať systémy využívajúce algoritmy a techniky považované inak za veľmi robustné.

V prednáške sa budeme venovať základným princípom bezpečnosti hardvérových a softvérových systémov založenej na absencii informačného toku. Ukážeme niekoľko formalizácii informačného toku pre rôzne typy útočníkov (líšiacich sa tým s akou podrobnosťou vedia atakovaný systém pozorovať či s ním komunikovať) a pre rôzne bezpečnostné požiadavky. Zaoberať sa budem kvalitatívnym i kvantitatívnym vyjadrením informačného toku.

Prvá časť prednášky bude venovaná širšiemu pohľadu na celkový problém a základným prístupom k jeho riešeniu a v druhej časti prednášky uvedieme niekoľko návrhov na nové riešenie problémov.

3. 11. 2009

Prof. Wolfgang Slany, TU Graz

Why game programming skills are important for children and what can be done about it

Abstrakt: Computer games with an explicit educational aim are well known for usually being rather unpopular among the intended audience :-). On the other hand, Neal Stephenson's science-fiction classic "Snow Crash" allegedly was one of the inspirations for the creation of "Second Life", a highly successful massive multi-player online game-like thingy that sets itself apart by allowing players, among other things and motivated by the book's story, to write computer programs that can be executed inside the environment. Stephenson's other, in particular among women popular book "The Diamond Age, or A Young Lady's Illustrated Primer Primer --- A Propaedeutic Enchiridion in which is told the Tale of Princess Nell and her various Friends, Kin, Associates, &c." (currently 346 amazon customer reviews) follows the education of a girl from very young age to adulthood, one of the culminations being the teaching of computer science to the teen-aged girl. This book notably was one of the inspirations for the ongoing One-Laptop-Per-Child (XO-OLPC) movement that so far distributed more or less 1.5 million rugged low-power subnotebook computers with mobile ad-hoc networking capabilites to young children, mostly in the developing world. One software that is preinstalled on these laptops is a programming environment for children from age 8 on. Scratch has been developed in the Lifelong Kindergarten project from MIT Media Lab. So far more than 550,000 programs have been uploaded by more than 83,000 contributors (mostly but not only children, out of more than 367,000 registered members). Harvard University is even using Scratch to introduce programming to its first year students! Most of the programs written are games. Variants allow to program multi-player network games and to program for Second Life, and a version for mobile phones is in development.

I will talk about my forays related to above.

10. 11. 2009

doc. RNDr. Václav Matyáš, M.Sc., Ph.D., RNDr. Marek Kumpošt, Ph.D., FIMU, Brno

How much is privacy worth?

Abstrakt: Přednáška se zabývá představením výsledků dvou experimentů (z let 2006, 2009), jejichž cílem bylo zjistit, jak si lidé cení svých soukromých informací. Aby byly získané údaje co možná nejméně ovlivněné tím, že se lidí přímo zeptáme na cenu za poskytnutí soukromých informací, byly oba experimenty provedeny formou se skrytím skutečného záměru. V prvním experimentu byla zjišťována cena informací o aktuální poloze člověka -- poloha by byla zjišťována pomocí mobilního telefonu. V druhém případě jsme se zaměřili na cenu informací týkající se využití nástrojů pro online komunikaci (posílání emailů nebo použití instant messagingu) -- informace o využití těchto typů online komunikace by byly zjišťovány pomocí námi vyvinutého specializovaného softwaru. V obou případech jsme se účastníků ptali, jakou finanční kompenzaci by požadovali v případě, že by se zúčastnili navrženého experimentu. Obě studie byly provedeny ve spolupráci s našimi zahraničními partnery (univerzitami) vrámci projektu FIDIS (Future of Identity in the Information Society).

24. 11. 2009

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

Parametrizovaná složitost aneb Hamiltonovská kružnice v lineárním čase

Abstrakt: Pro výpočetní složitost léta platilo zaběhlé schéma: Pokud o nějakém problému dokážeme, že je NP-úplný, není nutné se jeho složitostí více zabývat - deterministický výpočet pak běží v čase exponenciálním ve velikosti vstupu. Další výzkum se pak ubíral směrem heuristik, aproximativních a náhodnostních algoritmů. Ovšem postupně se začalo ukazovat, že ne všechny "těžké" problémy jsou těžké ze stejných důvodů. Zejména je často možné nalézt lineární/polynomiální algoritmy pro NP-úplné problémy pokud omezíme množinu vstupních instancí na základě nějakého fixovaného parametru k. Tímto fixovaným parametrem může být jak velikost hledaného objektu (např. najdi vrcholové pokrytí velikosti k), tak i "strukturální složitost" vstupu (např. grafy se stromovou šířkou k). Studiem parametrizovaných problémů se zabývá teorie parametrizované složitosti.

V přednášce se nejprve zaměříme na základní pojmy parametrizované složitosti. Dále si ukážeme lineární/polynomiální algoritmy pro NP-úplné problémy na grafech podobných stromům (parametr k zde měří onu podobnost) a nakonec budou prezentovány některé nové výsledky pro problémy na orientovaných grafech.

1. 12. 2009

Prof. RNDr. Luděk Kučera, DrSc., KAM MFF UK, Praha

ALGOVIZE aneb procházka krajinou algoritmů

Abstrakt: Cílem přednášky je představit Algovizi, soubor appletů, které autor vytvořil pro svoji přednášku "Algoritmy a datové struktury" na MFF UK. Základem filosofie Algovize je nevytvářet pouhé animace algoritmů, které je možno ve velkém množství najít na internetu, a které ukazují jen to, co se během výpočtu děje, ale především se pokusit vizuálními prostředky vysvětlit algoritmickou myšlenku, která je v pozadí, tedy vizualizovat proč se to tak počítá. Zpětným pohledem je možno identifikovat řadu postupů, které k tomuto cíli mohou vést, např. vizualizace algoritmů tak, aby byly zřejmými invarianty z důkazů správnosti a složitosti, animace matematických důkazů (např. existenční důkazy jsou často animovatelné algoritmy), zdůraznění logicky důležitých skutečností grafickými prostředky a podobně. Těžištěm tvorby vizualizací algoritmů tak přestává být softwarová produktivita a nejdůležitějšími se stávají kognitivní a psychologické aspekty vědecké činnosti a výuky v oblasti informatiky.

8. 12. 2009

Prof. RNDr. Jiří Wiedermann, DrSc., Ústav informatiky, AV ČR

Amorphous Computing Systems

Abstrakt: Under various disguise, the idea of amorphous computing systems has initially emerged in the sci-fi literature, cf. the 1957 novel “The Black Cloud” written by the astrophysicist Sir Fred Hoyle; or the 1999 Hugo Award novel “A Deepness in the Sky” by the mathematician and computer scientist Vernor Vinge where the advanced amorphous computing systems appear in the form of “localizers”. The contemporary engineering efforts for constructing such systems are represented, e.g., by the 2001 project of a “smart dust” by K.S J. Pister (University of California). Real bacteria represent an example of such systems in nature. From a computational viewpoint, the amorphous computing systems differ from the classical ones almost in every aspect: they consist of a set of simple processors or robots that can communicate wirelessly to a limited distance. The processors are randomly placed in a closed area or volume; in some applications they can move, either actively, or passively (e.g., in a bloodstream). All processors are equal; they do not share global clock and do not have unique identifiers. How can such systems compute? Do such systems possess universal computing power? Do finite automata suit such task? We present a generic model of such systems. The processors are modeled by timed probabilistic finite-state automata. In a “macro-sized” model, the automata communicate by a single-channel radio; in a “nano-sized” model, by molecular communication. We sketch the main ideas leading to the design of probabilistic communication protocols and to the emergence of communication networks and indicate some open problems. Although families of all resulting systems possess universal computing power it is not clear whether some of them can be simulated by a single universal machine.

15. 12. 2009

Dr. József Kovács, MTA SZTAKI, Budapešť

SZTAKI Desktop Grid in CancerGrid and EDGeS EU projects

Abstrakt: SZTAKI Desktop Grid (SZDG) is an extension of BOINC in order to make it more flexible, versatile and scalable. MTA SZTAKI has developed various tools to ease the usage of BOINC from several points of view like application development, work unit generation, project management, security and so on. The talk will give an overview about SZDG and detail the various extensions utilised in the CancerGrid and EDGeS EU projects. CancerGrid aims to provide an infrastructure to help chemists develop new compound libraries with high-content of anti-cancer leads. The CancerGrid infrastructure consists of the gUSE scientific gateway, a compound database, several workflow applications based on various chemoinfo tools and a private SZDG that executes the different part of the workflows. The EDGeS project aims to solve interoperability between service grids (SG) and desktop grids (DG) by developing a gateway called 3Gbridge. Based on the bridge a SG-DG combined infrastructure has been built and operated that executes plenty of different applications ported during the project.