Seminarium Algorytmika 2004/2005

czwartki, godz. 10:15, sala 5870, wydz. MIM UW, Banacha 2, Warszawa

Prowadzący: Krzysztof Diks, Wojciech Rytter

Uczestnicy: Michał Adamaszek, Grzegorz Andruszkiewicz, Paweł Benben, Artur Bil, Tomasz Czajka, Piotr Jędrzejewski, Rafał Kałuża, Paweł Kępka, Agata Kruszona-Zawadzka, Jakub Kruszona-Zawadzki, Łukasz Lew, Tomasz Malesiński, Piotr Miłoś, Anna Niewiarowska, Krzysztof Onak, Rafał Rusin, Konrad Wawruch

Tematem seminarium są algorytmy dla problemów dyskretnych.
Omawiamy metody układania takich algorytmów i analizowania ich złożoności obliczeniowej. Przedmiotem naszych zainteresowań są zarównono algorytmy sekwencyjne, jak i algorytmy równoległe, rozproszone, randomizowane oraz aproksymacyjne. Wiele miejsca poświęcamy także strukturom danych.
Na seminarium studenci referują prace z czasopism i sprawozdań z konferencji poświęconych tej dziedzinie informatyki.
Prace magisterskie mogą mieć charakter przeglądowy, jak i studialno-eksperymentalny.

Propozycje tematów referatów


Plan spotkań seminaryjnych

Kiedy Kto i o czym Wprowadzenie Bibliografia
14.10.2004 Piotr Miłoś
Kolorowanie grafów
Kolorowanie wierzchołkowe grafów jest problemem NP-zupełnym (pomijajac przypadek grafów dwudzielnych). Skłania to do szukania algorytów aproksymacyjnych. W przypadku grafów o znanej liczbie chromatycznej punktem wyjścia do dalszych poszukiwań jest algorytm Wigdersona dający w przypadku grafów 3-kolorowalnych kolorowanie o rozmiarze \sqrt(N). Bardziej ogólne podejście przedstawił w swojej pracy Blum, jednocześnie przedstawiając algorytm dający kolorowanie o rozmiarze n^(3/8). Avi Wigderson - A new approximate graph coloring algorithm
Avrim Blum - New approximation algorithms for graph coloring
21.10.2004 Rafał Rusin
(δ,γ) - string matching
Przedstawiłem przegląd algorytmów obliczających δ i γ string matching. δ-matching jest to rodzaj string matchingu, w którym wystąpienie ma miejsce, gdy kolejne litery wzorca i tekstu są odległe nie więcej niż o δ. W γ-matchingu suma odległości nie może przekroczyć γ. W praktyce najlepiej radzą sobie z tymi problemami algorytmy heurystyczne, ktore przedstawiłem. Camboropoulos, Crochemore, Iliopoulos, Mouchard, Pinzon, Algorithms for Computing Approximate Repetitions in Musical Sequences.
28.10.2004 Agata Kruszona-Zawadzka
Kwadraty w słowach a maksymalne powtórzenia
Dotychczas znane algorytmy, działające w czasie O(n log n) i pamięci O(1) potrafiły wykonać test na obecność kwadratu w słowie, do znalezienia maksymalnego powtórzenia nie wystarczała pamięć O(1). W roku 2003 przedstawiono dowód istnienia algorytmu, który znajduje wszystkie maksymalne powtórzenia w słowie w czasie O(n log n) i pamięci O(1). M. Crochemore & W. Rytter: Efficient Algorithms on Texts - rozdział 8
Space Efficient Search for Maximal Repetitions
4.11.2004 Arkadiusz Kindziuk
Równania na słowach
   
18.11.2004 Arkadiusz Kindziuk
Równania na słowach - część 2
   
25.11.2004 Michał Adamaszek
AKS i okolice
AKS jest wielomianowym algorytmem weryfikacji pierwszości z roku 2002. Opowiem o tym jak ten problem był na różne sposoby atakowany wcześniej i jakie ciekawe problemy matematyczno-algorytmiczne się z nim wiążą. Zobaczymy jaka droga prowadziła do odkrycia AKS, jak ten algorytm działa, dlaczego jest poprawny i jaką ma złożoność. Przedstawię związane z nim hipotezy.
  1. Agrawal, Kayal, Saxena, Primes is in P - praca z algorytmem AKS
  2. Smid, Primality testing in polynomial time - bardzo dobry, nietrudny artykuł z dowodem twierdzenia AKS, dokładną analizą i omówieniem wszystkich potrzebnych wiadomości z algebry
  3. Boremann, Primes is in P: A breakthroung for everyman, Notices of the AMS, Maj 2003 - bardzo fajny artykuł popularnonaukowo-historyczny o pracy nad algorytmem AKS, jego znaczeniu i reakcjach na niego
  4. Praca magisterska Marcina Stefaniaka
9.12.2004 Grzegorz Andruszkiewicz
Wprowadzenie do Teorii Gier
Przedstawię podstawowe definicje teorii gier, udowodnię mini-maxowe twierdzenie von Neumana przez sprowadzenie do programowania liniowego, pokażę różne formy zapisu gier i nawiążę do "popularnych" gier jak szachy.  
16.12.2004 Krzysztof Onak
Twierdzenie PCP
Twierdzenie PCP, jedno z największych osiągnięć w historii informatyki, daje nam definicję klasy NP konkurencyjną do definicji za pomocą klasycznej maszyny Turinga. Zobaczymy, jak za jego pomocą dowodzi się NP-trudność aproksymacji. S. Arora, Probabilistic Checking of Proofs and Hardness of Approximation Problems, 1994, praca doktorska
6.01.2005 Anna Urbańska    
13.01.2005 Piotr Jędrzejewski    
20.01.2005 Rafał Kałuża    
17.02.2005 Konrad Wawruch
Praktyczna implementacja algorytmów równoległych i problemy synchronizacji
Współczesne mechanizmy komunikacji między procesami obliczeniowymi w klastrach i superkomputerach bazują na dosyć naiwnych modelach komunikacji równoległej. Naiwność ta zaczyna dawać sobie we znaki ze względu na rosnącą liczbę jednocześnie wykorzystywanych procesorów przy heterogeniczności sieci jej łączącej, zazwyczaj dosyć wolnej, szczególnie w przypadku operacji grupowych. Tematem wystąpnienia będzie zaprezentowanie teoretycznych i praktycznych aspektów przetwarzania równoległego, oraz omówienie sposobów na polepszenie wydajności kolektywnej komunikacji poprzez oparcie się na zaawansowanych modelach komunikacji w systemach równoległych. slajdy (pdf)
24.02.2005 Tomasz Malesiński
Dynamiczna optymalność drzew BST
Rozważmy drzewa BST z nie zmieniającym się w czasie zbiorem kluczy. Dla każdego ciągu zapytań można wyobrazić algorytm, który wykonuje go w najlepszym czasie. Zadanie polega na znalezieniu jednej struktury BST, która wykonuje kolejno zapytania, nie znając przyszłych, w czasie możliwie bliskim optymalnemu dla tego ciągu zapytań. Na seminarium przedstawię drzewo BST, które wykonuje każdy ciąg zapytań w czasie gorszym o czynnik O(log log n) od optymalnego. Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu, Dynamic Optimality - Almost
D. Sleator, C. Wang "Dynamic Optimality and Multi-Splay Trees"
3.03.2005 Anna Niewiarowska
Trudność aproksymacji problemów NP-zupełnych
Przedstawię zagadnienia aproksymacji problemów NP-zupełnych. Okazuje się, że dla wielu problemów NP-zupełnych obliczanie dobrych rozwiązan przybliżonych jest również NP-zupełne. Omówię standardowe techniki dowodzenia nieaproksymowalności problemów: redukcje wprowadzające lukę i redukcje zachowujące lukę. Pokażę kilka przykładowych problemów, o których wiadomo, że nie można ich dobrze aproksymować. Oczywiście wszystko przy zalożeniu, że P!=NP. Vijay V. Vazirani 'Algorytmy aproksymacyjne'
Sanjeev Arora, Carsten Lund 'Hardness of Approximations'
10.03.2005 Anna Urbańska    
17.03.2005 Krzysztof Onak, Paweł Parys
Wyszukiwanie w grafach

Cel: Znaleźć wierzchołek w grafie.

Dostępne środki: Pytania o to, w którą stronę wychodzi najkrótsza ścieżka z danego wierzchołka do szukanego celu.

Zaprezentujemy metody, które pozwalają minimalizować liczbę pytań i ilość dodatkowych obliczeń dla różnych rodzajów grafów. Jeśli wystarczy czasu, to pokażemy także jak wyszukiwać w optymalnej liczbie pytań w drzewiastych zbiorach częściowo uporządkowanych.

K. Onak, P. Parys "Extension of binary search: searching in graphs" (w przygotowaniu)
Y. Ben-Asher, E. Farchi, I. Newman "Optimal search in trees"
24.03.2005 Piotr Miłoś
O kolorowaniu raz jeszcze
Na referacie przedstawił em algortym Karger-Sudana-Motowaniego kolorowania wierzchołków grafu. Jest to algortym opierający się na geometrycznych własnościach włożeń grafów w przestrzeń euklidesową. Algortym ten działa dobrze w grafach rzadkich. Approximate Graph Coloring by Semidefinite Programming
31.03.2005 Rafał Rusin
Subset matching
Przedstawiłem zarys algorytmu obliczającego subset matching, o pesymistycznej złożoności O(n log3n). Dzięki niemu można rozwiązywać problem znajdowania poddrzewa w drzewie w takim czasie. Bliski związek z tym algorytmem ma algorytm rozwiązujący problem δ-matchingu w czasie O((δ + logσ) n log n). Jest to najlepszy znany algorytm dla tego problemu, dla niewielkich wartości δ. Richard Cole, Ramesh Hariharan, Piotr Indyk, Tree Pattern Matching and Subset Matching in Deterministic O(n log3n) time
07.04.2005 Rafał Rusin
Subset matching - część 2
kontynuacja z poprzedniego tygodnia  
14.04.2005 Jakub Kruszona-Zawadzki
Wydajne algorytmy znajdowania wielu wzorców w tekście
Omówienie dwóch efektywnych algorytmów znajdowania wielu wzorców w tekście, a także praktycznych aspektów implementacji, znacznie zwiększających prędkość wyszukiwania. Alfred Aho, Margaret CorasickEfficient String Matching: An Aid to Bibliographic Search
Sun Wu, Udi ManberA Fast Algorithm For Multi-Pattern Searching
21.04.2005 Grzegorz Andruszkiewicz    
28.04.2005 Paweł Kępka    
05.05.2005 Michał Adamaszek
Graceful graphs
Tematem referatu będzie pewna mało znana własność kombinatoryczna etykietowań grafów liczbami całkowitymi. Kluczowym elementem tej teorii jest nieudowodniona wciąż hipoteza GTC. Opowiem o stanie wiedzy ludzkości na ten temat i pokażę kilka stosowanych w tej dziedzinie metod. Tematyka jest czysto kombinatoryczna, choć do komputerowej weryfikacji GTC potrzebne są np. szybkie algorytmy generowania drzew. Towards GTC - a survey
19.05.2005 Agata-Kruszona Zawadzka
Znajdowanie maksymalnych powtórzeń w słowie
Omówię dokładniej algorytm znajdywania wszystkich maksymalnych powtórzeń w słowach opisany w pracy "Space Efficient Search for Maximal Repetitions", a także wszelkie problemy jakie pojawiają się przy jego praktycznej implementacji (wielkość stałej). Leszek Gąsieniec, Roman Kolpakov, Igor Potapov Space Efficient Search for Maximal Repetitions