Informatique fondamentale

• logique Booléenne: syntaxe, sémantique, algorithmes de test de satisfaisabilité, déduction naturelle, résolution.

• réduction entre problèmes, et notamment réduction vers le problème de satisfaisabilité en logique Booléenne et utilisation de solveurs SAT.

• logique du premier ordre: syntaxe, sémantique, déduction naturelle, résolution, modélisation de problèmes en logique du premier ordre et utilisation de solveurs.
  
  automates finis et expressions rationnelles

• sujets avancés: limites algorithmiques pour le raisonnement logique

 

Ce cours vise à familiariser l'étudiant avec les concepts fondamentaux de l'informatique: logique et applications, systèmes de preuves, réduction entre problèmes, complexité, calculabilité, Machines de Turing et automates finis, correction de programmes. Le cours donne une introduction générale à ces notions et ne se substitue pas à des cours plus poussés donnés en Master, notamment sur la calculabilité et la complexité. Pour la réduction entre problèmes, le cours s'appuyera particulièrement sur le problème de satisfaisabilité en logique Booléenne, pour lequel de nombreux outils de résolution existent.

A l'issue de ce cours, l'étudiant devra avoir compris les notions de base abordées dans le cours, savoir modéliser des problèmes concrets d'informatique et les formaliser, notamment en logique, savoir formaliser des propriétés mathématiques, maîtriser les règles de déduction classique pour la formalisation de preuves.

Cours co-requis

Cours ayant celui-ci comme co-requis

Cours théoriques et exercices. 

Support(s) de cours

• Université virtuelle

Contacts

efiliot@ulb.ac.be

Campus

Plaine, Solbosch

Méthode(s) d'évaluation

• Examen écrit

Examen écrit

Examen écrit.

Construction de la note (en ce compris, la pondération des notes partielles)

En première comme en seconde session, la note sera celle de l'examen écrit.

Langue(s) d'évaluation

• français