Abstract FR:

Cette thèse traite de l'algorithmique d'énumération. Après avoir présenté les concepts particuliers des algorithmes d'énumération, nous nous intéressons plus particuliérement à deux problèmes, l'énumération des cliques maximales et l'énumération des bicliques maximales d'un graphe. Pour ce dernier problème, trois variantes seront traitées : énumération des bicliques maximales induites, non induites et pour le cas particulier des graphes biparti. Cette thèse propose des liens entre les algorithmes existants pour ces problèmes. On s'intéresse à l'énumération des éléments d'une base minimun d'implications. Comme il n'existe pas à l'heure actuelle d'algorithme d'énumération polynomial pour ce problème, les approches présentées ici utilisent un autre angle d'approche : trouver une base minimun plus petite, ou plus rapide à calculer, permettant de reconstruire la base minimum initiale en temps polynomial. Dans ce but, deux résultats sont présentés : les éléments clones d'une relation et la famille des systèmes de fermeture partageant une certaine partie d'une base minimun