Nie jesteś zalogowany | Zaloguj się
Powrót do listy aktywnych seminarów

Seminarium "Algorytmika"

Cotygodniowe seminarium badawcze

 


Organizatorzy

Informacje

piątki, 14:15 , sala: 5060

Strona domowa

https://semalgo.wordpress.com/

Lista referatów

  • 12 października 2006 12:15
    Łukasz Kowalik (Uniwersytet Warszawski)
    Konferencja SODA; "Mierz i zwyciężaj": metoda analizy algorytmów wykładniczych.
    Seminarium będzie się składało z dwóch części. Podczas części pierwszej krótko przedstawię najciekawsze wyniki z tegorocznej konferencji SODA. Nieco bardziej szczegółowo opowiem o pracy Fedor V. Fomin, Fabrizio Grandoni, Dieter Kratsch, "Measure and Conquer: A …

  • 25 maja 2006 12:15
    Bartosz Przydatek (ETH w Zurychu)
    Solving Medium-Density Subset Sum Problems in Expected Polynomial Time
    Solving Medium-Density Subset Sum Problems in Expected Polynomial Time. The subset sum problem (SSP) (given n numbers and a target bound B, find a subset of the numbers summing to B), is a classic NP-hard …

  • 11 maja 2006 12:15
    Piotr Sankowski (Uniwersytet Warszawski)
    Szybsze dynamiczne skojarzenia i spójność wierzchołkowa
    W ramach seminarium opowiem o pierwszych dynamicznych podkwadratowych algorytmach na obliczanie: liczby wierzchołkowo rozłącznych s,t-ścieżek, rozmiaru maksymalnego skojarzenia w grafie i skierowanej k-spójności wierzchołkowej. Prezentowane algorytmy są randomizowane z jednostronnym błędem. Algorytmy dynamiczne dla problemu …

  • 9 marca 2006 12:15
    Marcin Kubica i Tomasz Waleń (Uniwersytet Warszawski)
    O pewnych algorytmicznych problemach tekstowych
    Tomek Waleń opowie o wspólnej pracy z P. Kolmanem. Podczas seminarium zostanie przybliżony problem porównywania sekwencji genomów. W szczególności problem obliczania odległości pomiędzy napisami liczonej w liczbie odwróceń (całych bloków), potrzebnych do przekształcenia jednego napisu …

  • 2 marca 2006 12:15
    Wojciech Plandowski (Uniwersytet Warszawski)
    O rozwiązywaniu równań w półgrupie wolnej
    Na seminarium przedstawię pierwszy algorytm rozwiązujący równania w półgrupie wolnej, który działa w DEXPTIME. Prezentowane podejście pozwala na rozwiązanie w PSPACE następujących problemów: - sprawdzenia, czy zbiór rozwiązań równania jest skończony, - sprawdzenia, czy zbiór …

  • 26 stycznia 2006 12:15
    Anna Wojak (Uniwersytet Warszawski)
    Wyznaczanie Euklidesowej najkrótszej drogi na płaszczyźnie pomiędzy dwoma punktami z pominięciem wielokątnych przeszkód.
    Wyznaczanie Euklidesowej najkrótszej ścieżki jest jednym z najstarszych i dobrze znanych problemów w geometrii obliczeniowej. Obecnie istnieje wiele typów problemów związanych z wyznaczaniem najkrótszych dróg. Rozważmy płaszczyznę zawierająca zbiór rozłącznych przeszkód, których liczba wierzchołków wynosi …

  • 12 stycznia 2006 12:15
    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 …

  • 5 stycznia 2006 12:15
    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 …

  • 15 grudnia 2005 12:15
    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 …

  • 8 grudnia 2005 12:15
    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 …

  • 17 listopada 2005 12:15
    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 …

  • 10 listopada 2005 12:15
    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).

  • 27 października 2005 12:15
    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 …

  • 20 października 2005 12:15
    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ę …

  • 13 października 2005 12:15
    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 …

  • 6 października 2005 12:15
    Ł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 …

  • 25 listopada 2004 12:15
    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 …

  • 18 listopada 2004 12:15
    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 …

  • 4 listopada 2004 12:15
    Ł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ę …

  • 28 października 2004 12:15
    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 …

  • 21 października 2004 12:15
    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.

  • 14 października 2004 12:15
    Ł. 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.