Effectivité et efficacité pour résoudre un problème. Le modèle des machines de Turing et les problèmes demi-décidables. Les problèmes décidables. La réduction de problèmes.Un premier problème indécidable : l’arrêt des machines de Turing. Par réductions, d’autres problèmes indécidables : Rice, PCP, ... Les problèmes polynomiaux P, non-déterministes polynomiaux NP, et NP-complets. Un premier problème NP-complet (Cook) : SAT. Par réductions polynomiales, d’autres problèmes NP-complets : transversale, voyageur de commerce, chemin hamiltonien, partition, mariages à trois, ...,. Evaluation de la complexité de programmes itératifs et récursifs : sommations et récurrences.