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 de s’intéresse à 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, algorithmique du texte, combinatoire bijective, combinatoire analytique.
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.
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.
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, (UNICAEN)
DIEN Matthieu – Maître de conférences, (UNICAEN)
DORBEC Paul – Professeur, UNICAEN
PÉPIN Martin – Maître de conférences, UNICAEN
LHOTE, Loïck – Porfesseur, ENSICAEN
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
ACKERMANN Léo – Doctorant
BERGERAT Loris – Doctorant CIFRE
CANARD Sébastien – HDR-associé
CALLARD Antonin – Doctorant
DAUPRAT Quentin – Doctorant CIFRE
DOUTEAU Antoine – Doctorant
GRANDJEAN Etienne – Professeur émérite à l’Université de Caen Normandie
GHOLAMI Mostafa – Doctorant
GRENTE Théo – Chargé temporaire d’enseignement et de recherche
KARCZMARCZUK Jerzy – Chercheur associé
MARÉCHAL Rémi – Post-doctorant
MITTELSTAEDT Arthur – Doctorant
NGUYEN Thi Thu Quyen – Doctorante
REPEL Émeline – Ingénieure d’études
VALLÉE Brigitte – Directrice de recherche émérite au CNRS
Projet EPAA (Entropy and Probabilistic Analysis in Algorithms), 2024-2026 (France, Uruguay, Argentine).
Participation au SINFIN (Laboratoire Internationale Associé CNRS) depuis 2015, Buenos Aires, Argentine.
ANR C_SyDiSi (Complexité des Systèmes Dynamiques Simples), porteur : Gaétan Richard, participants : Ali Akhavi, Julien Clément, Julien Courtiel, Matthieu Dien, Loïck Lhote, Véronique Terrier et Pascal Vanier.
ANR PANDAG (Analyse de paramètres de classes de DAGs); coordinateur national : Antoine Genitrini; coordinateur local : Julien Clément; participants : Julien Clément, Julien Courtiel, Matthieu Dien et Martin Pépin.
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. Il s’agit d’un logiciel de génération aléatoire 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 : « Un cafard sous le chapeau », Victor Luftalla (LIS, Univ. Aix-Marseille)
26 novembre / 10:00 - 11:00Séminaire Algorithmique : « Combinatoire énumérative et bijective de différentes familles de chemins de Dyck avec trous d’air », Rémi Maréchal (GREYC, Caen)
19 novembre / 10:45 - 11:45Séminaire Algorithmique : « Planar or almost planar graphs: topology to the rescue of algorithms », Arnaud de Mesmay (LIGM, Univ. Paris-Est)
5 novembre / 10:00 - 11:00Séminaire Algorithmique : « Random Deterministic Automata With One Added Transition », Cyril Nicaud (LIGM, Univ. Paris-Est)
22 octobre / 10:45 - 11:45Séminaire Algorithmique : « Classes de sous-shifts définis par des formules logiques », Rémi Pallen (ENS Paris Saclay)
15 octobre / 10:00 - 11:00
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 !
A la rentrée 2020, l’équipe AMACC a accueilli un nouveau professeur : bienvenue à Pascal Vanier !