Previous seasons [2000/2001] [2001/2002] [2002/2003] [2003/2004] [2004/2005]

Season 2005/2006, Thursday 12:15-13:45, room 5870

06.10.2005 £ukasz Kowalik

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 bardzo ciekawych problemów otwartych -- przede wszystkim teoriografowych, ale równie¿ algorytmicznych. Lesistosæ (ang. arboricity) grafu to najczêsciej stosowana miara rzadko¶ci/gêstosci grafu. Problem mierzenia lesistosci jest wielomianowy, ale najlepsze znane algorytmy opieraja siê na metodach przeplywowych i maja z³o¿ono¶æ rzedu O(m^3/2). Je¶li starczy czasu druga czê¶æ seminarium poswiêcê na zreferowanie efektywnych algorytmow aproksymacyjnych dla problemu mierzenia lesistosci oraz pokrewnego problemu znajdowania optymalnej orientacji grafu. Tu takze opiszê kilka otwartych problemów (my¶lê ¿e du¿o prostszych ni¿ te zwi±zane z kolorowaniem listowym).

13.10.2005 Miros³aw Kowaluk

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 problemie najbli¿szego przodka w grafie acyklicznym pragniemy mo¿liwie szybko odpowiadaæ na pytanie, który z wierzcho³ków grafu jest najbli¿szym wspólnym przodkiem dwóch dowolnie wybranych wierzcho³ków tego grafu. W tym celu stosujemy preprocessing umo¿liwiaj±cy odpowied¼ na to pytanie w czasie sta³ym. Dotychczas najlepszy algorytm wykonywa³ preprocessing w czasie O(n^{(\omega+3)/2}, gdzie \omega=2,376. Z Andrzejem Lingasem poprawili¶my nieco ten wynik do O(n^{2+(1/(4-\omega))}.

20.10.2005 Marcin Pêczarski

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ê elementów do porównania, a przeciwnik wskazuje nam kolejno.æ tych elementów. Wskazane porównanie dzieli mo¿liwy zbiór rozszerzeñ liniowych na dwa roz³.czne podzbiory. Czyli gra polega na tym, ¿e w ka¿dym kroku my wybieramy podzia³ zbioru rozszerzeñ liniowych, a przeciwnik wskazuje ten podzbiór, który zawiera poszukiwane rozszerzenie liniowe. Gra koñczy siê, gdy pozostanie zbiór jednoelementowy. Omówiê trzy problemy badawcze, którymi siê zajmujê. 1. Hipoteza o z³otym podziale Sformu³ujê hipotezê o z³otym podziale porz.dku czê.ciowego. Prawdziwo.æ tej hipotezy implikuje prawdziwo.æ bardzo znanej hipotezy 1/3--2/3 oraz ciasn. górn. granicê dla sortowania porz.dków czê.ciowych. Przedstawiê wybrane wyniki badañ, w tym moje, nad dowodami powy¿szych hipotez. 2. Najgorzej zbalansowane porz.dki - drabiny z powy³amywanymi szczeblami Do.æ naturaln., choæ nie zawsze optymaln., strategi. sortowania porz.dku czê.ciowego jest wskazywanie podzia³u zbioru jego rozszerzeñ liniowych na mo¿liwie równoliczne podzbiory. Z³o.liwy przeciwnik, staraj.c siê utrudniæ nam zadanie, bêdzie wybiera³ podzbiór o wiêkszej mocy. Wspó³czynnik zbalansowania porz.dku czê.ciowego okre.la, jak bliski idealnemu (na równoliczne podzbiory) podzia³ mo¿emy wskazaæ. Zatem istotne jest pytanie, jak ¥le mo¿e byæ zbalansowany porz.dek czê.ciowy. Brightwell [1999] wskaza³ znane mu najgorzej zbalansowane porz.dki czê.ciowe. Przedstawiê, znalezion. za pomoc. komputera, nieskoñczon. klasê gorzej zbalansowanych porz.dków czê.ciowych. 3. Sortowanie z minimaln. liczb. porównañ Interesuje nas minimalna liczba porównañ, zawsze wystarczaj.ca do posortowania n elementów. Wiadomo, ¿e dla n < 12 i n = 20, 21 minimum to realizuje algorytm Forda-Johnsona. Algorytm ten jest równie¿ optymalny dla n = 12 [Wells 1969] oraz n = 13, 14, 15, 22 [Peczarski 2002,2004]. Najmniejsz. liczb. elementów, dla której znamy algorytm lepszy od algorytmu Forda-Jonhnsona, jest n = 47 [Moenting 1981]. Przedstawiê aktualny stan moich poszukiwañ najmniejszego n, dla którego algorytm Forda-Johnsona nie jest optymalny.

27.10.2005 Piotr Sankowski

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 jak mno¿enie macierzy rozmiaru n na n. Wynik ten zosta³ jednoczesnie przedstawony w pracach ,,Answering distance queries in directed graphs using fast matrix multiplication'' Raphael Yuster i Uri Zwick (FOCS'05) oraz ,,Shortest Paths in Matrix Multiplication Time'' Piotr Sankowski (ESA'05). Druga czê¶æ seminarium bêdzie po¶wiêcona obliczaniu odleg³o¶ci miêdzy wszystkimi parami wierzcho³ków w grafie. Skoncentrujê siê na przestawieniu wyników zawartych w pracy ,,All Pairs Shortest Paths in weighted directed graphs'' Uri Zwick (FOCS'98).

10.11.2005 Krzysztof Ciebiera

Opowiem o:
Motywacji dla istnienia takich struktur danych bior±cych siê z zastosowañ certyfikatów w Internecie.
Tradycyjnych metodach tworzenia po¶wiadczonych s³owników.
Najlepszych obecnie metodach implementacji po¶wiadczonych s³owników za pomoc± skip-list dzia³aj±cych w czasie 1.25log n+O(1).
Innych znanych zastosowaniach po¶wiadczonych struktur danych w geometrii i algorytmach grafowych.

17.11.2005 Anna Urbanska

Tematem referatu jest kombinatoryczna charakteryzacja wyznacznika, daj±ca prosty i ca³kowicie kombinatoryczny algorytm na jego obliczanie, dzia³aj±cy w czasie O(n^4). Algorytm ten nie wymaga dzielenia i pracuje nad dowolnym pier¶cieniem przemiennym. Postaram siê równie¿ pokazaæ, jak wykorzystuj±c algorytm szybkiego mno¿enia macierzy poprawiæ z³o¿ono¶æ czasow± tego algorytmu. Na koniec opowiem jak w analogiczny sposób mo¿na scharakteryzowaæ wszystkie pozosta³e wspó³czynniki wielomianu charakterystycznego oraz Pfaffian dowolnej macierzy sko¶no-symetrycznej oraz podam kombinatoryczne dowody poprawno¶ci znanych algorytmów obliczania wyznacznika (Chistova, Csanky'ego oraz Samuelsona).

24.11.2005 Wojciech Plandowski

Streszczenie

01.12.2005 Wojciech Plandowski

Kontynuacja seminarium z 24.11.2005

01.12.2005 Marcin Stefaniak

SilkRoute (2002) s³u¿y do wyci±gania danych z relacyjnej bazy (SQL) w postaci drzewiastej (XML) przy u¿yciu jêzyka zapytañ XQuery. Odbywa siê to poprzez stworzenie drzewiastego planu zapytañ SQL, co mo¿na zrobiæ na wiele sposobów. SilkRoute w celu optymalizacji planu zapytañ u¿ywa heurystycznych szacunków oraz zach³annego algorytmu, co przynosi zadowalaj±ce praktycznie rezultaty. Interesuj±ce, czy mo¿na dla tej z ¿ycia wziêtej sytuacji stworzyæ pewien (uproszczony) model matematyczny, tak aby ów problem algorytmiczny da³ siê ³adnie zanalizowaæ.

08.12.2005 Arek Paterek

Na seminarium omówiê w³asne eksperymenty zwi±zane z zastosowaniem technik uczenia z nadzorem do wyboru parametrów funkcji oceniaj±cej w programie graj±cym w szachy. Opowiem równie¿ o algorytmie BPIP, obiecuj±cej alternatywie dla algorytmu alfa-beta ciêæ. Jest to algorytm typu best-first search, oparty na teorii decyzji. Funkcja oceniaj±ca w algorytmie BPIP zwraca dla li¶ci drzewa rozk³ad prawdopodobieñstwa. Rozk³ady s± propagowane do korzenia drzewa przeszukiwania, zgodnie z regu³± minimaksow±. Przeszukiwanie polega na rozwijaniu li¶ci, które maj± najwiêkszy wp³yw na oczekiwan± wyp³atê. Dodatkow± zalet± algorytmu BPIP jest jasne kryterium zakoñczenia przeszukiwania.

15.12.2005 Krzysztof Diks

Streszczenie

05.01.2006 Krzysztof Onak

W sytuacji, gdy dysponujemy ograniczon± ilo¶ci± czasu, mo¿e nie byæ mo¿liwe sprawdzenie, czy dany obiekt (kombinatoryczny) posiada, pewn± ustalon± w³asno¶æ.
Tym niemniej nie jeste¶my ca³kowicie bezradni. Okazuje siê, ¿e w wielu przypadkach, odczytuj±c jedynie niewielki fragment danych opisuj±cych obiekt, mo¿emy z du¿ym prawdopodobieñstwem rozró¿niæ obiekty posiadaj±ce zadan± w³asno¶æ od tych, które nale¿a³oby znacznie zmodyfikowaæ, aby tê w³asno¶æ posiad³y. Takie podej¶cie nazywa siê zwyczajowo "testowaniem w³asno¶ci" (ang. property testing).
Skupiê siê na przyk³adach zwi±zanych z testowaniem wymiarowo¶ci danych, ale nie zapomnê o ho³ubionych na Uniwersytecie Warszawskim grafach i zaprezentujê przyk³adowe, bardzo ogólne twierdzenia dotycz±ce testowania w³asno¶ci grafowych.
Testowanie w³asno¶ci znajduje zastosowania w obszarach takich jak algorytmy aproksymacyjne, teoria kodów, uczenie maszynowe.
Przy okazji opowiem równie¿, jak wygl±da, z krótkiej pó³rocznej perspektywy czasu, studiowanie na MIT, czym tam siê ludzie zajmuj±, a tak¿e z przyjemno¶ci± odpowiem na wszelkie inne pytania.

12.01.2006 Dorota Cendrowska

W ramach seminarium zostan± poruszone kwestie dotycz±ce odpowiedzi na nastêpuj±ce pytania: Jak ludzie radz± sobie z problemem automatycznego rozdzielania liniowego dwóch zbiorów? Trop 1: Mo¿e "liniowo" to synonim "zbyt ³atwo: i sprawdza siê regu³a garbage rule garbage out jako parafraza regu³y garbage in garbage out? Trop 2: Co to w ogóle znaczy "rozdzielaæ zbiory liniowo"? Trop 3: Czego potrzebowaliby¶my do szczê¶cia, aby jednak algorytm rozdzielania liniowo dwóch zbiorów móc nazwaæ "u¿ytecznym"? Czy matematyka mo¿e byæ lekarstwem na ca³e to z³o? Algorytm badania liniowej rozdzielno¶ci a konstrukcja klasyfikatora -- dwa podej¶cia. Czy z tego wszystkiego jest jaki¶ mora³?

19.01.2006 Paulina Kania

Postaram siê krótko omówiæ co to s± algorytmy rozproszone i w jakich sytuacjach siê je spotyka. Model z przesy³aniem komunikatów. Krótki przegl±d podstawowych algorytmów rozproszonych: broadcast, gossip, consensus, wybór lidera. Rodzaje b³êdów w systemach rozproszonych. Analiza algorytmu consensusu w modelu synchronicznym oraz broadcastu w modelu asynchronicznym.

26.01.2006 Anna Wojak

Wyznaczanie Euklidesowej najkrótszej ¶cie¿ki jest jednym z najstarszych i dobrze znanych problemów w geometrii obliczeniowej. Obecnie istnieje wiele typów problemów zwi±zanych z wyznaczaniem najkrótszych dróg. Rozwa¿my p³aszczyznê zawieraj±ca zbiór roz³±cznych przeszkód, których liczba wierzcho³ków wynosi n oraz dany punkt ¼ród³a s. Problemem jest wyznaczenie najkrótszej drogi z punktu s do wszystkich punktów wolnej przestrzeni. Znane s± dwie g³ówne metody wyznaczania najkrótszych ¶cie¿ek: visibility graph (VG) oraz shortest path map (SPM) po³±czone z algorytmami Dijkstra oraz A*. Shortest path map polega na specjalnym podziale p³aszczyzny na obszary ukorzenione w wierzcho³kach przeszkód. Obszary te s± wyznaczane za pomoc± rozchodzenia siê czo³a fali frontowej z punktu ¼ród³a s na ca³± p³aszczyznê po¶ród wielok±tnych przeszkód. Na pocz±tku lat dziewiêædziesi±tych J.S.B. Mitchell pokaza³, ¿e wyznaczenie SPM wymaga O(n^{3/2} + \epsilon) dla \epsilon > 0. Nastêpnie Jonh Hersberger oraz Subhash Suri zaproponowali optymalny algorytm dla SPM dzia³aj±cy w najgorszym przypadku w czasie O(nlogn) i wymagaj±cy O(nlogn) pamiêci. Kluczowym pomys³em ich algorytmu jest specjalny podzia³ p³aszczyzny zwany conforming subdividion, który mo¿e byæ wyznaczony w czasie O(n+nlogn).

Last updated on 21/11/2005