La presente investigación está orientada a reflexionar sobre el problema de la complejidad a partir de la tesis del pensamiento complejo del filósofo Edgar Morín, puesto en contradicción con la filosofía de Aristóteles. Con respecto a nuestros estudios, vemos que Morin comienza con una perspectiva antropológica y biológica que le permite analizar la constitución del hombre desde el principio o la noción de complejidad; busca comprender la complejidad en la vida humana aplicando lo complejo como método, origen y destino. No se trata de un nuevo relativismo, sino de una nueva forma de entender la relación entre los opuestos. Es necesario reflexionar sobre el pensamiento complejo como un método, entendido como pensamiento de él, de carácter original y peculiar.

Magíster en Ciencias de la Ingeniería, Mención Matemáticas Aplicadas. Ingeniero Civil Matemático / Un conjunto de vértices de un grafo se dice convexo si contiene a los vértices de todos los caminos mínimos entre sus vértices. El problema de determinar si un grafo tiene una partición en p conjuntos convexos es NP-completo, pero hay diversas familias de grafos en las que se puede resolver en tiempo polinomial. El foco principal de este trabajo es estudiar el problema de la p-partición convexa en una familia de grafos definida recursivamente al reemplazar los vértices de un bosque por grafos de ésta. Esta familia resulta ser cerrada para subgrafos inducidos. Sin embargo, no queda totalmente determinada la familia de subgrafos prohibidos que determina a esta familia. Además, estos grafos resultan ser perfectos, por lo que varios problemas combinatoriales resultan tener soluciones polinomiales en esta familia. Además, se entrega un algoritmo polinomial para reconocer si un grafo pertenece a esta familia. Para atacar el problema de las particiones convexas en este contexto, combinaremos, mediante programación dinámica, particiones en subgrafos tales que sus particiones convexas son de tres tipos: todos los vértices, particiones en cliques y particiones en cliques más un conjunto localmente convexo. En el caso de las particiones en cliques, se entrega un algoritmo polinomial que lo resuelve. / Este trabajo ha sido parcialmente financiado por CONICYT mediante Proyecto Basal PFB 03

La presente investigación evalúa el concepto de computabilidad en la teoría de Alan Turing, justificándose por la existencia de opiniones divergentes entre diversos académicos, expresadas alrededor del significado de la tesis de Church-Turing, que trata a la función recursiva como equivalente al procedimiento efectivo. En la actualidad, operamos computadoras conectadas a la Internet, resultando habitual relacionar como computabilidad lo que se puede hacer en una computadora. Muy pocas veces asociamos a la computadora con la ejecución de un cálculo aritmético, tal vez porque disponemos de las máquinas calculadoras. En un sentido amplio, utilizamos la palabra computable como sinónimo de la obtención de un resultado utilizando una computadora. Cuando mencionamos cálculos, no sólo significa operaciones numéricas, también corresponde a operar símbolos, como ocurre cuando entendemos los elementos que nos rodean, los percibimos como fenómenos, incluso nos percatamos del ánimo de las personas y las interpretamos, aunque no siempre acertemos sobre los estados de ánimo.

Esta tesis trata de las relaciones entre la arquitectura y la naturaleza, naturaleza esta considerada a partir de su concepción científica contemporánea, dentro del marco de la Ciencia de la Complejidad. En este contexto, se da una especial énfasis al tema de la mímesis de la naturaleza, cuestionándose la vigencia de este procedimiento en arquitectura y analizándose sus perspectivas en la actualidad.En primer lugar, se identifica y se hace un primer análisis de la producción arquitectónica contemporánea que asume vinculaciones con los conceptos provenientes de la Ciencia de la Complejidad. En esta producción, se detecta una tendencia predominantemente simbólica y formalista en la incorporación de los conceptos científicos frente a una limitada consideración del potencial que la nueva visión científica de naturaleza sugiere aportar. A continuación, se profundiza en la Ciencia de la Complejidad, clarificando sus principales conceptos y horizontes filosóficos, con vistas a su adecuación al contexto de la mímesis. En este panorama, se nos desvela un universo complejo pautado por conceptos como autoorganización, no-linealidad, azar, imprevisibilidad e indeterminismo; además, se destaca la pertinencia de estos conceptos en todo sistema dinámico, en lo que se incluye la sociedad y el cuerpo humano, tanto a nivel biofísico como psicosocial.En seguida, se elabora un cuadro evolutivo de la mímesis de la naturaleza en las artes y la arquitectura, analizándose el tema desde una larga perspectiva histórica. Con ello se demuestra la persistencia y diversidad de este procedimiento a lo largo de la historia del arte y de la arquitectura, aunque no siempre teorizada como tal.Por fin, se establecen las conclusiones finales sobre el tema. Analizándose las estrategias y los argumentos de la mímesis de la naturaleza en arquitectura, se detecta su plena vigencia en la actualidad, con tendencia a una cientificización de este proceso, algo que remonta al Renacimiento. Y analizándose las aportaciones de la Ciencia de la Complejidad en el proceso mimético, se discute sobre su amplio potencial en distintos aspectos de la arquitectura: la perspectiva de un continuado futuro para una mímesis cognoscitiva fundada en la ciencia; la nueva imagen de naturaleza y la pertinencia de la imagen de la complejidad en arquitectura; el potencial de una subjetivación de la complejidad científica en la consideración del hacer arquitectónico; y una doble lectura mimética de arquitecturas ecológicas.

Este trabajo se inspira en la importancia que en el sostenimiento de la vida posee el sistema respiratorio humano, unido a la necesidad de aumentar la información sobre su funcionamiento dinámico y de elemento integrador de diversos subsistemas como los de anatomía, fisiología, regulación, control y características físico-químicas apropiadas para su actividad. Son de interés especial en esta pretensión el estudio de la variabilidad del patrón respiratorio mediante métodos de análisis de complejidad de sistemas no lineales. El trabajo desarrollado comienza con la definición del patrón respiratorio humano, el cual permitirá definir las tres series temporales de fundamental importancia: Tiempo Inspiratorio, TI, Tiempo Total TTOT y volumen circulante VT, obtenidas a partir de los registros continuos de volumen de aire en cada ciclo respiratorio. En el capítulo 1 se realiza también la descripción del estado del arte en variabilidad respiratoria. Se prosigue con una introducción al estudio de los sistemas dinámicos complejos, y finaliza con la formulación del objetivo fundamental de la tesis, y sus seis objetivos secundarios.El procesado de la señal de volumen pulmonar se presenta en el capítulo 2, desarrollándose las etapas de filtrado y detección automatizada de ciclos respiratorios, y de esta manera tener identificados los componentes que definen el patrón ventilatorio. Se describen allí las dos bases de datos utilizadas en el estudio del análisis de complejidad, la de registros pletismográficos del Hospital de la Santa Creu i Sant Pau (PRI-HSCSP) y la de registros polisomnográficos del MIT. Se han propuesto diversos algoritmos que realicen la determinación ciclo a ciclo de los instantes de inicio y fin inspiratorio, considerando distintos umbrales de tiempo y de flujo del patrón ventilatorio, que en conjunto representan diversos criterios de valorar el volumen de aire desplazado en las vías aéreas durante cada ciclo respiratorio. Los algoritmos desarrollados fueron validados sobre un conjunto de señales de volumen respiratorio, al contrastarse sus resultados con los indicados por un grupo de médicos neumólogos, logrando una muy elevada reproducibilidad. Es comúnmente aceptado que existen dos condiciones necesarias para realizar el análisis de complejidad en sistemas no lineales, una referida a garantizar la condición estacionaria de los registros. La segunda condición está referida a garantizar la no linealidad del sistema, comprobando que los registros no cumplen con el principio de superposición. El capítulo 3 de la tesis se ocupa de establecer cuales de los registros analizados cumplen con estas dos condiciones.El estudio de los sistemas no lineales y sus índices de complejidad se inicia con el capítulo 4, primero analizando como características cualitativas de las series temporales los mapas de fase y los diagramas de Poincaré. Los mapas de fase obtenidos permitieron clasificar en cinco diferentes topologías las estructuras generales que presentan los pacientes analizados: ciclos límite, órbitas cuasiperiódicas, trayectorias homoclínicas, trayectorias heteroclínicas y órbitas no estables. Este análisis permitió concluir que una particularidad del patrón respiratorio está dada por las diferencias cualitativas entre los registros de presión de soporte baja y alta, tanto para los mapas de fase como para los diagramas de Poincaré. El análisis cuantitativo mediante los índices de complejidad se inicia en el capítulo 5, con la estimación del retardo adecuado necesario para la reconstrucción fiable del atractor del sistema, para posteriormente calcular la dimensión de las series temporales de dos formas diferentes y complementarias: mediante la dimensión fractal (DF) de los Diagramas de Poincaré y mediante la dimensión de correlación (D2). Ambos métodos permiten identificar en un 81,3% los resultados de la valoración clínica de los pacientes. El capítulo 5 termina con la estimación de las entropías aproximadas de las series temporales, que definen el grado de regularidad de los registros. En el capítulo 6 se calculan los exponentes de Lyapunov mediante la técnica de la reconstrucción del atractor, con la finalidad de estudiar dos de sus principales implicaciones en la dinámica compleja como son la sensibilidad a las condiciones iniciales de las series y la estabilidad del sistema. Se han obtenido diferencias estadísticamente significativas (p=0,001) al comparar los pacientes con presión de soporte alta y baja. Se termina el capítulo proponiendo un nuevo índice combinado de complejidad para el análisis no lineal del patrón respiratorio, denominado Índice Combinado de Complejidad Ventilatoria (ICCV). El séptimo y último capítulo analiza globalmente los resultados cualitativos y cuantitativos obtenidos en la tesis, con la doble finalidad de verificar la analogía con la valoración clínica de los pacientes que presentan patologías que requieren de asistencia con presión de soporte ventilatorio, lográndose un nivel de identificación del 94% con el ICCV propuesto. Adicionalmente los resultados del análisis de complejidad predicen la subyacencia de ciclos ventilatorios intermedios de entre 8 y 32 ciclos respiratorios resultado de las interacciones dinámicas complejas propias del sistema pulmonar. La identificación de estructuras temporales y espaciales que engloben la variabilidad y complejidad del comportamiento de un sistema físico es parte clave en su definición y comprensión. El estudio del análisis de complejidad cualitativo y cuantitativo es una herramienta útil en la búsqueda de esta identificación, y en el caso particular del patrón ventilatorio, los resultados del análisis realizado permiten ver con optimismo una dirección a seguir para encontrar tales estructuras espacio-temporales en el sistema respiratorio. Como línea de investigación futura cabe destacar la aplicación de estos resultados a la ayuda en la toma de decisión del momento óptimo para la desconexión de los pacientes sometidos a ventilación mecánica, al considerarse que el sistema respiratorio con una complejidad más elevada ya es capaz de actuar de forma autónoma.

Memoria para optar al título de Socióloga

Ingeniero Civil Matemático / La presente memoria se enmarca en el contexto de la computación distribuida. Esta es un área de las ciencias de la computación relativamente reciente, que surge ante la necesidad de un nuevo paradigma de computación, capaz de trabajar con cantidades masivas de datos, como son, por ejemplo, las redes sociales. En particular, se estudia la complejidad del problema CONEXIDAD de un grafo $G=(V,E)$ en el modelo computacional number-in-hand. Este problema consiste en decidir si un grafo $G$ es o no conexo. Por otro lado, a grandes rasgos, la complejidad que se considera aquí mide el largo de los mensajes (en bits) que los nodos deben comunicar para decidir CONEXIDAD. En primer lugar, se demuestra que la complejidad, en el caso en que el grafo $G$ es arbitrario, es al menos $f(n)$, donde $f(n) = \log n - (\log \log n +1+ \log n /n)$. Sin embargo, esta fórmula no aporta información alguna cuando el grafo $G$ posee $n<27$ nodos, pues $f(n) \leq 1$ para tales valores. Es decir, indica que la cantidad de bits que se tienen que comunicar es al menos $\leq 1$, lo que es evidente. Por esta razón, se profundiza el estudio analizando grafos pequeños, y se demuestra que 1 bit no es suficiente para decidir el problema en tal caso. Por otro lado, la cota expuesta se obtiene a partir de una reducción que construye un grafo de grado no acotado. Por lo tanto, $f(n)$ puede ser poco ajustada para la familia de grafos de grado acotado. Así pues, se complementa el trabajo restringiéndose a esta clase de grafos, con el fin de saber si en tal caso existe una mejor cota para la complejidad de CONEXIDAD en el modelo number-in-hand. Usando técnicas de complejidad comunicacional se encuentra una cota inferior de $\Omega(\log n)$. Más aún, se demuestra que esta cota es ajustada para esta clase de grafos.

El presente estudio tuvo como finalidad establecer la relación que existe entre la comprensión lectora y el rendimiento académico en el área de Comunicación, en alumnos del primer grado de secundaria en una institución educativa estatal del distrito de Santiago de Surco, cuya participación fue de 65 alumnos y de una institución educativa no Estatal del mismo distrito, con un grupo estudiantil de 38 alumnos. Se llevó a cabo la prueba de bondad de ajuste de Kolmogorov – Smirnov para los puntajes de la Prueba de Comprensión Lectora de Complejidad Lingüística Progresiva Nivel 7 Forma B (CLP 7- B) y los promedios del tercer bimestre en el área de Comunicación de los estudiantes de la institución educativa no estatal del distrito de Santiago de Surco, la cual indicó que se podía emplear estadísticos paramétricos para la prueba de hipótesis. Los resultados mostraron la existencia de una relación estadísticamente significativa entre la comprensión lectora y el rendimiento escolar en el área de Comunicación en la muestra total de estudiantes. Asimismo, se encontró una relación significativa entre ambas variables en los estudiantes de primer año de secundaria tanto en la institución educativa estatal, como en la institución educativa no estatal del distrito de Surco. También se encontró que los estudiantes de la institución educativa no estatal tenían un mayor nivel de comprensión lectora que sus pares de la institución educativa estatal.

El objetivo principal de esta tesis es estudiar la teoría de prueba de la Programación en Lógica Rebatible (P.L.R.) y brindar una caracterización declarativa equivalente. La P.L.R. es una herramienta valiosa para la representación de conoci-miento tentativo, incierto y potencialmente inconsistente, que provee un mecanismo de inferencia basado en los sistemas argumentativos. En los últimos años, los sistemas argumenta-tivos han comenzado a ser utilizados en diversos campos de aplicación como la web y sistemas multiagentes. En esta Tesis se presenta una caracterización declarativa basada en la teoría de modelos y en la noción de juegos, de la P.L.R.. La semántica declarativa trivaluada desarrollada, que se denomi-na GS, es sensata y completa con respecto a la teoría de prueba de P.L.R.. Como punto intermedio, se brinda una forma-lización declarativa equivalente de la estructura de argumento y se circunscribe el conjunto de todos los posibles argumen-tos a favor y en contra que pueden construirse para una con-sulta dada bajo un programa lógico rebatible. A partir de los resultados obtenidos, se realizó un estudio de la complejidad computacional de la P.L.R.. En este sentido, se definieron pro-blemas de decision relevantes con respecto a los juegos bajo el contexto de un programa lógico rebatible y se calculó la complejidad computacional de la existencia de argumentos y contraargumentos. Asimismo, considerando el nexo existente entre la Programación en Lógica y las bases de datos deduc-tivas se definieron las complejidades de datos, expresión y combinada, y se establecio una cota superior para la com-plejidad de datos. Dichos resultados nos dan un indicio para determinar el poder expresivo de la P.L.R.. / The main goal of this thesis is to study Defeasible Logic Programming (DeLP) proof theory and to provide an equivalent declarative characterization. DeLP is a valued tool for repre-senting tentative, uncertain, and potentially inconsistent knowledge, that provide an inference mechanism based on argumentative systems. In the last decade, argumentative systems have been used in different applications fields, such as the web and multiagent systems. In this thesis we present a declarative caracterization based in model theory and in game concepts of Defeasible Logic Programming (DeLP). The trivalued declarative semantics developped, noted GS, is sound and complete with respect to DeLP proof theory. As an intermediate point, we provide an equivalent declarative for-malization of argument structure and we circunscribe the set of all possible arguments for and against that can be cons-tructed for a query under a defeasible logic program. From the results we have obtained, we carry out an study of DeLP computational complexity. We have defined relevants decision problems with respect to the construction of a game under a defeasible logic program and we calculate the computational complexity of arguments and conterargument existence. Furthermore, considering the link between Logic Programmning and deductive data bases we have defined data complexity, expression complexity and combined complexity and we have established a upper bound for data complexity. These results give us a trace for determining DeLP expressive power.

Ingeniero Civil Matemático / El presente trabajo consiste en el estudio de la complejidad computacional en algunas redes de autómatas. En particular en el problema de decisión, que llamamos PER, el cual consiste en predecir cambios de estado en un nodo determinado cuando la red se actualiza según una regla determinada. Dentro de los primeros en introducir complejidad computacional a los autómatas celulares (CA) y sistemas relacionados podemos destacar a C. Moore [19] quien estudió la regla de la mayoría estricta en lattices d-dimensionales, y a T. Neary con D.Woods [23], que prueban la P-Complitud de la regla 110 en autómatas unidimensionales. Estos estudios son interesantes porque, por un lado, usualmente es muy difícil obtener caracterizaciones del comportamiento general de la dinámica de un autómata celular en el tiempo; y por otro lado, están relacionados con el procesamiento paralelo de la información y algoritmos, ya que algunos CA son capaces de emular una máquina de Turing universal. Luego, la idea es construir un puente entre estos dos aspectos del problema: la naturaleza de su dinámica y sus capacidades algorítmicas. Por lo general estos trabajos se enfocan en acotar el problema por arriba , determinando P-Complitud. Este trabajo es novedoso en el sentido que a lo anterior agregamos un acota- miento por abajo , buscando demostrar que cuando el problema no es P-Completo, entonces debe ser eficientemente paralelizable, es decir, pertenecer a la clase NC. Esto lo haremos va- riando primero la topología de la red considerando siempre un modo de iterar paralelo, y posteriormente determinando la influencia de distintos modos de iterar en la complejidad. En términos más concretos, estudiaremos la complejidad computacional de Bootstrap Percolation (Capítulo 2). El resultado principal es que, para esta regla, el problema de decisión PER está en NC si restringimos al grafo que define a la red a pertenecer a la familia que tiene grado máximo pequeño, y en caso contrario el problema es P-Completo. Luego, en el Capítulo 3, cambiaremos a la regla de la mayoría estricta, donde el principal resultado del capítulo será que para esta regla PER es P-Completo en la familia de grafos planares. Finalmente, en el cuarto capítulo estudiaremos cómo varían los resultados anteriores cuando consideramos distintos modos de actualizar los estados de la red. El resultado principal tendrá relación con los distintos modos de iterar considerando en cada nodo una función booleana AND u OR. Por último, daremos algunas conclusiones y problemas abiertos. El trabajo aquí expuesto ha permitido una publicación en Theoretical Computer Science llamado The complexity of Bootstrapping Percolation [10], una charla invitada (Winter FRAC 2012, París), una conferencia invitada (CA2012 Córcega), un artículo actualmente enviado a Advances in Applied Mathematics y otro en desarrollo.