Informatique fondamentale

Informatique fondamentale

  • ECTS

    4 crédits

  • Composante

    Collège Sciences et Technologies pour l’Energie et l’Environnement (STEE)

  • Volume horaire

    39h

Description

L’objectif de cette UE est de donner aux étudiants les connaissances de base en calculabilité-décidabilité  et formaliser la calculabilité en s’appuyant sur le modèle de Machine de Turing. De plus, le but de cette UE est d’initier les étudiants aux :

- Méthodes formelles de raisonnement permettant de construire les preuves de terminaison et de correction partielle d’un algorithme,

 - Aux techniques pour estimer la complexité d’un algorithme.

Les thématiques abordées sont :

  • Calculabilité et limitation des algorithmes,
  • Modèle de machine de Turing,
  • Programmation de la machine de Turing,
  • Correction totale des algorithmes,
  • Complexité et classes de complexité.
Lire moins

Objectifs

À la fin de cette UE, vous serez capable de :

• Analyser la calculabilité d’un problème : décidabilité, semi-décidabilité et indécidabilité,

• Formaliser la notion de calculabilité au sens de Turing: modèle de Machine de Turing,

• Programmer la Machine de Turing,

• Apporter la preuve de correction totale d'un algorithme : preuve de terminaison et de correction partielle,

• Estimer la complexité d’un algorithme correct et déterminer la classe de complexité d’un problème.

Lire moins

Heures d'enseignement

  • Informatique fondamentale - CMCours Magistral19,5h
  • TDTravaux Dirigés10,5h
  • TPTravaux Pratique9h

Pré-requis obligatoires

Algorithmique I

Lire moins

Contrôle des connaissances

100% Contrôle Continu Intégral. 

L’évaluation se fait sur la base de deux contrôles continus écrits de 1h30 maximum.

Lire moins

Compétences acquises

Compétences

Niveau d'acquisition

Mise en œuvre de méthodes et d'outils du champ disciplinaireAnalyser et interpréter les résultats produits par l'exécution d'un programme: terminaison, test , complexité 1 - Notion
Expliquer et documenter la mise en œuvre d'une solution Informatique.3 - Maitrise
Caractériser le rôle des tests et des preuves de correction dans le développement des logiciels et mettre en œuvre des tests élémentaires et des invariants de boucle3 - Maitrise
Appliquer des approches raisonnées de résolution de problèmes complexes : modèle formel d'un problème, réduction et complétude de problèmes3 - Maitrise
Identification d'un questionnement au sein d'un champ disciplinaireChoisir, sur des critères objectifs, les structures de données et construire les algorithmes les mieux adaptés à un problème donné.3 - Maitrise