Shortest paths - exact and approximate algorithms
Prowadzi: Prof. Uri Zwick (Tel Aviv University).
O wyk�adowcy | Streszczenie | Materia�y dla student�w | Zadania zaliczeniowe
O wyk�adowcy:
Uri Zwick jest profesorem Wydzia�u Informatyki Uniwersytetu w Tel Avivie,
kt�rym kierowa� w latach 2000-2002.
Wcze�niej wyk�ada� i prowadzi� badania m. in. w University of Warwick (Anglia)
oraz University of California in Berkeley (USA).
Jest autorem ponad 100 prac naukowych w dziedzinie algorytmiki, opublikowanych
w najlepszych �wiatowych czasopismach. Ma na swoim koncie szeroko znane wyniki
z takich dziedzin jak randomizacja czy algorytmy dla problem�w najkr�tszych
�cie�ek w grafach.
Wielokrotnie by� cz�onkiem komitet�w programowych czo�owych konferencji
z informatyki teoretycznej takich jak ICALP, SODA czy FOCS, a w 2003 roku
kierowa� pracami komitetu programowego konferencji ESA.
Wypromowa� sze�ciu doktor�w.
Streszczenie: The two lectures of the mini-course would cover exact and approximate algorithms for the all-pairs shortest paths problem and some of its variants. The first lecture would focus on exact algorithms for the all-pairs shortest paths problem that rely on the use of fast matrix multiplication algorithms. The second lecture would focus on faster combinatorial algorithms for approximating distances. Distance oracles and spanners would also be considered.
- Wyk�ady 9.03 i 10.03 [PDF] [PPT]
- Zadania na �wiczenia 10.03 [PDF]
- Wyk�ady 27.04 i 28.04 [PPT]
- Zadania na �wiczenia 28.04 [PDF]
Zadania zaliczeniowe [PDF]
Prosimy o przesy�anie rozwiazan w plikach PDF na adres zwick at tau dot ac dot
il do 31 maja 2007.