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