No description available.

Esta tesis consiste en un estudio histórico sobre la evolución reciente del diseño estructural. Parte de la hipótesis de que la búsqueda de la eficacia y la optimización de las estructuras, emprendida en el siglo XVII con el nacimiento de la Era Moderna, continúa hasta nuestros días y ha provocado en los últimos 60 años el surgimiento de un nuevo nivel de complejidad en la geometría, el diseño, el cálculo y la fabricación de los proyectos arquitectónicos. Supone además que esta búsqueda tiene como principal objetivo la producción de estructuras bellas, racionales y económicas. Específicamente, pretende realizar un análisis del modo en que la búsqueda de la eficacia y la optimización de las estructuras ha evolucionado a lo largo de la segunda mitad del siglo XX y principios del siglo XXI bajo la influencia de nuevos conceptos surgidos a partir del desarrollo de las teorías científicas enmarcadas en la Teoría General de Sistemas, tales como complejidad, azar, autoorganización, emergencia, nolinealidad y fractalidad. El trabajo ha sido dividido en tres partes de modo de analizar la evolución reciente de tres tipologías estructurales que, si bien no abarcan la totalidad de los tipos estructurales empleados en la arquitectura, han sido consideradas como representativas de lo acontecido en la evolución reciente de la disciplina. Dichas tipologías han sido denominadas como estructuras de barras, estructuras superficiales y estructuras aporticadas. En las investigaciones recientes sobre la eficacia de las estructuras arquitectónicas se observa una adopción recurrente de los conceptos de autoorganización y de fractalidad. En las búsquedas recientes sobre la optimización de las estructuras arquitectónicas, consideradas como uno de los tantos componentes constructivos que necesitan ser coordinados en una obra arquitectónica, se observa una tendencia al diseño integrado de dispositivos capaces de responder a múltiples funciones, a la coordinación espacial jerárquica de los programas arquitectónicos con los huecos que la estructura genera y al diseño algorítmico.

No description available.

Esta reseña no presenta resumen.

Ingeniero Civil Matemático / En muchos problemas que surgen en el contexto de consultar información en bases de datos estructuradas sobre grafos (como encontrar asociaciones semanticas en grafos RDF, encontrar emparejamientos exactos o aproximados the patrones de texto, realizar alineación de secuencias de texto, etc.) es un requerimiento común el buscar entidades unidas por secuencias de etiquetas relacionales de acuerdo a un patrón regular. Para este propósito, el lenguaje de consulta $\CRPQ(\S)$ ha sido propuesto para extender la altamente estudiada clase de consultas conjuntivas por caminos regulares (CRPQs por su sigla en inglés), la cual es insuficiente para esta tarea, realizando comparación de caminos con relaciones en la clase $\S$.\\ Poco es conocido acerca de la complejidad computacional precisa de la evaluación de consultas en $\CRPQ(\S)$ cuando $\S$ es una relación de interés por aparecer naturalmente en aplicaciones en bases de datos, como lo son \emph{subsecuencia} ($\ss$), \emph{sufijo} $(\suff)$ y \emph{subpalabra} ($\sw$). Esta pregunta es consecuentemente estudiada en esta tesis, proporcionando nuevas cotas de complejidad para la evaluación de consultas en los lenguajes $\CRPQ(\ss)$, $\CRPQ(\suff)$ y $\CRPQ(\sw)$. Se muestra que el primer lenguaje es dificil de ser practicable, construyendo una consulta en él cuya complejidad de evaluación es $\NP$-completo. Se muestra también que la evaluación de consultas en los últimos dos lenguajes puede realizarse en $\PSPACE$, mediante la reducción del problema a \emph{ecuaciones de palabras con restricciones regulares}. Adicionalmente, se muestra que la classe $\CRPQ(\suff)$ es práctica, construyendo un algoritmo de evaluación cuya complejidad, cuando la consulta es considerada una constante, está en $\NLOGSPACE$ , la cuál es una complejidad de evaluación estandar en este contexto.\\ Esta tesis plantea además interesantes preguntas teóricas sobre ecuaciones de palabras con restricciones regulares. Más precisamente, cuál es la complejidad de resolver ecuaciones fijas con restricciones como entrada, la cual es una pregunta abierta en la literatura al leal saber y entendimiento del autor. Un resultado es establecido para el caso más simple, mostrando una clase de ecuaciones cuya satisfacibilidad con restricciones regulares puede ser decidida en $\NLOGSPACE$.

Encontrar buenas cotas inferiores y condiciones necesarias para nociones de complejidad y universalidad es uno de los mayores desafíos en el área de la informática teórica. En este sentido, la teoría de la complejidad comunicacional ha resultado ser una herramienta útil para abordar tal problemática en diversos modelos de computación, tales como circuitos booleanos, máquinas de Turing y modelos no convencionales. En este trabajo se incorporan tales técnicas al estudio del conjunto de autómatas celulares unidimensionales. Dada una relación de simulación ≤ y autómatas celulares (ACs) Φ y Ψ, se denota Φ ≤ Ψ si es el caso que Φ puede ser simulado por Ψ. Un AC Ψ capaz de simular a todo otro AC Φ es denominado como intrínsecamente ≤ - universal. Aquí son considerados tres tipos de simulaciones presentes en la literatura: sobreyectiva, inyectiva y mixta, siendo las dos últimas capaces de soportar universalidad intrínseca. Por otro lado, para la primera de éstas, la existencia de un elemento universal aún sigue siendo un problema abierto. Seguidamente, son definidos cinco problemas comunicacionales inducidos por ACs: Pred, Cycl, SInv, TInv y CInv, de tal manera que PΦ(x, y) indica la parametrización de un problema genérico P por un AC Φ, donde AΦ es el conjunto de estados de éste y x, y ϵ AΦ+ son inputs. Tales problemas cumplen con ser compatibles comunicacionalmente, esto es, si Ψ simula a Φ, se tiene que la complejidad comunicacional asociada a Φ es de menor o igual orden a la de Ψ. De este modo, si la complejidad comunicacional de PΦ es de orden estrictamente menor a la de PΨ, se puede deducir que Φ no es intrínsecamente universal. Luego, como punto fuerte, se introduce una nueva problemática comunicacional que logra aunar las técnicas y condiciones necesarias previamente estudiadas. Informalmente, cuando Alice y Bob (los participantes en el modelo usual de complejidad comunicacional) reciben respectivamente inputs x e y, tienen la posibilidad de escoger qué problema P resolver. Se entregan resultados mostrando que tal libertad hace de este nuevo problema, denominado Ovrl, un potente filtro a la hora de desechar ACs como intrínsecamente universales. Más precisamente, se construye un AC con complejidad máxima en los cinco problemas anteriores y complejidad constante en Ovrl. Finalmente, se utilizan las herramientas desarrolladas para descartar en familias completas de autómatas celulares la cualidad de universalidad intrínseca. Además, se estudia la estructura de los preórdenes dados por las relaciones de simulación, caracterizando algunos conjuntos cerrados bajo simulación, tales como los ACs sobreyectivos, cerrados y reversibles, entre otros.

No description available.

Para que se puedan construir rumbos de acción en ambientes reales, se debe considerar que las acciones pueden tener efectos distintos en el mundo (no determinismo) y ponderar el potencial de algún plan alternativo para alcanzar las metas del problema, considerando sus costes y recompensas (metas extendidas). Al respecto, la planificación basada en teoría de decisiones ha permitido solucionar problemas estocásticos, estableciendo rumbos de acción que involucran cantidades de información difíciles de procesar por el ser humano, evaluando sus fortalezas y debilidades con base en las teorías de probabilidad y de utilidad. Esta metodología ha incrementado últimamente su investigación debido al éxito de los procesos de decisión de Markov (MDPs) en problemas de investigación de operaciones, teoría de control, economía e inteligencia artificial, entre otros. Sin embargo, el problema de resolver los MDPs de considerables dimensiones con precisión y rapidez ha conducido a un reto computacional. Dado que el esfuerzo computacional es significativo, la investigación actual se centra en la búsqueda de técnicas superiores de aceleración. Por ejemplo, las propiedades de convergencia de sus métodos de solución actuales dependen, en gran medida, del orden de las operaciones de actualización. Por un lado, algoritmos tales como el de ordenamiento topológico han sido capaces de encontrar buenos ordenamientos, pero sus costes de inicio han sido usualmente altos. Por otro lado, los métodos de ruta más corta tales como el clásico algoritmo de Dijkstra, que está basado en colas de prioridad, han sido aplicados exitosamente a la solución de procesos de decisión de Markov de ruta determinística más corta. En esta tesis se propone un nuevo algoritmo de iteración de valor basado en el algoritmo de Dijkstra para resolver MDPs de ruta estocástica más corta. A diferencia de otros enfoques priorizados tales como el barrido priorizado mejorado, el enfoque aquí propuesto es capaz de tratar con múltiples estados meta y de inicio y, puesto que sucesivamente se actualiza cada estado utilizando la ecuación de Bellman, este enfoque garantiza la convergencia a la solución óptima. Además este algoritmo utiliza la función de valor actual como métrica de prioridad, puesto que el algoritmo de Dijkstra sugiere que un orden de actualización más adecuado está dado por el valor de la programación dinámica funcional. Los resultados experimentales obtenidos en una tarea de estrategias de navegación marítima en bote de vela muestran la factibilidad del enfoque propuesto. Se comprobó que el algoritmo propuesto reduce considerablemente el tiempo de solución requerido por el algoritmo de iteración de valor, desde un crecimiento de orden cuadrático -en función del número de estados- hasta uno de orden cercano a la linealidad. / García Hernández, MDG. (2013). Simplificación de los procesos de decisión de Markov mediante reglamentación de acciones y priorización de estados [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/18467 / Palancia

Tesis para optar al grado de Doctor en Ciencias, Mención Computación / Los refinamientos actuales del análisis del peor caso sobre instancias con tamaño de entrada fijo consideran el orden de la entrada (por ejemplo, las subsecuencias ordenadas en una secuencia de números y las cadenas poligonales simples en las que puede dividirse una secuencia de puntos) o la estructura de la entrada (por ejemplo, la multiplicidad de los elementos en un multiconjunto y las posiciones relativas entre un conjunto de puntos en el plano), pero nunca, hasta donde sabemos, ambos al mismo tiempo. En esta tesis se proponen nuevas técnicas que combinan soluciones que se aprovechan del orden y la estructura de la entrada en una sola solución sinérgica para ordenar multiconjuntos, y para calcular la eficiencia de Pareto y la envoltura convexa de un conjunto de puntos en el plano. Estas soluciones sinérgicas se aprovechan del orden y la estructura de la entrada de tal forma que asintóticamente superan cualquier solución comparable que se aproveche solo de una de estas características. Como resultados intermedios, se describen y analizan varios algoritmos de mezcla: un algoritmo para mezclar secuencias ordenadas que es óptimo para cada instancia del problema; el primer algoritmo adaptativo para mezclar eficiencias de Pareto; y un algoritmo adaptativo para mezclar envolturas convexas en el plano. Estos tres algoritmos se basan en un paradigma donde las estructuras se dividen antes de ser mezcladas. Este paradigma es conveniente para extenderlo al contexto donde se responden consultas. Karp et al. (1998) describieron estructuras de datos diferidas como estructuras "perezosas" que procesan la entrada gradualmente a medida que responden consultas sobre los datos, trabajando la menor cantidad posible en el peor caso sobre instancias de tamaño fijo y número de consultas fijo. En esta tesis se desarrollan nuevas técnicas para refinar aún más estos resultados y aprovechar al mismo tiempo el orden y la estructura de la entrada y el orden y la estructura de la secuencia de consultas en tres problemas distintos: calcular el rango y la posici\'on de un elemento en un multiconjunto, determinar si un punto está dominado por la eficiencia de Pareto de un conjunto de puntos en el plano y determinar si un punto pertenece a la envoltura convexa de un conjunto de puntos en el plano. Las estructuras de datos diferidas que se obtienen superan todas las soluciones previas que solo se aprovechan de un subconjunto de estas características. Como una extensión natural a los resultados sinérgicos obtenidos en este trabajo para ordenar un multiconjunto, se describen estructuras de datos comprimidas que se aprovechan del orden y la estructura de la entrada para representar un multiconjunto, mientras se responden consultas del rango y la posición de elementos en el multiconjunto. / CONICYT-PCHA/Doctorado Nacional/2013-63130161, y los proyectos CONICYT Fondecyt/Regular nos 1120054 y 1170366

Como resultado del constante aumento del tráfico de información, en los últimos años la industria de las telecomunicaciones ha evolucionado de manera vertiginosa. Este hecho exige el diseño de nuevos transceptores de comunicaciones digitales que permitan aumentar la velocidad de procesamiento. Este incremento de velocidad en combinación con las limitaciones del ancho de banda del canal de comunicaciones, exacerban los efectos de la interferencia inter-símbolo (Intersymbol Interference - ISI). Para compensar este efecto se requiere implementar en el receptor potentes esquemas de ecualización. El ecualizador realimentado por decisiones (Decison Feedback Equalizer - DFE) representa una de técnicas de ecualización más utilizadas en la industria. El DFE se caracteriza por tener una buena relación entre desempeño y complejidad. Desafortunadamente, su aplicación en sistemas de alta velocidad ha sido limitada debido a la elevada complejidad que aparece cuando se utilizan técnicas de procesamiento en paralelo como resultado de la existencia de lazos realimentados. En particular, la complejidad de las técnicas existentes incrementa exponencialmente con la memoria del canal. Esto lleva a restringir el uso de este tipo de ecualizadores para una ISI moderada. La presente Tesis propone un nuevo esquema de ecualización iterativo de complejidad reducida para receptores de alta velocidad. El nuevo ecualizador directo asistido por decisiones (Decision FeedForward Equalizer - DFFE) permite obtener un rendimiento similar al DFE pero con una arquitectura paralelizable cuya complejidad aumenta cuadráticamente con la memoria del canal. Para canales con gran ISI, esto se traduce en una drástica reducción de la complejidad en comparación con el DFE. La idea central detrás del DFFE, es la iteración de decisiones tentativas para mejorar la precisión de la estimación de la ISI. Para investigar el desempeño del nuevo receptor se desarrolla un estudio teórico y se lo verifica por exhaustivas simulaciones en computadora. Como una segunda contribución de la Tesis se presenta un detallado análisis de complejidad del procesamiento y además se realiza la implementación en FPGA del DFFE en paralelo. Este estudio permite demostrar los importantes beneficios que tiene utilizar una arquitectura de implementación directa (forward) y además verificar experimentalmente el desempeño del DFFE. Todas estas ventajas convierten al DFFE en una excelente opción para receptores de sistemas de comunicaciones digitales de alta velocidad. / As a result of the steady increase in data traffic, the telecommunications industry has evolved dramatically in recent years. In this context, new digital communications transceivers that outperform processing speed are required. This speed increase combined with the limitations of the bandwidth communications channel exacerbate the impacts of the intersymbol interference (ISI). In order to compensate for this effect, it is necessary to implement efficient receiver equalization schemes. The decision feedback equalizer (DFE) is one of the most popular equalization techniques in industry, featuring a good relationship between performance and complexity. Unfortunately, its use in high speed systems has been limited due to the high complexity reached when processing techniques are used in parallel as a result of the existence of feedback loops. In particular, the complexity of the existing techniques increases exponentially with the channel memory, leading to a restriction in the use of such equalizers for moderate ISI. This Thesis proposes a new scheme of reduced complexity iterative equalization for high-speed receivers. The new Decision FeedForward Equalizer (DFFE) allows for a similar performance to the DFE but with a parallelizable architecture whose complexity increases quadratically with the channel memory. For channels with large ISI, this results in a drastic reduction in complexity compared to the DFE. The main feature of the DFFE is the iteration of tentative decisions to improve the accuracy of the ISI estimation. With the purpose of investigating the performance of the new receiver, a theoretical study is developed and the DFFE is verified by extensive computer simulations. The second contribution of the present Thesis is a detailed analysis of processing complexity and the implementation in FPGA of parallel DFFE. This study allows to demonstrate the important benefits of using a forward implementation architecture and verify experimentally the performance of DFFE. All these advantages make the DFFE an excellent choice for system receivers of digital high-speed communications.