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.

• introduction à la complexité de problèmes: classes de complexité P et NP, NP-complétude, autres classes.

• introduction à la calculabilité: machines de Turing, problèmes indécidables

• logique du premier ordre: syntaxe, sémantique, résolution, modélisation de problèmes en logique du premier ordre et utilisation de solveurs.

• formalisation de propriétés de programmes et preuves de correction: triplets de Hoare.

• automates finis et expressions rationnelles

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. Réalisation d'un projet : résolution d'un problème à l'aide d'une formalisation en logique et d'un solveur.

Contribution au profil d'enseignement

Ce cours contribue à l'apprentissage de la formalisation rigoureuse de problèmes et de leur analyse. Les notions abordées dans ce cours sont fondamentales et font partie des connaissances de base indispensables à l'analyse rigoureuse de problèmes tant pratiques que théoriques.

Support(s) de cours

• Université virtuelle

Contacts

efiliot@ulb.ac.be

Campus

Plaine, Solbosch

Méthode(s) d'évaluation

• Examen écrit
• Projet

Examen écrit

Projet

Examen écrit et un projet

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

Examen écrit: 3/4 Projet: 1/4

Il n'y a pas de seconde session projet. 

Langue(s) d'évaluation

• français