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

Michal Dvořák : Pathfinding in Self-Deleting Graphs (Hledání cest v samorozvíjejících se grafech)

Pondělí 29. září, 14:00

Studujeme problém pathfindingu na grafech závislých na traverzování, tj, Konkrétně studujeme samovymazávací grafy, které zavedli Carmesin a další (Sarah Carmesin, David Woller, David Parker, Miroslav Kulich a Masoumeh Mansouri) a které se skládají z grafu G=(V, E) a funkce f: V->2^E, kde f(v) je množina hran, které budou vymazány po návštěvě vrcholu v. V problému (nejkratší) samovymazávací s-t-cesta je dán samovymazávací graf a jeho vrcholy s a t a máme za úkol najít (nejkratší) cestu z s do t takovou, aby po návštěvě v pro žádný vrchol v neprocházela hranou v f(v).

Dokážeme, že Self-Deleting s-t-path je NP-obtížný, i když je daný graf vnější rovinný, bipartitní, má maximální stupeň 3, šířku pásma 2 a |f(v)| ≤ 1 pro každý vrchol v. Ukážeme, že Shortest Self-Deleting s-t-path je W[1]-complete parametrizovaný délkou hledané cesty a že Self-Deleting s-t-path je W[1]-complete parametrizovaný počtem vrcholových obálek, počtem zpětnovazebních vrcholů a hloubkou stromu. Ukážeme také, že problém se stává FPT, když jej parametrizujeme maximální velikostí f(v) a několika strukturálními parametry. Nakonec ukážeme, že problém nepřipouští polynomiální jádro ani pro parametrizaci pomocí čísla vrcholového krytu a maximální velikosti f(v) dohromady již na 2-outerplanárních grafech.

Daniela Černá : Rozbíjení trojic se šesti permutacemi a související problémy

Pondělí 6. října, 14:00

Nechť n≥3 je celé číslo a ( _π1, _π2, _π3, _π4, _π5, _π6) je šest permutací téže základní množiny [n]. Řekneme, že trojice _{aπ1, _a2, _a3}⊂[n] je roztříštěna ( _π1, _π2, _π3, _π4, _π5, _π6), jestliže v množině {( _πi ( _a1), _πi ( _a2), _πi ( _a3)):i∈[6]} najdeme všechna možná uspořádání.

Přirozenou extremální otázkou je určení maximálního možného počtu trojic, které lze tímto způsobem roztříštit pro pevně dané n.

Metodou praporkové algebry dokážeme, že žádná šestice permutací nerozbije více než 1/2 C(n,3) O( ⁿ²) trojic. Na druhou stranu pro každé n≥3 zkonstruujeme šestici permutací [n], která rozbije alespoň 975/482 trojic C(n,30). Určíme také přesné hodnoty pro n∈{6,7,8,9}. Tyto výsledky zlepšují dříve známé meze Johnsona a Wickese.

Dále se zaměříme na příbuzné problémy, kde přidáme další omezení na šestici trojic ( _π1, _π2, _π3, _π4, _π5, _π6).

Jedná se o společnou práci s Alexandrem Cliftonem, Bartłomiejem Kielakem a Janem Volecem.

Aneta Pokorná: Rekonstrukce grafů pomocí posloupností stupňů grafletů

Pondělí 10. října, 14:00

Graflety jsou malé podgrafy s kořenem v pevném vrcholu. Počet výskytů grafletů zarovnaných na určitý vrchol, tzv. posloupnost stupňů grafletů, poskytuje topologický popis okolí analyzovaného vrcholu.

Dlouhodobě otevřený problém v teorii grafů, tzv. rekonstrukční domněnka, se ptá, zda je struktura grafu jednoznačně určena jeho vrcholově vymazanými podgrafy. My se ptáme, zda je struktura grafu G jednoznačně určena posloupnostmi stupňů grafletů jeho vrcholů (uvažujeme všechny graflety menší než G). Ukážeme, že odpověď je kladná pro grafy, které mají určitý typ asymetrických vrcholově vymazaných podgrafů. Všimněte si, že myšlenka využití asymetrie je nová i mezi dílčími výsledky pro (obtížnější) rekonstrukci z vrcholově vymazaných podgrafů.

Sabine Rieder: Vysvětlení rozhodovacích stromů v kontextu strojového učení

Pondělí 27. října, 14:00

Důvěra v rozhodovací systém vyžaduje jak bezpečnostní záruky, tak schopnost interpretovat a pochopit jeho chování. To je obzvláště důležité pro učené systémy, jejichž rozhodovací procesy jsou často velmi neprůhledné. V poslední době se pro reprezentaci regulátorů a politik staly obvyklými rozhodovací stromy.

V této přednášce zkoumáme dva směry, v nichž lze rozhodovací stromy použít k vysvětlení systémů RL. První oblastí použití je stínění. Stínění je významná modelová technika pro vynucení bezpečnosti v posilovacím učení. Protože jsou však štíty automaticky syntetizovány pomocí přísných formálních metod, jsou jejich rozhodnutí pro člověka často podobně obtížně interpretovatelná a ze své podstaty nedeterministická. Proto se jejich reprezentace rozhodovacích stromů stávají příliš rozsáhlými na to, aby je bylo možné v praxi vysvětlit. Abychom tento problém vyřešili, navrhujeme nový přístup k vysvětlitelnému bezpečnému RL, který zvyšuje důvěryhodnost tím, že poskytuje lidsky interpretovatelná vysvětlení rozhodnutí štítu. Naše metoda reprezentuje politiku štítu jako hierarchii rozhodovacích stromů a nabízí vysvětlení shora dolů na základě případu.

Za druhé uvažujeme vysvětlení založená na konceptu neuronových sítí, kde uzly v DT odpovídají sémantickému konceptu v NN. Na rozdíl od předchozí práce se naše vysvětlení zaměřují na věrnost vzhledem k původní síti.

Tomáš Hons: Polynomiální Ramseyho výrok pro ohraničenou VC-dimenzi

Pondělí 3. listopadu, 14:00

Věta autorů Dinga, Oporowského, Oxleyho a Vertigana říká, že každý dostatečně velký bipartitní graf bez dvojčat obsahuje jako indukovaný podgraf shodný, souladný nebo poloviční graf libovolné dané velikosti. Dokážeme, že toto Ramseyho tvrzení má polynomiální závislost za předpokladu omezené VC-dimenze výchozího grafu, přičemž využijeme nedávné ověření Erdős-Hajnalovy vlastnosti pro grafy omezené VC-dimenze. Protože věta Dinga a spol. hraje roli v teorii (konečných) modelů, která studuje ještě omezenější struktury, komentujeme také další zpřesnění věty v tomto kontextu.

Elizaveta Streltsova: Tvárné počty úrovní v uspořádáních a aplikace na křížová čísla

Pondělí 10. listopadu, 14:00

Hladiny v uspořádáních hrají zásadní roli v diskrétní a výpočetní geometrii a jsou přirozeným zobecněním konvexních polytopů, které odpovídají hladině 0. V přednášce se zaměřím na dva nové výsledky. Určíme prostor všech lineárních a afinních vztahů mezi lícovými čísly hladin v jednoduchých uspořádáních o n polokoulích v Sd, čímž dokončíme dlouhou řadu výzkumu těchto vztahů a odpovíme na otázku, kterou položili Andrzejak a Welzl v roce 2003. Kromě toho jsme dokázali speciální případ n = d + 4 dlouholeté domněnky Eckhoffa, Linharta a Welzla o složitosti (⩽ k)-úrovní, z níž vyplývá (podle Galeovy duality) těsná dolní mez pro sférické obloukové číslo křížení úplných grafů. Abychom získali tyto výsledky, zavedeme pojem g-matice, který kóduje počty tváří úrovní v uspořádání a zobecňuje klasický g-vektor polytopu.

Společná práce s Ulim Wagnerem

Calvinem Chauem: s Chauvem Chauvem, který spolupracuje s Chauvem Chauvem, a to v oblasti certifikátů a svědků pro víceúčelové dotazy v markovských rozhodovacích procesech

Pondělí 24. listopadu, 14:00

Pravděpodobnostní kontrola modelu (PMC) je výkonná technika pro formální verifikaci pravděpodobnostních systémů, jako jsou náhodné algoritmy nebo komunikační protokoly. V posledních letech se intenzivně studují nezávisle kontrolovatelné certifikáty a svědci, aby se zvýšila důvěryhodnost a vysvětlitelnost nástrojů pro kontrolu modelů.

Tato přednáška se zaměřuje na certifikáty a svědky pro víceúčelové dotazy v Markovových rozhodovacích procesech (MDP). Markovovy rozhodovací procesy jsou standardním modelem v PMC a víceobjektivní dotazy jsou přirozeným formalismem pro specifikaci více konfliktních požadavků. Pro osvědčení nejprve zobecníme předchozí práci na osvědčeních pro jednoobjektivní dosažitelnost a poté zdokonalíme stávající osvědčení pro rozklad maximálních koncových komponent. Na základě charakterizace certifikátů jsou odvozeny smíšené celočíselné lineární programy (MILP) pro nalezení minimálních svědků ve formě subsystémů. Nakonec informujeme o implementaci a slibných experimentálních výsledcích, které ukazují účinnost našich technik.

Lenka Kopfová: Moranův proces při silném výběru

Pondělí 1. prosince, 14:00

Moranův proces je standardní náhodný proces v evoluční teorii her, který modeluje konkurenci mezi dvěma nebo více druhy v populaci podobné síti. Populace je reprezentována grafem, kde vrcholy odpovídají jedincům a hrany přímým interakcím mezi nimi. Jedinci se rozmnožují, jejich potomci migrují podél hran sítě a nahrazují své sousedy.

Studujeme modifikovanou verzi Moranova procesu, která odpovídá silnému výběru, jako je tomu v dynamice invazních druhů. V tomto procesu se šíří pouze mutantní jedinci, kteří nakonec ovládnou celou populaci. Klíčovou veličinou, kterou studujeme, je tzv. fixační čas, což je očekávaná doba, než se všichni jedinci stanou mutanty. Uvádíme těsné horní a dolní meze pro dobu fixace na obecné populační struktuře a upřesňujeme je pro některé třídy.

Nikola Sadovek: Nutná a postačující podmínka pro k-dimenzionální transverzály

Čtvrtek 4. prosince, 14:00, místnost A502

Hellyho věta (1913) dává kritérium, kdy má rodina konvexních množin v R^d společný bod: jestliže se každá skupina d+1 množin protíná, pak se protíná celá rodina. Pokud se na bod díváme jako na 0-rozměrný afinní podprostor, věta Goodmana, Pollacka a Wengera (1988) poskytuje analogickou podmínku pro existenci hyperplochy ((d-1)-rozměrného afinního podprostoru), která se setkává s každou množinou v rodině. V této přednášce představíme společné zobecnění těchto výsledků tím, že charakterizujeme, kdy k-rozměrný afinní podprostor R^d protíná všechny množiny v dané rodině konvexních množin, pro libovolné 0≤k≤d-1. Jedná se o společnou práci s Danielem McGinnisem.

Kristýna Pekárková: Identifikace nedokonalých klonů ve volbách

Pondělí 8. prosince, 14:00

Na mnoho kolektivních rozhodovacích procesů lze nahlížet jako na volby, v nichž je množina alternativ ("kandidátů") hodnocena skupinou agentů ("voličů"), přičemž každý z nich vyjadřuje své preference. S takovými "volbami" se setkáváme všude, od nejviditelnějších příkladů v politice (včetně místních referend, parlamentních a prezidentských voleb), přes rozhodování, jako je výběr uchazečů o danou pracovní pozici, až po běžné situace, jako je rozhodování, na který film se má skupina dívat.

Obor Computational Social Choice (COMSOC) studuje algoritmické a kombinatorické aspekty těchto rozhodovacích procesů. Zkoumá širokou škálu témat, včetně: Jaký je efektivní a spravedlivý způsob výběru vítěze? Jak lze zabránit manipulaci nebo strategickému hlasování? Jaké druhy struktury lze v preferenčních datech odhalit a jak obtížné je je najít?

Ve volbách jsou dokonalými klony skupiny kandidátů, které se z pohledu voličů jeví jako nerozlišitelné - buď je každý volič řadí za sebou (v ordinálních volbách, kde jsou preference vyjádřeny jako úplné pořadí), nebo je schvalují úplně stejní voliči (ve schvalovacích volbách, kde každý volič o každém kandidátovi vynáší jednoduchý soud ano/ne). Taková dokonalá podobnost je však příliš přísná a v reálných datech se pozoruje jen zřídka. V této přednášce se budeme zabývat konceptem nedokonalých klonů pro ordinální i schvalovací volby. Pro každé nastavení navrhneme několik relaxací dokonalých klonů a analyzujeme (parametrizovanou) složitost dvou základních úloh: detekce přítomnosti nedokonalých klonů v daných volbách a rozdělení celé množiny kandidátů na rodiny nedokonalých klonů.

Přednáška vychází ze společné práce s Théo Delemazurem, Piotrem Faliszewským, Łukaszem Janeczkem, Dušanem Knopem, Grzegorzem Lisowskim, Janem Pokorným, Šimonem Schierreichem a Ildi Schlotterovou.

Vincent Fischer: Runtime Verification for LTL in Stochastic Systems (Ověřování za běhu pro LTL ve stochastických systémech)

Středa 10. prosince, 14:00, místnost C123

Runtime verifikace zahrnuje několik lehkých technik pro kontrolu, zda aktuální provádění systému splňuje danou specifikaci. Zaměříme se na runtime verifikaci pro lineární časovou logiku (LTL). Předchozí práce popisují monitory, které v každém časovém kroku produkují jeden ze tří výstupů - pravdivý, nepravdivý nebo neprůkazný - v závislosti na tom, zda pozorovaný prefix provádění definitivně určuje splnění formule. U mnoha formulí LTL, například u vlastností životaschopnosti, však nelze z žádného konečného prefixu vyvodit splnění. Pro tyto vlastnosti budou tradiční monitory vždy dávat nepřesvědčivý výstup. Navrhujeme nový přístup k monitorování, který nahrazuje tvrdé verdikty pravděpodobnostními předpověďmi a přidruženým skóre spolehlivosti. Naše metoda zaručuje případnou správnost předpovědi a zajišťuje, že důvěryhodnost od tohoto okamžiku neomezeně roste.

Marek Filakovský: Topologie zobecněných klikových komplexů mřížkových grafů

Pondělí 15. prosince, 14:00, místnost C117

Je klasické, že vlastnosti grafu G lze zachytit pomocí vyšší dimenzionální datové struktury zvané simpliciální komplex. V průběhu let bylo definováno mnoho různých grafových komplexů - sousedský, krabicový, klikový, nezávislostní, shodný... Běžnou technikou v této oblasti je výpočet topologických (homotopie, homologie, kohomologie) nebo kombinatorických vlastností(shellability) grafových komplexů pocházejících z nějaké omezené rodiny grafů.

Pokračujeme v tomto přístupu a určíme typ homotopie zobecnění klikových komplexů, které nazýváme k-ohraničené klikové komplexy pro třídu grafů, která obsahuje mřížkové grafy. Pomocí Alexaderovy duality získáme typ homotopie totálně k-řezaných komplexů mřížkových grafů, který nedávno zavedli Bayer et. al. (DCG 2024) v souvislosti s Fröbergovou větou.