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