Semaine du lundi 9 décembre 2024
Le programme de cette semaine inclut une très grande partie du chapitre de calculabilité :
- il faut connaître la notion de fonction calculable
- il faut savoir ce qu'est un problème de décision, un problème d'optimisation, et savoir associer un problème de décision à un problème d'optimisation
- il faut savoir ce que sont des problèmes décidables et indécidables
- il faut connaître au moins le problème de l'arrêt comme problème indécidable
- il faut connaître la notion de réduction, et savoir montrer par réduction la décidabilité ou l'indécidabilité d'un problème en s'appuyant sur un autre (en faisant attention au sens).
- il faut connaître la classe P, la classe NP, et savoir justifier qu'un problème de décision est dans l'une ou l'autre de ces classes
- il faut connaître la notion de réduction polynomiale
Les notions de NP-dureté et de NP-complétude n'ont été que peu travaillées pour l'instant, et ne sont pas exigibles pour cette semaine.
