Abstract FR:

Nous étudions l'algorithmique de deux problèmes centraux d'Intelligence Artificielle, pour des bases de connaissances représentées, notamment, par des formules propositionnelles de Horn, bijonctives, Horn-renommables ou affines. Nous traitons tout d'abord l'acquisition de connaissances à partir d'exemples : nous donnons notamment un algorithme efficace et général pour l'acquisition exacte, complétons l'état de l'art pour l'approximation et donnons un algorithme pour le PAC-apprentissage des formules affines. Nous étudionsensuite des problèmes de raisonnement : nous donnons un algorithme général pour l'abduction et posons de premières pierres pour l'étude de l'abduction avec des connaissances approximatives. L'étude des formules affines pour la représentation de connaissances n'avait jamais été réellement menée. Les résultats présentés dans ce mémoire montrent qu'elles possèdent de nombreuses bonnes propriétés.