PRÉSENTATION
Responsable d’équipe : Paul DORBEC
L’équipe AMACC se caractérise par une identité culturelle forte, celle de l’informatique mathématique (IM). L’équipe se retrouve d’abord autour deux concepts génériques, l’algorithme et la complexité, qui sous-tendent toutes ses activités. Elle y adopte des points de vue complémentaires. Le premier étudie les modèles de calcul et la notion de complexité, dans le pire des cas, via les classes de complexité. Le second travaille dans un cadre aléatoire, avec des modèles probabilistes, comme outil notamment pour l’analyse de complexité en moyenne.
Mots clés : informatique mathématique, modèles de calcul, complexité, automates cellulaires, machines RAM, analyses dynamiques d’algorithmes, algorithmes euclidiens, réseaux euclidiens, algorithmique du texte, combinatoire bijective, combinatoire analytique, cryptographie.
THÉMATIQUE DE RECHERCHE
Les activités principales de l’équipe s’articulent autour de trois piliers fondamentaux : l’algorithme, le problème, et la donnée d’entrée. Schématiquement, un algorithme traite une donnée pour résoudre un problème. Les travaux de l’équipe portent sur ces trois notions fondamentales de l’informatique, vus comme des objets mathématiques, ainsi que sur les relations entre ces objets.
Il s’agit d’étudier la complexité en moyenne, mais aussi dans le pire des cas. La complexité est une étude de l’algorithme au regard de l’ensemble des ses données d’entrée. Pour étudier la complexité en moyenne d’un algorithme, il est nécessaire de représenter les entrées dans leur ensemble. Ceci peut passer par une énumération des objets d’étude, ou considérer un modèle probabiliste sur ces données.
L’équipe s’intéresse aussi aux modèles d’algorithmes, définissant l’algorithme comme un système dynamique, et à la création ou l’amélioration d’algorithmes.
Pour un problème, on parle aussi de complexité, au sens de la théorie de la complexité. C’est une étude du problème au regard de l’ensemble des algorithmes qui peuvent le traiter. Nous nous intéressons aux différentes classes de complexité des problèmes (les plus réputées étant P et NP), indépendamment de la spécificité de chaque algorithme. Les problèmes difficiles à résoudre ont, en particulier, des applications en cryptographie.
L’étude de la complexité des problèmes fait également appel à des modèles de calcul et à de la logique.
Les données sont ici étudiées en tant qu’objets combinatoires, tels que des mots, des arbres ou des graphes. Notamment, l’intérêt se porte sur les propriétés structurelles de ces objets, leur dénombrement ainsi qu’à leur génération. L’équipe étudie aussi l’entropie d’un ensemble de données qui traduit la quantité d’information nécessaire pour modéliser la diversité des données possibles.
VIDÉOS DE PRESENTATION
POUR EN SAVOIR PLUS
CLÉMENT Julien – Chargé de recherche au CNRS, HDR
COURTIEL Julien – Maître de conférences, UNICAEN
DAVID Julien – Maître de conférences, HDR, UNICAEN
DIEN Matthieu – Maître de conférences, UNICAEN
DORBEC Paul – Professeur, UNICAEN
LHOTE, Loïck – Porfesseur, ENSICAEN
PÉPIN Martin – Maître de conférences, UNICAEN
RANAIVOSON Solomanpionona – Maître de conférences, UNICAEN
RICHARD Gaétan – Maître de conférences, UNICAEN
ROUX-LANGLOIS Adeline – Directrice de recherche CNRS
TERRIER Véronique – Maître de conférences, HDR, UNICAEN
VANIER Pascal – Professeur, UNICAEN
BEAUGRAND Agathe – Chargée temporaire d’enseignement et de recherche
BERGERAT Loris – Doctorant CIFRE
CANARD Sébastien – HDR-associé
DEMARET Hugo – Doctorant
DOUTEAU Antoine – Doctorant
GRANDJEAN Etienne – Professeur émérite à l’Université de Caen Normandie
GRENTE Théo – Chargé temporaire d’enseignement et de recherche
KARCZMARCZUK Jerzy – Chercheur associé
MITTELSTAEDT Arthur – Doctorant
REPEL Émeline – Doctorante
VALLÉE Brigitte – Directrice de recherche émérite au CNRS
Projet ANR-ASTRID AMIRAL: AMélioration des sIgnatures reposant sur les Réseaux et Applications aux fonctionnaLités cryptographiques avancées, 2022-2026. Coordinatrice nationale : Adeline Roux-Langlois; Participantes: Adeline Roux-Langlois et Emeline Repel.
Projet STIC AmSud EPAA : Entropy and Probabilistic Analysis in Algorithms, 2024-2025 (France, Uruguay, Argentine). Participant.es : Julien Clément, Julien David, Matthieu Dien, Loïck Lhote, Martin Pépin et Brigitte Vallée.
Projet Lyndex : projet autour des mots de Lyndon financé par la fédération Normastic. Participants : Julien Clément et Julien David.
Projet ANR PANDAG : Analyse de paramètres de classes de DAGs, 2024-2027. Coordinateur national : Antoine Genitrini; Coordinateur local : Julien Clément; Participants : Julien Clément, Julien Courtiel, Matthieu Dien et Martin Pépin.
Projet ANR PLASMA : Programming Languages, Algorithms and Structures: Models and Analysis, 2026-2030. Coordinateur national : Cyril Nicaud; Participant.es : Julien Clément, Julien Courtiel, Julien David, Matthieu Dien, Martin Pépin et Brigitte Vallée.
PEPR PQ-TLS : Post-quantum padlock for web browser, 2022-2027. Participante : Adeline Roux-Langlois.
Participation au SINFIN, Projet de Recherche International du CNRS avec l’Argentine depuis 2015, dont nous somme co-responsables de l’équipe Randomness and Analysis of Algorithms. Participant.es : Julien Clément, Julien David, Matthieu Dien, Loïck Lhote, Martin Pépin et Brigitte Vallée.
Au niveau normand : participation à l’axe AlgoComb de la fédération NormaStic.
Au niveau national : participation à divers groupes de travail du GDR IFM et du GDR Sécurité
Au niveau international : collaboration étroite avec l’Amérique du Sud (Argentine, Uruguay) via des projets internationaux (voir onglet du dessus)
Projet ThemaMap : outil de cartographie thématique multi plateforme, distribué en tant que logiciel libre. Il est développé en collaboration par le GREYC, le SAIC-CERTIC et le CRH.
Usain Boltz, par Matthieu Dien et Martin Pépin. Librairie Python pour la génération aléatoire uniforme efficace de grandes structures de données.
VIE D’ÉQUIPE
L’équipe se réunit également de mpériodiquement autour d’un Groupe de Lecture et de Travail (GLT).
URL : https://glt-amacc.greyc.fr/
L’équipe anime et organise le séminaire hebdomadaire d’Algorithmique, depuis maintenant une vingtaine d’années.
URL: https://clementj01.users.greyc.fr/semalgo/ et le calendrier du GREYC.
Séminaire Algorithmique : Rachelle Heim (UC Louvain, Belgique), « Generic attacks using random functions statistics »
18 novembre / 10:45 - 11:45Séminaire Algorithmique : Paul Dorbec (GREYC) « How can the balance game be so unfair? »
4 novembre / 10:20 - 11:20Séminaire Algorithmique : Michel Seck (Ecole Politech. Thiès, Sénégal) « Towards post-quantum Bitcoin blockchain using Dilithium signature »
21 octobre / 10:45 - 11:45Séminaire Algorithmique : France Gheeraert (LAMFA, Univ. Picardie) «String attractors, ou comment capturer la combinatoire d’un texte»
14 octobre / 10:45 - 11:45Séminaire Algorithmique : Sarah Riva (LIFL, Univ. Lille) « Control and synthesis of minimal trap spaces in Boolean Network »
7 octobre / 10:45 - 11:45
FAITS MARQUANTS
A l’heure de l’évaluation HCERES, l’équipe AMACC a réalisé quelques vidéos présentant bilan et projet pour le quinquennat 2020-2025.
Paul Dorbec a écrit un chapitre survey sur la « Power Domination » de graphes, qui est apparu dans le livre « Topics in Domination in Graphs ». Ce dernier vient d’être publé chez Springer. A lui les nombreuses citations !