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
AKHAVI Ali – Maître de conférences, UNICAEN
CLÉMENT Julien – Chargé de recherche au CNRS, HDR
COURTIEL Julien – Maître de conférences, UNICAEN
DAVID Julien – Maître de conférences, (LIPN/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
GRANDJEAN Etienne – Professeur émérite à l’Université de Caen Normandie
GHOLAMI Mostafa – Doctorant
KARCZMARCZUK Jerzy – Chercheur associé
LECOQ Romain – Doctorant
NGUYEN Thi Thu Quyen – Doctorante
PAVIET SALOMON Léo – Doctorant
ROBIN Cléophée – Postdoctorante
VALLÉE Brigitte – Directrice de recherche émérite au CNRS
Projet STIC RAPA2: Groupe « Randomness and Probabilistic Analysis of Algorithms », 2020 (France, Uruguay, Argentine).
Participation au SINFIN (Laboratoire Internationale Associé CNRS), 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.
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 : « Combinatoire de mots, musiques traditionnelles et improvisation avec ordinateur », Marc Chemillier (EHESS, Paris)
8 octobre / 10:00 - 11:00Séminaire Algorithmique : « StarMalloc : un allocateur de mémoire moderne renforcé formellement vérifié », Antonin Reitz (équipe Prosecco, INRIA Paris)
2 juillet / 10:00 - 11:00Séminiare Algorithmique « Sous-shifts au langage stable », Samuel Petite (LAMFA, Univ. Picardie)
18 juin / 10:00 - 11:00Séminaire Algorithmique : « Génération aléatoire des graphes de Git », Julien Courtiel (GREYC)
11 juin / 10:00 - 11:00Séminaire Algorithmique : « Turing machine dynamics and the SMART machine », Anahi Gajardo (Univ. Conception, Chili)
4 juin / 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 !