-
Partager cette page
Informatique fondamentale
Titulaire(s) du cours
Emmanuel FILIOT (Coordonnateur)Crédits ECTS
5
Langue(s) d'enseignement
français
Contenu du cours
-
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
Objectifs (et/ou acquis d'apprentissages spécifiques)
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.
Pré-requis et Co-requis
Cours co-requis
Cours ayant celui-ci comme co-requis
Méthodes d'enseignement et activités d'apprentissages
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
Autres renseignements
Contacts
efiliot@ulb.ac.be
Campus
Plaine, Solbosch
Evaluation
Méthode(s) d'évaluation
- Examen écrit
- Projet
Examen écrit
Projet
Examen écrit et projet obligatoires (pas de seconde session pour le 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