6533b831fe1ef96bd1298433

RESEARCH PRODUCT

Probability and algorithmics: a focus on some recent developments

Christelle RovettaPeggy CénacMathieu SablikRémi VarlootIrène Marcovici

subject

[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]T57-57.97Focus (computing)Applied mathematics. Quantitative methodsTheoretical computer scienceMarkov chainComputer science[MATH.MATH-DS]Mathematics [math]/Dynamical Systems [math.DS][INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]Variable lengthRandom walkCellular automaton[INFO.INFO-CL]Computer Science [cs]/Computation and Language [cs.CL]Perfect sampling[MATH.MATH-PR]Mathematics [math]/Probability [math.PR]Coupling from the past[INFO.INFO-IT]Computer Science [cs]/Information Theory [cs.IT][INFO.INFO-MA]Computer Science [cs]/Multiagent Systems [cs.MA]Algorithmics[MATH.MATH-CO]Mathematics [math]/Combinatorics [math.CO]QA1-939Mathematics

description

Jean-François Coeurjolly, Adeline Leclercq-Samson Eds.; International audience; This article presents different recent theoretical results illustrating the interactions between probability and algorithmics. These contributions deal with various topics: cellular automata and calculability, variable length Markov chains and persistent random walks, perfect sampling via coupling from the past. All of them involve discrete dynamics on complex random structures.; Cet article présente différents résultats récents de nature théorique illustrant les interactions entre probabilités et algorithmique. Ces contributions traitent de sujets variés : automates cellulaires et calculabilité, chaînes de Markov à mémoire variable et marches aléatoires persistantes, échantillonnage parfait par la méthode de couplage par le passé. Leur point commun est de faire intervenir des dynamiques discrètes sur des structures aléatoires complexes.

yearjournalcountryeditionlanguage
2017-01-01
10.1051/proc/201760203https://hal.archives-ouvertes.fr/hal-01970755