MOKIP 13.12.12

I Gobeliny XX OI

  • Przechodzimy wielokąt zgodnie z ruchem wskazówek zegara.
  • Jeśli odcinki n i n+1 mają być nieoświetlone, to możemy je zamienić w jeden (pod warunkiem, że ich punkt wspólny leży po lewej stronie prostej wyznaczonej przez pierwszy pkt. odcinka n i drugi pkt. odcinka n+1)
  • Po takim przejściu mamy 2 możliwości:

a) wszystkie odcinki mają być oświetlone
b) istnieją odcinki, które mają być nieoświetlone

  • Co ciekawe, dla obu przypadków postępowanie jest podobne. Znów przechodzimy graf clockwise i teraz:

- dla odcinka oświetlonego wywalamy część wielokąta leżącą po lewej stronie
- dla odcinka nieoświetlonego wywalamy część po prawej stronie

  • W wywalanej części nie może znajdować się lampa. "Wywalanie" to może być np. usuwanie punktów, które mieliśmy w dalszej kolejności odwiedzić.
  • Jeśli mieliśmy do czynienia z przypadkiem a) to w powstały na końcu w wielokąt wstawiamy lampę i sprawdzamy, czy oświetli nam wszystkie odcinki. Dla b) lampa musi się znajdować na przecięciu się prostych wyznaczonych przez odcinki zaciemnione.

II Algorytmy tekstowe

1. Podstawowe pojęcia (link do poprzednich zajęć z 7 listopada)
2. Algorytm KMP

  • wyznacza tablice sufixową (KMP_Make)
  • która może posłużyć do odnalezienia wzorca w podanym słowie (KMP_Match)
  • pseudokod O(n+m) n - długość słowa, m - długość wzorca

3. Zadanie Szablon XII OI.

  • Zauważamy, że rozwiązanie, czyli szukany najkrótszy szablon, musi być pref-sufixem podanego napisu S.
  • Trzeba trochę zmodyfikować KMP tak aby nie odnajdywał najdłuższych pref-sufixów podsłów słowa S (na końcu także samego S), ale wszystkie(od najkrótszych do najdłuższych) pref-sufixy tylko słowa S
  • Jeśli na tym poprzestaniemy to mamy algorytm O(n^2) (dla każdego pref-sufixu sprawdzamy czy jest szablonem). Takie sprawdzanie to nic innego jak wyszukiwanie wzorca w tekście.
  • Ostanie spostrzeżenie, prowadzące do rozwiązania wzorcowego O(n*log_n):

1. Oznaczmy przez X zbiór wszystkich pref-sufixów słowa S.
2. Niech X będzie posortowany rosnąco względem długości pref-sufixów.
3. Jeśli y_i oraz y_i+1 należą do X to jeżeli y_i+1 /2 <= y_i to możemy y_i+1 przedstawić tylko za pomocą odpowiedniego połączenia ze sobą dwóch y_i (widać ładnie na rysunku).
4. Oznacza to, że jeżeli y_i nie jest najkrótszym szablonem, to jako kolejny wzorzec wybieramy więc takie y, że y > 2*y_i co powoduje że sprawdzimy co najwyżej log_n ilości pref-sufixów.

III Zadanie Wojna PA 2012

1. Treść
2. Omówienie

Zachęcamy do zapisania obu zadań! Dla leniwych kody pojawią się wkrótce… ;)