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)
Séminaire Algorithmique : Mostafa Gholami (GREYC, Caen) « Multicolor bipartite Ramsey numbers for paths, cycles, and stripes »
Sciences 3- S3 351Frank Ramsey introduced the theory that bears his name in 1930. The main subject of the theory are complete graphs whose subgraphs can have some regular properties. Most commonly, we look for monochromatic complete subgraphs, i.e., complete subgraphs in which all of the edges have the same color. Ramsey numbers have attracted the attention of … Continue reading Séminaire Algorithmique : Mostafa Gholami (GREYC, Caen) « Multicolor bipartite Ramsey numbers for paths, cycles, and stripes »
Séminaire Algorithmique : Pierre Béaur (LISN, Université Paris-Saclay) « Walking On a Line: détection de marches S-adiques dans les ω-automates »
Sciences 3- S3 351En dynamique symbolique s'intersectent études des langages, des mots infinis et des structures dynamiques associées. Deux méthodes classiques de construction de ces objets coexistent. D'abord, la méthode de Thue construit un mot infini à l'aide d'une substitution (un morphisme de mots) : on itère la substitution sur une lettre initiale, et on considère le mot … Continue reading Séminaire Algorithmique : Pierre Béaur (LISN, Université Paris-Saclay) « Walking On a Line: détection de marches S-adiques dans les ω-automates »
Séminaire Algorithmique : “Robustness of the RAM model” or “how to perform a division in constant time”, Etienne Granjean (GREYC, Caen)
Sciences 3- S3 351Accurately measuring the complexity of algorithms and establishing the intrinsic computational complexity of problems are among the most important tasks/goals in computer science. For this, everyone agrees that the right model of computation (for sequential algorithms) is the random access machine (RAM). Contrary to this general agreement, paradoxically, there is no consensus on how to … Continue reading Séminaire Algorithmique : “Robustness of the RAM model” or “how to perform a division in constant time”, Etienne Granjean (GREYC, Caen)