Seminář o základech výpočetní techniky

Tento výzkumný seminář poskytuje prostor pro prezentaci výsledků výzkumu týkajícího se návrhu algoritmů, diskrétní matematiky, formálních metod, logiky a příbuzných oblastí teoretické informatiky. Seminář společně pořádají výzkumné laboratoře DIMEA, FORMELA a LIVE. Seminář navazuje na seminář FMDSA , který v minulosti pořádala laboratoř FORMELA.

Čas a místo konání

Seminář se koná v pondělí ve 14 hodin semestrálního času v místnosti C226a v budově Fakulty informatiky v (zhruba) týdenním rozvrhu.

Jaro 2025 - přehled rozvrhu

Přednášející

Nadcházející

Jan Hladký : Nehomogenní náhodný 2SAT

Pondělí 24. února, 11:00, místnost C325

Náhodný k-SAT je standardní model náhodně generovaných booleovských formulí. Tento model je extrémně náročný na analýzu (zejména asymptotické téměř jisté splnitelnosti) pro k > 2, zatímco pro k = 2 zůstává relativně jednoduchý. V nedávné společné práci s Petrem Savickým zavádíme nehomogenní variantu náhodného 2-SAT. Nehomogenita je generována funkcí dvou proměnných podobným způsobem, jakým Bollobás, Janson a Riordan zobecnili Erdős-Rényiho náhodné grafy. Zejména identifikujeme určitý spektrální parametr modelu, který určuje jeho asymptotickou téměř jistou splnitelnost či nesplnitelnost.

Soichiro Fuiji : Hom komplexy grafových homomorfismů a grafy bez čtverce

Pondělí 3. března, 14:00, místnost C226a

Hom komplex Hom(G, H) je určitý polyedrický komplex spojený s dvojicí (neorientovaných, konečných a jednoduchých) grafů G a H, jehož vrcholy odpovídají homomorfismům grafů z G do H. Hom komplexy byly aplikovány na problém barvení grafů a souvisí také s novějším tématem kombinatorické rekonfigurace. V této přednášce začnu základy Hom komplexů a vysvětlím náš nedávný výsledek určující typ homotopie (každé spojité komponenty) Hom(G, H), když H je bez čtverce, což znamená, že neobsahuje čtyřcyklový graf jako podgraf. Ačkoli je známo, že homotopický typ Hom(G, H) může být obecně poměrně komplikovaný, pro spojitý G a bezčtvercový H ukážeme, že každá spojitá složka Hom(G, H) je homotopicky ekvivalentní klínovitému součtu kružnic. (Na základě společné práce s Keiem Kimurou a Yutou Nozakim.)

Zoltán Vidnyánszky : Nekonečné verze věty o dichotomii CSP

Pondělí 10. března, 14:00, místnost C226a

Věta o dichotomii CSP Bulatova a Žuka je slavným výsledkem v informatice: říká, že pro danou konečnou strukturu H je problém rozhodnutí, zda struktura G připouští homomorfismus k H, buď snadný (v P), nebo velmi těžký (NP-úplný). V této přednášce poskytnu přehled této věty a proberu dvě rozšíření na nekonečné domény - jedno v Borelově a druhé v bezvýběrovém prostředí.

Max Hadek : Nový pohled na uspokojování omezení: Zázračná země adjunkcí

Pondělí 24. března, 14:00, místnost C226a

Tzv. algebraický přístup k problémům splnění omezení je od počátku tisíciletí převládající metodou studia složitosti těchto problémů a poskytuje základ slavných dichotomických důkazů Bulatova a Žuka. Probereme nový, shora dolů směřující pohled na hlavní věty algebraického přístupu a odhalíme jeho souvislosti s teorií kategorií a algebraickou topologií.

Jakub Rydval : Problémy splnění omezení s nekonečnými doménami

Pondělí 31. března, 14:00, místnost C226a

Bodirského-Pinskerova domněnka rozšiřuje větu o dichotomii CSP Bulatova a Žuka na určité vysoce symetrické nekonečné struktury. V této přednášce domněnku motivuji a poskytnu přehled současného stavu CSP s nekonečnými doménami. Probereme nedávný pokrok, problémy a souvislosti s dalšími příbuznými obory.

Tomáš Jakl : Herní komonády a parametry hustých grafů

Pondělí 26. května, 14:00, místnost A321

Modelové srovnávací hry jsou důležitým nástrojem pro vyjádření výsledků v teorii databází a teorii konečných modelů. V posledních letech se setkáváme s rostoucím počtem příkladů modelových srovnávacích her (jako jsou kamínkové hry nebo Ehrenfreucht-Fraisseho hry), které jsou kódovány sémanticky, jako komonády na třídě grafů nebo relačních struktur. Kromě souvislostí s logikou vyjadřují komonády her také řadu důležitých parametrů v teorii konečných modelů a kombinatorice, jako je šířka a hloubka stromu.

V této přednášce uvedu motivaci a stručný úvod do herních komonád a budu diskutovat o současném pokroku při zachycování parametrů hustých grafů, jako je modulární šířka a šířka kliky.