Projekty

2022 - 2024

Projekt (ve specifickém cíli B) si klade za cíl vytvoření nového magisterského studijního programu Kvantová informatika s výrazným podílem informatiky. Má připravovat odborníky pro technologickou a technickou praxi spojenou s druhou kvantovou revolucí umožňující radikálně nové výpočetní a řídící postupy a komunikaci s bezprecedentní bezpečností. Absolventi budou vybaveni řadou inženýrských dovedností a budou schopni zavádět kvantové postupy na pracovištích orientovaných na pokročilé technologie. Přepokládá se zapojení čtyř fakult ČVUT, a to FEL, FIT, FS a FJFI. Jednotlivé fakulty mají komplementární kompetence potřebné k zavedení a rozvíjení studijního programu Kvantová informatika, a to na magisterském stupni. Důraz bude kladen na informatické a inženýrské aspekty kvantové informatiky. Pro jednotlivé fakulty jsou zajímavé odpovídající směry (komunikace, počítání a metrologie) s různou vahou. Předpokládá se realizace dvou laboratoří kvantové komunikace a kryptografie (FEL, FJFI) a kvantového počítání (FIT, FS, FJFI, FEL). Vybudované laboratoře budou k dispozici všem fakultám v rámci výuky. Na FITu vznikne laboratoř kvantového počítání. Z projektu vybavíme učebnu(y) simulátorem optického kvantového počítače. Fakulta bude rozvíjet kvantovou informatiku, zejména se bude zaměřovat na kvantové algoritmy pro paralelizaci výpočtů, kryptování/šifrování, bezpečnostní algoritmy, teorii složitosti, data mining (učení paralelních struktur – sítě s hlubokým učením). FEL a FJFI společně vytvoří výukovou laboratoř kvantové kryptografie a její následné napojení na národní kryptografickou síť. Projekt by měl sloužit i k přípravě studijních programů/specializací na součástech ČVUT (FJFI, FIT, FEL, FS). Dále bude snahou se aktivně zapojit do vznikajícího mezinárodního konsorcia pro kvantové technologie.

2022 - 2024

Pro návrh algoritmů na řešení těžkých problémů v oblasti výpočetní sociální volby jsou dnes standardem jak parametrizované tak aproximační algoritmy. Kernelizace, jedna z hlavních technik v parametrizované složitosti, je překvapivě málo používána pro řešení problémů sociální volby. Jsme přesvědčeni, že kernelizace -- formalismus pro bezpečnou redukci vstupních dat -- má své místo ve všech výzkumných odvětvích týkajících se velkých vstupních dat. Nejnovějšı́ koncept je tzv. ztrátová kernelizace, která je jednak použitelná v kombinaci s aproximačními algoritmy (narozdíl od normální kernelizace, kterou lze kombinovat pouze s exaktními algoritmy), a druhak dokáže obejít těžkostní výsledky za cenu zavedení mírné nepřesnosti do výsledku. Navrhujeme aplikovat tyto moderní nástroje -- ztrátovou kernelizaci -- ve výpočetní sociální volbě. Navrhovaný projekt navazuje na naši předchozí práci v tomto oboru a uvažované směřování výzkumu bude vyžadovat nové algoritmické přı́stupy. Vytipovali jsme řadu zajímavých otevřených problémů a otázek, kde vidíme potenciál dosáhnout výsledků aplikováním zmíněných technik. Cílem je významně prohloubit poznání výpočetní složitosti těchto problémů nalezením polynomiálně velkých (ztrátových) kernelů popřípadě vyloučit jejich existenci.

2021 - 2022

Výpočetní kolektivní volba (Computational Social Choice) je moderní oblast informatiky, ve které se setkává teoretická informatika a teorie her (ekonomie). Mnoho zásadních problémů v této oblasti je NP-těžkých, proto se začala v poslední dekádě stále častěji uplatňovat tzv. parametrizovaná analýza, která si klade za cíl identifikovat parametry, jejichž zafixování na malých hodnotách vede k efektivní řešitelnosti daného problému. V předkládaném projektu se hodláme zaměřit na strukturální parametry (mezi nejznámější bezpochyby patří stromová šířka) vstupních instancí, čímž omezíme například vzájemnou interakci mezi agenty hledajícími kolektivní rozhodnutí a podobně.

2017 - 2019

Parametrizovaná nebo multivarietní analýza se v minulých dvou dekádách stala standardním přístupem k (NP-) těžkým problémům. Oproti klasické výpočetní složitosti se zde efektivita algoritmů měří nejen vzhledem k délce vstupu, ale také vzhledem k určenému parametru. V poslední době je kladen větší důraz na získání nejlepšího možného stupně polynomu stejně jako nejlepší asymptotické závislosti na parametru. To je prokázáno předvedením dolních mezí ukazujících, že existence výrazně rychlejších algoritmů je nepravděpodobná, typicky založených na hypotéze exponenciálního času, nebo její silné formě. V tomto návrhu projektu se zaměřujeme na několik zásadních problémů v návrhu sítí spojených se souvislostí v orientovaných grafech z parametrizovaného pohledu. Náš cíl je získat nové algoritmy pro tyto problémy s lepší časovou složitostí než mají existující algoritmy, nebo získat dolní meze ukazující, že takové vylepšení je nepravděpodobné. Naším hlavním zaměřením jsou problémy Steinerovského typu na orientovaných grafech.

2014 - 2016

Parametrizované algoritmy se staly v posledních dvou dekádách standardním nástrojem pro řešení výpočetně těžkých (NP-těžkých) problémů. Časová složitost se v tomto vyjadřuje pomocí druhotné míry (parametru) navíc k velikosti vstupu, čímž se dosahuje jemnější analýza původu těžkosti problému. Parametrizovaná složitost představuje matematický rámec pro analyzování takových algoritmů a také umožnuje ukázat, že pro některé problémy a parametry (pravděpodobně) žádný takový algoritmus neexistuje. V rámci toho projektu plánujeme studovat některé otevřené otázky související se základními problémy v oblasti návrhu sítí z pohledu parametrizované složitosti. Přesněji se zaměříme na tyto dvě oblasti: problémy Steinerovského typu v grafech a měření, navigace a umístění zdrojů v sítích. Plánujeme připravit systematickou multivarietní analýzu, která podle našeho názoru v této oblasti chybí.

2018

Jedná se již o 4. ročník této konference. Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům prostor pro prezentaci jejich vědecké práce a činnosti mezi sebou, příležitost naučit se novým technikám a postupům z aktuálních vědeckých výsledků, nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy, a v neposlední řadě též příležitost navázat mezi sebou kontakty. Během dne proběhne několik přednáškových bloků. Zbývající čas je vyhrazen na řešení problémů a diskuze. Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu, nebo aktuálního vědeckého výsledku zapadajícího do tématiky konference. Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty k budoucímu výzkumu a nabídnou tak vhodné problémy k řešení. Tématicky je konference vymezena na tyto oblasti: - teoretická informatika - diskrétní matematika - teorie grafů - výpočetní složitost a algoritmy - datové struktury Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.

2017

Jedná se již o 3. ročník této konference. Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům prostor pro prezentaci jejich vědecké práce a činnosti mezi sebou, příležitost naučit se novým technikám a postupům z aktuálních vědeckých výsledků, nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy, a v neposlední řadě též příležitost navázat mezi sebou kontakty. Během dne proběhne několik přednáškových bloků. Zbývající čas je vyhrazen na řešení problémů a diskuze. Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu, nebo aktuálního vědeckého výsledku zapadajícího do tématiky konference. Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty k budoucímu výzkumu a nabídnou tak vhodné problémy k řešení. Tématicky je konference vymezena na tyto oblasti: - teoretická informatika - diskrétní matematika - teorie grafů - výpočetní složitost a algoritmy - datové struktury Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.

2016

Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům prostor pro prezentaci jejich vědecké práce a činnosti mezi sebou, příležitost naučit se novým technikám a postupům z aktuálních vědeckých výsledků, nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy, a v neposlední řadě též příležitost navázat mezi sebou kontakty. Během dne proběhne několik přednáškových bloků. Zbývající čas je vyhrazen na řešení problémů a diskuze. Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu, nebo aktuálního vědeckého výsledku zapadajícího do tématiky konference. Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty k budoucímu výzkumu a nabídnou tak vhodné problémy k řešení. Tématicky je konference vymezena na tyto oblasti: - teoretická informatika - diskrétní matematika - teorie grafů - výpočetní složitost a algoritmy - datové struktury Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.

2015

Cílem konference STIGMA je poskytnout studentům a mladým vědeckým pracovníkům prostor pro prezentaci jejich vědecké práce a činnosti mezi s sebou, příležitost naučit se novým technikám a postupům z aktuálních vědeckých výsledků, nabídnout čas, ve kterém mohou účastníci řešit otevřené problémy, a v neposlední řadě též příležitost navázat mezi sebou kontakty. Během dne proběhne několik přednáškových bloků. Zbývající čas je vyhrazen na řešení problémů a diskuze. Doktorandi a studenti přednesou přednášky týkající se buďto jejich vlastního výzkumu, nebo aktuálního vědeckého výsledku zapadajícího do tematiky konference. Mladí vědečtí pracovníci přednesou přednášky, které budou mít za cíl inspirovat studenty k budoucímu výzkumu a nabídnou tak vhodné problémy. Tematicky je konference vymezena na tato témata: - teoretická informatika - diskrétní matematika - teorie grafů a grafové algoritmy - výpočetní složitost a algoritmy Konference je určena především pro doktorandy a studenty ČVUT, kteří na ní budou mít přednášku.