Propozycje tematów referatów
Algorytmy tekstowe i nie tylko: propozycje prof. Ryttera
- Analiza algorytmu Frama-Stewarta dla k wiez Hanoi.
- ALgorytm na uogolniona gre "pietnastka" - relokacja na grafie
- Gry kombinatoryczne - uogolnienie gry Wythoffa.
- Ciekawe generacje obiektow kombinatorycznych (typu permutacje, kombinacje).
- Uogolnione drzewa Huffmana (lopsided terees, drzewa koslawe), problem o ktorym nie wiadomo czy jest NP-zupelny ani czy jest w P.
- Algorytm Zimina sprawdzania unikalnosci wzorcow ze ze zmiennymi, ang. patternow.. (problem o ktorym nie wiadomo czy jest NP-zupelny ani czy jest w P).
- Analiza (glownie eksperymentalna) liczby kwadratow w slowach.
- Dwyuwymiarowy pattern-matching z mala pamiecia.
- Problem PCP(2) -deterministyczny algorytm wielomianowy.
- Problem slabego szablonu, ang. seeds, (trudna wersja zadania szablon z Olimp. Inf.).
- Automaty komorkowe - ciekawe algorytmy.
- Analiza zachlannego algorytmu dla najkrotszego nadslowa.
- Obliczanie liczby dominacji dla hetmanow i skoczkow na szachownicy.
- Obliczanie liczby cyklow Hamiltona skoczka na szachownicy torusowej i normalnej
- Ciagi de Bruijna - porownanie algorytmow generacji
- Skompresowane grafy podslow dla slow o strukturze regularnej
- Porownanie metod konstrukcji minimalnej gramatycznej kompresji.
- Eksperymentalna analiza algorytmu GREEDY na minimalne najkrotsze podslowo
- Eksperymentalna analiza liczby maksymalnych powtorzen i kwadratow w slowach.
Algorytmy grafowe i teoria grafów
-
Liczba doskonałych skojarzeń w fulerenach
Niedawno ukazał się dość prosty dowód otwartej przez wiele lat hipotezy,
że grafy fulerenów (cząsteczek chemicznych składających się z wielu atomów
węgla) mają wykładniczą liczbę doskonałych skojarzeń.
Fulereny to grafy planarne o bardzo mocnej strukturze.
Źródło:
[PDF]
(kontakt: Ł. Kowalik) -
Algebraiczny dowód tw. Brooksa
Tw. Brooksa mówi, że jeśli graf o maksymalnym stopniu D nie jest cyklem
nieparzystej długości ani kliką, to można ko pokolorować D kolorami.
Okazuje się, że jest to prawdą również w wersji listowej, tzn. gdy w każdym wierzchołku
mamy listę D dozwolonych kolorów (listy są niekoniecznie takie same) to
możemy znaleźć legalne kolorowanie grafu.
Praca zawiera nowy dowód tego faktu oparty o ciekawą technikę algebraiczną.
(kontakt: Ł. Kowalik) -
Divide and color modyfikacja znanej techniki color-coding,
służącej m.in. do znajdywania k-ścieżki w grafie.
(kontakt: Ł. Kowalik) -
Unique-sink orientations
zob. PDF tutaj
(kontakt: Ł. Kowalik)
Gry (kontakt: P. Sankowski)
- Cena stabilności w grach tworzenia sieci.
- Cena anarchii w grach opóźnień na sieci.
- Cena anarchii w równoległej aukcji drugiej ceny.
Algorytmy na ogromnych zbiorach danych
- External-memory algorithms. Gdy algorytm działa na ogromnych
danych i przechowuje je w pamięci, siłą rzeczy system operacyjny większość
tych danych umieszcza na dysku. Wtedy zdarza się, że większość czasu
działania algorytmu przypada na transfery bloków danych między szybką
pamięcią (,,cache'') a wolną pamięcią (dyskiem). Jak kontrolować to zjawisko
w sposób optymalny, zakładając, że znamy rozmiar transferowanych bloków i
dysponujemy np. możliwością wykonania transferu pojedynczego bloku?
Zobacz: notatki do wykładu E. Demaine'a z MIT [PDF], praca przeglądowa J. Vittera [PDF].
(kontakt: K. Diks / Ł. Kowalik) - Cache oblivious algorithms. Tak samo jak powyżej, ale nie znamy
rozmiaru bloków i nie mamy mozliwości kontrolowania transferów (albo nie
chcemy tego robić). Okazuje się, że w dalszym ciągu możemy kontrolować
zjawisko kosztownego transferu bloków w sposób optymalny lub niemal
oprymalny!
Zobacz: Wikipedia oraz notatki notatki do wykładu E. Demaine'a z MIT (punkt 3) [PDF]
(kontakt: K. Diks / Ł. Kowalik)
Wspomagane komputerowo badania hipotez (kontakt: M. Peczarski).
- Optymalne strategie dla wariantów gry mastermind.
- Wspomagany komputerowo dowód hipotezy o złotym podziale dla porządków k-cienkich (każdy element nieporównywalny z co najwyżej k innymi). Ulepszenie algorytmów. Rozszerzenie na przypadek k > 6. Więcej...
- Czy dla każdego ułamka p/q z przedziału [1/3, 1/2] istnieje porządek częściowy o współczynniku zbalansowania p/q? Definicja współczynnika zbalansowania Więcej...
- Ile porównań wystarcza do posortowania 16, 17, 18, 19 elementów? Więcej...
.
.
.
.
.
.
.
.
.
.
.
Tematy już wykorzystane
Ogólne techniki algorytmiczne
-
Skojarzenia i kolorowanie krawędziowe.
Przegląd bardzo eleganckich technik znajdowania i zliczania doskonałych skojarzeń w regularnych grafach dwudzielnych z zastosowaniami do kolorowania
krawędziowego.
Źródło: A. Schrijver, Matching, edge-colouring, dimers, in:
``Graph-Theoretic Concepts in Computer Science'' (H.L. Bodlaender, ed.),
Lecture Notes in Computer Science 2880, Springer-Verlag, Berlin, 2003, pp.
13--22, [PDF]
(kontakt: K. Diks) - Przyspieszanie programowania dynamicznego. Przy pewnych założeniach dotyczących tablicy obliczanej przez algorytm dynamiczny można obliczenia takie przyspieszyć. Np metoda Knutha-Yao pozwala na przyspieszenie algorytmu znajdowania optymalengo drzewa binarnego z O(n^3) do O(n^2). (kontakt: K. Diks)
Problemy grafowe
- Spannery w oczekiwanym czasie liniowym (algorytm Baswany-Sena). Spanner to rzadki podgraf danego grafu G, w którym odległości między wierzchołkami są bliskie odległości w G (np. nie większe niż dwukrotnie większe). Stosuje się je jako struktury danych do szybkiego znajdowania krótkich ścieżek w grafach. Jest to nowy, ale nietrudny i bardzo piękny algorytm. (kontakt: Ł. Kowalik)
-
Aproksymacja ogólnego problemu stabilnych małżeństw
Problem stabilnych małżeństw (zob.Wikipedia) w wersji klasycznej ma eleganckie,
wielomianowe rozwiązanie. W wersji gdy listy preferencji nie muszą być
maksymalnej długości i mogą zawierać remisy problem jest NP-trudny.
Ostatnio pojawił się dość prosty algorytm 5/3 aproksymacyjny.
Źródło:
[PDF]
(kontakt: Ł. Kowalik) - Aproksymacja zbioru niezależnego
Problem zbioru niezależnego nie daje się aproksymować ze wsp. n^{1-epsilon},
o ile P!=NP.
Do zreferowania jest elegancki algorytm ze wsp. aproksymacji n/(log^2 n).
Algorytm jest także ciekawy o tyle, że ma związek z liczbami Ramseya (w
szczególności daje prosty dowód istnienia tych liczb).
Źródło: Ravi Boppana, Magnús M. Halldórsson, "Approximating Maximum Independent Sets by Excluding Subgraphs", SWAT'90, [Citeseer].
(Kontakt: Ł. Kowalik) - Problem drzewa Steinera. (Dany graf G=(V,E) z wagami na krawędziach i podzbiór wierzchołków S. Znaleźć najlżejszy spójny podgraf, który zawiera wszystkie wierzchołki S).
- Algorytm klasyczny (Dreyfus, Wagner) O*(3^|S|) i ostatnie wyniki w dziedzinie. [notacja O* pomija czynniki wielomianowe]
- Fuchs i inni: algorytm O*(c^|S|) dla dowolnej stałej c
- Bjorklund i inni: algorytm O*(2^|S|) dla przypadku gdy wagi krawędzi są małe.
-
problem Bandwidth (znaleźć permutację wierzchołków grafu p tak żeby
największa "długość krawędzi" |p(u)-p(v)| była jak najmniejsza).
Przeglad znanych algorytmow:
- Sprawdzanie czy da się uzyskać |p(u)-p(v)|<=b: Sprytne programowanie dynamiczne O(n^{b+1})
- Algorytm dla dowolnego b: O*(10^n)
- Algorytm O(log^3 n)-aproksymacyjny (szkic).
- Kolorowanie krawędziowe grafów kubicznych
Tw. Vizinga mówi, że graf, w którym wszystkie wierzchołki są stopnia D można
pokolorować krawędziowo D+1 kolorami (tak, aby incydentne krawędzie miały inne
kolory). Można takie kolorowanie znaleźć w czasie wielomianowym (ale
znacznie gorszym niż liniowy).
Tymczasem dla grafów stopnia 3 istnieje bardzo elegancki, liniowy algorytm.
Źródło: San Skulrattanakulchai "4-edge-coloring graphs of maximum degree 3 in linear time" IPL 81(4) 191-195 (2002) [Citeseer]
kontakt: K. Diks
Algorytmika internetu
- Zastosowanie wartości własnych macierzy -- algorytmy HITS, PageRank,
SALSA. Źródło: Meyer, Langville "A Survey of Eigenvector Methods of Web Information
Retrieval" [PDF]
kontakt: K. Diks - Ciekawy problem związany z routerami w sieci.
Routery chcą obliczać statystyki na temat przesyłanych pakietów, ale
pakietów jest mnóstwo, a one mają mało pamięci. Co robić???
[Praca
Demaine, Lopez-Ortiz, Munro]
kontakt: K. Diks
Geometria obliczeniowa
- Controlled perturbation. Większość algorytmów geometrycznych wymaga "niezdegenrowanych danych" (np. brak 3 punktów współliniowych etc) i nieskończonej precyzji obliczeń. Controlled perturbation to generyczna randomizowana metoda "radzenia" sobie z tymi ograniczeniami: punkty z wejścia są lekko przesuwane w losowych kierunkach. Dowodzi się, że z dużym prawdopodobieństwem (np. 1/2) dany algorytm zadziała dla tak zmodyfikowanych danych. Jeśli nie zadziała -- losujemy od nowa. Bardzo piękna i praktyczna idea. (kontakt: Ł. Kowalik)