Seminar Algorithms

Organizers

• dr hab. Michał Pilipczuk, prof. UW

Information

Home page

List of talks

• Jan. 12, 2006, 12:15 p.m.
  Dorota Cendrowska (Uniwersytet Warszawski)
  Konstrukcja klasyfikatora obiektów z wykorzystaniem algorytmu badania rozdzielności liniowej dwóch zbiorów
  W ramach seminarium zostaną poruszone kwestie dotyczące odpowiedzi na następujące pytania: Jak ludzie radzą sobie z problemem automatycznego rozdzielania liniowego dwóch zbiorów? Trop 1: Może "liniowo" to synonim "zbyt łatwo" i sprawdza się reguła garbage …

  ---

• Jan. 5, 2006, 12:15 p.m.
  Krzysztof Onak (Uniwersytet Warszawski)
  Testowanie własności
  W sytuacji, gdy dysponujemy ograniczoną ilością czasu, może nie być możliwe sprawdzenie, czy dany obiekt (kombinatoryczny) posiada, pewną ustaloną własność. Tym niemniej nie jesteśmy całkowicie bezradni. Okazuje się, że w wielu przypadkach, odczytując jedynie niewielki …

  ---

• Dec. 15, 2005, 12:15 p.m.
  Arkadiusz Paterek (Uniwersytet Warszawski)
  O ulepszaniu algorytmów dla gier dwuosobowych z pełną informacją
  Na seminarium omówię własne eksperymenty związane z zastosowaniem technik uczenia z nadzorem do wyboru parametrów funkcji oceniającej w programie grającym w szachy. Opowiem również o algorytmie BPIP, obiecującej alternatywie dla algorytmu alfa-beta cięć. Jest to …

  ---

• Dec. 8, 2005, 12:15 p.m.
  Marcin Stefaniak (Uniwersytet Warszawski)
  Algorytmiczne aspekty infrastruktury SilkRoute
  SilkRoute (2002) służy do wyciągania danych z relacyjnej bazy (SQL) w postaci drzewiastej (XML) przy użyciu języka zapytań XQuery. Odbywa się to poprzez stworzenie drzewiastego planu zapytań SQL, co można zrobić na wiele sposobów. SilkRoute …

  ---

• Nov. 17, 2005, 12:15 p.m.
  Anna Urbańska (Uniwersytet Warszawski)
  Kombinatoryczny algorytm obliczania wyznacznika
  Tematem referatu jest kombinatoryczna charakteryzacja wyznacznika, dająca prosty i całkowicie kombinatoryczny algorytm na jego obliczanie, działający w czasie O(n^4). Algorytm ten nie wymaga dzielenia i pracuje nad dowolnym pierścieniem przemiennym. Postaram się również pokazać, jak …

  ---

• Nov. 10, 2005, 12:15 p.m.
  Krzysztof Ciebiera (Uniwersytet Warszawski)
  Poświadczone struktury danych
  Zagadnienia: 1. Co to są poświadczone struktury danych? 2. Tradycyjne metody tworzenia poświadczonych słowników. 3. ''Skip-lists'' - metoda implementacji poświadczonych słowników. 4. Inne znane zastosowania poświadczonych struktur danych (w geometrii i algorytmach grafowych).

  ---

• Oct. 27, 2005, 12:15 p.m.
  Piotr Sankowski (Uniwersytet Warszawski)
  Obliczanie odległości w grafie przy użyciu mnożenia macierzy
  Tematem seminarium jest obliczanie odległości w grafie z wykorzystaniem mnożenia macierzy. Rozpocznę od przedstawienia tegorocznych wyników pokazujących w jaki sposób bliczyć odległości z zadanego wierzchołka w grafie dla całkowitoliczbowych wag krawędzi w takim samym czasie …

  ---

• Oct. 20, 2005, 12:15 p.m.
  Marcin Peczarski (Uniwersytet Warszawski)
  Komputerowo wspomagane badanie własności porządków częściowych
  Własności, o których będę mówił, związane są z sortowaniem za pomocą porównań. Sortowanie porządku częściowego polega na znalezieniu jednego z jego rozszerzeń liniowych. Sortowanie możemy sobie wyobrazić jako grę. W każdym ruchu my wybieramy parę …

  ---

• Oct. 13, 2005, 12:15 p.m.
  Mirosław Kowaluk (Uniwersytet Warszawski)
  Problem najbliższego wspólnego przodka w grafach acyklicznych
  Najbliższym wspólnym przodkiem dwóch wierzchołków u,v grafu acyklicznego jest wierzchołek będący wspólnym przodkiem wierzchołków u, v i nie będęcy przodkiem żadnego innego wspólnego przodka tych wierzchołków. Wybór najbliższego wspólnego przodka nie musi być jednoznaczny. W …

  ---

• Oct. 6, 2005, 12:15 p.m.
  Łukasz Kowalik (Uniwersytet Warszawski)
  Listowe kolorowanie krawędziowe grafów i aproksymacja lesistości grafu
  Postaram się krótko przedstawić problem listowego kolorowania krawędziowego grafów oraz opowiedzieć o znanych wynikach w tej dziedzinie. Szczególnie uważnie będę się przyglądał grafom planarnym. Z listowym kolorowaniem krawędziowym grafów ogólnych i planarnych wiąże się kilka …

  ---

• Nov. 25, 2004, 12:15 p.m.
  Krzysztof Diks (Uniwersytet Warszawski)
  O dwóch ciekawych problemach grafowych
  Opowiemy o dwóch znanych problemach grafowych postawionych ogólniej niż się to robi klasycznie. Przedstawimy ugólnione twierdzenie Vizinga o kolorowaniu krawędzi multigrafu i pokażemy, w jaki sposób znajdować cykle Eulera w grafach mieszanych, tzn. takich, w …

  ---

• Nov. 18, 2004, 12:15 p.m.
  Arkadiusz Paterek (Uniwersytet Warszawski)
  Modelowanie funkcji oceniającej w grach
  W programach grających w gry dwuosobowe, opartych na algorytmach typu minimax, stosuje się często funkcję oceniającą w postaci kombinacji liniowej wybranych numerycznych własności pozycji. Dysponując wystarczająco dużym zbiorem pozycji z oceną ustaloną przez wyrocznię, można …

  ---

• Nov. 4, 2004, 12:15 p.m.
  Łukasz Kowalik (Uniwersytet Warszawski)
  Kolorowanie krawędziowe grafów planarnych
  W problemie kolorowania krawędziowego grafu należy krawędziom grafu przypisać kolory tak, aby incydentne krawędzie otrzymały różne kolory. Rozważa się bardzo naturalne uogólnienie tego problemu: listowe kolorowanie krawędziowe. W tej wersji każda krawędź ma przypisaną listę …

  ---

• Oct. 28, 2004, 12:15 p.m.
  Piotr Sankowski (Uniwersytet Warszawski)
  Od macierzy odwrotnoścci do dynamicznych najkrótszych ścieżek
  W trakcie seminarium przedstawię najważniejsze elementy konstrukcji algorytmów dla dynamicznego liczenia macierzy odwrotnej oraz ich zastosowanie do liczenia dynamicznego domknięcia przechodniego. Konstrukcja ta daje asymptotyczne najszybsze znane algorytmy dla tego problemu. W drugiej części seminarium …

  ---

• Oct. 21, 2004, 12:15 p.m.
  Katarzyna Paluch (Instytut Informatyki, Uniwersytet Wrocławski)
  Aproksymacyjne algorytmy pokrywania tablic liczbowych prostokątami
  Przedstawione zostaną główne wyniki rozprawy doktorskiej prelegentki: dwa algorytmy aproksymacyjne dla problemu ,,Rectangle Tiling", pierwszy o współczynniku aproksymacji 9/4 i drugi o współczynniku aproksymacji 17/8.

  ---

• Oct. 14, 2004, 12:15 p.m.
  Ł. Kowalik, M. Mucha, P. Sankowski (Uniwersytet Warszawski)
  European Symposium on Algorithms 2004
  Przegląd najważniejszych prac prezentowanych podczas konferencji European Symposium on Algorithms 2004, która miała miejsce we wrześniu, w Bergen, Norwegia.

  ---