Objectifs du module 1 (examen) :

Leçon I.1 (Algorithmes et complexité) :

+ savoir définir ce qu'est un algorithme

+ connaître les notions d'instruction élémentaire, expression et structures de contrôle

+ savoir « lire » (= faire dérouler) un algorithme itératif simple

+ savoir écrire un algorithme itératif simple

+ savoir définir la complexité d'un algorithme (notion de fonction de la taille de l'entrée)

+ savoir calculer la complexité d'un algorithme itératif simple

+ connaître la meilleure complexité d'algorithmes de recherche dans une liste non triée, recherche dans une liste triée, tri (interne) d'une liste 

----------------------------------------------------------------------
Leçon I.2 (Stratégies de résolution de problèmes) :

+ savoir définir ce qu'est un algorithme récursif

+ connaître les principes de la programmation dynamique

+ savoir « lire » (= faire dérouler) un algorithme récursif simple

+ savoir écrire un algorithme récursif simple

+ savoir calculer la complexité d'un algorithme récursif simple

+ connaître la meilleure complexité d'algorithmes de plus court chemin

----------------------------------------------------------------------
Leçon I.3 (Théorie du calcul) :

+ savoir ce que sont une machine de Turing et LA machine de Turing universelle

+ savoir lire (et appliquer) une table de machine de Turing

+ comprendre ce qu'est un problème (question + instances)

+ connaître (= savoir expliquer) les notions de décidabilité/calculabilité et complexité d'un problème (décidable)

+ savoir définir P et NP ; les positionner (P dans NP, et on en sait pas si NP est P ou non)

+ pouvoir citer un exemple de problème non-décidable

+ pouvoir citer quelques exemples de problèmes dans P, et d'autres dans NP dont on ne sait pas s'ils sont dans P

+ savoir que le problème de la 3-coloration de graphe est dans NP

----------------------------------------------------------------------
Leçon I.4 (Représentation des nombres) :

+ savoir représenter un nombre entier positif en binaire

+ savoir représenter un nombre entier négatif en binaire en utilisant le complément à 2

+ savoir additionner deux nombres entiers dans chacune des deux représentations citées ci-dessus

+ connaître les notions de bits de poids forts, de poids faibles et bit de signe

+ comprendre la notion de dépassement de capacité des représentations des nombres entiers

+ savoir représenter en format « à virgule flottante » un nombre décimal de valeur absolue supérieure ou égale à 1

+ comprendre et savoir calculer la notion d'erreur relative

+ savoir que l'erreur relative des représentations « à virgule flottante » est majorée par la constante 2^{- taille de la mantisse} (hors du voisinage de 0)