Análisis probabilístico de algoritmos y problemas combinatorios sobre cuerpos finitos

Mostrar todas las versiones(3)

En esta tesis analizamos la complejidad en promedio de dos algoritmos probabilísticos. Uno de ellos calcula puntos Fq-racionales de hipersuperficies definidassobre el cuerpo finito Fq de q elementos en base a una estrategia de "búsqueda enbandas verticales". El otro es el algoritmo clásico...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autor principal: Pérez, Mariana Valeria
Formato: Tesis Doctoral
Lenguaje:Español
Publicado: 2016
Materias:
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
Acceso en línea:https://hdl.handle.net/20.500.12110/tesis_n6121_Perez
Aporte de:
Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA) de Universidad de Buenos Aires
id todo:tesis_n6121_Perez
record_format dspace
spelling todo:tesis_n6121_Perez2023-10-03T13:05:11Z Análisis probabilístico de algoritmos y problemas combinatorios sobre cuerpos finitos Probabilistic analysis of algorithms and combinatorial problems over finite fields Pérez, Mariana Valeria 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 En esta tesis analizamos la complejidad en promedio de dos algoritmos probabilísticos. Uno de ellos calcula puntos Fq-racionales de hipersuperficies definidassobre el cuerpo finito Fq de q elementos en base a una estrategia de "búsqueda enbandas verticales". El otro es el algoritmo clásico de factorización de polinomios univariadoscon coeficientes en Fq. En este caso nos interesa su comportamiento cuandose aplica a familias de polinomios cuyos coeficientes satisfacen ciertas relacioneslineales. A fin de realizar dichos análisis, proporcionamos estimaciones explícitas del promediodel cardinal del conjunto de valores y la distribución de patrones de factorización en familias lineales de polinomios sobre cuerpos finitos. Los resultadosexpuestos, que mejoran los existentes en la literatura sobre el tema, se basan en unnuevo enfoque, que reduce estas cuestiones combinatorias a la estimación del númerode puntos Fq-racionales de ciertas intersecciones completas singulares. Por talmotivo, parte de esta tesis se centra en el estudio de ciertas propiedades geométricasde dichas variedades. In this thesis we analyze the average-case complexity of two probabilistic algorithms. The first one computes Fq-rational points of an hysuperface defined overthe finite field Fq of q elements based on a search strategy in "vertical strips". Thesecond one is the classical factorization algorithm for univariate polynomials withcoeficients in Fq. In this case we are interested in the behavior of the algorithmapplied to families of polynomials whose coeficients satisfy certain linear relations. For this purpose, we obtain explicit estimates on the average cardinality of thevalue set and on the distribution of factorization patterns on linear families of polynomialsover a finite field. The above results, which improve the existing results inthe literature, were obtained with a new approach that reduces these combinatorialissues to estimating the number of Fq-rational points of certain singular completeintersections. For this reason, part of this thesis focuses on the study of certaingeometric properties of these varieties. Fil: Pérez, Mariana Valeria. Universidad de Buenos Aires. Facultad de Ciencias Exactas y Naturales; Argentina. 2016 Tesis Doctoral PDF Español info:eu-repo/semantics/openAccess https://creativecommons.org/licenses/by-nc-sa/2.5/ar https://hdl.handle.net/20.500.12110/tesis_n6121_Perez
institution Universidad de Buenos Aires
institution_str I-28
repository_str R-134
collection Biblioteca Digital - Facultad de Ciencias Exactas y Naturales (UBA)
language Español
orig_language_str_mv Español
topic 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
spellingShingle 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
Pérez, Mariana Valeria
Análisis probabilístico de algoritmos y problemas combinatorios sobre cuerpos finitos
topic_facet 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
description En esta tesis analizamos la complejidad en promedio de dos algoritmos probabilísticos. Uno de ellos calcula puntos Fq-racionales de hipersuperficies definidassobre el cuerpo finito Fq de q elementos en base a una estrategia de "búsqueda enbandas verticales". El otro es el algoritmo clásico de factorización de polinomios univariadoscon coeficientes en Fq. En este caso nos interesa su comportamiento cuandose aplica a familias de polinomios cuyos coeficientes satisfacen ciertas relacioneslineales. A fin de realizar dichos análisis, proporcionamos estimaciones explícitas del promediodel cardinal del conjunto de valores y la distribución de patrones de factorización en familias lineales de polinomios sobre cuerpos finitos. Los resultadosexpuestos, que mejoran los existentes en la literatura sobre el tema, se basan en unnuevo enfoque, que reduce estas cuestiones combinatorias a la estimación del númerode puntos Fq-racionales de ciertas intersecciones completas singulares. Por talmotivo, parte de esta tesis se centra en el estudio de ciertas propiedades geométricasde dichas variedades.
format Tesis Doctoral
author Pérez, Mariana Valeria
author_facet Pérez, Mariana Valeria
author_sort Pérez, Mariana Valeria
title Análisis probabilístico de algoritmos y problemas combinatorios sobre cuerpos finitos
title_short Análisis probabilístico de algoritmos y problemas combinatorios sobre cuerpos finitos
title_full Análisis probabilístico de algoritmos y problemas combinatorios sobre cuerpos finitos
title_fullStr Análisis probabilístico de algoritmos y problemas combinatorios sobre cuerpos finitos
title_full_unstemmed Análisis probabilístico de algoritmos y problemas combinatorios sobre cuerpos finitos
title_sort análisis probabilístico de algoritmos y problemas combinatorios sobre cuerpos finitos
publishDate 2016
url https://hdl.handle.net/20.500.12110/tesis_n6121_Perez
work_keys_str_mv AT perezmarianavaleria analisisprobabilisticodealgoritmosyproblemascombinatoriossobrecuerposfinitos
AT perezmarianavaleria probabilisticanalysisofalgorithmsandcombinatorialproblemsoverfinitefields
_version_ 1782028692993605632

Ejemplares similares