You are not logged in |
Research seminar (Fridays, at 14.15 in room 5060)
For schedule or link to online meetings, see https://semalgo.wordpress.com/
If you want to get notifications, sign up to the mailing list algorytmy@mimuw.edu.pl
Rules for PhD studens: https://www.mimuw.edu.pl/~mp248287/algorithmsSeminarRules.pdf
Google calendar: https://calendar.google.com/calendar/embed?src=q1pbv62cra5jf9satch9ip49ms%40group.calendar.google.com&ctz=Europe%2FWarsaw
YouTube cannel: https://www.youtube.com/playlist?list=PLzdZSKerwrXpfAgaKQpsH8ElCik3pINPp
Organizers
- dr hab. Marcin Pilipczuk, prof. UW
Information
Fridays, 2:15 p.m. , room: 5060Home page
https://semalgo.wordpress.com/List of talks
-
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.
