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é-complexité.
- Les thématiques abordées sont :
- Notion de modèle de calcul,
- Étude des automates finis déterministes,
- Coût asymptotique d’un algorithme.
Objectifs
À la fin de cette UE, vous serez capable de :
- Déterminer ce qui est calculable ou non dans un modèle simple de calcul,
- Manipuler les automates finis déterministes,
- Estimer le coût asymptotique d’un algorithme.
Heures d'enseignement
- CMCours Magistral15h
- TDTravaux Dirigés24h
Pré-requis obligatoires
Algorithmique I.
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.
Compétences acquises
Compétences | Niveau d'acquisition | |
|---|---|---|
| Mise en œuvre de méthodes et d'outils du champ disciplinaire | Mettre en œuvre des méthodes d'analyse pour concevoir des modèles de données et des algorithmes à partir d'un cahier des charges partiellement défini. | 3 - Maitrise |
| Analyser 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 boucle | 3 - 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èmes | 3 - Maitrise | |
| Identification d'un questionnement au sein d'un champ disciplinaire | Choisir, sur des critères objectifs, les structures de données et construire les algorithmes les mieux adaptés à un problème donné. | 3 - Maitrise |
Liste des enseignements
Informatique fondamentale - Calculabilité
2 crédits19,5hInformatique fondamentale - Complexité
2 crédits19,5h