ÉQUIPE AMACC

Algorithmes, Modèles de calcul, Aléa, Combinatoire, Complexité

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.

Au niveau normand : participation à l’axe AlgoComb de la fédération NormaStic.

Au niveau national : participation à divers groupes de travail du GDR IM

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. 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.

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 !