Informatique fondamentale

Présentation

1. Calculabilité et modèle de Machine de Turing
2. Problème de terminaison d'un algorithme
3. Correction d'un algorithme
4. Complexité d'un algorithme et Classes de complexité

Objectifs

• Formaliser les notions de Calculabilité/Décidabilité et d'Algorithmes
• Apprendre à vérifier si un algorithme se termine, prouver sa correction et estimer son efficacité en calculant sa complexité

Conditions d'admission

Algorithmique - Structures de données - Algèbre 1

Volume horaire

• CM : 19,5 h
• TD : 19,5 h

Examens

Contrôle continu (50%)

Examen terminal (50 %)