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)
- Rozvoj liských zdrojů pro výzkum v teoretické informatice
- Centrum excelence – Institut teoretické informatiky (CE-ITI)
- Extremální teorie grafů a aplikace
- Predikátové škálované logiky a jejich aplikace v informatice
- Neklasické logické modely informační dynamiky
- Usuzování se škálovanými vlastnostmi
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
Členové oddělení
- Bílková Marta, Mgr., Ph.D.
- Cintula Petr, doc.Ing., Ph.D.
- Haniková Zuzana, RNDr., Ph.D.
- Kubíková Iveta, Ing.
- Majer Ondrej, RNDr., CSc.
- Moraschini Tommaso
- Piguet Diana, Mgr., Ph.D.
- Porubský Štefan, prof. RNDr., DrSc.
- Punčochář Vít, Ph.D.
- Reggio Luca, Ph.D.
- Rocha De Souza Israel, Dr., Ph.D.
- Saumell Mendiola Maria, Ph.D.
- Savický Petr, RNDr., CSc.
- Sedlár Igor, Mgr., Ph.D.
- Šileikis Matas, Ph.D.
- Šíma Jiří, doc. RNDr., DrSc.
- Tedder Andrew, Ph.D.
- Vidal Wandelmer Amanda, Ph.D.
- Žák Stanislav, RNDr., CSc.
Sekretářská podpora
