"Algorytmika"

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