Sezon 2004/2005, czwarek 12:15-13:45, sala 5870

07.10.2003 Wojciech Frączak

CSM (Concatenation State Machines) odgrywają ważną rolę w klasyfikacji pakietów realizowanej przez PAX.port - specjalizowany mikro-procesor zaprojektowany w IDT Canada. Badania, których rezultaty zaprezentujemy na seminarium, były prowadzone w celu lepszego zrozumienia możliwości jakie PAX.port nam oferuje. Na początku PAX.port został pomyślany jako "sprytny" interpreter dla "sequential transducers", gdzie wprowadziliśmy "węzeł sklejania" (concatenation node) dla celów kompresji pamięci przeznaczonej do opisu stanoów automatu. Okazało się, że wprowadzenie "wezlow sklejania" rozszerzyło siłę wyrazu urządzenia. Funkcje częściowe, które mogą być opisane przez CSM (czyli automat ze stanami sklejania) nazwaliśmy "funkcjami prostymi", gdyż są one naturalnym rozszerzeniem językow prostych. Na seminarium wprowadzimy pojęcie "klasyfikatorow" jako funkcji częściowych na słowach, przedstawimy pewne wlasności klasyfikatorów, oraz ich związek z funkcjami prostymi.

14.10.2004 Łukasz Kowalik, Piotr Sankowski, Marcin Mucha

Przegląd najwazniejszych prac prezentowanych podczas konferencji ESA 2004, która miała miejsce we wrześniu, w Bergen, Norwegia.

21.10.2004 Katarzyna Paluch

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.

28.10.2004 Piotr Sankowski

W trakcie seminarium przedstawię najważniejsze elementy konstrukcji algorytmów dla dynamicznego liczenia macierzy odwrotnej oraz zastosowanie tego algorytmu do liczenia dynamicznego domknięcia przechodniego. Konstrukcja ta daje asymptotyczne najszybsze znane algorytmy dla tego problemu. W drugiej części seminarium opowiem o rozszerzeniach tego algorytmu dla obliczeń nad pierścieniami. Rozszerzenie to umożliwi konstrukcję efektywnych dynamicznych algorytmów na obliczanie długości najkrótszych ścieżek w grafie.

04.11.2004 Łukasz Kowalik

W problemie kolorowania krawedziowego grafu nalezy krawedziom grafu przypisac kolory tak, aby incydentne krawedzie otrzymaly rozne kolory. Rozwaza sie bardzo naturalne uogolnienie tego problemu: listowe kolorowanie krawedziowe. W tej wersji kazda krawedz ma przypisana liste dozwolonych kolorow. Na seminarium opowiem o algorytmach kolorowania krawedziowego i listowego kolorowania krawedziowego grafow planarnych. Beda nas interesowaly wylacznie liniowe algorytmy i optymalne kolorowanie -- uzywajace mozliwie malej liczby kolorow lub dzialajace dla mozliwie krotkich list. Opowiem o nowych wynikach w tej dziedzinie, uzyskanych we wspolpracy z Richardem Cole.

11.11.2004

18.11.2004 Arek Paterek

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 ustalić współczynniki funkcji, minimalizując jej bład dla ocenionych pozycji.
Na seminarium opowiem o eksperymencie z mojej pracy magisterskiej, polegającym na ustaleniu parametrów funkcji oceniającej w programie szachowym, przy użyciu metody najszybszego spadku.

25.11.2004 Krzsztof Diks

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 których mogą się pojawiać zarówno krawędzie skierowane, jak i nieskierowane. W naszych rozważaniach skoncentrujemy się na algorytmicznych aspektach omawianych zagadnień.

02.12.2004 Wojtek Dudek

Streszczenie

09.12.2004 Rafał Dowgird

Streszczenie

16.12.2004 Tomek Waleń

Streszczenie

06.01.2005 Robert Dąbrowski

Główne wyniki rozprawy doktorskiej.

13.01.2005 Kuba Pawlewicz

Streszczenie

17.02.2005 Piotr Sankowski

W trakcie seminarium przedstawię algorytm znajdowania doskonałych skojarzeń równolegle. Opowiem jak skonstruować dla tego problemu algorytm RNC wykonujący taką samą pracę jak najszybsze algorytmy sekwencyjne, tzn., algorytm ten używać będzie O(n^omega) procesorów.

24.02.2005 Piotr Sankowski

W ramach seminarium przedstawię algorytm wykorzystujący mnożenie macierzy do znajdowania ważonych doskonałych skojarzeń w dowolnych grafach o całkowitoliczbowych wagach krawędzi. Algorytm ten oparty jest na bardzo świeżych (2003) algorytmach dla algebry macierzowej nad wielomianami. Pokażę jak znaleźć najcięższe skojarzenie ważone w grafie w czasie O(Cn^omega), gdzie C jest największa waga krawędzi w grafie.

14.04.2005 Wojtek Plandowski

Zbior testowy dla jezyka jest podzbiorem tego jezyka o pewnych silnych wlasnosciach. Twierdzenie Ehrenfeuchta mowi, ze kazdy jezyk posiada skonczony zbior testowy. Nic jednak nie mowi o rozmiarze zbioru testowego. Na seminarium omowie znane dolne i gorne granice na rozmiary zbiorow testowych dla rodziny wszystkich jezykow, rodziny jezykow przemiennych, rodziny jezykow regularnych i rodziny jezykow bezkontekstowych.

21.04.2005 Wojtek Plandowski

Ciąg dalszy.

28.04.2005 Maciek Kurowski

Opowiem o kilku twierdzeniach dotyczących rysowania grafów. Między innymi o bardzo ładnym tw. Schnydera i rysowaniu grafów łamanymi z dobrą rozdzielczością kontową.

Indeks

Ostatnio aktualizowane 05/11/2004