Séminaire Algorithmique : Solène Esnay (IMT, Univ. Toulouse 3) « Arithmetical Complexity of the Language of Generic Limit Sets of Cellular Automata »
Sciences 3- S3 351Dynamical systems have various notions of attractor, and they characterize different asymptotic properties. Among them is the notion of generic attractor: a closed set that attracts most of the space in the topological sense, meaning its basin of attraction is comeager. The generic limit set is the smallest generic attractor and contained in all of … Continue reading Séminaire Algorithmique : Solène Esnay (IMT, Univ. Toulouse 3) « Arithmetical Complexity of the Language of Generic Limit Sets of Cellular Automata »
Séminaire Algorithmique : Mehdi Naima « Extending Brandes algorithm to improve betweenness centrality computation in temporal graphs with discrete and continuous time »
Sciences 3- S3 351Betweenness centrality has been a long subject of study in network science since it was introduced by Freeman in 1977. This centrality measure assesses the importance of nodes in a graph, it has been used for example in social, biological and research collaboration networks. Moreover, betweenness centrality has been used in graph partitioning and community … Continue reading Séminaire Algorithmique : Mehdi Naima « Extending Brandes algorithm to improve betweenness centrality computation in temporal graphs with discrete and continuous time »
Séminaire Algorithmique : « Algorithmes pour la Dimension Métrique dans les graphes dirigés » Antoine Dailly (LIMOS, Univ. Clermont-Ferrand)
Sciences 3- S3 351Résumé : Le problème de la Dimension Métrique d’un graphe se pose de la façon suivante : on cherche un ensemble R de sommets de taille minimale tel que, pour toute paire de sommets du graphe, il existe un sommet de R dont les distances aux deux sommets de la paire sont distinctes. Ce problème … Continue reading Séminaire Algorithmique : « Algorithmes pour la Dimension Métrique dans les graphes dirigés » Antoine Dailly (LIMOS, Univ. Clermont-Ferrand)
Séminaire Algorithmique : « Complexity of positionnal games » Valentin Gledel (Univ. Umea, Suède)
Sciences 3- S3 351Attention ! Exceptionnellement, le séminaire à lieu lundi à 14h. Résumé : Complexité des jeux positionnels Les jeux positionnels sont des jeux à deux joueurs joués dans un hypergraphe. Les joueurs sélectionnent alternativement des sommets de l'hypergraphe et les conditions de victoires dépendent uniquement du remplissage des hyperarêtes. Le morpion est un exemple célèbre de … Continue reading Séminaire Algorithmique : « Complexity of positionnal games » Valentin Gledel (Univ. Umea, Suède)
Séminaire Algo: Alexandros Singh (LIPN, Univ. Paris Nord) « Combinatorics of the lambda-calculus and maps: bijections and limit properties »
Sciences 3- S3 351This talk concerns maps (graphs embedded on surfaces), the linear lambda-calculus, and their combinatorial interactions. Using a combination of new bijective and analytic techniques, we will explore the structure of large random cubic maps and linear lambda-terms, focusing on the study of various statistics on such objects, in particular those related to the presence of … Continue reading Séminaire Algo: Alexandros Singh (LIPN, Univ. Paris Nord) « Combinatorics of the lambda-calculus and maps: bijections and limit properties »
Séminaire Algo : Pierre Popoli (LORIA, Univ. de Lorraine) « Sum of digits, pseudorandomness and measures of complexity »
Sciences 3- S3 351The sum of digits function in base 2, also called the Hamming weight, is the number of non-zero binary digits of an integer. This function is a central object for all my present research and appears in many scientific fields, such as number theory, combinatorics on words, and coding theory. In this talk, I will … Continue reading Séminaire Algo : Pierre Popoli (LORIA, Univ. de Lorraine) « Sum of digits, pseudorandomness and measures of complexity »
Séminaire Algorithmique : Martin Pépin (LIPN, Univ. Paris Nord) « Directed Ordered Acyclic Graphs, asymptotic analysis and efficient random sampling »
Sciences 3- S3 351Directed Acyclic Graphs (DAGs) are directed graphs in which there is no path from a vertex to itself. They are an omnipresent data structure in computer science and the problem of counting the DAGs of given number of vertices has been solved in the 70’s by Robinson. In this talk, I will introduce a new … Continue reading Séminaire Algorithmique : Martin Pépin (LIPN, Univ. Paris Nord) « Directed Ordered Acyclic Graphs, asymptotic analysis and efficient random sampling »
Séminaire Algorithmique: ANNULÉ EN RAISON DU MOUVEMENT DE GRÈVE
Sciences 3- S3 351Silvère Gangloff (Univ. AGH, Cracovie, Pologne) « Classes de transitivité pour les sous-décalages de type fini multi-dimensionnels » Ce travail est en commun avec B. Hellouin et P. Oprocha. Les sous-décalages de type fini multidimensionnels ont été étudiés dans les dernières décennies à travers le spectre de propriétés topologiques telles que la transitivité ou le … Continue reading Séminaire Algorithmique: ANNULÉ EN RAISON DU MOUVEMENT DE GRÈVE
Séminaire Algo : Edwin Hamel (Univ. libre Bruxelles, Belgique) « Two-player boundedness counter games »
Sciences 3- S3 351We consider two-player zero-sum games with winning objectives beyond regular languages, expressed as a parity condition in conjunction with a Boolean combination of boundedness conditions on a finite set of counters which can be incremented, reset to 0, but not tested. A boundedness condition requires that a given counter is bounded along the play. Such … Continue reading Séminaire Algo : Edwin Hamel (Univ. libre Bruxelles, Belgique) « Two-player boundedness counter games »
Séminaire Algorithmique : Gabriel Le Bouder (LIP6, Sorbonne Univ.) « Memory-Optimization for Self-Stabilizing Distributed Algorithms »
Sciences 3- S3 351Self-stabilization is a suitable paradigm for distributed systems, particularly prone to transient faults. Errors such as memory or messages corruption, break of a communication link, can put the system in an inconsistent state. A protocol is self-stabilizing if, whatever the initial state of the system, it guarantees that it will return a normal behavior in … Continue reading Séminaire Algorithmique : Gabriel Le Bouder (LIP6, Sorbonne Univ.) « Memory-Optimization for Self-Stabilizing Distributed Algorithms »
Séminaire Algorithmique : Julien Clément (GREYC, Caen) « Combinatorics of reduced ordered binary decision diagrams. Application to random uniform sampling »
Sciences 3- S3 351Any Boolean function corresponds to a complete full binary decision tree. This tree can in turn be represented in a maximally compact form as a directed acyclic graph where common subtrees are factored and shared, keeping only one copy of each unique subtree. This yields the celebrated and widely used structure called reduced ordered binary … Continue reading Séminaire Algorithmique : Julien Clément (GREYC, Caen) « Combinatorics of reduced ordered binary decision diagrams. Application to random uniform sampling »
Séminaire Algorithmique : Victor Lutfalla (GREYC, Caen)
Salle à déterminerUn pavage est un recouvrement du plan par des tuiles qui ne se chevauchent pas. On appelle sous-shift un ensemble de pavages qui est invariant par translation et fermé (pour la topologie habituelle sur les pavages). Ici on s’intéresse au cas où il y a un nombre fini de tuiles à translation près, les tuiles … Continue reading Séminaire Algorithmique : Victor Lutfalla (GREYC, Caen)