Ilość operacji arytmetycznych, liczenie wyznacznika

adambak · Post autor: **adambak** » 30 gru 2011, o 16:01

Uzasadnij, że wyznacznik macierzy \(\displaystyle{ A \in \mathbb{R}^{n,n}}\) można obliczyć wykonując \(\displaystyle{ O(n^3)}\) operacji arytmetycznych.

jeśli miałbym pisać taki program to byłoby to oczywiste.. napisałoby się eliminację Gaussa i na koniec liniowo iloczyn elementów na diagonali.. a sam Gauss to oczywiście \(\displaystyle{ O(n^3)}\) bo byśmy mieli trzy pętle (druga zagnieżdżona w pierwszej a trzecia w drugiej).. ale jak takie rzeczy pokazuje się ściśle matematycznie?

szw1710 · Post autor: **szw1710** » 30 gru 2011, o 16:28

Po prostu przeanalizuj algorytm Gaussa i policz potrzebne do wykonania operacje arytmetyczne. Najpierw na prostych macierzach 2x2, potem 3x3, a wreszcie ogólnie. Dostaniesz konkretny wzór na liczbę operacji arytmetycznych.

adambak · Post autor: **adambak** » 30 gru 2011, o 16:30

to już zrobiłem.. myślałem, że to się jakoś super pokazuje.. pseudokod programu może być dowodem?

szw1710 · Post autor: **szw1710** » 30 gru 2011, o 16:32

Czyli taki program quasi-pascalowy? Ja nie jestem specem od informatyki. Ala raczej nie. Optowałbym za wyprowadzeniem wzoru. I w informatyce są dowody matematyczne.

adambak · Post autor: **adambak** » 30 gru 2011, o 16:39

wiem, w Cormenie ich dużo.. ale w informatyce też coś takiego (trzy pętle jedna w drugiej) byłoby straszną oczywistością, że to złożoność sześcienna..

ale dzięki bo faktycznie nie ma wielkiej finezji w wyprowadzeniu dokładnego wzoru znowu za szybko zrezygnowałem z przemyślenia, echh..