We study the algorithmics of two central problems in Artificial Intelligence, for knowledge bases represented, in particular, by propositional Horn, bijunctive, Horn-renamable, or affine formulas. We first study knowledge acquisition from examples: in particular, we give a generic and efficient algorithm for exact acquisition, we complete the state-of-the-art for approximation, and we give an algorithm for PAC-learning affine formulas. Then we study reasoning problems: we give a generic algorithm for abduction, which enables us to exhibit new polynomial classes, and we give first results about this process for the case when the knowledge base is approximate. The study of affine formulas for knowledge representation had never really been undertaken. The results presented in this thesis show that they have many good properties.
