Aspectos algorítmicos de geometría semialgebraica

Mostrar todas las versiones(3)

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

Descripción completa

Guardado en:

Detalles Bibliográficos
Autor principal:	Perrucci, Daniel
Otros Autores:	Sabia, Juan
Formato:	Tesis doctoral publishedVersion
Lenguaje:	Español
Publicado:	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales 2008
Materias:	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 SYMBOLIC COMPUTATION NASH EQUILIBRIA
Acceso en línea:	https://hdl.handle.net/20.500.12110/tesis_n4354_Perrucci https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n4354_Perrucci_oai
Aporte de:	Repositorio Digital de la Universidad de Buenos Aires (UBA) de Universidad de Buenos Aires

id	I28-R145-tesis_n4354_Perrucci_oai
record_format	dspace
spelling	I28-R145-tesis_n4354_Perrucci_oai2024-09-02 Sabia, Juan Jeronimo, Gabriela Perrucci, Daniel 2008 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. 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. Fil: Perrucci, Daniel. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. application/pdf https://hdl.handle.net/20.500.12110/tesis_n4354_Perrucci 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 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 Aspectos algorítmicos de geometría semialgebraica Algorithmic aspects in semialgebraic geometry info:eu-repo/semantics/doctoralThesis info:ar-repo/semantics/tesis doctoral info:eu-repo/semantics/publishedVersion https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n4354_Perrucci_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	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
spellingShingle	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 Perrucci, Daniel Aspectos algorítmicos de geometría semialgebraica
topic_facet	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
description	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.
author2	Sabia, Juan
author_facet	Sabia, Juan Perrucci, Daniel
format	Tesis doctoral Tesis doctoral publishedVersion
author	Perrucci, Daniel
author_sort	Perrucci, Daniel
title	Aspectos algorítmicos de geometría semialgebraica
title_short	Aspectos algorítmicos de geometría semialgebraica
title_full	Aspectos algorítmicos de geometría semialgebraica
title_fullStr	Aspectos algorítmicos de geometría semialgebraica
title_full_unstemmed	Aspectos algorítmicos de geometría semialgebraica
title_sort	aspectos algorítmicos de geometría semialgebraica
publisher	Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales
publishDate	2008
url	https://hdl.handle.net/20.500.12110/tesis_n4354_Perrucci https://repositoriouba.sisbi.uba.ar/gsdl/cgi-bin/library.cgi?a=d&c=aextesis&d=tesis_n4354_Perrucci_oai
work_keys_str_mv	AT perruccidaniel aspectosalgoritmicosdegeometriasemialgebraica AT perruccidaniel algorithmicaspectsinsemialgebraicgeometry
_version_	1824354882715385856

Aspectos algorítmicos de geometría semialgebraica

Ejemplares similares