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.
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. |
|
| 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 |