Tesis > Documento


Ver el documento (formato PDF)   Perrucci, Daniel.  "Aspectos algorítmicos de geometría semialgebraica"  (2008)
Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
URL:
     
Resumen:
Esta tesis versa sobre distintos aspectos algorítmicos de geometría semialgebraica; más concretamente, sobre la resolución efectiva de sistemas de ecuaciones e inecuaciones polinomiales sobre el cuerpo de los números reales. El trabajo se encuentra dividido en tres capítulos en los que se consideran problemas encuadrados en este marco general. En el primer capítulo, estudiamos cotas inferiores de complejidad para los algoritmos de resolución de ecuaciones polinomiales sobre los reales. Probamos resultados relacionados con la intratabilidad tanto de decidir la existencia como de aproximar las raíces reales para polinomios univariados con coeficientes enteros codificados vía straight-line programs. En el segundo capítulo presentamos nuevos métodos probabilísticos para decidir la existencia de soluciones de un sistema de ecuaciones e inecuaciones polinomiales sobre los reales y para encontrar puntos en el conjunto de soluciones de estos sistemas. La complejidad de estos métodos mejora la de los algoritmos anteriores conocidos que resuelven el mismo problema. Finalmente, en el tercer capítulo estudiamos un problema proveniente de la teoría de juegos que se modela mediante sistemas de ecuaciones e inecuaciones polinomiales sobre los reales. Para tratar con estos sistemas, desarrollamos métodos específicos de manera de aprovechar las particularidades que presentan.

Abstract:
This thesis deals with different algorithmic aspects in semialgebraic geometry; more precisely, with the effective resolution of polynomial systems of equations and inequalities over the real numbers. The thesis is divided into three chapters in which problems within this general frame are considered. In the first chapter, we study lower bounds for the complexity of algorithms solving polynomial equation systems over the real numbers. We prove some results related to the intractability of both the problem of deciding the existence of real roots and the problem of approximating real roots of univariate polynomials with integer coefficients encoded by straight-line programs. In the second chapter, we present new probabilistic methods to decide the existence of solutions to polynomial systems of equations and inequalities over the real numbers and to find points in the solution sets of these systems. The complexity of these methods is lower than the ones of the previous known algorithms solving the same problem. Finally, in the third chapter, we study a problem from game theory that can be modeled by means of polynomial systems of equations and inequalities over the real numbers. To deal with these systems, we develop specific methods in order to exploit the particularities they present.

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

Registro:
Título : Aspectos algorítmicos de geometría semialgebraica     =    Algorithmic aspects in semialgebraic geometry
Autor : Perrucci, Daniel
Director : Sabia, Juan
Jeronimo, Gabriela
Consejero : Sabia, Juan
Jurados : Rojas, Maurice  ; Cukierman, Fernando  ; Dickenstein, Alicia
Año : 2008
Editor : Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
Filiación : Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
Grado obtenido : Doctor de la Universidad de Buenos Aires en el área de 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_4354_Perrucci
Idioma : Español
Area Temática : Matemática / Álgebra
Palabras claves : SISTEMAS DE ECUACIONES E INECUACIONES POLINOMIALES; TEORIA DE COMPLEJIDAD; STRAIGHT-LINE PROGRAMS; CALCULO SIMBOLICO; EQUILIBRIOS DE NASH; POLYNOMIAL SYSTEMS OF EQUATIONS AND INEQUALITIES; COMPLEXITY THEORY; STRAIGHT-LINE PROGRAMS; SYMBOLIC COMPUTATION; NASH EQUILIBRIA
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