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.

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 projet obligatoires (pas de seconde session pour le projet).

Note importante: A chaque session d'examen, un.e étudiant.e pourra être contacté.e par le responsable du cours afin de justifier ses réponses à l'examen écrit. La date à laquelle des étudiant.es pourraient être convoqué.es au bureau du responsable sera communiquée à l'avance à toute la cohorte, en début de session. Les étudiant.es convoqué.es seront contacté.es au minimum un jour avant cette date, par email. En cas de non-présentation, la note pour le cours sera un zéro.

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

Première session:

L'examen écrit comporte une question qui porte sur le projet. Si l'étudiant.e obtient au moins 50% des points à cette question, le projet compte pour 1/4 de la note finale (pourvu que la note de projet remonte la note). Sinon, le projet ne compte pas. La note est donc construite selon la règle suivante:

SI note_question_projet > 0.5 x note_max_question_projet 
ALORS note_cours := MAX(note_examen, (3 x note_examen + note_projet) / 4)
SINON note_cours := note_examen

où
- note_question_projet : note de l'étudiant à la question de l'examen écrit portant sur le projet
- note_max_question_projet : note maximale possible à cette question
- note_cours : note finale du cours
- note_projet : note du projet
- note_examen : note à l'examen écrit

Remarque 1: note_question_projet compte pour calculer note_examen, il est donc fortement recommandé de réaliser le projet afin d'obtenir des points à cette question. 
Report de note de projet: une note de projet ne peut PAS être reportée d'une année n à une année n+1

Deuxième session:

La deuxième session consiste également en un examen écrit (il n'y a pas de deuxième session projet). Il ne comporte pas de question sur le projet. 
La note de projet ne comptera pour 1/4 de la note de deuxième session, que si la question projet a été réussie à au moins 50% à l'examen écrit de première session, et que cette note de projet remonte la note globale.  

SI note_question_projet > 0.5 x note_max_question_projet 
ALORS note_cours := MAX(note_examen_2eme_session, (3 x note_examen_2eme_session + note_projet) / 4)
SINON note_cours := note_examen_2eme_session

Langue(s) d'évaluation

• français