Poprzednie sezony [2000/2001] [2001/2002] [2002/2003] [2003/2004] [2004/2005]

Sezon 2005/2006, czwarek 12:15-13:45, sala 5870

06.10.2005 Łukasz Kowalik

Postaram się krótko przedstawić problem listowego kolorowania krawędziowego grafów oraz opowiedzieć o znanych wynikach w tej dziedzinie. Szczególnie uważnie będę się przyglądał grafom planarnym. Z listowym kolorowaniem krawędziowym grafów ogólnych i planarnych wiąże się kilka bardzo ciekawych problemów otwartych -- przede wszystkim teoriografowych, ale również algorytmicznych. Lesistosć (ang. arboricity) grafu to najczęsciej stosowana miara rzadkości/gęstosci grafu. Problem mierzenia lesistosci jest wielomianowy, ale najlepsze znane algorytmy opieraja się na metodach przeplywowych i maja złożoność rzedu O(m^3/2). Jeśli starczy czasu druga część seminarium poswięcę na zreferowanie efektywnych algorytmow aproksymacyjnych dla problemu mierzenia lesistosci oraz pokrewnego problemu znajdowania optymalnej orientacji grafu. Tu takze opiszę kilka otwartych problemów (myślę że dużo prostszych niż te związane z kolorowaniem listowym).

13.10.2005 Mirosław Kowaluk

Najbliższym wspólnym przodkiem dwóch wierzchołków u,v grafu acyklicznego jest wierzchołek będący wspólnym przodkiem wierzchołków u, v i nie będęcy przodkiem żadnego innego wspólnego przodka tych wierzchołków. Wybór najbliższego wspólnego przodka nie musi być jednoznaczny. W problemie najbliższego przodka w grafie acyklicznym pragniemy możliwie szybko odpowiadać na pytanie, który z wierzchołków grafu jest najbliższym wspólnym przodkiem dwóch dowolnie wybranych wierzchołków tego grafu. W tym celu stosujemy preprocessing umożliwiający odpowiedź na to pytanie w czasie stałym. Dotychczas najlepszy algorytm wykonywał preprocessing w czasie O(n^{(\omega+3)/2}, gdzie \omega=2,376. Z Andrzejem Lingasem poprawiliśmy nieco ten wynik do O(n^{2+(1/(4-\omega))}.

20.10.2005 Marcin Pęczarski

Własno.ci, o których będę mówił, zwi.zane s. z sortowaniem za pomoc. porównań. Sortowanie porz.dku czę.ciowego polega na znalezieniu jednego z jego rozszerzeń liniowych. Sortowanie możemy sobie wyobrazić jako grę. W każdym ruchu my wybieramy parę elementów do porównania, a przeciwnik wskazuje nam kolejno.ć tych elementów. Wskazane porównanie dzieli możliwy zbiór rozszerzeń liniowych na dwa rozł.czne podzbiory. Czyli gra polega na tym, że w każdym kroku my wybieramy podział zbioru rozszerzeń liniowych, a przeciwnik wskazuje ten podzbiór, który zawiera poszukiwane rozszerzenie liniowe. Gra kończy się, gdy pozostanie zbiór jednoelementowy. Omówię trzy problemy badawcze, którymi się zajmuję. 1. Hipoteza o złotym podziale Sformułuję hipotezę o złotym podziale porz.dku czę.ciowego. Prawdziwo.ć tej hipotezy implikuje prawdziwo.ć bardzo znanej hipotezy 1/3--2/3 oraz ciasn. górn. granicę dla sortowania porz.dków czę.ciowych. Przedstawię wybrane wyniki badań, w tym moje, nad dowodami powyższych hipotez. 2. Najgorzej zbalansowane porz.dki - drabiny z powyłamywanymi szczeblami Do.ć naturaln., choć nie zawsze optymaln., strategi. sortowania porz.dku czę.ciowego jest wskazywanie podziału zbioru jego rozszerzeń liniowych na możliwie równoliczne podzbiory. Zło.liwy przeciwnik, staraj.c się utrudnić nam zadanie, będzie wybierał podzbiór o większej mocy. Współczynnik zbalansowania porz.dku czę.ciowego okre.la, jak bliski idealnemu (na równoliczne podzbiory) podział możemy wskazać. Zatem istotne jest pytanie, jak Ľle może być zbalansowany porz.dek czę.ciowy. Brightwell [1999] wskazał znane mu najgorzej zbalansowane porz.dki czę.ciowe. Przedstawię, znalezion. za pomoc. komputera, nieskończon. klasę gorzej zbalansowanych porz.dków czę.ciowych. 3. Sortowanie z minimaln. liczb. porównań Interesuje nas minimalna liczba porównań, zawsze wystarczaj.ca do posortowania n elementów. Wiadomo, że dla n < 12 i n = 20, 21 minimum to realizuje algorytm Forda-Johnsona. Algorytm ten jest również optymalny dla n = 12 [Wells 1969] oraz n = 13, 14, 15, 22 [Peczarski 2002,2004]. Najmniejsz. liczb. elementów, dla której znamy algorytm lepszy od algorytmu Forda-Jonhnsona, jest n = 47 [Moenting 1981]. Przedstawię aktualny stan moich poszukiwań najmniejszego n, dla którego algorytm Forda-Johnsona nie jest optymalny.

27.10.2005 Piotr Sankowski

Tematem seminarium jest obliczanie odległości w grafie z wykorzystaniem mnożenia macierzy. Rozpocznę od przedstawienia tegorocznych wyników pokazujących w jaki sposób bliczyć odległości z zadanego wierzchołka w grafie dla całkowitoliczbowych wag krawędzi w takim samym czasie jak mnożenie macierzy rozmiaru n na n. Wynik ten został jednoczesnie przedstawony w pracach ,,Answering distance queries in directed graphs using fast matrix multiplication'' Raphael Yuster i Uri Zwick (FOCS'05) oraz ,,Shortest Paths in Matrix Multiplication Time'' Piotr Sankowski (ESA'05). Druga część seminarium będzie poświęcona obliczaniu odległości między wszystkimi parami wierzchołków w grafie. Skoncentruję się na przestawieniu wyników zawartych w pracy ,,All Pairs Shortest Paths in weighted directed graphs'' Uri Zwick (FOCS'98).

10.11.2005 Krzysztof Ciebiera

Opowiem o:
Motywacji dla istnienia takich struktur danych biorących się z zastosowań certyfikatów w Internecie.
Tradycyjnych metodach tworzenia poświadczonych słowników.
Najlepszych obecnie metodach implementacji poświadczonych słowników za pomocą skip-list działających w czasie 1.25log n+O(1).
Innych znanych zastosowaniach poświadczonych struktur danych w geometrii i algorytmach grafowych.

17.11.2005 Anna Urbanska

Tematem referatu jest kombinatoryczna charakteryzacja wyznacznika, dająca prosty i całkowicie kombinatoryczny algorytm na jego obliczanie, działający w czasie O(n^4). Algorytm ten nie wymaga dzielenia i pracuje nad dowolnym pierścieniem przemiennym. Postaram się również pokazać, jak wykorzystując algorytm szybkiego mnożenia macierzy poprawić złożoność czasową tego algorytmu. Na koniec opowiem jak w analogiczny sposób można scharakteryzować wszystkie pozostałe współczynniki wielomianu charakterystycznego oraz Pfaffian dowolnej macierzy skośno-symetrycznej oraz podam kombinatoryczne dowody poprawności znanych algorytmów obliczania wyznacznika (Chistova, Csanky'ego oraz Samuelsona).

24.11.2005 Wojciech Plandowski

Streszczenie

01.12.2005 Wojciech Plandowski

Kontynuacja seminarium z 24.11.2005

01.12.2005 Marcin Stefaniak

SilkRoute (2002) służy do wyciągania danych z relacyjnej bazy (SQL) w postaci drzewiastej (XML) przy użyciu języka zapytań XQuery. Odbywa się to poprzez stworzenie drzewiastego planu zapytań SQL, co można zrobić na wiele sposobów. SilkRoute w celu optymalizacji planu zapytań używa heurystycznych szacunków oraz zachłannego algorytmu, co przynosi zadowalające praktycznie rezultaty. Interesujące, czy można dla tej z życia wziętej sytuacji stworzyć pewien (uproszczony) model matematyczny, tak aby ów problem algorytmiczny dał się ładnie zanalizować.

08.12.2005 Arek Paterek

Na seminarium omówię własne eksperymenty związane z zastosowaniem technik uczenia z nadzorem do wyboru parametrów funkcji oceniającej w programie grającym w szachy. Opowiem również o algorytmie BPIP, obiecującej alternatywie dla algorytmu alfa-beta cięć. Jest to algorytm typu best-first search, oparty na teorii decyzji. Funkcja oceniająca w algorytmie BPIP zwraca dla liści drzewa rozkład prawdopodobieństwa. Rozkłady są propagowane do korzenia drzewa przeszukiwania, zgodnie z regułą minimaksową. Przeszukiwanie polega na rozwijaniu liści, które mają największy wpływ na oczekiwaną wypłatę. Dodatkową zaletą algorytmu BPIP jest jasne kryterium zakończenia przeszukiwania.

15.12.2005 Krzysztof Diks

Streszczenie

05.01.2006 Krzysztof Onak

W sytuacji, gdy dysponujemy ograniczoną ilością czasu, może nie być możliwe sprawdzenie, czy dany obiekt (kombinatoryczny) posiada, pewną ustaloną własność.
Tym niemniej nie jesteśmy całkowicie bezradni. Okazuje się, że w wielu przypadkach, odczytując jedynie niewielki fragment danych opisujących obiekt, możemy z dużym prawdopodobieństwem rozróżnić obiekty posiadające zadaną własność od tych, które należałoby znacznie zmodyfikować, aby tę własność posiadły. Takie podejście nazywa się zwyczajowo "testowaniem własności" (ang. property testing).
Skupię się na przykładach związanych z testowaniem wymiarowości danych, ale nie zapomnę o hołubionych na Uniwersytecie Warszawskim grafach i zaprezentuję przykładowe, bardzo ogólne twierdzenia dotyczące testowania własności grafowych.
Testowanie własności znajduje zastosowania w obszarach takich jak algorytmy aproksymacyjne, teoria kodów, uczenie maszynowe.
Przy okazji opowiem również, jak wygląda, z krótkiej półrocznej perspektywy czasu, studiowanie na MIT, czym tam się ludzie zajmują, a także z przyjemnością odpowiem na wszelkie inne pytania.

12.01.2006 Dorota Cendrowska

W ramach seminarium zostaną poruszone kwestie dotyczące odpowiedzi na następujące pytania: Jak ludzie radzą sobie z problemem automatycznego rozdzielania liniowego dwóch zbiorów? Trop 1: Może "liniowo" to synonim "zbyt łatwo: i sprawdza się reguła garbage rule garbage out jako parafraza reguły garbage in garbage out? Trop 2: Co to w ogóle znaczy "rozdzielać zbiory liniowo"? Trop 3: Czego potrzebowalibyśmy do szczęścia, aby jednak algorytm rozdzielania liniowo dwóch zbiorów móc nazwać "użytecznym"? Czy matematyka może być lekarstwem na całe to zło? Algorytm badania liniowej rozdzielności a konstrukcja klasyfikatora -- dwa podejścia. Czy z tego wszystkiego jest jakiś morał?

19.01.2006 Paulina Kania

Postaram się krótko omówić co to są algorytmy rozproszone i w jakich sytuacjach się je spotyka. Model z przesyłaniem komunikatów. Krótki przegląd podstawowych algorytmów rozproszonych: broadcast, gossip, consensus, wybór lidera. Rodzaje błędów w systemach rozproszonych. Analiza algorytmu consensusu w modelu synchronicznym oraz broadcastu w modelu asynchronicznym.

26.01.2006 Anna Wojak

Wyznaczanie Euklidesowej najkrótszej ścieżki jest jednym z najstarszych i dobrze znanych problemów w geometrii obliczeniowej. Obecnie istnieje wiele typów problemów związanych z wyznaczaniem najkrótszych dróg. Rozważmy płaszczyznę zawierająca zbiór rozłącznych przeszkód, których liczba wierzchołków wynosi n oraz dany punkt źródła s. Problemem jest wyznaczenie najkrótszej drogi z punktu s do wszystkich punktów wolnej przestrzeni. Znane są dwie główne metody wyznaczania najkrótszych ścieżek: visibility graph (VG) oraz shortest path map (SPM) połączone z algorytmami Dijkstra oraz A*. Shortest path map polega na specjalnym podziale płaszczyzny na obszary ukorzenione w wierzchołkach przeszkód. Obszary te są wyznaczane za pomocą rozchodzenia się czoła fali frontowej z punktu źródła s na całą płaszczyznę pośród wielokątnych przeszkód. Na początku lat dziewięćdziesiątych J.S.B. Mitchell pokazał, że wyznaczenie SPM wymaga O(n^{3/2} + \epsilon) dla \epsilon > 0. Następnie Jonh Hersberger oraz Subhash Suri zaproponowali optymalny algorytm dla SPM działający w najgorszym przypadku w czasie O(nlogn) i wymagający O(nlogn) pamięci. Kluczowym pomysłem ich algorytmu jest specjalny podział płaszczyzny zwany conforming subdividion, który może być wyznaczony w czasie O(n+nlogn).

6. 04.2006, Wojciech Dudek,

13.04. 2006, Krzysztzof Jachimiuk

Dynamiczny algorytm dla problemu wyszukiwania wszsytkich par najkrotszych sciezek w grafie skierowanym

20.04,2006, Anna Urbanska,

Ostatnio aktualizowane 05.IV.2006