Algoritmo de Strassen - Multiplicación de matrices PDF

Preview

Summary

Multiplicación de matrices...

Description

UNIVERSIDAD NACIONAL MAYOR DE SAN MARCOS

GRUPO INTEGRANTES :

Universidad del Perú, DECANA DE AMÉRICA

 CHAVEZ GUERRERO, GABRIEL ALEXANDER

FACULTAD

F. INGENIERÍA DE SISTEMAS E INFORMÁTICA CURSO

Algorítmica 3

 FERNANDEZ FIGUEROA, JOSE ALBERTO

 GARCIA JARA, ROSA MIRELLY

 GONZALES DURAN, JEFFERSON ERVYN  HERMENEGILDO FLORES, FRANCO JOSSEP

ALGORITMO DE SCHONHAGE-STRASSEN En la disciplina matemática del álgebra lineal, el algoritmo de Strassen, llamado así por Volker Strassen, es un algoritmo usado para la multiplicación de matrices. Es asintóticamente más rápido que el algoritmo de multiplicación de matrices estándar, pero más lento que el algoritmo más rápido conocido, y es útil en la práctica para matrices grandes.

n k =b b

n =7k 7

⇒

PROBLEMA k

Como n ≠ 2 n ⇒n → T ( n) en lugar de t(2 ) k

Como n=2 , se sigue que k =log n T ( n )=T (2 T ( n )=7

logn

)

log n+ 1

Por propiedad : 7log n=7 log 7 log n+¿ 1 ¿ T ( n )=4.7

1

T ( n )=4.7 .7

log n

T ( n )=4.7 . n2.81 ∴T ( n) ϵ O(n

2.81

)

2...