Registro:
| Documento: | Tesis Doctoral |
| Disciplina: | matematica |
| Título: | Complejidad de conjuntos semialgebraicos |
| Autor: | Solernó, Pablo Luis |
| Editor: | Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales |
| Filiación: | Instituto Argentino de Matemática (IAM)
|
| Publicación en la Web: | 2019-03-29 |
| Fecha de defensa: | 1989 |
| Fecha en portada: | 1989-03 |
| Grado Obtenido: | Doctorado |
| Título Obtenido: | Doctor en Ciencias Matemáticas |
| Director: | Heintz, Joos |
| Idioma: | Español |
| Formato: | PDF |
| Handle: |
http://hdl.handle.net/20.500.12110/tesis_n2213_Solerno |
| PDF: | https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n2213_Solerno.pdf |
| Registro: | https://bibliotecadigital.exactas.uba.ar/collection/tesis/document/tesis_n2213_Solerno |
| Ubicación: | Dep.002213 |
| Derechos de Acceso: | Esta obra puede ser leída, grabada y utilizada con fines de estudio, investigación y docencia. Es necesario el reconocimiento de autoría mediante la cita correspondiente. Solernó, Pablo Luis. (1989). Complejidad de conjuntos semialgebraicos. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de http://hdl.handle.net/20.500.12110/tesis_n2213_Solerno |
Resumen:
Sea L el lenguaje de primer orden sobre cuerpos real-cerrados. Para cada fórmula ɸ є L si P c Z [x1,...,xn] es el conjunto de polinomios que aparecen en ɸ notamos σ (ɸ): = 2 + ΣpєP deg (P) y |ɸ| := longitud de ɸ. 1. Se exhibe un algoritmo que elimina cuantificadores en L (y en particular descompone cilíndricamente R^n). Para cualquier fórmula ɸ en n-variables dicho algoritmo funciona en tiempos: σ(ɸ)² °(n)+o(|ɸ|) (secuencial) y 2°(n)log2^4σ(ɸ)+O(log2|ɸ|) (paralelo). Se muestra además que estas cotas superiores son optimales. 2. Dado un conjunto semialgebráico A descrito por ecuaciones e inecuaciones sobre una familia finita de polinomios F c Z [x1,...,xn], se construye un sistema de representantes para las componentes convexas de A por medio de un algoritmo que funciona en tiempos: d^n°(¹) (secuencial) y (n log2^d) °(¹) (paralelo), donde d := ΣpєP deg P. 3. Se exhibe un algoritmo tal que, dada ɸ є L, sin variables libres y escrita en forma prenexa, con r := número de bloques de cuantificadores, se decide la verdad o falsedad de ɸ en tiempos: σ(ɸ)^n°(r) (secuencial) y n°(r) (log σ(ɸ))°(¹) (paralelo).
Citación:
---------- APA ----------
Solernó, Pablo Luis. (1989). Complejidad de conjuntos semialgebraicos. (Tesis Doctoral. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales.). Recuperado de https://hdl.handle.net/20.500.12110/tesis_n2213_Solerno
---------- CHICAGO ----------
Solernó, Pablo Luis. "Complejidad de conjuntos semialgebraicos". Tesis Doctoral, Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales, 1989.https://hdl.handle.net/20.500.12110/tesis_n2213_Solerno
Estadísticas:
Descargas totales desde :
Descargas mensuales
https://bibliotecadigital.exactas.uba.ar/download/tesis/tesis_n2213_Solerno.pdf
