Plan seminariów w roku akademickim 2006/2007

Semestr letni

2007.02.22 Ustalenie planu spotkań

2007.03.01 Jakub Radoszewski
Znajdowanie k-tego leksykograficznie sufiksu slowa długości n z użyciem O(n) porownań
Streszczenie: Autorzy pracy znalezli rozwiazanie problemu analogicznego do tego, czy wyszukiwanie statystyk pozycyjnych w ciagu liczbowym mozna wykonac efektywniej niz sortowanie. Na seminarium zaprezentuje algorytmy o zlozonosciach O(n^2) i O(nlog(n)) rozwiazujace ten problem, ktore wprowadzaja w idee glownego algorytmu, dalej pokaze szczegolne przypadki algorytmu liniowego i wreszcie szkic samego algorytmu, ktory sam niestety jest dosc techniczny.

2007.03.08 Jakub Radoszewski
Znajdowanie k-tego leksykograficznie sufiksu slowa długości n z użyciem O(n) porownań -- kontynuacja

2007.03.15 Adam Iwanicki
Problem skoczka szachowego i inne cykle Hamiltona na szachownicy n x n
Ludzie od wieków taktowali problem skoczka szachowego, jako łamigłówkę logiczną. Mimo, że w ogólności problem cyklu Hamiltona jest NP-zupełny, to jednak podobnie jak w przypadku innych problemów NP-zupełnych, udało nam się znaleźć pewne specyficzne klasy grafów dla których jesteśmy w stanie ten problem rozwiązać efektywnie. Jedną z takich klas są grafy skoczka szachowego, dla kwadratowej planszy n x n, dla n parzystego - wówczas istnieje elegancki algorytm liniowy (O(n^2)) oparty na metodzie dziel i zwyciężaj. Algorytm ten umożliwa nam także znajdowanie drog skoczka charakteryzujących się aspektami wizualnymi, takimi jak np. niezmienniczość na obroty.
Źrodło (inne są zawarte w prezentacji): [PDF].
Prezentacja: [PDF]

2007.03.22 Adam Iwanicki
Sortowanie bitoniczne w optymalnej pracy
Dzisiejsze procesory graficzne (GPU) są niejednokrotnie szybsze i bardzij skomplikowane, niż standardowe procesory (CPU). Problemem jest jednak dobre wykorzystanie drzemiącej w nich mocy obliczeniowej. Na drodze staje nam do tego znalezienie odpowiednich algorytmów równoległych - tych jednak znamy już bardzo wiele, głównym problemem jest jednak strumieniowy charakter przetwarzania danych. Na seminarium przedstawię algorytm sortowania, oparty na adaptacyjnym sortowaniu bitonicznym. Posiada on optymalną złożoność (w modelu porównaniowym) O((n * log n)/p) gdzie p jest liczba procesorów, co więcej pozwala on na strumieniowe przetwarzania danych.
Źrodło: [PDF].

2007.03.29 Seminarium odwołane (Olimpiada Informatyczna)

2007.04.05 Piotr Stańczyk
Implementacja algorytmów na kartach graficznych: kompilator CUDA

2007.04.12 Piotr Cerobski
Zastosowanie programowania liniowego do algorytmów aproksymacyjnych
Dla wielu problemów optymalizacyjnych nie są znane algorytmy znajdujące dokładne rozwiązanie w czasie wielomianowym. Natomiast czas wykładniczy zazwyczaj jest niedopuszczalny. Z tego powodu bada się algorytmy aproksymacyjne czyli takie które dają w wyniku przybliżone rozwiązanie postawionego problemu. Na seminarium opowiem o programowaniu liniowym i tym jak za jego pomocą konstruować algorytmy aproksymacyjne. Na przykładzie problemu pokrycia zbioru postaram się przedstawić dwie podstawowe techniki wykorzystujące programowanie liniowe: zaokrąglanie i schemat prymalno dualny.

2007.04.19 Marek Cygan
Minimum maximal matching (wyniki własne)
Problem ten jest NP-trudny, ponadto udowodniono, że nie da się go aproksymować ze stałą mniejszą niż 7/6, o ile P!=NP. Przedstawię algorytm znajdujący rozwiązanie optymalne w czasie O*(1.354^n) i wielomianowej pamięci. Schemat wywołań rekurencyjnych algorytmu stanowi wykładniczej wielkości drzewo poszukiwań. W liściach tego drzewa mamy do czynienia z problemem o większej liczbie założeń, niż oryginalny, dlatego też możemy go rozwiązać w czasie wielomianowym.

2007.04.26 Marek Żylak
Kolorowanie grafów 3-kolorowalnych

2007.05.10 Marianna Mysiorska
Hipoteza Hadwigera - kontynuacja

2007.05.17 Tomasz Zdunowski
Minimalne drzewo rozpinające w oczekiwanym czasie liniowym
Opowiem o algorytmie znajdowania minimalnego drzewa rozpinajacego w oczekiwanym czasie liniowym, autorstwa Karger, Klein, Tarjan. Algorytm jest rekurencyjny i niedeterministyczny. Wykorzystuje idee algorytmu Boruvki do znajdowania minimalnego drzewa rozpinajacego oraz algorytm King'a do weryfikacji.
Źrodło: David R. Karger, Philip N. Klein, and Robert E. Tarjan. A randomized linear-time algorithm to find minimum spanning trees. Journal of the ACM, 42(2): 321--328, 1995

2007.05.24 Prof. Artur Czumaj, University of Warwick (gościnnie)
Sublinear-time Algorithms

2007.05.31 Mateusz Wykurz
Efektywna reprezentacja grafów rzadkich
Na seminarium opowiem o strukturze danych do reprezentacji rodziny grafów rzadkich - grafów o ograniczonej lesistości (arboricity). Struktura ta pozwala sprawdzać czy dwa wierzchołki są sąsiednie w czasie O(C) i w czasie zamortyzowanym wykonywać operacje wstawiania O(1) i usuwania O(C + log(n)), gdzie C to współczynnik lesistości grafu, tzn minimalna liczba lasów, na jakie można rozłożyć krawędzie grafu.
Źrodło: Brodal, G.S. and Fagerberg, R., Dynamic representations of sparse graphs. In: Lecture Notes in Comput. Sci., vol. 1663. Springer, Berlin. pp. 342-351.

Semestr zimowy

2007.01.18 Janusz Parfieniuk
Szerokość drzewowa
Streszczenie: Dokładne rozwiązywanie problemów NP-trudnych, w ogólnym przypadku, wiąże się z użyciem algorytmów wykładniczych. Jeżeli jednak wiemy, że dane wejściowe mają określoną strukturę, wówczas rozwiązanie problemu może okazać się znacznie łatwiejsze. Na seminarium przedstawię kilka prostych przykładów pokazujących jak można wykorzystać informacje o pewnych własnościach danych wejściowych. Następnie zdefiniuję drzewo dekompozycji grafu i pokażę jak takie drzewo wykorzystać do rozwiązywania problemu zbioru niezależnego o maksymalnej wadze. Na koniec przedstawię algorytm konstrukcji dekompozycji drzewowej dla grafów, dla których wiemy, że ich szerokoœć drzewowa jest mniejsza niż stała w.
Slajdy: [PDF]

2007.01.11 Marcin Michalski
Algorytmy certyfikujace

2007.01.04 Piotr Stańczyk
General-Purpose Computation Using Graphics Hardware
Streszczenie: Architektura komputerów w ostatnich latach osiaga fizyczne granice prędkości. Nie jest już możliwe zwiększanie wydajności poprzez zwiększanie częstotliwości procesorów. Nowym kierunkiem jest stosowanie obliczeń równoległych (chociażby poprzez wprowadzanie takich technologii jak Hyper Threading czy Core Duo). Coraz większe możliwości udostępniajś nam również karty graficzne - one właśnie będą temat referatu. Podczas seminarium postaram się przybliżyć możliwości dzisiejszych kart graficznych oraz przedstawię sposoby realizacji różnych algorytmów (problem wyznaczania diagramów Voronoi, symulacja sieci neuronowych, teselacja krzywych w systemach graficznych...) z wykorzystaniem karty graficznej.

2006.12.21 Katarzyna Zimnoch
Testowanie izomorfizmu grafów

2006.12.14 Jakub Radoszewski
Efektywna najlepsza aproksymacja ciągów ciągami monotonicznymi

Streszczenie: Dla danego skończonego ciągu rzeczywistego (całkowitego) będziemy poszukiwali efektywnych algorytmów najlepszej aproksymacji tego ciągu równolicznym ciągiem monotonicznym. Jakość aproksymacji definiujemy jako wartość pewnej popularnej normy (pierwszej, drugiej lub normy nieskończoność) na wektorze zdefiniowanym współrzędnymi będącymi różnicami odpowiadających sobie elementów ciągów: przybliżanego i przybliżającego. Na seminarium przedstawię liniowe algorytmy najlepszej aproksymacji ciągu w normach drugiej i nieskończoność oraz liniowo-logarytmiczny algorytm w normie pierwszej. Zaprezentuję też kilka wolniejszych ale pouczających algorytmów rozwiązujących opisane zagadnienie w tych trzech normach.

2006.12.07 Marianna Mysiorska
Liczba chromatyczna tensorowego produktu grafow
Streszczenie: What is the chromatic number of the product of two graphs? The conjecture of Hedetniemi (Hedetniemi, University of Michigan, 1966), which is more than 30 years old, is X(G x H) = min{X(G), X(H)}. Na prezentacji pokaze dowody dla produktu grafow, z ktorych przynajmniej jeden ma liczbe chromatyczna co najwyzej 3

2006.11.30 Marek Żylak
Szkic algorytmu wielomianowego na testowanie pierwszości

2006.11.23 Tomek Zdunowski
Dynamiczne kodowanie Huffmana.
Streszczenie: Przypomne dwu-fazowy algorytm kodowania Huffmana ktory jest optymalny dla danego ciagu wejsciowego, czyli najbardziej zblizony do entropii tego ciagu. Celem referatu jest przedstawie algorytmu dynamicznego kodowania Huffmana, ktory jest algorytmem on-line, opracowanym przez Knutha. Omowie rowniez algorytm Vittera, ktory generuje kod prawie dwa razy krotszy niz algorytm zaproponowany przez Knutha. Przedstawie jeszcze problemy otwarte poruszone w pracy Vittera. Literatura: D. E. Knuth, Dynamic Huffman Coding, Journal of Algorithms, 6:163-180, 1985. J. S. Vitter, Design and Analysis of Dynamic Huffman Codes, Journal of ACM, 34(4):825-845, 1987

2006.11.16 Adam Iwanicki
Algorytmy dokladne dla problemu komiwojazera

2006.11.09: Mateusz Wykurz
Problem stabilnych małżeństw: wersja klasyczna i aproksymowanie wersji NP-trudnej

2006.11.02: Danuta Karwańska
Ekspandery

2006.10.19: Marcin Pilipczuk
Algorytmy wyszukiwania wzorca w tekście wykonujące niewiele porównań liter.

2006.10.26: Marek Cygan
Perełki algorytmów wykładniczych