Oddělení teoretické informatiky
Členové našeho oddělení působí především ve třech vzájemně propojených základních disciplínách teoretické informatiky: matematické logice, výpočetní složitosti, diskrétní matematice. Naší vizí je pomocí špičkového základního výzkumu rozšířit repertoár přístupů, které jsou v našich oblastech považovány za standardní. Konkrétní cíle v jednotlivých oblastech jsou:
Logika: aplikování neklasických logik pro usuzování, v situacích přirozených a umělých, s informacemi z reálného světa, které jsou často nejisté, stupňované nebo dokonce protichůdné a měnící se v čase.
Výpočetní složitost: prohloubení našich znalostí o vztazích mezi třídami složitosti a našeho porozumění standardním i nestandardním výpočetním modelům s ohledem na nové míry složitosti týkající se současných technologických výzev.
Diskrétní matematika: zkoumání extremální teorie grafů a aplikované teorie čísel a využití dosažených výsledků v kryptografii, teorii počítání a studiu náhodnosti.
Oblast našeho výzkumu
Logika: matematická fuzzy logika, substrukturální logika, vágnost, parakonzistentní logika, logika a usuzování, stupňované pojmy, dynamická a nemonotónní logika, modální logika, abstraktní algebraická logika, složitost neklasických logik.
Výpočetní složitost: branching programy, neuronové sítě, booleovské funkce, předběžné zpracování problému SAT, logické popisy výpočtů, nestandardní číselné systémy.
Diskrétní matematika: extremální teorie grafů, regularita, pravděpodobnostní metoda, limity grafů, náhodné grafy, výpočetní geometrie, kombinatorické a algebraické metody v teorii čísel, uniformní distribuce číselných posloupností, kryptologie.
Pracovní skupiny a jejich semináře
Kombinatorická skupina: skupina věnující se studiu extremální teorie grafů a výpočetní geometrie, Spolu se skupinou Graph limits and inhomogeneous random graphs z MÚ AV ČR pořádáme seminář teorie grafů s důrazem zejména na extremální teorii grafů.
LogICS: skupina věnující se studiu (neklasických) logik. Společně s Českou společností pro kybernetiku a informatiku pořádáme seminář aplikované matematické logiky (nazývaný také Hájkův seminář podle jeho zakladatele), který se koná od konce šedesátých let.
Aktuální projekty (zde)
- FoNeCo: Analytické základy neurovýpočtů (2019-2021; GAČR)
- Národní centrum kompetence – Kybernetika a umělá inteligence (2019-2021; GAČR)
- Reprezentace booleovských funkcí úplné vzhledem k jednotkové propagaci (2019-2021; GAČR)
- Strukturální vlastnosti viditelnosti terénů a Voroného diagramů nejvzdálenější barvy (2019-2021; GAČR)
- Vnořování, pakování a limity v grafech (2019-2021; GAČR)
- Rozvoj lidských zdrojů pro výzkum v teoretické informatice (2018-2020; MŠMT)
- Neklasické logické modely informační dynamiky (2018-2020; GAČR)
- Usuzování se škálovanými vlastnostmi (2018-2020; GAČR)
- CONNECT – Combinatorics of Networks and Computation (2017-2020; H2020 MSCA RISE)
- Predikátové škálované logiky a jejich aplikace v informatice (2017-2019; GAČR)
- SYSMICS: Syntax a sémantika: Metody, interakce a souvislosti v substrukturálních logikách (2016-2019; GAČR)
- Extremální teorie grafů a aplikace (2016-2018; GAČR)
- Modelování vágních kvantifikátorů v matematické fuzzy logice (2015-2017; GAČR)
- Neklasické výrokové a predikátové logiky: přístup založený na uspořádání (2013-2016; GAČR)
- Centrum excelence – Institut teoretické informatiky (CE-ITI) (2012-2018; GAČR)
- Distribuční a metrické vlastnosti číselných posloupností a jejich aplikace (2012-2015; GAČR)
- Algebraické metody v teorii důkazů (2011-2015; GAČR)
Vybrané publikace
- Kučera Petr; Savický Petr; Vorel Vojtěch. A lower bound on CNF encodings of the at-most-one constraint. Theoretical Computer Science, 2018
- Šíma Jiří; Savický Petr. Quasi-periodic β – expansions and cut languages. Theoretical Computer Science, 2018
- Bezhanishvili Guram; Moraschini Tommaso; Raftery James Gordon. Epimorphisms in Varieties of Residuated Structures. Journal of Algebra, 2017
- Cabello Sergio; Cibulka Josef; Kynčl Jan; Saumell Maria; Valtr Pavel. Peeling Potatoes Near-Optimally in Near-Linear Time. SIAM Journal on Computing, 2017
- Moraschini Tommaso. A Computational Glimpse at the Leibniz and Frege Hierarchies. Annals of Pure and Applied Logic, 2017
- Šíma Jiří; Žák Stanislav. On tight separation for Blum measures applied to Turing machine buffer complexity. Fundamenta Informaticae, 2017
- Böttcher Julia; Hladký Jan; Piguet Diana; Taraz Anusch. An approximate version of the tree packing conjecture. Israel Journal of Mathematics, 2016
- Haniková Zuzana; Savický Petr. Term satisfiability in FLew-algebras. Theoretical Computer Science 31, 2016
- Hladký Jan; Piguet Diana; Simonovits Miklos; Stein Maya; Szemeredi Endre. The approximate Loebl-Komlos-Sos conjecture and embedding trees in sparse graphs. Electronic Research Announcements in Mathematical Sciences, 2016
- Hladký Jan; Piguet Diana. Loebl-Komlos-Sos Conjecture: dense case. Journal of Combinatorial Theory, 2016
- Chvalovský Karel; Horčík Rostislav. Full Lambek Calculus with Contraction is Undecidable. Journal of Symbolic Logic, 2016
- Moraschini Tommaso. The Semantic Isomorphism Theorem in Abstract Algebraic Logic. Annals of Pure and Applied Logic, 2016
- Strauch Oto; Porubský Štefan. Distribution of Sequences: A Sampler. Peter Lang GmbH, Electronic revised version December 8, 2016
- Cintula Petr (ed.); Fermüller C. (ed.); Hájek Petr (ed.), Noguera Carles (ed.). Handbook of Mathematical Fuzzy Logic (in three volumes). London: College Publications, 2011, 2015
- Cintula Petr; Noguera Carles. A Henkin-Style Proof of Completeness for First-Order Algebraizable Logics. Journal of Symbolic Logic, 2015
- Chvalovský Karel. Undecidability of consequence relation in Full Non-associative Lambek Calculus. Journal of Symbolic Logic, 2015
- Horčík Rostislav. Word Problem for Knotted Residuated Lattices. Journal of Pure and applied Algebra, 2015
Organizované akce
