ECTS
5
Établissement
INP - ENSEEIHT
Liste des enseignements
Programmation Déclarative
Établissement
INP - ENSEEIHT
Période de l'année
Printemps
La matière gravite autour de plusieurs cours visant à introduire différentes techniques et outils formels pour la modélisation de problèmes (programmation
logique, réseaux de contraintes, problèmes SAT/SMT), ainsi que pour leur résolution automatique (système résolution + branch-and-bound/branch-and-prune,
arbres de décision, réduction de symétries...).
La théorie abordée en cours est mise en pratique au travers de divers TP, introduisant des technologies comme Prolog (programmation logique) et Z3
(solveur SAT/SMT), et amenant les étudiants à modéliser des problèmes divers (problèmes combinatoires, problèmes d'opitimization en variables entières,
résolution de sudoku, synthèse d'expressions arithmétiques...).
Les compétences relatives à cette matière sont validées par une bureau d'étude (TP noté) qui recouvre l'ensemble des connaissances et techniques abordées au
fil des cours et des TP.
Programmation Avancée
Établissement
INP - ENSEEIHT
Période de l'année
Printemps
Cette matière expose des approches modernes de la programmation :
décorateurs/annotations, inversion de contrôle et injection de dépendances, proxy, programmation par aspects. Les langages supports sont Python et Java.
Calculabilité
Établissement
INP - ENSEEIHT
La première partie du cours explore les fondements théoriques de l’informatique, en s’appuyant sur le modèle des machines de Turing pour définir la notion de calcul et d’algorithme. Il aborde les concepts clés d’indécidabilité (comme le problème de l’arrêt) et de réduction, illustrant comment certains problèmes ne peuvent pas être résolus par un algorithme. Le cours présente également des variantes des machines de Turing (multi-rubans, non-déterminisme) et leur équivalence. Il discute des limites du calcul, notamment à travers la thèse de Church-Turing.
La seconde partie introduit les concepts fondamentaux de la complexité algorithmique, en se concentrant sur l'analyse des ressources (temps, espace) nécessaires pour résoudre des problèmes. Il définit les classes de complexité comme P (problèmes solubles en temps polynomial) et NP (problèmes vérifiables en temps polynomial), et explore la question ouverte majeure P = NP ?. Le cours aborde également les notions de réduction polynomiale, de NP-complétude, illustrée par des problèmes emblématiques comme SAT (satisfiabilité booléenne), et de complexité spatiale. Enfin, il présente les limites des modèles de calcul classiques et introduit brièvement la complexité probabiliste (BPP) et quantique (BQP).