Catálogo de publicaciones - tesis
Título de Acceso Abierto
Sobre la complejidad en espacio y tiempo de la eliminación geométrica
Guillermo Matera Joos Heintz
publishedVersion.
Resumen/Descripción – provisto por el repositorio digital
Se estudia la complejidad en espacio y tiempo de los procedimientos de eliminación geométrica tanto desde el punto de vista algorítmico como del de la complejidad computacional. Desde el punto de vista algorítmico, se desarrollan algoritmos determinísticos que resuelven algunos de los principales problemas de eliminación y requieren bajo recursos de espacio de memoria. Posteriormente se desarrolla una clase de algoritmos probabiísticos cuyo comportamiento en cuanto al tiempo es superior, que es capaz de distinguir sistemas bien condicionados de sistemas mal condicionados. Desde el punto de vista de la complejidad computacional, se demuestra una cota inferior para el tradeoff espacio-tiempo de los procedimientos de evaluación de polinomios y se exhiben varios casos naturales donde se alcanza esta cota. Finalmente se demuestra que todos los métodos generalistas existentes sobre el tema y todas sus posibles variantes requieren tiempo exponencial.Palabras clave – provistas por el repositorio digital
ELIMINACION; ALGORITMOS; COMPLEJIDAD; TRADEOFFS; CIRCUITOS; ELEMINATION; ALGORITHMS; COMPLEXITY; CIRCUITS
Disponibilidad
| Institución detectada | Año de publicación | Navegá | Descargá | Solicitá |
|---|---|---|---|---|
| No requiere | 1997 | Biblioteca Digital (FCEN-UBA) (SNRD) |
|
Información
Tipo de recurso:
tesis
Idiomas de la publicación
- español castellano
País de edición
Argentina
Fecha de publicación
1997
Información sobre licencias CC
