Este seminario irregular reúne a un diverso grupo de investigadores de la Universidad de Concepción interesados en álgebra, matemática discreta, lógica, combinatoria y otros temas que giran en torno a la informática teórica. El objetivo de estas charlas es crear una discusión en torno al tema y que todos aprendan algo -incluyendo al expositor. Normalmente duran una hora y hay mucho tiempo para preguntas. Esta página reúne algo de material y enlaces a las fuentes. Asisten varios estudiantes de post-grado y cursos superiores de pregrado. Si usted desea asistir, informarse de las próximas charlas u ofrecer una ponencia, no dude en escribir al@ organizador@.
Organizadora de turno: anahi(@ing-mat.udec.cl) Gajardo.
Sobre los conjuntos de enteros positivos sin progresiones aritméticas
de largo 3 y las transversales de los hipergrafos
Pablo Sáez, Independiente
Hay una conjetura famosa de Erdös y Turán que dice que
todo conjunto grande de enteros positivos tiene dentro de sí
progresiones aritméticas de largo arbitrario.
Un conjunto es grande por definición si y solo si la suma de los recíprocos de sus elementos diverge.
El nivel de dificultad de una eventual demostración de esta conjetura parece ser muy alto.
Por ejemplo, los célebres teoremas de Szemerédi y de Green-Tao son casos particulares.
Incluso una versión mucho más débil de la conjetura, a saber demostrar que todo conjunto
grande tiene dentro de sí una progresión aritmética de largo 3 es un problema abierto.
Nos interesa por lo tanto el problema de acotar la cantidad de elementos de conjuntos de enteros sin progresiones aritméticas de largo 3.
El estado del arte es un resultado reciente de Bloom.
Nuestro enfoque es reducir este problema al del cálculo de transversales de hipergrafos, que es de carácter más bien computacional, o de lógica proposicional.
La reducción es simple pero aparentemente ha pasado inadvertida.
Viernes 1 de julio de 2016, sala Enrique Oelker, 3er piso, Departamento de Física, FCFM, a las 12:00.
Propiedades dinámicas y topológicas de Máquinas de Turing
Rodrigo Torres Avilés, Phd (c) en Ciencias Aplicadas, Universidad de Concepción
La charla aborda sistemas dinámicos topológicos de las máquinas de Turing, tales como TMT, TMH y t-shift, junto con propiedades aún no estudiadas en el ámbito. Se tratará la técnica demostrativa 'Embedding', y como ella nos permite estudiar tanto los conjuntos de máquinas como la decibilidad en transitividad, mixing, minimalidad y entropía topológica.
Viernes 2 de octubre de 2015, sala IS3-1, Edificio de Ingeniería de Sistemas, a las 16:00.
Signed graph embedding, when everybody can sit closer to friends than enemies
Christopher Thraves, DIM, Universidad de Concepción
Signed graphs are graphs with signed edges. They are commonly used to
represent positive and negative relationships in social networks. While
balance theory and clusterizable graphs deal with signed graphs, recent
empirical studies have proved that they fail to reflect some current
practices in real social networks. In this presentation we address the
issue of drawing signed graphs and capturing such social interactions. We
relax the previous assumptions to define an embedding as a model in which
every vertex has to be placed closer to its neighbors connected via a
positive edge than its neighbors connected via a negative edge in the
resulting space. Based on this definition, we address the problem of
deciding whether a given signed graph has a drawing in the 1-dimensional
Euclidean space. We provide a polynomial time algorithm that decides if a
given complete signed graph has a drawing, and provides it when
applicable. When the input signed graph is not complete the
recognition problem has
been proved to be NP-complete. If we have enough time, we will show a greedy heuristic with
interesting recognition capabilities when the input is not complete.
Viernes 4 de septiembre de 2015, sala Enrique Oelker, FCFM, a las 15:30.
Simulación entre Autómatas Celulares
Sr Diego Maldonado, Universidad de Concepción
Viernes 5 de diciembre de 2014, sala de Diplomado I-5, Edificio de Ingeniería de Sistemas, a las 15:15.
Introducción a los juegos de influencia
Dr Fabián Riquelme, Universidad de Concepción
Viernes 28 de noviembre de 2014, sala de Diplomado I-5, Edificio de Ingeniería de Sistemas, a las 15:15.
Una visión general de la criptografía moderna, sin detalles y (casi) sin matemáticas
Dr Joachim von zur Gathen, Universität Bonn, Alemania
Lunes 10 de noviembre de 2014, auditorio 105, Facultad de Ingeniería, a las 10:00.
Taller de trabajo en autómatas celulares, 3 al 7 de noviembre
Gracias al financiamiento del programa ECOS-CONICYT y FONDECYT, organizamos una semana de trabajo en torno a los autómatas celulares.
Positive expansivity and Besicovitch sensitivity
Dr Ville Salo, CMM, U de Chile
Permutations vs. computation
Dr Guillaume Theyssier, CMM-CNRS, U de Chile
Decidability of the periodicity of one-sided CA?
Dr Martin Delacourt, CMM, U de Chile
Randomization problem in cellular automata
Dr Benjamin Hellouin, Universidad Andrés Bello
Topological randomization in bipermutive CA
Dr Ville Salo, CMM, U de Chile
Knight tiles
Sr Bastien Le Gloannec, LIFO, Université d'Orléans, Francia
Substitutive Z^2 subshifts with certain "affine symmetries"
Dr Michael Schraudner, CMM, U de Chile
Physically universal CA
Dr Ville Salo, CMM, U de Chile
Concurrent stochastic games with optimal memoryless strategies
Sr Bruno Karelovic, LIAFA, Paris 7, Francia
Viernes 24 de octubre de 2014, en la sala de Diplomado I-5, Edificio de Ingeniería de Sistemas, a las 15:15.
Existencia de Matrices complejas de Hadamard
Dr Dardo Goyeneche, Departamento de Física y CEFOP, UdeC
Una matriz compleja de Hadamard es una matriz cuadrada cuyas
columnas son ortogonales y cada componente es un número complejo de
amplitud 1 (ej. transformada de Fourier). La clasificación completa de
este tipo de matrices es conocida para toda dimensión menor a seis. Este
tipo de matrices tiene importantes aplicaciones en física, en particular,
en mecánica cuántica. En esta charla, presentaremos un nuevo método para
generar familias continuas de matrices complejas de Hadamard en toda
dimensión par mayor a dos.
Viernes 10 de octubre de 2014, en la sala de Diplomado I-5, Edificio de Ingeniería de Sistemas, a las 15:15.
Teoría de probabilidades para consistente
Dr Aldo Delgado, Departamento de Física y CEFOP, UdeC
Viernes 3 de octubre de 2014, en la sala de Diplomado I-5, Edificio de Ingeniería de Sistemas, a las 15:15.
El cálculo de situaciones, veinte años después
Dr Pablo Sáez
Resumen
Viernes 26 de septiembre de 2014, en la sala de Diplomado I-5, Edificio de Ingeniería de Sistemas, a las 15:15.
Gracias al apoyo del programa ECOS-CONICYT y del centro CI²MA realizamos hoy un nuevo encuentro al rededor de la matemática y la computación.
Substitutions and strongly deterministic tilesets
Dr Nicolas Ollinger,
University of Orleans, France
Turmit number 6: Simpler but with the same complexity
Diego Maldonado, DIM, UdeC
Mu-limit sets of two-dimensional cellular automata
Dr Martin Delacourt, CMM, Universidad de Chile
Introducing freezing automata
Dr Guillaume Theyssier, CMM, Universidad de Chile
Coded t-shifts
Rodrigo Torres, DIM, UdeC
Sofic machines
Dra Anahí Gajardo, Universidad de Concepción, Chile
En esta ocasión hemos reunido dos expositores en la sala multiuso del DIM, desde las 15 horas.
Indecibilidad en el mundo de los conjuntos finitos
Dr Carlos Martínez, DMAT, UdeC
Is there something like "modellability"? On some differences between cellular automata and multi-agent systems
Dr Nazim Fatès, LORIA, Francia
Gracias al financiamiento del programa ECOS-CONICYT organizamos una jornada de nuestro taller.
Lugar: Sala 203, FCFM.
Complejidad del problema de dualidad regular
Dr Andreas Polymeris, DIICC, UdeC
Problemas inversos con esquemas de actualización en redes Booleanas
Luis Gómez, DIM, UdeC
Redes Booleanas con esquemas de actualización parcial
Eduardo Palma, DIICC, UdeC
Pilas de arena de Kadanoff
Dr Kevin Perrot, ENS-Lyon, Francia
Dinámica y complejidad en máquinas de Turing
Rodrigo Torres, DIM, UdeC
Con motivo de la visita de varios amigos a Chile, hemos organizado un encuentro, la cita es en el Centro de Investigación en Ingeniería Matemática CI²MA a quien agradecemos por su apoyo financiero y logístico.
Lugar: Cabina 6.
Fixed points and forbidden sub-networks in Boolean networks
Dr Adrian Richard, CNRS, Francia
A Hoare Logic for discrete dynamical systems: application to gene networks
Dr Jean-Paul Comet, Université de Nice, Francia
Periodicity and immortality in reversible computing
Dr Nicolas Ollinger, Université d'Orleans, Francia
Symbolic systems and Turing machines
Dra Anahí Gajardo, Universidad de Concepción, Chile
Con motivo de la defensa de tesis de Marco Montalva, hemos organizado un encuentro. Debido a las protestas se realizará en Mac Iver 1710, Barrio La Virgen.
Evolution of biological regulation networks
Dr Jacques Demongeot, Université de Grenoble, Francia
Limit cycles and update digraphs in Boolean networks
Luis Gómez, Universidad de Concepción, Chile
A constraint-based method for analyzing discrete genetic regulatory networks
Dr Eric Fanchon, Université de Grenoble, Francia
Estudio de la complejidad del lenguaje asociado a la dinámica simbólica de un autómata con marcadores
Camilo Lacalle, Universidad de Concepción, Chile
Coloraciones inyectivas con restricciones aditivas
Dr Martín Matamala, Universidad de Chile, Chile
Problemas matemáticos asociados a la física cuántica
Dr. Aldo Delgado, DFIS, UdeC.
Viernes 19 de noviembre de 2010, 17:10, Auditorio profesor Alamiro Robledo, 1er piso FCFM.
El viernes 26 de noviembre tendremos todo el día dedicado al taller, con el programa que se indica más abajo (no están necesariamente en el orden definitivo).
Lugar: de 10 a 13 horas: Auditorio Prof. Robledo, 1er piso FCFM; de 15 a 18 horas: Auditorio 105, 1er piso, Facultad de Ingeniería.
Existencia de autómatas celulares estables e inestables con el mismo conjunto límite
Dr. Alexis Ballier, Post-doc, CMM, U Chile.
Se define la noción de conjunto límite para un autómata celular (AC). Algunos ACs lo alcanzan en tiempo finito y son llamados "estables", los otros son "inestables". En su trabajo de tesis, A. Maass plantea una pregunta abierta: øpuede un mismo conjunto ser el límite de un AC estable y de uno inestable? Nosotros construiremos un AC inestable cuyo conjunto satisface ciertas condiciones descritas por A. Maass, para luego mostrar otro AC estable que tienen el mismo conjunto límite, respondiendo así la pregunta de manera afirmativa.
Simetría temporal en Autómatas Celulares Dr. Andrés Moreira, Departamento de Informática, UTFSM.
Junto con el concepto de reversibilidad, otra importante noción física es la simetría temporal, la cual expresa que no hay forma de distinguir si el sistema va hacia atrás o adelante en el tiempo. Esta noción ha sido prácticamente ignorada en el estudio de sistemas dinámicos discretos. En la presente charla la formalizaremos en el contexto de autómatas celulares y estableceremos algunas relaciones y resultados básicos. También plantearemos algunos problemas abiertos.
Dependencia del pasado en ACs unidimensionales
Sr Pierre-Etienne Meunier, estudiante de doctorado, DIM, U Chile y U de Savoie, Francia.
Problemas de conteo delgados y el método de Schutzenberger
Dr. Andrés Montoya, Escuela de Matemáticas, Universidad Industrial de Santander, Colombia.
El método de Schutzenberger es un método de conteo que puede ser usado para diseñar algoritmos eficientes para una gran variedad de problemas de conteo delgados (tally counting problems). Este metodo explota la calculabilidad en tiempo polinomial de las funciones de censo de los lenguajes regulares. Es posible obtener algunas aplicaciones interesantes del método respecto a problemas de conteo delgados que surgen de algunos modelos discretos de la mecánica estadística. En la charla se estudiaran algunas aplicaciones del metodo en el conteo de caminos simples (self-avoiding walks) y polyominoes.
Dualidad de hipergrafos
Dr Andreas Polymeris, DIICC, UdeC.
Sobre la Conjetura de Stanley para una clase especial de árboles (caterpillars)
Dr José Aliste, Post-doc, CMM, U. de Chile.
Viernes 22 de octubre de 2010, en la sala del DIM, FCFM, a las 16 horas.
El polinomio simétrico cromatico (PSC) de Stanley y el U polinomio de Noble y Welsh son dos invariantes de grafos. La conjetura de Stanley establece que el PSC es un invariante completo entre los árboles, i.e., Dos árboles no isomorfos no tienen nunca el mismo polinomio simétrico cromatico (u equivalentemente, no tienen el mismo U polinomio). En esta charla, abordaremos la conjetura para una clase especial de arboles conocidas como cuncunas (caterpillars) y mostraremos cómo la conjetura puede ser estudiada aprovechando la estructura especial de las cuncunas y explicaremos los resultados parciales obtenidos. Este es un trabajo en curso en colaboración con José Zamora de la Universidad Andres Bello.
Un ejemplo de Teoria KAM: condiciones diofantinas sobre sistemas dinámicos
Sr. Héctor Pastén, estudiante de Magister en Matemática, UdeC.
Viernes 30 de octubre de 2009, en la sala de postgrado de matemática, a las 14:30 horas.
Un número real alpha irracional se dice diofantino si existen C, epsilon>0 tales que para todo número racional p/q se cumple |alpha-p/q|>C/q^(2+epsilon). El teorema de Roth nos dice que todos los números algebraicos reales no racionales son diofantinos y se puede probar que los números no diofantinos tienen medida cero en los reales (R). En esta charla estudiaremos un ejemplo de dinámica sobre un cilindro [0,1]xR y mostraremos que esta dinámica es conjugada clase C^(infinito) a una traslación lineal sobre el cilindro si cierto parámetro real de la dinámica es diofantino. Este teorema, conocido como 'Baby-KAM' es un ejemplo ilustrativo de como las condiciones diofantinas gobiernan ciertas dinámicas en baja dimensión. Se mencionarán también otros ejemplos que pondrán más en contexto el caso tratado. Este tema fue tomado de un cursillo dictado por el profesor Mario Ponce de la PUC en la XXXVI Semana de la Matemática.
Métodos geométricos en problemas de scheduling
Dr Pablo Sáez
Viernes 16 de octubre, en la sala de postgrado de matemática, 1er piso FCFM a las 14:30.
Daremos una introducción a los problemas de planificación de la producción industrial, centrándonos en aquellos que tienen soluciones geométricas. Explicaremos en particular el problema de Akers-Friedman y el de Johnson, para luego revisar brevemente otros problemas más generales del área. En una charla posterior seguiremos con temas más específicos, incluyendo el scheduling cíclico, el algoritmo de Romanovsky y otros.
Funciones booleanas monótonas e hypergrafos
Dr Andreas Polymeris, DIICC, UdeC.
Viernes 2 de octubre, en la sala de postgrado de matemática, 1er piso FCFM a las 14:30.
Combinatorics on update digraphs of Boolean networks
Dr Julio Aracena, DIM, UdeC.
Viernes 4 de septiembre, en la sala de postgrado de matemática, a las 14:30.
Consistency and Trust in Peer Data Exchange Systems
Dra Loreto Bravo, DIICC, UdeC.
Viernes 14 de agosto de 2009, en la sala FM-204, a las 14:30.
Recubrimientos por cuadrados solapados que no se tocan
Dra Lilian Salinas, DIICC, UdeC.
Viernes 26 de junio de 2009, en la sala de postgrado de matemática, a las 16 horas.
Decimos que dos cuadrados en el plano discreto no se tocan si ellos no comparten esquinas ni segmentos de lados. Usando esta condición definimos recubrimientos del plano discreto, estos recubrimientos pueden ser fuertes o débiles, regulares o no-regulares. En este trabajo, nos ocupamos de los recubrimientos regulares, es decir, todos los cuadrados en el recubrimiento tienen el mismo tamaño e intersectan el mismo número de cuadrados. Se dan condiciones mínimas para la existencia de recubrimientos fuertes y débiles del plano discreto en función del tamaño de los cuadrados y del número de cuadrados adyacentes permitidos para cada uno.
L. Salinas, E. Goles. "Covering by squares". Theoretical Computer Science, Volume 396, Issues 1-3, 10 May 2008, Pages 10-27.
Un algoritmo cuadrático para un caso particular del problema 2-cyclic robotic scheduling
Dr. Pablo Sáez
Viernes 12 de junio de 2009, en la sala de postgrado de matemática, a las 16 horas.
El problema de optimización combinatorial "2-cyclic robotic scheduling" surge en el ámbito de las líneas de producción automatizadas y no es difícil de formular. Para el caso general se conocen algoritmos de orden quíntico. En el caso particular que abordaremos en esta charla es posible derivar un algoritmo cuadrático. Esta área de investigación se encuentra plenamente vigente.
P. Sáez. "A quadratic algorithm for the 2-cyclic robotic scheduling problem". Theoretical Computer Science, Volume 410, Issues 8-10, 1 March 2009, Pages 973-976
Robustez en redes booleanas
Sr. Luis Gómez, estudiante de Doctorado en Ciencias Aplicadas, UdeC.
Viernes 29 de mayo de 2009, en la sala de postgrado de matemática, a las 16 horas.
Un resultado condicional sobre representación de cuadrados en un campo de números y la conjetura de Lang
Sr. Héctor Pastén, estudiante de Magister en Matemática, UdeC.
Viernes 15 de mayo de 2009, en la sala de postgrado de matemática, a las 17 horas.
Dinámica de autómatas y lenguajes formales - Parte II
Dra. Anahí Gajardo, DIM, UdeC.
Viernes 10 de abril de 2009, en la sala de postgrado de matemática a las 16 horas.
Nos focalizaremos ahora en la relación entre el movimiento de la máquina y el autómata que reconoce su shift asociado. Particularmente en cómo es posible calcular el conjunto de células alcanzables por la máquina a partir de la estructura de su autómata.
Dinámica de autómatas y lenguajes formales - Parte I
Dra. Anahí Gajardo, DIM, UdeC.
Viernes 3 de abril de 2009, en la sala de postgrado de matemática a las 16 horas.
Se trata de estudiar el comportamiento de autómatas que se desplazan sobre una grilla cúbica infinita (o en una grilla cuadrada o en Z). Al igual que una máquina de Turing, el autómata tiene un estado interno, y una regla de transición determinista, que indica cómo cambiará su estado, qué escribirá en la grilla y en qué dirección se moverá. A este tipo de autómata es posible asociar un subshift, es decir un conjunto de secuencias infinitas de caracteres de un alfabeto finito. En esta charla estudiaremos en particular aquellas máquinas cuyo shift es sófico. Ver las transparencias de la charla general que di en las Jornadas Matemáticas de la Zona Sur.
Criptografía probabilista basada sistemas dinámicos discretos
Dr. Marcelo Sobottka, DIM, UdeC.
Lunes 22 de diciembre de 2008, a las 11:00.
Retículos distributivos
Dr Andreas Polyméris, DIICC, UdeC.
Viernes 28 de noviembre de 2008, en la sala FM-204, a las 18:00 horas.
Continuando con el tema de "Dualidad de Hipergrafos" -donde se había demostrado la existencia de un retículo distributivo asociado- se recordó algo de la teoría general de retículos distributivos desarrollada por Birkhoff, mostrando que el retículo asociado a la dualidad juega un rol central y aprovechando de demostrar varias propiedades particulares de éste último. El documento asociado a esta charla está aquí.
Minicurso de Dualidad de Hipergrafos III
Dr Pablo Sáez
Viernes 14 de noviembre de 2008, en la sala FM-204, a las 18:00 horas.
Los hipergrafos que estudiamos con mi colega Andreas Polyméris son una abstracción de la lógica proposicional. Estamos interesados en una relación de orden sobre hipergrafos irredundantes que se parece mucho a la relación de consecuencia lógica. Veremos que se obtiene con esto un retículo distributivo, que por ende cumple con los axiomas de las álgebras de Heyting, es decir con los de la lógica intuicionista, o constructivista (la que niega la ley del tercio excluido). Mostraremos algunas propiedades de este retículo y reconstruiremos "para variar" el problema de la dualidad de hipergrafos en este nuevo contexto. Las transparencias de las sesiones pasadas están aquí.
Minicurso de Dualidad de Hipergrafos II
Dr Pablo Sáez
Viernes 24 de octubre de 2008, en la sala FM-204, a las 18:00 horas.
"Algoritmos estándar para el problema de dualidad: algoritmo de Berge. Algoritmo de Fredman & Khachiyan."
Minicurso de Dualidad de Hipergrafos I
Dr Pablo Sáez
Viernes 10 de octubre de 2008, en la sala FM-204, a las 18:30 horas.
Definiciones, operadores. Dualidad de hipergrafos y sus aplicaciones (ver resumen). El problema de la dualidad de hipergrafos es un tema que Andreas Polymeris, y últimamente Pablo Sáez, estudia desde hace muchos años (ver su último artículo aquí). Es equivalente a varios problemas de muy distinta índole, algunos han sido estudiados por investigadores de renombre, y aún siguen abiertos. Vea aquí un survey general del problema y acá un survey de sus aplicaciones.
Una Extensión del Problema de Büchi para Anillos de Polinomios en Característica Cero
Sr Héctor Pastén, estudiante de Licenciatura en Matemática, UdeC.
Viernes 3 de octubre de 2008, en la sala FM-204, a las 18 horas.
Remarks on chaos-based cryptography
Dr. Marcelo Sobottka, DIM, UdeC.
Viernes 4 de julio, 17:00, sala postgrado matemática, 1er piso Fac. de Cs. Físicas y Matemáticas.
Chaotic dynamics can produce information by deterministic means. This leads to the proposal of some cryptosystems based on chaotic dynamics. The first applications of chaotic systems for cryptography were based on their synchronization and on their control. At present, the direct use of the chaotic orbits has been used for encoding/decoding plain texts. One of the most cited cryptosystem of this kind is the one proposed by Baptista using the logistic map F_mu(x)=mu x(1-x) in the closed interval [0,1], with 3 < mu <= 4 for which F_mu is chaotic.
Hilbert's tenth problem: undecidability of polynomial equations
Dra. Alexandra Shlapentokh
East Carolina university, Greenville (NC), USA.
Viernes 20 de junio, 17:00, sala postgrado matemática, 1er piso Fac. de Cs. Físicas y Matemáticas.
Hilbert's Tenth Problem was a question posed by David Hilbert at the beginning of the XX century concerning an algorithm to establish existence of integer solutions to polynomial equations. In the late sixties it was shown that such an algorithm did not exist. We discuss this result and its extensions to subrings of the field of rational numbers. Transparencias.
Problemas NP-completos asociados a conjuntos recubridores de ciclos.
Sr Marco Montalva
Given a directed graph G=(V,E) and a sign function w, we study the positive (negative) feedback vertex set problem, denoted by PFVS (NFVS), which consists on finding a minimum cardinality set of vertices that meets all the cycles with an even (odd) number of negative arcs. We study the complexity of these problems and several other related problems. Some of them result to be NP-complete while other are polynomial. Transparencias.
Topological Properties of Networks: A Qualitative Reasoning Approach
Dra. Andrea Rodriguez, DIICC, UdeC.
Viernes 4 de abril, 17:00, sala postgrado matemática, 1er piso Fac. de Cs. Físicas y Matemáticas.
Qualitative reasoning uses a limited set of relevant distinctions of the domain to allow a flexible way of representing and reasoning about it.†This work presents a conceptual framework for qualitative reasoning about information networks from a spatial-topological point of view. We consider the properties of connectivity and some topological invariants to describe the structural characteristics of and the topological relationships between networks. The talk presents a data model for networks which generalizes the notion of graph, founded in algebraic and topological considerations, and compares it to †well-known approaches from the spatial domain. Such conceptual tool can be useful in different domains, from social to technological networks. Transparencias.