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

Guardado en:
Detalles Bibliográficos
Autor principal: Matera, Guillermo
Otros Autores: Heintz, Joos
Formato: Tesis doctoral publishedVersion
Lenguaje:Español
Publicado: Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 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
http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n2931_Matera_oai
Aporte de:
Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires
id I28-R145-tesis_n2931_Matera_oai
record_format dspace
spelling I28-R145-tesis_n2931_Matera_oai2023-04-26 Heintz, Joos Matera, Guillermo 1997 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. application/pdf https://hdl.handle.net/20.500.12110/tesis_n2931_Matera spa Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar ELIMINACION ALGORITMOS COMPLEJIDAD TRADEOFFS CIRCUITOS ELEMINATION ALGORITHMS COMPLEXITY TRADEOFFS CIRCUITS Sobre la complejidad en espacio y tiempo de la eliminación geométrica On the space-time complexity of geometric elimination info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n2931_Matera_oai
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-145
collection Repositorio Digital de la Universidad de Buenos Aires (UBA)
language Español
orig_language_str_mv spa
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.
author2 Heintz, Joos
author_facet Heintz, Joos
Matera, Guillermo
format Tesis doctoral
Tesis doctoral
publishedVersion
author 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
publisher Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate 1997
url https://hdl.handle.net/20.500.12110/tesis_n2931_Matera
http://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n2931_Matera_oai
work_keys_str_mv AT materaguillermo sobrelacomplejidadenespacioytiempodelaeliminaciongeometrica
AT materaguillermo onthespacetimecomplexityofgeometricelimination
_version_ 1766015473205379072

Ejemplares similares