Ústav informatiky
Akademie věd České republiky
"Jednoduchost je velká ctnost, ale vyžaduje mnoho práce, aby jí bylo dosaženo, a vzdělání, aby byla oceněna. A co je horší: složitost se lépe prodává." - E. W. Dijkstra

Výsledky a ocenění

Vybrané výsledky z činnosti Ústavu informatiky

Ocenění zdrojů znečištění ovzduší z hlediska jejich příspěvku ke zvýšení mortality

V rámci výzkumu byly testovány vlivy různých zdrojů znečištění na mortalitu způsobenou krátkodobými zvýšeními ozónu a oxidů dusíku. Naše skupina prováděla evropskou část experimentu.

V oblasti environmentální informatiky jsme se zabývali oceněním zdrojů znečištění ovzduší z hlediska jejich příspěvku ke zvýšení mortality. Příspěvek různých zdrojů znečištění ke zvýšení mortality na určitém území se velice liší v závislosti na jejich umístění, časovém režimu i na chemickém složení produkovaných látek. Poznání těchto rozdílů a jejich kvantifikace má zásadní význam pro nastavení efektivních regulatorních opatření. Dosavadní používané modelovací metody převážně ohodnocovaly příspěvek jednotlivého vybraného zdroje nebo skupiny zdrojů ke změně sledovaného ukazatele. Byly testovány vlivy různých zdrojů znečištění na mortalitu způsobenou krátkodobými zvýšeními ozónu a oxidů dusíku pro tři oblasti, a to pro Evropu, USA a Kanadu, přičemž naše skupina prováděla evropskou část experimentu. Výsledky experimentů ukazují vysokou prostorovou i časovou variabilitu významu jednotlivých zdrojů, která sahá od přínosu ke snížení mortality na Evropě způsobené ozónem vyčíslitelného na téměř 320 mil. Euro za den pro 10% snížení emisí oxidů dusíku v oblasti Barcelony až po nulový či záporný příspěvek zdrojů v některých oblastech Anglie a Holandska. Práce byla prezentována na konferenci ITM 2012 v Holandsku a publikovaná ve sborníku „Air Pollution Modelling and its Applications XXII“ (Springer, 2013) pod názvem „Pappin, A., Hakami A., Resler, J., Liczki, J., Vlcek, O.: Source attribution of air pollution abatement health benefits“.

Krylov Subspace Methods, Principles and Analysis.Oxford University Press 2012

Metody Krylovových podprostorů reprezentují jednu z nejdůležitějších tříd metod pro řešení soustav lineárních rovnic. Myšlenka autorů napsat společnou knihu vznikla již v roce 1997, samotná práce na knize trvala 10 let.

U nakladatelství Oxford University Press vyšla v roce 2012 monografie o rozsahu 408 stran Jörga Liesena (TU Berlín) a Zdeňka Strakoše, Krylov Subspace Methods, Principles and Analysis (ISBN 978-0-19-965541-0). Myšlenka autorů napsat společnou knihu vznikla již v roce 1997, samotná práce na knize trvala 10 let. Metody Krylovových podprostorů reprezentují jednu z nejdůležitějších tříd metod pro řešení soustav lineárních rovnic (byly zařazeny mezi deset nejdůležitějších algoritmických myšlenek 20. století). Jsou popsány v několika prvotřídních knihách vynikajících autorů, které odrážejí současný stav zejména jako výsledek enormního algoritmického rozvoje trvajícího několik desetiletí. Předložená monografie je zaměřena jiným způsobem. Jejím cílem je popsat matematické základy metod Krylovových podprostorů. Tím je nutně dává do kontextu několika matematických oborů stejně jako do historického kontextu, který jde několik století zpět a přitom je spojen s výsledky posledního rozvoje výpočetní matematiky a výpočetních metod v přírodních vědách. Podstatná část zahrnutého materiálu je zpracována knižním způsobem poprvé, některé výsledky jsou zcela nové. Důraz na výklad namísto důrazu na algoritmické popisy výrazně odlišuje předloženou monografii od existující literatury.

Způsob identifikace osob se zvýšeným genetickým rizikem úmrtí po infarktu myokardu

Na poli medicínské informatiky a biostatistiky byly v rámci studie vytipovány různé sady genů, které umožňují identifikovat jedince se zvýšeným genetickým rizikem vzniku infarktu za pomoci molekulárně genetického vyšetření.

Na poli medicínské informatiky a biostatistiky byly v rámci kardiovaskulární genetické studie vytipovány různé sady genů, které umožňují identifikovat jedince se zvýšeným genetickým rizikem vzniku infarktu za pomoci molekulárně genetického vyšetření. Některé z nich jsou zaměřeny na zvýšené riziko úmrtí do 6 měsíců od okamžiku výskytu infarktu. Metody vedoucí k nalezení těchto sad genů následně vedly k udělení tří patentů. Pro názornost uveďme krátký popis jednoho z těchto patentů, patentu č. 303458 autorů J. Zvárové, I. Mazury, Z. Valenty, P. Feglarové a H. Grünfeldové s názvem Způsob identifikace osob se zvýšeným genetickým rizikem úmrtí po infarktu myokardu, datum publikace patentu 19. 9. 2012. Specifický návrh celogenomové studie genové exprese pacientů s akutním infarktem myokardu a párových kontrol s obdobnými hodnotami klinických rizikových faktorů výskytu akutního infarktu myokardu umožnil identifikaci relativně úzké množiny genů a transkriptů, která souvisí se zvýšeným rizikem úmrtí pacienta v relativně krátkém období od okamžiku výskytu srdeční příhody. Extrémní hodnoty genové exprese vybraných genů mohou v praxi u pacientů s výskytem akutního infarktu myokardu posloužit jako indikátor požadavku zvýšené léčebné péče a lékařského dohledu, zejména v krátkém období bezprostředně po hospitalizaci pacienta v důsledku akutního infarktu myokardu.

Může náhoda zefektivnit výpočty s omezenou pamětí?

Kladná odpověď by přinesla paměťově efektivní a bezchybné řešení pro stovky praktických problémů. Námi vyřešený problém byl na nejprestižnějších konferencích uváděn jako mez, pro kterou všechny známé techniky selhávají.

V oboru teoretické informatiky byl v sérií tří článků J. Šímy a S. Žáka dokázán hluboký výsledek (matematický důkaz zabral zhruba 40 stran), který přispívá k řešení jednoho z ústředních otevřených problémů výpočetní teorie (teorie složitosti). Jeden z těchto článků, vyšel v roce 2011 (LNCS 6651, Berlin: Springer-Verlag, str. 120-133), druhý v roce 2012 (LNCS 7147, Berlin: Springer-Verlag, str. 406-418) a třetí byl zaslán k publikaci. Jde o problém spojený s otázkou, zda náhoda může zefektivnit výpočty s omezenou pamětí. Ilustrujme problém na příkladu z běžného života. Představme si, že se potřebujeme v nám neznámém velkoměstě dopravit autem bez mapy z jednoho místa (start) do jiného (cíl). Takovou úlohu za nás dnes řeší navigace. Situace je komplikována tím, že ve městě jsou jednosměrné ulice, různé nadjezdy, podjezdy, tunely a uzavírky. Jednou z možností je vyjet ze startu a zkoušet systematicky projíždět všechny možné trasy, dokud nedorazíme do cíle. To znamená, že pokud dojedeme do místa, kde jsme již byli, nebo skončíme ve slepé ulici, pak se musíme vrátit zpátky k první křižovatce, ze které vede ulice, kterou jsme ještě neprojeli. Tento postup však vyžaduje, abychom si pamatovali, kde jsme již byli, což může být ve velkém městě se stovkami ulic problém. Jinou možností je náhodný průjezd městem, kdy si na každé křižovatce házíme korunou, zda máme zabočit vlevo či vpravo, resp. vhodnou kostkou, pokud je křižovatka komplikovanější a máme více možností, jak pokračovat v jízdě. Je zajímavé, že se dá matematicky dokázat, že se s velkou pravděpodobností v rozumném čase dostaneme do cíle. Navíc si v tomto případě nemusíme pamatovat již projetou trasu. Naopak hlavní nevýhodou tohoto postupu je, že do cíle nemusíme dorazit vůbec (resp. v daném časovém termínu), i když víme, že možnost selhání náhodného průjezdu je málo pravděpodobná. Otázkou je, zda existuje způsob, jak ze startu s jistotou dojet do cíle, aniž bychom si házeli korunou, pokud jsme schopni si zapamatovat např. jen několik orientačních bodů. Uvedený dopravní problém již postihuje všechny aspekty počítání s omezenou pamětí, takže na něm můžeme studovat obecnou otázku, zda se při těchto výpočtech lze zbavit (málo pravděpodobné) možnosti chyby. Kladná odpověď by přinesla paměťově efektivní a bezchybné řešení pro stovky důležitých praktických problémů. Zásadní význam tohoto problému pro informatiku ilustruje skutečnost, že za vyřešení jeho jednodušší verze (bez jednosměrných ulic) byla mj. v roce 2009 udělena Gödelova cena (obdoba Nobelovy ceny v teoretické informatice). Protože tento problém je velmi těžký pro univerzální modely počítačů (např. Turingovy stroje), zkoumá se na omezených výpočetních modelech. Nám se jej podařilo vyřešit pro tzv. 1-branching programy šířky 3, které se během výpočtu mohou nacházet de facto jen ve 3 stavech (pro řešení původního problému by bylo potřeba dokázat příslušnou matematickou větu pro neomezenou šířku). Ačkoliv je uvedený výpočetní model velmi slabý, námi vyřešený problém byl na nejprestižnějších konferencích v teoretické informatice uváděn jako mez, pro kterou všechny známé techniky selhávají. V chystané monografii (S. Vadhan: Pseudorandomness), která náš výsledek cituje, je tato hranice posunuta na šířku 4, pro kterou je problém doposud otevřený.

Analýza metod pro maticové výpočty, Matfyzpress 2012

Záměrem autorů bylo napsat učebnici pro studenty technických oborů, která by je uvedla do světa maticových výpočtů a numerické matematiky.

Záměrem autorů J. Duitjera Tebbense, I. Hnětynkové, M. Plešingera, Z. Strakoše a P. Tichého bylo napsat učebnici pro studenty technických oborů, která by je uvedla do světa maticových výpočtů a numerické matematiky. Na základě přednášek autorů na různých univerzitách vznikla monografie s názvem Analýza metod pro maticové výpočty, která vyšla u nakladateství Matfyzpress (ISBN 978-80-7378-201-6, 328 stran). Styl výkladu udržuje v rovnováze formalismus a srozumitelnost. Vhodnost tohoto stylu je dána tím, že se autoři pohybují na pomezí klasické a aplikované matematiky, která naráží na složitosti tohoto světa. Vyložení podstaty jevu slovním popisem často umožňuje daleko hlubší pochopení jevu, než by tomu bylo u přesného formalistického výkladu, který by význam pojmů často nepřípustným způsobem zužoval. Autoři vycházejí z Schurovy věty, která je východiskem mnoha cest, a postupně vykládají ortogonální transformace, základní maticové rozklady (QR, LU, SVD), řešení úloh nejmenších čtverců, částečného problému vlastních čísel a řešení soustav lineárních algebraických rovnic pomocí iteračních metod. Přitom kladou velký důraz na analýzu a pochopení algoritmů a na výpočetní stránku věci, včetně chování uvažovaných algoritmů v prostředí konečné aritmetiky počítače.

Ocenění pracovníků ÚI AV ČR

2013

  • Medaile Josefa Hlávky
    Fiedler Miroslav, prof. RNDr. DrSc.
  • Prémie Otto Wichterleho pro mladé vědecké pracovníky v AV ČR
    Hlinka Jaroslav, Ing. Mgr. Ph.D.
  • Čestná oborová medaile B. Bolzana za zásluhy v matematických vědách
    Strakoš Zdeněk, prof. Ing. DrSc.

2012

  • Cena Neuron za celoživotní dílo, Nadační fond Karla Janečka
    Fiedler Miroslav, Prof. RNDr.DrSc.
  • Prémie Otto Wichterleho pro mladé vědecké pracovníky v AV ČR
    Kalina Jan, RNDr.Ph.D.
  • Účast v českém finále mezinárodní soutěže FameLab 2012
    Kalina Jan, RNDr.Ph.D.

2011

  • Minisymposium na počest M. Fiedlera na konferenci ILAS
    Fiedler Miroslav, Prof. RNDr.DrSc.
  • Prémie Otto Wichterleho pro mladé vědecké pracovníky v AV ČR
    Martinková Patrícia, RNDr.Ph.D.
  • EUSFLAT cena za nejlepší studentský příspěvek
    Víta Martin, Mgr.

2010

  • Čestná oborová medaile B. Bolzana za zásluhy v matematických vědách
    Kůrková Věra, RNDr.DrSc.

2009

  • Cena Antonína Svobody pro nejlepší disertační práci roku
    Běhounek Libor, Mgr.Ph.D.
  • Medaile Josefa Hlávky
    Hájek Petr, Prof. RNDr.DrSc.
  • Prémie Otto Wichterleho
    Haniková Zuzana, RNDr.Ph.D.
  • Cena rektora ČVUT I. stupně za vynikající disertační práci
    Petrík Milan, Ing.Ph.D.
  • Cena Josefa Hlávky pro mladé pracovníky AV ČR
    Vejmelka Martin, Ing.Ph.D.

2008

  • Prémie Otto Wichterleho
    Horčík Rostislav, Ing.Ph.D.
  • Medaile 1. lékařské fakulty Univerzity Karlovy v Praze
    Zvárová Jana, Prof. RNDr.DrSc.

2007

  • Cena Akademie věd ČR pro mladé vědecké pracovníky za vynikající výsledky
    Cintula Petr, Ing.Ph.D.
  • Státní vyznamenání – Medaile za zásluhy I. stupně
    Fiedler Miroslav, Prof. RNDr.DrSc.
  • Cena Josefa Hlávky pro mladé pracovníky AV ČR
    Horčík Rostislav, Ing.Ph.D.
  • Prémie Otto Wichterleho
    Tichý Petr, RNDr.Ph.D.

2006

  • Cena Josefa Hlávky pro mladé pracovníky AV ČR
    Cintula Petr, Ing.Ph.D.
  • Cena Učené společnosti mladým vědeckým pracovníkům
    Cintula Petr, Ing.Ph.D.
  • Čestná medaile DE SCIENTIA ET HUMANITATE OPTIME MERITIS
    Fiedler Miroslav, Prof. RNDr.DrSc.
  • Státní vyznamenání - Medaile za zásluhy III. stupně
    Hájek Petr, Prof. RNDr.DrSc.
  • Cena Akademie věd ČR za dosažené vynikající výsledky velkého vědeckého významu
    Tůma Miroslav, Prof. Ing.CSc.
    Strakoš Zdeněk, Prof. Ing.DrSc.
    Rozložník Miroslav, Doc. Dr. Ing.

2005

  • Cena rektora ČVUT I. stupně za vynikající disertační práci
    Cintula Petr, Ing.Ph.D.
  • Prémie Otto Wichterleho
    Cintula Petr, Ing.Ph.D.
  • Čestná medaile DE SCIENTIA ET HUMANITATE OPTIME MERITIS
    Hájek Petr, Prof. RNDr.DrSc.
  • Medaile za zakladatelské zásluhy v oboru biomedicínské informatiky a statistické aplikace v lékařských disciplínách
    Zvárová Jana, Prof. RNDr.DrSc.

2004

  • Medaile za vynikající výsledky ve výuce a vzdělávání v oblasti medicínské informatiky
    Zvárová Jana, Prof. RNDr.DrSc.

2003

  • Prémie Otto Wichterleho
    Šíma Jiří, Doc. RNDr.DrSc.

2002

  • Prémie Otto Wichterleho
    Rozložník Miroslav, Doc. Dr. Ing.
    Paluš Milan, RNDr.DrSc.

2000

  • Čestná oborová medaile B. Bolzana za zásluhy v matematických vědách
    Hájek Petr, Prof. RNDr.DrSc.

1999

  • Vyznamenání za vynikající výsledky ve výuce medicínské informatiky
    Zvárová Jana, Prof. RNDr.DrSc.

1998

  • Cena AV ČR pro mladé vědecké pracovníky
    Neruda Roman, Mgr.CSc.
    Šíma Jiří, Doc. RNDr.DrSc.
  • Medaile za činy pro rozvoj medicínské informatiky
    Zvárová Jana, Prof. RNDr.DrSc.