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.