Kombinatoryczny algorytm obliczania wyznacznika

Prelegent(ci)

Anna Urbańska

Afiliacja

Uniwersytet Warszawski

Termin

17 listopada 2005 12:15

Pokój

p. 5870

Seminarium

Seminarium "Algorytmika"

---

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).

---