Ingeniero Civil Matemático / La computación distribuida, rama de las ciencias de la computación, se focaliza en estu- diar sistemas distribuidos, tales como internet, redes sociales o protocolos de mensajería. La información se encuentra distribuida entre las distintas entidades que conforman el sistema y el objetivo último es resolver algún problema global. Para ello las distintas entidades se comunican mediante los canales de la red hasta que encuentran la solución. Esta memoria comienza estudiando el problema de la degenerancia de un grafo en los modelos de computación distribuida UCAST y BCAST, donde la degenerancia de un grafo G se define como el máximo grado mínimo de un subgrafo F de G. Los modelos distribuidos UCAST y BCAST corresponden a redes completas de n individuos, los cuales se comunican de manera síncrona por los canales de la red en rondas. En el primer caso, cada individuo por ronda puede enviar diferentes mensajes por cada uno de sus canales. En el segundo caso, cada individuo por ronda envía a través de sus canales el mismo mensaje. En general, se suele decir que BCAST es una restricción de UCAST. Primero, se construye un protocolo aleatorio en el modelo UCAST que calcula una (1 + ε)- aproximación de la degenerancia en O(log n) rondas con mensajes de largo O(log n). En el modelo BCAST se demuestra que el problema de calcular la degenerancia es difícil en 1 ronda. Más específicamente, se demuestra que todo protocolo aleatorio de 1 ronda que calcule exactamente la degenerancia debe enviar un mensaje de largo Ω(n). En el mismo modelo, se construye un protocolo aleatorio de 2 rondas con mensajes de largo O(log 2 n) que calcula una (1 + ε)-aproximación de la degenerancia para grafos α-densos. Finalmente, se construye un protocolo determinista que calcula una (2 + ε)-aproximación de la degenerancia en O(log n) rondas con mensajes de largo O(log n). Como segunda parte de este trabajo, y motivado por el protocolo en BCAST que calcula una (2 + ε)-aproximación de la degenerancia, se estudia la siguiente dinámica sobre grafos: Durante cada iteración, eliminar todos los vértices que tengan grado a lo más el grado prome- dio del grafo +1. Se conjetura que para todo grafo G de n vértices la dinámica toma O(log n) iteraciones en vaciar el grafo. Se aborda el problema estudiando clases de grafos tales como: bosques, grafos planares, grafos con degenerancia acotada y grafos unión disjunta de cliques. Finalmente, se estudian diversos problemas en el modelo BCAST. Se comienza estudiando el problema de calcular el conjunto independiente maximal con un vértice fijo. Se prueba que el problema es difícil en 1 ronda y luego se contruye un protocolo que en O(log n) rondas, usando mensaje de largo O(log n), calcula el conjunto independiente. Se estudia también el problema de calcular el número cromático de un grafo. Se prueba que el problema resulta difícil en 1 ronda. Concluyendo el capítulo, se estudian los problemas de encontrar conjuntos dominantes de tamaño k y conjuntos -dominantes de tamaño k, en ambos casos se demuestra que los problemas son difíciles en 1 ronda. / Este trabajo ha sido parcialmente financiado por Proyecto Fondecyt 1130061

Se presenta un método de punto proximal escalarizado inexacto para resolver problemas irrestrictos de minimización multiobjetivo cuasiconvexos definidos en espacios Euclidianos, donde las funciones vectoriales son localmente Lipschitz. Bajo algunas hipótesis naturales, se prueba que la sucesión generada por el método está bien definida y converge globalmente. Seguidamente proporcionando al método propuesto dos criterios de error, se obtienen dos variantes del mismo, y se prueba que las sucesiones generadas por cada una de esas variantes, convergen hacia un punto crítico Pareto-Clarke del problema; también se prueba que al dotar a la función vectorial de ciertas condiciones, la tasa de convergencia de uno de estos métodos es lineal y superlineal. Finalmente para validar el método propuesto y los resultados encontrados, se presentan algunos experimentos computacionales. / Tesis

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.