Tesis > Documento


Ver el documento (formato PDF)   Pérez, Mariana Valeria.  "Análisis probabilístico de algoritmos y problemas combinatorios sobre cuerpos finitos"  (2016-12-06)
Facultad de Ciencias Exactas y Naturales. Universidad de Buenos Aires
URL:
     
Resumen:
En esta tesis analizamos la complejidad en promedio de dos algoritmos probabilísticos. Uno de ellos calcula puntos Fq-racionales de hipersuperficies definidas sobre el cuerpo finito Fq de q elementos en base a una estrategia de "búsqueda en bandas verticales". El otro es el algoritmo clásico de factorización de polinomios univariados con coeficientes en Fq. En este caso nos interesa su comportamiento cuando se aplica a familias de polinomios cuyos coeficientes satisfacen ciertas relaciones lineales. A fin de realizar dichos análisis, proporcionamos estimaciones explícitas del promedio del cardinal del conjunto de valores y la distribución de patrones de factorización en familias lineales de polinomios sobre cuerpos finitos. Los resultados expuestos, que mejoran los existentes en la literatura sobre el tema, se basan en un nuevo enfoque, que reduce estas cuestiones combinatorias a la estimación del número de puntos Fq-racionales de ciertas intersecciones completas singulares. Por tal motivo, parte de esta tesis se centra en el estudio de ciertas propiedades geométricas de dichas variedades.

Abstract:
In this thesis we analyze the average-case complexity of two probabilistic algorithms. The first one computes Fq-rational points of an hysuperface defined over the finite field Fq of q elements based on a search strategy in "vertical strips". The second one is the classical factorization algorithm for univariate polynomials with coeficients in Fq. In this case we are interested in the behavior of the algorithm applied to families of polynomials whose coeficients satisfy certain linear relations. For this purpose, we obtain explicit estimates on the average cardinality of the value set and on the distribution of factorization patterns on linear families of polynomials over a finite field. The above results, which improve the existing results in the literature, were obtained with a new approach that reduces these combinatorial issues to estimating the number of Fq-rational points of certain singular complete intersections. For this reason, part of this thesis focuses on the study of certain geometric properties of these varieties.

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

Registro:
Título : Análisis probabilístico de algoritmos y problemas combinatorios sobre cuerpos finitos     =    Probabilistic analysis of algorithms and combinatorial problems over finite fields
Autor : Pérez, Mariana Valeria
Director : Matera, Guillermo
Director Asistente : Cesaratto, Eda
Consejero : Solernó, Pablo
Jurados : Jerónimo, Gabriela  ; D´Andrez, Carlos  ; Pacharoni, María Inés
Año : 2016-12-06
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
Universidad Nacional de General Sarmiento (UNGS). Instituto del Desarrollo Humano
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_6121_Perez
Idioma : Español
Area Temática : 
Palabras claves : COMPLEJIDAD EN PROMEDIO; ALGORITMOS PROBABILISTICOS; FAMILIAS LINEALES DE POLINOMIOS CON COEFICIENTES EN UN CUERPO FINITO; CONJUNTO DE VALORES; PATRONES DE FACTORIZACION; INTERSECCIONES COMPLETAS SINGULARES; LUGAR SINGULAR; PUNTOS RACIONALES; AVERAGE-CASE COMPLEXITY; PROBABILISTIC ALGORITHMS; LINEAR FAMILIES OF POLYNOMIALS OVER FINITE FIELDS; VALUE SETS; FACTORIZATION PATTERNS; SINGULAR COMPLETE INTERSECTIONS; SINGULAR LOCUS; FQ-RATIONAL POINTS
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