Research and doctorate seminar A L G O R Y T M I K A

Season 2003/2004, Thursday 12:15-13:45, room 5870

09.10.2003 Krzysztof Diks

Spotkanie organizacyjne

Ustalenie planu referatów. Osoby referuj±ce proszone s± o nadsylanie streszczeñ referatów do publikacji na stronie.

16.10.2003 Robert D±browski

Równania w pó³grupie wolnej

Problem rozwi±zywania równañ w pó³grupie wolnej z 2 niewiadomymi.

23.10.2003 Rafa³ Dowgird

Przydzia³ czêstotliwo¶ci w sieciach radiowych.

Streszczenie

30.10.2003 Tomek Waleñ

Sortowanie przez odwracanie

Problem sortowania permutacji przez odwracanie. Przegl±d znanych wyników, przedstawienie wyników w³asnych i problemów otwartych.

06.11.2003 Maciek Kurowski

Greedy Algorithms for Dynamic Graph Problems

We deal with the following fully dynamic problems in sparse graphs (of bounded arboricity): We show how to maintain a vertex coloring using at most $O(\sqrt[6]{n})$ colors and support edge insertions/deletions in $O(\sqrt{n})$ amortized time. We show how to maintain an $O(\sqrt[3]{n})$-orientation and support edge insertions/deletions in $O(1)$ amortized time.

13.11.2003 Piotr Sankowski

Dwa dok³adne algorytmy zliczania

W trakcie seminarium opowiem o dwóch wielomianowych algorytmach zliczaj±cych: algorytmie zliczania drzew rozpinaj±cych w dowolnych grafach, oraz algorytmie zliczania doskonal³ych skojarzeñ w grafach planarnych. Obydwa algorytmy obrazuj± wykozystanie kombinatorycznych wla¶ciwosci wyznacznika do zliczania.

20.11.2003 Karol Go³±b

Temat

Streszczenie

27.11.2003 £ukasz Sznuk

Temat

Streszczenie

04.12.2003 Artur Ratyñski

Wyszukiwanie zewnetrzne przy pomocy drzew GiST.

Drzewa GiST (ang. Generalized Index Search Tree) pozwalaja na indeksowanie roznorodnych typow danych. Stanowia swoisty szablon, ktorego realizacje moga sie zachowywac identycznie jak, na przyklad: B+-drzewa, R-drzewa, RD-drzewa, k-D-B-drzewa, Ch-drzewa, hB-drzewa, V-drzewa, TV-drzewa, itd.

11.12.2003 Staszek Pa¶ko

Temat

Streszczenie

18.12.2003 Franciszek Grzegorek

Równania na jêzykach

Kilka problemów dotycz±cych równañ, a takze nierówno¶ci (zawieranie) na jêzykach.

08.01.2004 £ukasz Kowalik

Kolorowanie grafów planarnych bez trójk±tów

Streszczenie

15.01.2004 Marcin Mucha

Temat

Streszczenie

Przerwa miedzysemestralna

19.02.2004 Franciszek Grzegorek

Równania i nierówno¶ci w pó³grupach zbiorów s³ów

Opowiem o dwóch problemach. Pierwszy dotyczy nierówno¶ci (zawieranie siê wyra¿enia regularnego z niewiadomymi w wyra¿eniu regularnym bez niewiadomych) i jest PSPACE-zupe³ny, drugi dotyczy równo¶ci (wyra¿enie regularne z niewiadomymi = wyra¿enie regularne bez niewiadomych) i jest EXPSPACE-zupe³ny.

26.02.2004 Tomasz Tyrakowski

Modele grafowe w sieciach bezprzewodowych

Streszczenie

04.03.2004 Krzysiek Ciebiera

Temat

Streszczenie

11.03.2004

Jerzy Mycka, Instytut Matematyki, UMCS

Referat bêdzie dotyczy³ zagadnienia formalizacji obliczalno¶ci analogowej poprzez pojêcie rzeczywistych funkcji rekurencyjnych. Najpierw zostanie omówiony kontekst badañ prowadzonych w tym kierunku (General Purpose Analog Computer - C. Shannon, Extended Analog Computer - L. Rubel, funkcje ró¿niczkowalne algebraiczne). Nastêpnie zostanie wprowadzona i poddana analizie definicja funkcji R-rekurencyjnych (C. Moore). Wskazane zostan± w³asno¶ci i znaczenie przej¶æ granicznych w kontek¶cie obliczalno¶ci w czasie ci±g³ym.

18.03.2004

Semianrium siê nie odbêdzie

Streszczenie

25.03.2004

Seminarium siê nie odbêdzie

Streszczenie

01.04.2004

Seminarium siê nie odbêdzie

Streszczenie

08.04.2004

Kuba Pawlewicz

Streszczenie

15.04.2004

Workshop on broadcasting in radio networks

Workshop odbêdzie siê w godzinach 10-14 w sali Rady Wydzia³u. Jest dostêpna strona workshopu .

22.04.2004

Rafa³ Dowgird

Streszczenie

29.04.2004

£ukasz Sznuk

Streszczenie

06.05.2004

Piotr Sankowski

Streszczenie

13.05.2004

Marcin Mucha

Streszczenie

20.05.2004

Tomek Waleñ

Streszczenie

27.05.2004

Maciek Kurowski

Streszczenie

Index

Last updated on 18/03/2004

Robert Dabrowski