Registro:
| Documento: | Tesis Doctoral |
| Disciplina: | matematica |
| Título: | Sobre la complejidad en espacio y tiempo de la eliminación geométrica |
| Título alternativo: | On the space-time complexity of geometric elimination |
| Autor: | Matera, Guillermo |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Filiación: | Departamento de Matemática
|
| Publicación en la Web: | 2017-03-01 |
| Fecha de defensa: | 1997 |
| Fecha en portada: | 1997 |
| Grado Obtenido: | Doctorado |
| Título Obtenido: | Doctor en Ciencias Matemáticas |
| Director: | Heintz, Joos |
| Idioma: | Español |
| Palabras clave: | ELIMINACION; ALGORITMOS; COMPLEJIDAD; TRADEOFFS; CIRCUITOSELEMINATION; ALGORITHMS; COMPLEXITY; TRADEOFFS; CIRCUITS |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/tesis_n2931_Matera |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n2931_Matera.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n2931_Matera |
| Ubicación: | Dep.002931 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Matera, Guillermo. (1997). Sobre la complejidad en espacio y tiempo de la eliminación geométrica. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/tesis_n2931_Matera |
Resumen:
Se estudia la complejidad en espacio y tiempo de los procedimientos deeliminación geométrica tanto desde el punto de vista algorítmico como delde la complejidad computacional. Desde el punto de vista algorítmico, se desarrollan algoritmos determinísticosque resuelven algunos de los principales problemas de eliminacióny requieren bajo recursos de espacio de memoria. Posteriormente se desarrollauna clase de algoritmos probabiísticos cuyo comportamiento en cuantoal tiempo es superior, que es capaz de distinguir sistemas bien condicionadosde sistemas mal condicionados. Desde el punto de vista de la complejidad computacional, se demuestrauna cota inferior para el tradeoff espacio-tiempo de los procedimientosde evaluación de polinomios y se exhiben varios casos naturales donde sealcanza esta cota. Finalmente se demuestra que todos los métodos generalistasexistentes sobre el tema y todas sus posibles variantes requieren tiempoexponencial.
Abstract:
The space-time complexity of geometric elimination procedures is studiedfrom both the algorithmic and the computational complexity point of view. From the algorithmic point of view, deterministic algorithms are developedwhich solve some of the main elimination problems and require smallspace resources. Afterwards, a class of probabilistic algorithms is developedwhich has a better time performance and is able to distinguish well conditionatedfrom ill-posed systems. From the computational complexity point of view, an optimal lower boundfor the space-time tradeoff of polynomial evaluation procedures is shown andseveral natural cases where this bound is reached are exhibited. Finally, allthe existent general purpose methods on the subject and all their posiblevariants are proved to require exponential time.
Citación:
---------- APA ----------
Matera, Guillermo. (1997). Sobre la complejidad en espacio y tiempo de la eliminación geométrica. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n2931_Matera
---------- CHICAGO ----------
Matera, Guillermo. "Sobre la complejidad en espacio y tiempo de la eliminación geométrica". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 1997.https://hdl.handle.net/20.500.12110/tesis_n2931_Matera
Estadísticas:
Descargas totales desde :
Descargas mensuales
https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n2931_Matera.pdf
