Algorytmy dynamiczne (!= programowanie dynamiczne)

Opis zajęć

Na wstępie zastrzeżenie - na tym wykładzie nie będziemy się zajmować algorytmami wypełniającymi komórki tablicy w zależności od komórej sąsiednich (typu algorytm znajdowania najdłuższego wspólnego podciągu dwóch słów), która to technika jest znana pod nazwą programowania dynamicznego. Algorytmy dynamiczne nie mają z tym nic wspólnego.

Algorytmem dynamicznym nazywamy algorytm, pozwalający na utrzymywanie informacji o zmieniającej się strukturze danych, umożliwiający wykonywanie zmian na strukturze i odpowiadania na zapytania o jakieś własności tej struktury w czasie krótszym, niż zajęłoby policzenie wszystkiego od zera. Najbardziej znane przykłady to:

  • słowniki: gdybyśmy trzymali słownik po prostu jako listę słów, sprawdzenie, czy dane słowo jest w słowniku, w pesymistycznym przypadku wymagałoby przejrzenia wszystkich słów; jeśli jednak trzymamy słownik w zrównoważonym drzewie wyszukiwań binarnych, koszt wyszukiwania jest logarytmiczny - wykorzystanie bardziej złożonej struktury danych pozwoliło nam zbić czas zapytania kosztem niewielkiego zwiększenia czasu modyfikacji, czyli dodania słowa do słownika ($O(1)$ w przypadku listy, $O(log n)$ w przypadku drzewa),
  • utrzymywanie zbiorów rozłącznych (działamy na rodzinie zbiorów: możemy łączyć dwa zbiory oraz pytać, czy dwa elementy są w tym samym zbiorze) - dzięki zastosowaniu sprytnej struktury danych (drzew find-union) możemy zbić zamortyzowany czas zapytania - jak się okazuje po zastosowaniu jeszcze sprytniejszej analizy złożoności - do niemal stałego
  • kolejki priorytetowe (utrzymujemy zbiór liczb, chcemy dodawać do zbioru dowolne liczby i usuwać liczbę aktualnie najmniejszą) - zastosowanie różnego rodzaju kopców pozwala nam osiągać bardzo małe (pesymistyczne lub zamortyzowane) czasy operacji

Warsztaty powinny pomóc porządnie opanować algorytmiczne rzemiosło - kilka koegzystujących w jednym algorytmie różnych struktur danych, których elementami są jeszcze inne struktury danych, i do jeszcze randomizowane, to w tej działce normalka (choć błyskotliwe, proste pomysły również się zdarzają). Wyniki, o których będziemy mówić, są w miarę świeże, i dają nadzieję, że wystarczy dołożyć do tego jeszcze jedną małą strukturkę, i uzyska się zupełnie nowy, lepszy wynik.

Program

  • w pełni dynamiczne drzewa i ich zastosowania do innych problemów
  • dynamiczne drzewa rozpinające
  • dynamiczne wyszukiwanie wzorca w tekście
  • dynamiczne najkrótsze ścieżki
  • jeśli czas pozwoli - jeszcze kilka algorytmów dynamicznych

Wymagania

  • znajomość notacji "dużego O" i podstawowych struktur danych,
  • znajomość co najmniej jednego rodzaju zrównoważonych drzew wyszukiwania binarnego (do wyboru drzewa AVL, drzewa czerwono-czarne, drzewa splay, 2-3-4 drzewa)
  • zrozumienie zamortyzowanej analizy złożoności (w tym wypadku jednak lepiej się jej uczyć z Cormena, a nie z wikipedii)
  • znajomość co najmniej jednego algorytmu znajdowania minimalnego drzewa rozpinającego, wyszukiwania wzorca
  • trochę obycia algorytmicznego

Literatura

  • Cormen, Leiserson, Rivest[, Stein] - Wprowadzenie do algorytmów (kilka odpowiednich rozdziałów)
  • Wikipedia

Zadania kwalifikacyjne

Aby zakwalifikować się na warsztaty, należy rozwiązania obu zadań wysłać na adres moc.liamg|sytlosk#moc.liamg|sytlosk. Za wyniki częściowe / mądre przemyślenia też będą jakieś punkty - w szczególności można będzie się zakwalifikować bez drugiego punktu 2. zadania. W razie problemów wysyłajcie pytania mailem.

Zadanie 1
Zaproponuj algorytm ubytkowy (tzn. algorytm dynamiczny umożliwiający tylko usuwanie elementów ze struktury) dla problemu spójności ścieżki o $n$ wierzchołkach. Algorytm inicjowany jest dla ścieżki i możemy tylko usuwać krawędzie. Algorytm powinien pozwalać na wykonywanie operacji:

  • usunięcia krawędzi w czasie $O(log n)$ (może to być czas zamortyzowany - amortyzujemy po usunięciu wszystkich krawędzi)
  • zapytania o to, czy istnieje ścieżka między parą wierzchołków w czasie $O(1)$ (pesymistycznym)

Zadanie 2
Mamy pokój z nieskończoną taśmą, której pozycje mogą zawierać zera lub jedynki. Początkowo na taśmie jest nieskończony ciąg zer. Mamy również $n$ ludzi, którzy niezależnie od siebie, pojedynczo wchodzą do tego pokoju. Każda osoba wchodzi do pokoju dokładnie jeden raz - może poznać pewną ilość bitów na taśmie i pewne z nich zmienić bądź nie. Chcemy, aby osoba, która wejdzie do tego pokoju jako ostatnia ($n$-ta) wiedziała, że wszyscy przed nią już byli w tym pokoju. Poszukujemy strategii, która umożliwi nam ograniczyć z góry pesymistyczną liczbę bitów, które sprawdza dana osoba, interesuje nas oszacowanie asymptotyczne (ściślej: chcemy powiedzieć, że osoba, która sprawdza najwięcej bitów, sprawdza $O( f ( n ) )$ bitów; szukamy strategii, która da nam jak najmniejsze $f ( n )$). A w terminach algorytmów dynamicznych - chcemy umieć usuwać elementy ze zbioru i odpowiadać na zapytania "czy zbiór jest pusty" w jak najmniejszym czasie.
Każda z osób zna liczbę $n$.

  • podaj algorytm działający w pesymistycznym czasie $O (log n)$
  • czy istnieje lepszy algorytm (działający w mniejszym pesymistycznym czasie)? Opisz go, lub udowodnij, że taki algorytm nie istnieje.

A tak na marginesie (to już nie jest część zadań kwalifikacyjnych) - mamy $n$ osób, które są niezależnie od siebie, pojedynczo wprowadzane do pokoju, w którym jest jedna żarówka (która, jak to żarówka, może mieć dwa stany). Mamy warunek, że każda z osób wejdzie do pokoju potencjalnie nieskończenie wiele razy. Chcemy, by pewna osoba mogła zgodnie z prawdą stwierdzić, że wszystkie pozostałe osoby już kiedyś były w tym pokoju. Jaka strategia im to umożliwi?

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License