Tesis > Documento


Ver el documento (formato PDF)   Matera, Guillermo.  "Sobre la complejidad en espacio y tiempo de la eliminación geométrica"  (1997)
Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
URL:
     
Resumen:
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.

Abstract:
The space-time complexity of geometric elimination procedures is studied from both the algorithmic and the computational complexity point of view. From the algorithmic point of view, deterministic algorithms are developed which solve some of the main elimination problems and require small space resources. Afterwards, a class of probabilistic algorithms is developed which has a better time performance and is able to distinguish well conditionated from ill-posed systems. From the computational complexity point of view, an optimal lower bound for the space-time tradeoff of polynomial evaluation procedures is shown and several natural cases where this bound is reached are exhibited. Finally, all the existent general purpose methods on the subject and all their posible variants are proved to require exponential time.

* A este resumen le pueden faltar caracteres especiales. Consulte la versión completa en el documento en formato PDF

Registro:
Título : Sobre la complejidad en espacio y tiempo de la eliminación geométrica     =    On the space-time complexity of geometric elimination
Autor : Matera, Guillermo
Director : Heintz, Joos
Año : 1997
Editor : Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Filiación : Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
Departamento de Matemática
Grado obtenido : Doctor en Ciencias Matemáticas
Ubicación : Preservación - http://digital.bl.fcen.uba.ar/gsdl-282/cgi-bin/library.cgi?a=d&c=tesis&d=Tesis_2931_Matera
Idioma : Español
Area Temática : 
Palabras claves : ELIMINACION; ALGORITMOS; COMPLEJIDAD; TRADEOFFS; CIRCUITOS; ELEMINATION; ALGORITHMS; COMPLEXITY; TRADEOFFS; CIRCUITS
URL al Documento : 
URL al Registro : 
hola chau _gs.DocumentHeader_ chau2 _documentheader_ chau3
Estadísticas:
     http://digital.bl.fcen.uba.ar
Biblioteca Central Dr. Luis Federico Leloir - Facultad de Ciencias Exactas y Naturales - Universidad de Buenos Aires
Intendente Güiraldes 2160 - Ciudad Universitaria - Pabellón II - C1428EGA - Tel. (54 11) 4789-9293 int 34