Catálogo de publicaciones - tesis
Título de Acceso Abierto
Análisis probabilístico de algoritmos y problemas combinatorios sobre cuerpos finitos
Mariana Valeria Pérez Guillermo Matera
publishedVersion.
Resumen/Descripción – provisto por el repositorio digital
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.Palabras clave – provistas por el repositorio digital
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
Disponibilidad
| Institución detectada | Año de publicación | Navegá | Descargá | Solicitá |
|---|---|---|---|---|
| No requiere | 2016 | Biblioteca Digital (FCEN-UBA) (SNRD) |
|
Información
Tipo de recurso:
tesis
Idiomas de la publicación
- español castellano
País de edición
Argentina
Fecha de publicación
2016-12-06
Información sobre licencias CC
