Usando la descomposición de un grafo Halin para el diseño de algoritmos autoestabilizantes

Using Halin graph decomposition for the design of self-stabilizing algorithm

Daniel Uriel Orozco Lomelí (2023, [Tesis de maestría])

Sea G = (V, E) un grafo no dirigido. El problema de encontrar un conjunto independiente fuerte en G, es identificar un conjunto S ⊆ V , tal que dados dos vértices arbitrarios de S, éstos estén separados entre sí por el menos tres aristas. Encontrar un conjunto S de tamaño máximo pertenece a la clase NP-Difícil. Por otro lado, el problema de encontrar un conjunto dominante total en G es identificar un conjunto D ⊆ V , tal que cualquier vértice en V tenga al menos un vecino que pertenezca a D. Encontrar un conjunto D de tamaño mínimo también pertenece a la clase NP-Difícil. En este trabajo de tesis se diseñaron dos algoritmos, uno que resuelve el problema de encontrar un conjunto independiente fuerte maximal y otro que resuelve el problema de encontrar un conjunto dominante total minimal. Estos dos problemas son menos restrictivos que las versiones de optimización descritas al principio de este texto y se sabe que pertenecen a la clase P. Los algoritmos diseñados corren en un sistema distribuido, son autoestabilizantes, son tolerantes a fallas transitorias y funcionan para grafos Halin. Los grafos Halin pertenecen a la clase de grafos 2-outerplanares y tienen la propiedad de que se pueden partir en dos subgrafos muy conocidos, un árbol y un ciclo. Los algoritmos propuestos aprovechan la propiedad anterior para disminuir la complejidad de los mismos. Hasta donde tenemos conocimiento, los algoritmos propuestos, que corren en tiempo lineal en el número de vértices, son los algoritmos más rápidos existentes para los problemas del conjunto independiente fuerte maximal y el conjunto dominante total minimal.

Let G = (V, E) be an undirected graph. The problem of finding a strong stable set in G, is to identify a set S ⊆ V , such that given two arbitrary vertices of S, they are separated from each other by at least three edges. Finding a set S of maximum size belongs to the class NP-Hard. On the other hand, the problem of finding a total dominanting set in G is to identify a set D ⊆ V , such that any vertex in V has at least one neighbor belonging to D. Finding a set D of minimum size also belongs to the class NP-Hard. In this thesis work, two algorithms were designed, one that solves the problem of finding a maximal strong stable set and one that solves the problem of finding a minimal total dominanting set. These two problems are less restrictive than the optimization versions described at the beginning of this text and are known to belong to the P class. The designed algorithms run on a distributed system, are self-stabilizing, are transient fault tolerant, and work for Halin graphs. Halin graphs belong to the 2-outerplanar class of graphs and have the property that they can be split into two well-known subgraphs, a tree and a cycle. The proposed algorithms take advantage of the above property to decrease the complexity of the algorithms. To the best of our knowledge, the proposed algorithms, which run in linear time in the number of vertices, are the fastest existing algorithms for the maximal strong stable set and minimal total dominating set problems.

Grafo Halin, Sistemas Distribuidos, Autoestabilización, Conjunto Independiente Fuerte, Conjunto Dominante Total Halin Graph, Distributed Systems, Self-stabilizing, Strong Stable Set, Total Dominating Set INGENIERÍA Y TECNOLOGÍA CIENCIAS TECNOLÓGICAS TECNOLOGÍA DE LOS ORDENADORES LENGUAJES ALGORÍTMICOS LENGUAJES ALGORÍTMICOS

SOCIO-SPATIAL TRENDS: A GENERAL READING OF PUBLIC SPACE IN HOUSING DEVELOPMENTS

Mariel Organista Camacho Karen Estrella Martínez-Torres Claudia Rivera-Torres (2023, [Artículo, Artículo])

Human nature implies social interaction in diverse environments, where public space, seen as an essential mediator, becomes disconnected, impersonal, and deteriorated exterior spaces, coupled with a lack of interest in participation, inclusion, and personal development. Therefore, this research aimed to analyze the socio-spatial relationships in public spaces based on the inhabitant perception of two housing developments in Ensenada, Baja California, Mexico. This study used a mixed methodological approach to collect information by applying the following instruments: a questionnaire on public spaces, a series of in situ and aerial photographs, and field observations. A total of 196 surveys were applied from 2016 to 2019; the morphological, typological, and functional characteristics of the public space were also observed. The results evidenced an imminent need to carry out their daily activities on a smaller scale and intensity within the housing complex with a level of spatial satisfaction within a scale of 6.37/10. In this regard, the inhabitants reported a higher attendance of the public space use in Los Encinos in contrast to Villas (62.6% and 39.3%, respectively), even though the travel times were shorter in Villas. Regarding the public space usefulness, both cases weighted spatial understanding followed by access ease to the housing complex with a Pearson correlation coefficient equal to or greater than 0.47. In this sense, spatial relations showed dispersion, disorganization, and fragmentation from the ephemeral. In contrast, social relations were considered impersonal, hurried, and of convenience, subordinated to the conditions of the environment, being that personal well-being is built from relations with the exterior and with the collective itself.

Baja California Habitability Public space Social Developments Social-espatial relation conjuntos habitacionales, habitabilidad, Baja California, espacio público, relaciones socioespaciales. HUMANIDADES Y CIENCIAS DE LA CONDUCTA HUMANIDADES Y CIENCIAS DE LA CONDUCTA

Control de sistemas usando aprendizaje de máquina

Systems control using machine learning

Jesús Martín Miguel Martínez (2023, [Tesis de maestría])

El aprendizaje por refuerzo es un paradigma del aprendizaje de máquina con un amplio desarrollo y una creciente demanda en aplicaciones que involucran toma de decisiones y control. Es un paradigma que permite el diseño de controladores que no dependen directamente del modelo que describe la dinámica del sistema. Esto es importante ya que en aplicaciones reales es frecuente que no se disponga de dichos modelos de manera precisa. Esta tesis tiene como objetivo implementar un controlador óptimo en tiempo discreto libre de modelo. La metodología elegida se basa en algoritmos de aprendizaje por refuerzo, enfocados en sistemas con espacios de estado y acción continuos a través de modelos discretos. Se utiliza el concepto de función de valor (Q-función y función V ) y la ecuación de Bellman para resolver el problema del regulador cuadrático lineal para un sistema mecánico masa-resorte-amortiguador, en casos donde se tiene conocimiento parcial y desconocimiento total del modelo. Para ambos casos las funciones de valor son definidas explícitamente por la estructura de un aproximador paramétrico, donde el vector de pesos del aproximador es sintonizado a través de un proceso iterativo de estimación de parámetros. Cuando se tiene conocimiento parcial de la dinámica se usa el método de aprendizaje por diferencias temporales en un entrenamiento episódico, que utiliza el esquema de mínimos cuadrados con mínimos cuadrados recursivos en la sintonización del crítico y descenso del gradiente en la sintonización del actor, el mejor resultado para este esquema es usando el algoritmo de iteración de valor para la solución de la ecuación de Bellman, con un resultado significativo en términos de precisión en comparación a los valores óptimos (función DLQR). Cuando se tiene desconocimiento de la dinámica se usa el algoritmo Q-learning en entrenamiento continuo, con el esquema de mínimos cuadrados con mínimos cuadrados recursivos y el esquema de mínimos cuadrados con descenso del gradiente. Ambos esquemas usan el algoritmo de iteración de política para la solución de la ecuación de Bellman, y se obtienen resultados de aproximadamente 0.001 en la medición del error cuadrático medio. Se realiza una prueba de adaptabilidad considerando variaciones que puedan suceder en los parámetros de la planta, siendo el esquema de mínimos cuadrados con mínimos cuadrados recursivos el que tiene los mejores resultados, reduciendo significativamente ...

Reinforcement learning is a machine learning paradigm with extensive development and growing demand in decision-making and control applications. This technique allows the design of controllers that do not directly depend on the model describing the system dynamics. It is useful in real-world applications, where accurate models are often unavailable. The objective of this work is to implement a modelfree discrete-time optimal controller. Through discrete models, we implemented reinforcement learning algorithms focused on systems with continuous state and action spaces. The concepts of value-function, Q-function, V -function, and the Bellman equation are employed to solve the linear quadratic regulator problem for a mass-spring-damper system in a partially known and utterly unknown model. For both cases, the value functions are explicitly defined by a parametric approximator’s structure, where the weight vector is tuned through an iterative parameter estimation process. When partial knowledge of the dynamics is available, the temporal difference learning method is used under episodic training, utilizing the least squares with a recursive least squares scheme for tuning the critic and gradient descent for the actor´s tuning. The best result for this scheme is achieved using the value iteration algorithm for solving the Bellman equation, yielding significant improvements in approximating the optimal values (DLQR function). When the dynamics are entirely unknown, the Q-learning algorithm is employed in continuous training, employing the least squares with recursive least squares and the gradient descent schemes. Both schemes use the policy iteration algorithm to solve the Bellman equation, and the system’s response using the obtained values was compared to the one using the theoretical optimal values, yielding approximately zero mean squared error between them. An adaptability test is conducted considering variations that may occur in plant parameters, with the least squares with recursive least squares scheme yielding the best results, significantly reducing the number of iterations required for convergence to optimal values.

aprendizaje por refuerzo, control óptimo, control adaptativo, sistemas mecánicos, libre de modelo, dinámica totalmente desconocida, aproximación paramétrica, Q-learning, iteración de política reinforcement learning, optimal control, adaptive control, mechanical systems, modelfree, utterly unknown dynamics, parametric approximation, Q-learning, policy iteration INGENIERÍA Y TECNOLOGÍA CIENCIAS TECNOLÓGICAS TECNOLOGÍA DE LOS ORDENADORES INTELIGENCIA ARTIFICIAL INTELIGENCIA ARTIFICIAL

REAL TIME EMBBEDED RGB-D SLAM USING CNNS FOR DEPTH ESTIMATION AND FEATURE EXTRACTION

Marcos Renato Rocha Hernández (2023, [Tesis de maestría])

"A robust and efficient Simultaneous Localization and Mapping (SLAM) system is essential for intelligent mobile robots to work in unknown environments. For visual SLAM algorithms, though the theoretical framework has been well established for most aspects, feature extraction and association is still empirically de signed in most cases, and can be vulnerable in complex environments. Also, most of the most robust SLAM algorithms rely on special devices like a stereo camera or depth sensors, which can be expensive and give more complexity to the system, that is why monocular depth estimation is an essential task in the computer vision community. This work shows that feature extraction and depth estimation using a monocular camera with deep convolutional neural networks (CNNs) can be incorporated into a modern SLAM framework. The proposed SLAM system utilizes two CNNs, one to detect keypoints in each im age frame, and to give not only keypoint descriptors, but also a global descriptor of the whole image and the second one to make depth estimations from a single image frame, all using only a monocular camera."

SLAM Inteligencia Artificial CNN Sistemas embebidos Redes neuronales Cámara monocular INGENIERÍA Y TECNOLOGÍA CIENCIAS TECNOLÓGICAS TECNOLOGÍA DE LOS ORDENADORES INTELIGENCIA ARTIFICIAL INTELIGENCIA ARTIFICIAL

Monitoreo con drones en gráficas con viento dinámico

Jovanni Manuel López Elisea (2024, [Tesis de maestría])

108 páginas. Maestría en Optimización.

Dada una gráfica completa no dirigida, se desea recorrer un subconjunto de sus aristas usando una flotilla de drones. Los drones tienen baterías limitadas que pueden recargarse al regresar a la base y, en principio, el tiempo para recorrer una arista está en función de la distancia entre sus vértices. Sin embargo, ante la presencia de viento el tiempo de recorrer una arista puede depender del sentido en el que se haga. La dificultad del problema aumenta si además la intensidad del viento puede variar de un instante a otro. En esta tesis se aborda el problema anteriormente descrito para el caso particular en el que los vértices son puntos en el plano, el impacto del viento en los tiempos de recorrido de las aristas está relativamente acotado y el subconjunto de las aristas a recorrer inducen un árbol que abarca todos los vértices excepto la base de los drones. Dado que los drones operan simultáneamente y pueden recorrer distintas partes de la gráfica de manera independiente, se desea minimizar el tiempo que emplea el dron con el recorrido más tardado. Esta tesis presenta un modelo matemático para resolver el problema de manera exacta, así como tres heurísticas diferentes para obtener buenas soluciones factibles. La primera de estas heurísticas transforma una solución sin viento y sin batería en una solución con viento y batería. La segunda heurística es un algoritmo glotón sin comunicación entre los drones y la última heurística también es un algoritmo glotón, pero con comunicación entre los drones. Aunque el problema abordado resulta ser lo suficientemente difícil como para que su resolución exacta sea inviable en la práctica, las heurísticas diseñadas son fáciles de implementar y obtuvieron resultados razonables en un tiempo corto de cómputo.

Drone aircraft--Control systems. Drone aircraft--Mathematical models. Mathematical optimization. Heuristic programming. Dynamical systems. Graph theory. Micro vehículos aéreos. Optimización matemática. Programación heurística. Teoría de grafos. TL589.4 CIENCIAS FÍSICO MATEMÁTICAS Y CIENCIAS DE LA TIERRA MATEMÁTICAS INVESTIGACIÓN OPERATIVA DISTRIBUCIÓN Y TRANSPORTE

Implementación de algoritmos basados en la teoría de grafos en proyectos de sectorización de redes de agua potable

Velitchko Tzatchkov VICTOR HUGO ALCOCER YAMANAKA (2011, [Artículo])

Los proyectos de sectorización de redes de agua potable, en proceso en diferentes ciudades mexicanas actualmente, consisten en dividir la red de la ciudad en varias subredes o sectores más pequeños con una o máximo dos entradas de agua por sector. Para diseñar los sectores se emplean modelos de redes de agua potable que revisan si la sectorización propuesta puede funcionar hidráulicamente de manera adecuada. Para los proyectos de sectorización en redes grandes se requieren, sin embargo, facilidades algorítmicas adicionales, como análisis de conectividad, zona de influencia y contribución de cada fuente sobre el consumo. En el presente artículo se discuten eficientes algoritmos de este tipo basados en la teoría de los grafos, implementados en un sistema de cómputo.

Modelos de redes de distribución Redes de distribución de agua Algoritmos sobre grafos INGENIERÍA Y TECNOLOGÍA

Narrativas de la transgresión : afectos y emociones en los crímenes de odio contra mujeres lesbianas en México

Ytzel Maya (2022, [Tesis de maestría])

"El objetivo principal de esta tesis es analizar cómo se configuran los afectos en la legitimación del odio en los casos de crímenes de odio de mujeres lesbianas en México y qué relación tiene con la configuración de una narrativa política de los efectos (repugnancia, vergüenza y estigma) dentro del Estado".

Violencia contra las mujeres; México; Crímenes de odio; Aspectos sociales; Lesbianismo; Lesiones y agresión; Discriminación CIENCIAS SOCIALES CIENCIA POLÍTICA SISTEMAS POLÍTICOS SISTEMAS POLÍTICOS

Cambio climático: percepciones sobre manifestaciones, causas e impactos en el distrito de temporal tecnificado Margaritas-Comitán, Chiapas

DENISE SOARES ANTONINO GARCIA GARCIA LUIS RICARDO MANZANO SOLIS (2018, [Artículo])

Se exploran percepciones acerca de las manifestaciones del cambio climático, sus causas e impactos en el cotidiano de actores sociales locales en el Distrito de Temporal Tecnificado Margaritas-Comitán (DTT011) ubicado en la Meseta Comiteca, estado de Chiapas, perteneciente a la parte alta de la cuenca del río Usumacinta. Asimismo, se propone argumentar con base en información empírica que, independiente de la aprehensión del concepto de cambio climático, a nivel local se observa, interpreta y siente el impacto de las variaciones en los periodos de lluvia y del incremento del calor, las cuales presentan consecuencias en términos económicos en la zona, toda vez que los sistemas productivos se ven afectados y se pierden cosechas.

Cambio climático Sistemas productivos Vulnerabilidad CIENCIAS SOCIALES

RELACIONES SOCIALES Y TRABAJO EMOCIONAL EN EL ENTRAMADO DE LOS PROCESOS DE SALUD, ENFERMEDAD Y ATENCIÓN: EL CASO DE LAS CONSTELACIONES FAMILIARES EN MÉXICO

CLARA LUZ VILLANUEVA AGUILAR (2024, [Tesis de doctorado])

“Las constelaciones familiares (en adelante CF), como una modalidad o método terapéutico, han tenido un crecimiento importante en las últimas décadas, una muestra concreta es que diferentes plataformas de streaming tienen series completas que se focalizan en las CF o que al menos las presentan como una modalidad terapéutica en boga. Cuando se hace una búsqueda en internet, Google arroja cientos de respuestas, entre ellas: centros de CF, publicaciones, así como diferentes alcaldías de la CDMX, aparecen anuncios de centros de CF incluidas sus actividades. Este hecho en sí es un fenómeno social que es pertinente estudiar, más aún cuando el desarrollo de esta psicoterapia se acrecentó durante el confinamiento a causa de la pandemia por COVID 19, a partir del uso de recursos terapéuticos y digitales, lo cual fue novedoso y también indispensable para la continuidad de su desarrollo. En este sentido, nos interesó comprender qué objetivos llevan a lxs consultantes a utilizar esta terapéutica, cuáles son sus necesidades de salud física, mental y emocional y si están encontrando en esta psicoterapia una eficacia empírica y/o simbólica por la cual los grupos CF están creciendo sostenidamente, aun durante el confinamiento. También consideramos relevante comprender cuáles son los elementos más y menos cuestionables de este tipo de terapia para consultantes y curadorxs, tomando en cuenta que su auge no solo está relacionado a aspectos positivos, ya que existen otros elementos que están en juego en el desarrollo de todo método terapéutico. Consideramos que un aspecto fundamental en el estudio del crecimiento de esta terapéutica, es la descripción y el análisis comparativo entre las características y funciones de las CF en relación con las características y funciones de la biomedicina, desde la perspectiva de los actores involucrados; ya que por un lado, la búsqueda de atención a la salud en forma integral”.

Familias - Aspectos psicológicos. Sistemas sociales. Enfermos - Relaciones familiares. Terapia sistémica (Terapia familiar). Teoría de las constelaciones familiares. Tesis - Doctorado en Antropología, CDMX. CIENCIAS SOCIALES SOCIOLOGÍA PROBLEMAS SOCIALES ENFERMEDAD ENFERMEDAD

Evaluación del desempeño climático de un invernadero baticenital del centro de México mediante dinámica de fluidos computacional (CFD)

Climate performance evaluation of a greenhouse in central Mexico using computational fluid dynamics (CFD)

JORGE FLORES VELAZQUEZ ENRIQUE MEJIA SAENZ IRINEO LORENZO LOPEZ CRUZ (2014, [Artículo])

Una de las principales actividades económicas en México es la producción de hortalizas para satisfacer el mercado estadounidense y la superficie cultivada en ambiente protegido aumenta alrededor de 20 % anualmente. Pero la producción es restringida debido a temperaturas altas y bajas en periodos específicos, planteando la necesidad de un sistema de enfriamiento. La ventilación natural eficiente es un método efectivo para controlar el clima, pero su descripción es compleja y una simplificación demanda mayor conocimiento del proceso. El objetivo del presente estudio fue mostrar, mediante el planteamiento y la solución del modelo físico de movimiento del aire, la representación visual del flujo en un invernadero baticenital de 10 naves (110×90×4.7), típico del centro de México, y la distribución de temperaturas en el interior donde se simula un cultivo de tomate (Lycopersicon esculentum Mill.) totalmente desarrollado (IAF=4).

Invernaderos Clima Energía eólica Sistemas de computación INGENIERÍA Y TECNOLOGÍA