Lien de la soutenance :

https://cnrs.zoom.us/j/96289847336?pwd=SEpPYXE0bTNnc0JKZG5WWTRwMm1zdz09
ID de réunion : 962 8984 7336
Code secret : WvL35j

La théorie des espaces de connaissance est un domaine de la psychologie mathématique dont l'objectif principal est de fournir des outils informatiques permettant de représenter et évaluer la connaissance des étudiants. L'objet central de cette théorie, les espaces de connaissances, est mieux connu sous le nom de système de fermeture (ou treillis). Les systèmes de fermeture sont utilisés dans de nombreux domaines de l'informatique tels que l'analyse formelle des concepts, la logique propositionnelle, la théorie des bases de données, l'optimisation combinatoire ou la théorie de l'argumentation. Toutefois, en raison de leur taille, les systèmes de fermetures sont souvent représentés implicitement par des implications ou par leurs éléments inf-irréductibles. Dans cette thèse, nous étudions deux problèmes concernant les systèmes de fermeture et leurs représentations.

Dans un premier temps, nous nous intéressons au problème de traduction entre les représentations d'un système de fermeture. Ce problème ouvert bien connu est une généralisation du problème de dualisation des hypergraphes. Notre approche consiste en une décomposition hiérarchique d'une base d'implications reposant sur l'opération de split (acyclique). Nous déduisons de cette opération une caractérisation récursive des inf-irréductibles du système de fermeture associé. De cette caractérisation, nous obtenons alors de nouvelles classes de systèmes de fermeture dans lesquels l'énumération des inf-irréductibles peut-être conduite en temps total quasi polynomial, en nous reposant sur la dualisation des hypergraphes.

Ensuite, nous étudions les familles d'ensembles interdits dans les systèmes de fermeture. Plus précisément, nous considérons les problèmes d'énumération des ensembles fermés (les éléments du système de fermeture) qui sont admissibles ou préférés (parmi les admissibles, les minimaux ou les maximaux) par rapport à une famille d'ensembles interdits. En utilisant la dualisation dans les treillis, nous donnons plusieurs résultats de complexité. D'autre part, nous obtenons des algorithmes totaux polynomiaux ou quasi polynomiaux sous certaines restrictions concernant les paires ou co-paires interdites et le nombre de Carathéodory d'un système de fermeture.

Membres du jury :
Kira Adaricheva - Professor - Hoftstra University, Hempstead - Rapporteur
Karel Bertet - Maître de conférences (HDR) - Université de la Rochelle - Rapporteur
Sergeï Kuznetsov - Professor - Higher School of Economics, Moscou - Rapporteur
Arnaud Mary - Maître de conférence - Université Lyon 1 - Examinateur
Jean-Marc Petit - Professeur des universités - Université Lyon 1 - Examinateur
Lhouari Nourine - Professeur des universités - Université Clermont Auvergne - Directeur