Od macierzy odwrotnoścci do dynamicznych najkrótszych ścieżek

Prelegent(ci)

Piotr Sankowski

Afiliacja

Uniwersytet Warszawski

Termin

28 października 2004 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

W trakcie seminarium przedstawię najważniejsze elementy konstrukcji algorytmów dla dynamicznego liczenia macierzy odwrotnej oraz ich zastosowanie do liczenia dynamicznego domknięcia przechodniego. Konstrukcja ta daje asymptotyczne najszybsze znane algorytmy dla tego problemu. W drugiej części seminarium opowiem o rozszerzeniach przedstawionych metod 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.

---