Season 2004/2005, Thursday 12:15-13:45, room 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±.

Index

Last updated on 05/11/2004