Sobre la complejidad en espacio y tiempo de la eliminación geométrica

Mostrar todas las versiones(3)

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

Descripción completa

Detalles Bibliográficos
Autor principal: Matera, Guillermo
Formato: Tesis Doctoral
Lenguaje:Español
Publicado: 1997
Materias:
ELIMINACION
ALGORITMOS
COMPLEJIDAD
TRADEOFFS
CIRCUITOS
ELEMINATION
ALGORITHMS
COMPLEXITY
CIRCUITS
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n2931_Matera
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:tesis_n2931_Matera
record_format dspace
spelling todo:tesis_n2931_Matera2023-10-03T12:34:41Z Sobre la complejidad en espacio y tiempo de la eliminación geométrica On the space-time complexity of geometric elimination Matera, Guillermo ELIMINACION ALGORITMOS COMPLEJIDAD TRADEOFFS CIRCUITOS ELEMINATION ALGORITHMS COMPLEXITY TRADEOFFS CIRCUITS 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. 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. Fil: Matera, Guillermo. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 1997 Tesis Doctoral PDF Español info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n2931_Matera
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Español
orig_language_str_mv Español
topic ELIMINACION
ALGORITMOS
COMPLEJIDAD
TRADEOFFS
CIRCUITOS
ELEMINATION
ALGORITHMS
COMPLEXITY
TRADEOFFS
CIRCUITS
spellingShingle ELIMINACION
ALGORITMOS
COMPLEJIDAD
TRADEOFFS
CIRCUITOS
ELEMINATION
ALGORITHMS
COMPLEXITY
TRADEOFFS
CIRCUITS
Matera, Guillermo
Sobre la complejidad en espacio y tiempo de la eliminación geométrica
topic_facet ELIMINACION
ALGORITMOS
COMPLEJIDAD
TRADEOFFS
CIRCUITOS
ELEMINATION
ALGORITHMS
COMPLEXITY
TRADEOFFS
CIRCUITS
description 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.
format Tesis Doctoral
author Matera, Guillermo
author_facet Matera, Guillermo
author_sort Matera, Guillermo
title Sobre la complejidad en espacio y tiempo de la eliminación geométrica
title_short Sobre la complejidad en espacio y tiempo de la eliminación geométrica
title_full Sobre la complejidad en espacio y tiempo de la eliminación geométrica
title_fullStr Sobre la complejidad en espacio y tiempo de la eliminación geométrica
title_full_unstemmed Sobre la complejidad en espacio y tiempo de la eliminación geométrica
title_sort sobre la complejidad en espacio y tiempo de la eliminación geométrica
publishDate 1997
url https://hdl.handle.net/20.500.12110/tesis_n2931_Matera
work_keys_str_mv AT materaguillermo sobrelacomplejidadenespacioytiempodelaeliminaciongeometrica
AT materaguillermo onthespacetimecomplexityofgeometricelimination
_version_ 1807315973500305408

Ejemplares similares