Plan seminariów w roku akademickim 2007/2008

Semestr letni

2008.02.21 Bartłomiej Romański
Transformata Burrowsa-Wheelera

Referat dotyczył transformaty tekstów użytecznej m.in. przy kompresji danych (jest ona podstawą algorytmu bzip2). Zobacz także w Wikipedii.

2008.02.28 Mateusz Wykurz
Color Coding

2008.03.06, 03.13 Jakub Radoszewski
Jak grać w Hackenbusha

Prezentacja składa się z dwóch części. W pierwszej przypomnę zasadniczą teorię dotyczącą "impartial games" (twierdzenie Sprague-Grundy'ego) i zastosuję ją do opracowania algorytmu ustalającego zwycięzcę w grze Green Hackenbush. To będzie zasadnicza część referatu: w niej zamierzam dokładnie uzasadnić wszystkie reguły rządzące omawianą grą. W drugiej skupimy się na "partizan games". Opowiem o specyfice gry Red-Blue Hackenbush i jej związkach z liczbami "nierzeczywistymi". Na koniec wspomnę kilka słów na temat gry Green-Red-Blue Hackenbush, będącej połączeniem dwóch poprzednich.
Przeczytaj też o grze Hackenbush w Wikipedii.

2008.03.20 Marcin Pilipczuk
Nowe wyniki związane z ciągiem EKG i problemem Bandwidth

W tym roku zajmowałem się po trochu wieloma rzeczami, ale w dwóch udało się posunąć trochę do przodu. Chciałem pokrótce opowiedzieć o tych wynikach.

Wraz z Piotrkiem Hofmanem zajmowaliśmy się ciągiem EKG, o którym opowiadałem na jesieni. Udowodniliśmy podstawową (i najciekawszą) część hipotez związanych z tym ciągiem. Mianowicie udowodniliśmy zachowanie asymptotyczne ciągu oraz fakt, że każda liczba pierwsza p występuje w sekwencji 2p, p, 3p.

Wraz z Markiem Cyganem, w pociągu z Moskwy do Petrozavodska, wymyśliliśmy nowy algorytm rozwiązujący dokładnie problem Bandwidth, a dokładniej odpowiadający na pytanie, czy bandwidth grafu jest niemniejszy niż b. Działa on w czasie O*(6^n) dla dowolnych grafów. Składa się ze znanej już fazy podziału na kubełki na 3^n sposobów, a następnie z sprytnego programowania dynamicznego. Ten algorytm, z pewną modyfikacją, działa lepiej dla pytań o duży bandwidth: dla b >= n/2 da się osiągnąć O*(2^{3/2n}), zaś dla n/2 > b >= n/3 da się osiągnąć O*(4^n).

2008.03.27 Szymon Bargłowski
Kolorowanie krawędziowe grafów kubicznych

Twierdzenie Vizinga mówi, że każdy graf o maksymalnym stopniu wierzchołków D można pokolorować krawędziowo D+1 kolorami. Tematem referatu będzie algorytm który znajduje takie kolorowanie w czasie liniowym dla grafów (sub)kubicznych (stopnia co najwyżej 3).

2008.04.03 Wszyscy
Dyskusja nad zadaniami III etapu OI

2008.04.17 Marek Cygan
Aproksymacja w czasie wykładniczym przez redukcję rozmiaru danych

2008.04.24 Bartek Romański
Transformata Burrowsa-Wheelera, kontynuacja.

Kompresja tekstów za pomocą BWT -- algorytm bzip2; O BWT na słowach Sturma.

2008.05.08 Piotr Jędrzejewski
Przyspieszanie programowania dynamicznego: algorytm SMAWK

2008.05.15 Adam Iwanicki
Zastosowanie wartości własnych macierzy w wyszukiwarkach internetowych -- algorytmy HITS, PageRank, SALSA.

Prezentacja: [PDF]
Źródło: Meyer, Langville "A Survey of Eigenvector Methods of Web Information Retrieval" [PDF]

2008.05.29 Marcin Michalski
Skojarzenia w grafach kubicznych

2008.06.05 Bogdan Yakovenko
Ciekawy problem związany z routerami w sieci

Routery chcą obliczać statystyki na temat przesyłanych pakietów, ale pakietów jest mnóstwo, a one mają mało pamięci. Co robić???
Źródło: Praca Demaine, Lopez-Ortiz, Munro [PDF]

Semestr zimowy

2007.10.04 Omówienie propozycji referatów

2007.10.11 Szymon Acedański, Marek Cygan, Adam Iwanicki
Algorytmika w google.

Streszczenie: Wszystkie publiczne prace naukowe google'a mozna znalezc tutaj , a my opowiadalismy dwie z nich:

2007.10.18 Marcin Pilipczuk
Ciąg EKG

Streszczenie: Ciąg a_n EKG liczb całkowitych dodatnich definiujemy następująco: a_1 = 1, a_2 = 2, a_{n+1} = minimalna liczba całkowita dodatnia nie występująca jeszcze w ciągu, która ma wspólny dzielnik większy od zera z a_n. Początkowymi wyrazami ciągu są 1, 2, 4, 6, 3, 9, 12, 8, ....

Eksperymentalnie sprawdzono, że a_n jest "bardzo blisko" n za wyjątkiem momentów, gdy a_n=p, p pierwsze. Wówczas a_{n-1} = 2p i a_n = 3p, i n jest bliskie 2p. To jednak wciąż jest numeryczna hipoteza. Pokażę kilka oszacowań i podstawowych faktów dla tego ciągu. Są one jednak bardzo dalekie od tego, co można zobaczyć eksperymentalnie.

Sam problem można traktować jako taką "kombinatoryczną zagadkę", do pogłówkowania w przerwie między większymi problemami :-)

2007.10.25 Jakub Radoszewski
Wyznaczanie statystyk pozycyjnych w ciagu Fareya rzedu n w zlozonosci czasowej O(n^{2/3}*polylog(n)) za pomoca modyfikacji Patrascu algorytmu Pawlewicza.

2007.11.08 Tomasz Zdunowski
Minimalne drzewa rozpinające

2007.11.15 Szymon Bargłowski
Drzewa Steinera

2007.11.22 Dyskusja o zadaniach I etapu OI

2007.11.29 Piotr Jędrzejewski
Przyspieszanie programowania dynamicznego

2007.12.06 Piotr Truszkowski
Problem Bandwidth

2007.12.13 Marek Cygan
Uogolniona zasada wlaczen i wylaczen w zastosowaniach do algorytmow wykladniczych

Streszczenie: Na seminarium opowiem o tym, jak wykorzystać zasadę włączeń i wyłączeń do sprawdzania, czy w grafie istnieje ścieżka Hamiltona w czasie O*(2^n) i w wielomianowej pamięci. Następnie przedstawię algorytm który sprawdza czy graf jest k-kolorowalny w czasie O(2^n), po czym opiszę jego usprawnienie wykorzystujące wzory inwersyjne dla zbiorów częściowo uporządkowanych, dzięki któremy dla grafów rzadkich uzyskamy wynik o(2^n).
Źródło: Andreas Bjorklund, Thore Husfeldt, Petteri Kaski And Mikko Koivisto "Trimmed Moebius Inversion And Graphs Of Bounded Degree", STACS 2008.

2007.12.20 Szymon Acedański
Controlled Perturbation

Streszczenie: Większość algorytmów geometrycznych wymaga "niezdegenrowanych danych" (np. brak 3 punktów współliniowych etc) i nieskończonej precyzji obliczeń. Controlled perturbation to generyczna randomizowana metoda "radzenia" sobie z tymi ograniczeniami: punkty z wejścia są lekko przesuwane w losowych kierunkach. Dowodzi się, że z dużym prawdopodobieństwem (np. 1/2) dany algorytm zadziała dla tak zmodyfikowanych danych. Jeśli nie zadziała -- losujemy od nowa.

2007.01.03 Łukasz Kowalik
O dwóch algorytmach z randomizacją

Streszczenie: Algorytmy wykorzystujące losowanie są często bardzo proste i praktyczne. W wielu przypadkach można także udowodnić ograniczenia na ich czas oczekiwany, choć metody szacowania tego czasu nie są jeszcze zupełnie powszechnie znane i stosowane.
Zacznę o prostego i znanego algorytmu na znajdowanie k-tej co do wielkości liczby w tablicy: algorytmu Hoare'a. Pokażę standardową analizę prowadzącą do równania rekurencyjnego. Jest ona prosta ale nie oddaje intuicji stojącej za tym algorytmem. Pokażę także prostą analizę opartą na liniowości wartości oczekiwanej, a naśladującą rozumowanie intuicyjne. W drugiej części opowiem o haszowaniu kukułkowym: realizacji słownika umożliwającego wyszukiwanie w _pesymistycznym_ czasie stałym i wstawianie w _oczekiwanym_ czasie stałym.

2007.01.10 Mateusz Wykurz
Wyszukiwanie w grafie planarnym dowolnego podgrafu

2007.01.17 Piotr Cerobski
Kontrukcja spanerów w oczekiwanym czasie liniowym

2007.01.24 Bartłomiej Romański
Burrows-Wheeler transform