2002/2003, czwartki, godz. 12:15, sala 5870
Lista spotkan:
03.09.2002 Spotkanie organizacyjne
10.10.2002 Maciek Kurowski, Lukasz Kowalik
Najkrotsze sciezki w grafach planarnych
Zajmujemy sie pewna odmiana klasycznego problemu szukania najkrotszych sciezek pomiedzy wierzcholkami w grafach planarnych. Ustalamy stala k. Dla danego grafu wykonujemy preprocessing w czasie O(n). Potem w czasie O(1) umiemy znalezc najkrotsza sciezke pomiedzy dowolnymi wierzcholkami pod warunkiem, ze jej dlugosc nie przekracza k.
17.10.2002 Maciek Kurowski, Lukasz Kowalik
Grafy planarne cd.
24.10.2002 Piotr Sankowski
Zliczanie i #P
Na seminarium przedstawie klase problemow #P, oraz #P-zupelnosc. Na kilku przykladach omowie konstrukcje algorytmow aproksymacyjnych dla takich problemow. Oraz zwiazek generowania z rozkladem jednostajnym i zliczania w kontekscie lancuchow Markowa.
31.10.2002 Andrzej Szalas
Zlozonosc 'transversal hypergraph problem'
In the paper we present a purely logical approach to estimating computational complexity of potentially intractable problems. The approach is based on descriptive complexity and second-order quantifier elimination techniques. We illustrate the approach on the case of the transversal hypergraph problem, \transhyph, which has attracted a great deal of attention. The complexity of the problem remains unsolved for over twenty years. Given two hypergraphs, $G$ and $H$, \transhyph\ depends on checking whether $G=H^d$, where $H^d$ is the transversal hypergraph of $H$. In the paper we provide a logical characterization of minimal transversals of a given hypergraph and prove that checking whether $G\subseteq H^d$ is tractable. For the opposite inclusion the problem still remains open. However, we interpret the resulting quantifier sequences in terms of determinism and bounded nondeterminism. The results give better upper bounds than those known from the literature, e.g., in the case when hypergraph $H$ has a sub-logarithmic number of hyperedges and (for the deterministic case) all hyperedges have the cardinality bounded by a function sub-linear wrt maximum of sizes of $G$ and $H$.
07.11.2002
brak seminarium
14.11.2002 Kamil Kulesz (IPPT)
Twierdzenie o liczbie grafow o zadanej liczbie wierzcholkow, ktore mozna pokolorowac n kolorami.
Planuje przedstawic twierdzenie, dowod oraz pokazac zastosowania do kodowania/kryptografii.
21.11.2002 Robert Dabrowski
Kompletna charakterystyka relacji zero-wyrazalnych przez rownania na slowach
Wprowadzone zostanie pojecie relacji wyrazalnych przez rownania na slowach oraz przedstawiona zostanie kompletna charakterystyka klasy relacji zero-wyrazalnych.
28.11.2002 Miroslaw Kowaluk
Problem strzelca
Dla danych n odcinkow na plaszczyznie szukamy punktu, z ktorego mozemy poprowadzic minimalna liczbe polprostych przecinajacych wszystkie odcinki
05.12.2002 Marcin Mucha
Hipoteza Tovey'a i takie tam
Czy hipoteza Tovey'a jest prawdziwa? Co to w ogole za hipoteza? Po co to wszystko? I co to wlasciwie znaczy 'hipoteza'? Jesli chcesz poznac odpowiedzi na te i inne pytania, przyjdz koniecznie!
12.12.2002
Konferencja FIT
19.12.2002 Krzysztof Ciebiera
09.01.2003 Jakub Pawlewicz
Optymalizacja Algorytmu Context Tree Weighting
W 1994 przedstawiono algorytm kompresji statystycznej świednie nadający się do kompresji plików tekstowych dający wyniki kompresji lepsze niż inne metody kompresji statystycznej jak PPMD. W ciągu kolejnych lat powstały liczne modyfikacje tego algorytmu. Niestety z powodu dużego zapotrzebowania na pamięć operacyjną nie pojawiła się dotąd żadna komercyjna implementacja tego algorytmu. W mojej pracy magisterskiej o powyższym tytule przedstawiam znane dotąd modyfikacje oraz wprowadzam nową, która kosztem niedużej straty jakości kompresji pozwala stosować algorytm przy dowolnie ograniczonej pamięci operacyjnej.
16.01.2003 Karol Golab
13.02.2002
brak seminarium
20.02.2003 Tomek Walen
27.02.2003 Lukasz Sznuk
06.03.2003 Piotr Sankowski
Zliczanie skojarzen w grafach
W czasie seminarium opowiem o propozycji na konstrukcje algorytmu FPRAS (w pelni wielomianowego randomizowanego schematu aproksymacyjny) dla liczby doskonalych skojarzen w grafach. Algorytm oparty jest na estymatorze Godmana-Gutsila. Pokaze jak losowo wygenerowac liniowo wiele macierzy, tak aby wzgledna wariancja estymatora byla ograniczona przez stala.
13.03.2003 Marcin Mucha
20.03.2003 Lukasz Kowalik
Krotkie cykle w grafach planarnych
Opowiem o nastepujacym problemie: dla danego grafu planarnego G = (V,E) znalezc w G jeden (lub wszystkie) cykl dlugosci k. Zakladamy, ze k jest stala i poszukujemy wielomianowych algorytmow dla opisanego problemu (jesli nie zalozymy, ze k jest stala, dla k = |V| otrzymujemy problem cyklu Hamiltona). Chociaz istnieja ogolne algorytmy wyszukiwania takich cykli o zlozonosci O(|V|), stala ukryta w notacji "O" (zalezna od k) jest tak duza, ze nie nadaja sie one do uzycia w praktyce nawet gdy k=4. Opowiem o kilku liniowych "praktycznych" algorytmach znajdowania cykli o dlugosciach od 3 do 6. Przy okazji pokaze dolne i gorne ograniczenie na liczbe cykli dlugosci k (asymptotyczna).
27.03.2003 Maciek Kurowski
03.04.2003 Krzysztof Ciebiera
O Gridach dla algorytmikow
Na wykładzie przedstawię główne założenia architektury Grid (model obliczeń oparty o heterogeniczne środowisko komputerowo-sieciowe). Opowiem o problemie przydziału pracy w tym modelu. Przedstawię rozwiązanie tego problemu dla zadań o złożoności liniowej.
10.04.2003
Konferencja ETAPS'03
17.04.2003 Darek Kowalski
Wykonywanie zadan w srodowisku asynchronicznym (wyniki wlasne)
Rozwazany bedzie problem wykonywania niezaleznych zadan przez system procesorow, ktore moga komunikowac sie przez wysylanie komunikatow. Podam gorne i dolne ograniczenia na prace takiego systemu w modelu asynchronicznym.
24.04.2003 Karol Golab
01.05.2003
brak seminarium
08.05.2003 Wojskowy Instytut Lacznosci
15.05.2003 Robert Dabrowski
Rownania w polgrupie wolnej z dwiema niewiadomymi
22.05.2003 Rafal Dowgird
29.05.2003 Adam Malinowski
05.06.2004 Mirek Kowaluk
12.06.2004 Wojtek Plandowski
19.06.2004 Krzysztof Diks
| RD |