Seminarium Algorytmika 2005/2006
czwartki, godz. 10:15, sala 5870, wydz. MIM UW, Banacha 2, Warszawa
Prowadzący: Krzysztof Diks, Wojciech Rytter, Piotr Sankowski
Uczestnicy: Adamaszek Michał, Borny Michał, Dębiak Przemysław, Dulęba Krzysztof, Greszta Mateusz, Jędrzejewski Piotr, Kałuża Rafał, Karwańska Danuta, Kępka Paweł, Kindziuk Arkadiusz, Kruszona-Zawadzka Agata, Lipiński Konrad, Malesiński Tomasz, Mysiorska Marianna, Niewiarowska Anna, Regulski Marcin, Stańczyk Piotr, Zimnoch Katarzyna, Żylak Marek
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.
Proszę przysyłać rezerwacje terminów i opisy wystąpień na adres chogata@91.pl.
Plan spotkań seminaryjnych
| Kiedy | Kto i o czym | Wprowadzenie | Bibliografia |
|---|---|---|---|
| 13.10.2005 | Agata Kruszona-Zawadzka "Sortowanie i wyszukiwanie w obecności błędów pamięci" |
Ogólne uwagi na temat algorytmów działającyh w pamięci z błędami. Algorytm sortowania w pamięcie z błędami - naiwny i optymalny. Algorytm wyszukiwania binarnego w pamięci z błędami - naiwny i optymalny. |
Irene Finocchi, Giuseppe F. Italiano "Sorting and Searching in the Presence of Memory Faults (without Redundancy)" |
| 20.10.2005 | Piotr Stańczyk "Exact algorithms for NP-hard problems" |
Przegląd różnych wykładniczych algorytmów rozwiązujących problemy NP-trudne. Analiza problemów komiwojażera, spełnialności formuł, problem plecakowy, zbiór niezależnych wierzchołków, porządkowania zadań z zależnościami, minimalna rozpiętość krawędzi w grafie... | Gerhard J. Woeginger "Exact algorithms for NP-hard problems. A survey." |
| 27.10.2005 03.11.2005 |
Marek Żylak "3-kolorowanie w czasie O(1.3289n)" |
Ogólne uwagi na temat problemów NP-zupełnych. Wprowadzenie problemów typu (a,b)-CSP i algorytmów ich rozwiązywania. Najlepsze algorytmy wykładnicze dla 3-kolorowania, 3-kolorowania listowego, 3-kolorowania krawędzi i 3-spełnialności. | Richard Beigel, David Eppstein
"3-Coloring in Time O(1.3289n)" Michel Vasquez "New Results on the Queens_n2 Graphs Coloring Problem" |
| 10.11.2005 | Tomasz Malesiński "Samoorganizujące się struktury danych" |
Samoorganizujące się struktury danych to takie, które po każdej operacji mogą zmieniać swój stan według pewnej reguły. Reguła ta jest tak dobrana, by struktura danych mogła się dostosowywać do specyficznych własności ciągu operacji. Przedstawię różne kryteria ich konkurencyjności i związanej z tym optymalności. Opowiem również o poszukiwaniach dynamicznie optymalnego drzewa BST. | S. Albers, J. Westbrook.
A Survey of Self-Organizing Data Structures. E. Demaine, D. Harmon, J. Iacono, M.Patrascu. Dynamic Optimality - Almost D. Sleator, C. Wang. Dynamic Optimality and Multi-Splay Trees. |
| 17.11.2005 | Piotr Jędrzejewski "Shortest Superstrings" |
Shortest Superstring - problem polegający na znalezieniu najkrótszego nadsłowa, czyli znalezienu dla danego zbioru słów s1,...,sN takiego najkrótszego słowa s, że każde ze słów zbioru występuje jako spójne podsłowo s. Sam problem jest NP-trudny, ale istnieją algorytmy, które go liniowo aproksymują. Na zajęciach został pokazany algorytm zachłanny, który aproksymuje rozwiązanie z dokładnością do 3n (zakładając, że n jest długością najkrótszego szukanego słowa). Zostało też krótko omówione podejście genetyczne do problemu najkrótszego nadsłowa. | A.Blum, T.Jiang, M.Li, J.Tromp, M.Yannakakis
Linear Approximation of Shortest Superstring Z.Sweedyk A 2,5-APPROXIMATION ALGORITHM FORSHORTEST SUPERSTRING B.Gurion Coevolving Solutions to the Shortest Common Superstring Problem |
| 24.11.2005 | Paweł Kępka | ||
| 01.12.2005 | Anna Niewiarowska | ||
| 08.12.2005 | Marcin Regulski "Informatyka - nauka teoretyczna czy eksperymentalna?" |
||
| 15.12.2005 | Krzysztof Dulęba "Wyrocznie przybliżonych odległości" |
Jak efektywnie czasowo i pamięciowo przetwarzać duże grafy, by można było w czasie stałym zwracać przybliżone odległości między wierzchołkami. | prezentacja |
| 05.01.2005 | Przemysław Dębiak | ||
| 12.01.2006 | Danuta Karawańska "Ekspandery" |
Ekspandery pozwoliły na uzyskanie kilku istotnych wyników z różnych dziedzin informatyki. Zdefiniuje podstawowe pojęcia ich dotyczące i opowiem jak wykorzystać te grafy przy dowodzie trudności aproksymacji kliki. | Lecture 1: http://www.math.ias.edu/~boaz/ExpanderCourse/ "Algorytmy aproksymacyjne" V.V.Vazirani (29.6) |
| 19.01.2006 | Katarzyna Zimnoch "Color-coding" |
Opowiem o randomizacyjnej metodzie, wykorzystującej kodowanie przy pomocy kolorowania, do znajdowania prostych ścieżek i cykli ustalonej długości k, dla danego grafu G=(V, E). Algorytmy randomizacyjne otrzymane przy zastosowaniu tej metody mogą byc zderandomizowane przy pomocy funkcji haszujących. | N. Alon, R. Yuster, U. Zwick. Color-coding |
| 26.01.2006 | Marianna Mysiorska | ||
| 23.02.2006 | Piotr Stańczyk "Temat - Graph Minor Theorem" |
prezentacja | |
| 02.03.2006 | Konrad Wawruch | ||
| 09.03.2006 | Arkadiusz Kindziuk | ||
| 16.03.2006 | Michał Adamaszek "Generowanie obiektów kombinatorycznych" |
Tematem referatu jest generowanie obiektów kombinatorycznych. Skupię się głównie na algorytmie generującym wszystkie drzewa o zadanej liczbie wierzchołków w czasie proporcjonalnym do liczby tych drzew (czyli średnio w czasie stałym na jedno drzewo) i w małej pamięci. | Li, Ruskey, The advantages of forward thinking in generating rooted and free trees |
| 23.03.2006 | Tomasz Malesiński "Własności drzew splay" |
Tematem wystąpienia są własności drzew splay mówiące o tym, jak potrafią się one dostosowywać do charakterystycznych cech ciągów zapytań, jak również intuicje, które pozwalają zrozumieć dlaczego prosty algorytm wykonywania operacji splay daje tak dobre efekty. | D. Sleator, R. Tarjan
Self-Adjusting Binary Search Trees G. Georgakopoulos, D. McClurkin General Splay: A Basic Theory and Calculus R. Cole On the Dynamic Finger Conjecture link 1 link 2 J. Derryberry, D. Sleator, C. Wang A Lower Bound Framework for Binary Search Trees with Rotations |
| 30.03.2006 | Michał Borny "Biased Skip List" |
Przedstawiona zostanie słownikowa struktura danych oparta na listach, zapewniajaca optymalny czas wykonania ciągu dostępów przy zdefiniowanej częstotliwości dostępu do każdego elementu - Biased Skip List. Jak wykonać operację utrzymujące słownik, czy randomizacja może coś ułatwić? | materiał (ps) |
| 06.04.2006 | Marcin Regulski "Inkrementalne algorytmy randomizacyjne w geometrii obliczeniowej." |
Przedstawię inkrementalny algorytm randomizacyjny do budowania mapy trapezoidalnej w celu rozwiązania problemu lokalizacji punktów na płaszczyźnie, oraz inkrementalny algorytm randomizacyjny do wyznaczania triangulacji Delaunay. Przedstawię też metodę szacowania złożoności czasowej i pamięciowej działania tych (i podobnych) algorytmów przy pomocy tzw. przestrzeni konfiguracyjnej. | Mark de Berg, Otfried Schwarzkopf, Marc van Kreveld, Mark Overmars Computational Geometry: Algorithms and Applications |
| 20.04.2006 | Piotr Jędrzejewski | ||
| 27.04.2006 | Krzysztof Dulęba | ||
| 04.05.2006 | Anna Niewiarowska | ||
| 11.05.2006 | Danuta Karwańska | ||
| 18.05.2006 | Katarzyna Zimnoch | ||
| 25.05.2006 | Marianna Mysiorska | ||
| 01.06.2006 | Paweł Kępka | ||
| 08.06.2006 | Agata Kruszona-Zawadzka |