Jakub Radoszewski

Wykład 18. Algorytmów tekstowych cd.

 Na wykładzie omówiłem następujące zagadnienia:

Wykład 16. Zamiatanie w geometrii

Na wykładzie omówiłem następujące zagadnienia:

  • Zadanie Poziomice z PA 2006.
  • Problem najbliższej pary punktów za pomocą zamiatania.
  • Sprawdzanie przynależności wielu punktów do wielokąta (dowolnego).
  • Pole i obwód sumy prostokątów.
  • Zadanie Łyżwy z II etapu XVI OI (może nie ma związku z zamiataniem, ale z drzewami przedziałowymi już tak).

Wykład poprowadził Jakub Radoszewski. Lokalizacja: 3130. Termin: 17.03.2009, 16:15-18:00.

Dostępne materiały: Nagrania.

Wykład 13. Proste (czyżby?) algorytmy grafowe

Na wykładzie omówiłem różne w sumie podstawowe algorytmy związane z grafami. Przy większości z nich wspomniałem o tym, jak według mojego doświadczenia najlepiej (np. najłatwiej) go zaimplementować, jak najłatwiej uzasadnić jego poprawność i jak go stosować do różnych fajnych rzeczy. Na wykładzie zakładałem raptem... znajomość poniższych algorytmów:).

  • BFS (tak, nawet w zwykłym BFS-ie coś ciekawego siedzi!).
  • Silnie spójne składowe i sortowania topologiczne.
  • Cykl Eulera.
  • Algorytm Dijkstry z moim ulubionym zastosowaniem.
  • Algorytm Floyda-Warshalla i zastosowania do ujemnych cykli w grafie (patrz zadanie Studia z PA 2008).
  • "Dzielenie przez 32" na przykładzie algorytmów grafowych (w tym zliczanie trójkątów w grafie i inne Floydy).

Wykład poprowadził Jakub Radoszewski. Lokalizacja: 3130. Termin: 24.02.2009, 16:00-17:45.

Dostępne materiały: Nagrania.

Wykład 12. Solidna dawka teorii liczb

Na wykładzie omówione zostały różne ciekawe rozwiązania zadania I z AMPPZ 2008, które zawierają niejako przy okazji solidną dawkę teorii liczb, m.in.:

  • Proste własności grup Zp*, które są przydatne w teorii liczb, typu: generatory, ich istnienie i liczba, MTF.
  • Liczenie odwrotności modulo na dwa sposoby (z rozszerzonego algorytmu Euklidesa i z MTF).
  • Logarytm dyskretny.
  • Chińskie twierdzenie o resztach.
  • Szukanie pierwiastków wielomianów za pomocą Lematu Hensla.

Nie jest wymagana zbyt duża wiedza z zakresu teorii liczb, ew. jakieś podstawy.

Wykład poprowadził Jakub Radoszewski. Lokalizacja: 3130. Termin: wtorek 17.02.2009, 16:00-17:45.

Dostępne materiały: Nagrania.

Wykład 11. Potyczki Algorytmiczne 2008 — omówienie rozwiązań

 Zagadnienia, które były poruszone na wykładzie:

  • Zadanie Pytania z PA 2008 i zadanie "Wizards" z srma 299.
  • Bardzo krótkie omówienie rozwiązań najtrudniejszych zadań z PA 2008.

Wykład poprowadził Jakub Radoszewski. Lokalizacja: 3150. Termin: 02.06.2008, 16:15-17:45.

Dostępne materiały: Nagrania.

Wykład 10. Programowanie dynamiczne a zagadki logiczne

 Zagadnienia, które były poruszone na wykładzie:

  • Konstrukcja i redukcja rozmiaru wykładniczej przestrzeni stanów. Zadania: "Gra" z FZI 2 i "Wires and Switches" z IOI 1995.
  • Klasyczna zagadka o zrzucaniu jajek i jej uogólnienia, czyli kiedy maszyna zaczyna kłamać. Zadania: "Jajka" z VII OI, "Destruction" z TCO 2007 runda 1A (pozostawione jako zadanie domowe) i "Force test" z srma 276.

Wykład poprowadził Jakub Radoszewski. Lokalizacja: 3150. Termin: 26.05.2008, 16:15-17:45.

Dostępne materiały: Nagrania.

Wykład 9. Teoria gier (część II)

Zagadnienia, które były poruszone na wykładzie:

  • Gra Green Hackenbush — przypomnienie.
  • Gra Red-Blue Hackenbush.

Wykład poprowadził Jakub Radoszewski. Lokalizacja: 3150. Termin: 28.04.2008, 16:15-17:45.

Ten wykład nie był niestety filmowany.

Wykład 6. Teoria gier

 Zagadnienia, które były poruszone na wykładzie:

  • Gra Nim: przypomnienie, Misere Nim, Staircase Nim, Gra w Pionki.
  • Twierdzenie Sprague-Grundy'ego, zastosowania.
  • Gra Green Hackenbush.

Wykład poprowadził Jakub Radoszewski. Lokalizacja: 3150. Termin: 07.04.2008, 16:15-17:45.

Dostępne materiały: Nagrania.

Wykład 2. Zastosowania drzew przedziałowych

 Zagadnienia poruszone na wykładzie:

  • Drzewo przedziałowe: właściwości oraz prosta i efektywna, nierekurencyjna implementacja.
  • Zastosowanie do problemu: "wstawianie punktów, zapytania o przedziały". Kilka uogólnień na przypadki wielowymiarowe.
  • Rozwiązanie problemu: "wstawianie przedziałów, zapytania o punkty".
  • Problem "wstawianie przedziałów, zapytania o przedziały". Rozważaliśmy wersje: (+, max) (zadanie Koleje z I etapu IX OI), (max, max) (zadanie "Tetris 2D") oraz (+, +) i znaleźliśmy dla nich wspólny mianownik. Wspomniane zostały także wersje (=, +) oraz (=, max) z rozwiązaniem za pomocą bitów aktualności.
  • Parę słów o tym, że w węzłach drzewa może być coś ciekawszego niż pojedyncze liczby (przedziały -- zadanie Pole uprawne z PA 2006; permutacje -- zadanie Skrętka Liliany z ONTAK-a 2005; macierze -- zadanie Autostrady z PA 2005).

Wykład poprowadził Jakub Radoszewski. Lokalizacja: 3150. Termin: 03.03.2008, 16:15-17:45.

Dostępne materiały: Nagrania, Notatki.

Wykład 1. Liniowe algorytmy tekstowe

 Zagadnienia poruszone na wykładzie:

  • Prefikso-sufiksy i algorytm KMP w wersji z prostym dowodem i prostą implementacją.
  • Związki między prefikso-sufiksami, okresami a pierwiastkami słowa. Pierwiastek pierwotny słowa, jego wyznaczanie i właściwości.
  • Wyznaczanie najkrótszego szablonu słowa (słowa, którym można w całości pokryć dane słowo) w czasie O(n*log(n)).
  • Algorytm Manachera wyznaczania promieni palindromów parzystych.
  • Funkcja PREF -- jej wyznaczanie oraz szkic metody jej zastosowania do rozwiązania zadania "Prawie równoważne słowa".
  • Algorytmy tekstowe w zadaniach geometrycznych (badanie możliwości przekształcenia jednego zbioru punktów na drugi za pomocą algorytmu na równoważność cykliczną napisów, wyznaczanie osi symetrii wielokąta za pomocą algorytmu Manachera). Tego nie zdążyłem omówić na wykładzie, ale jest zawarte w notatkach.

Wykład poprowadził Jakub Radoszewski. Lokalizacja: 3150. Termin: 25.02.2008, 16:20-17:45.

Dostępne materiały: Nagrania, Notatki.

Syndicate content