ITC2 Python Q.

Fortier

Python M = []
test d’égalité == for i in range(n):
différent != L = []
inférieur ou égal ≤ <= for j in range(p):
division euclidienne // [Link](0)
modulo % [Link](L)
et and
ou or Attention : le code ci dessous ne marche pas, car M a n fois
négation not la même ligne (modifier l’une modifie les autres).

• On peut utiliser if a % b == 0 pour savoir si b divise a

M = []
(exemple : if n % 2 == 0 pour savoir si n est pair).
L = []
• Ne pas confondre == (comparer deux valeurs, dans un if ou for j in range(p):
while) et = (modifier la valeur d’une variable). [Link](0)
for i in range(n):
• La variable modifiée est toujours à gauche du = : [Link](L) # M contient n fois la même liste L !!!
a = b modifie a.
• L[i] donne une erreur si L[i] n’existe pas : • Les types de base (int, float, bool...) sont copiés par
défaut, contrairement aux list :
L = []
a = 3 L1 = [3]
L[0] = 0 # ERREUR !!!
b = a L2 = L1
L = [0] # faire ceci à la place
b = 2 # ne modifie pas a L2[0] = 4 # modifie L1
L = []
[Link](0) # ou ceci
De même lors du passage en argument d’une fonction :

def f(L):
• Ne pas écrire if x == True ou if x == False mais if x L[0] = 3
ou if not x (plus idiomatique). L1 = [2]
• Si L1 et L2 sont des listes de tailles n1 et n2 , L1 + L2 donne f(L1) # L1 est modifié
en complexité O(n1 + n2 ) une nouvelle liste contenant les
éléments de L1 suivis des éléments de L2. • Les indices commencent à partir de 0 : le premier élément
est L[0], le dernier L[len(L) - 1] (qui est obtenu aussi
• n*L duplique la liste L n fois (même chose que avec L[-1]).
L + L + ... + L). Exemple : [0]*4 donne [0, 0, 0, 0].
• L[i:j] extrait de L une sous-liste des indices i à j - 1.
• [... for i in ...] est une création de liste par com- On peut copier une liste avec L[:] ou [Link]().
préhension. Par exemple, [i**2 for i in range(5)]
donne [0, 1, 4, 9, 16] et est équivalent à : • Si x est une liste, un n-uplet, une chaîne de caractères ou
un tableau numpy :
L = [] – x[i] est le îềme élément de x
for i in range(5):
– x[-i] est le ième élément en partant de la fin
[Link](i**2)
– x[i:j] extrait les éléments de x du ième au jème exclu
(exemple : si )
• On peut aussi ajouter une condition dans une liste par com- – len(x) est la taille de x En revanche, on ne peut pas
préhension : [i**2 for i in range(5) if i % 2 == 0] modifier un n-uplet ou une chaîne de caractères (pas
donne [0, 4, 16]. de x[i] = ... ou de [Link](...) dans ce cas).
• Opérations sur une matrice M (comme liste de listes) : • Éviter de faire plusieurs fois le même appel de fonction :
stocker le résultat dans une variable à la place.
Python Signification
M[i][j] mi,j (élément ligne i, colonne j) • Ne pas confondre indice et élément d’une liste :
M[i] ième ligne for i in range(len(L)) parcourt les indices de L (i vaut
len(M) nombre de lignes 0, 1, 2, …, len(L) - 1), alors que for x in L parcourt les
len(M[0]) nombre de colonnes éléments de L (x vaut L[0], L[1], L[2], …, L[len(L) - 1]).
• for i in range(a, b, p) parcourt les entiers de a à
b - 1 en allant de p en p (par défaut a = 0 et p = 1).
• Créer une matrice n × p remplie de 0 :
• Pour écrire une fonction récursive, il faut toujours un cas de
M = [[0]*p for _ in range(n)]
base (qui ne fait pas appel à la fonction elle-même) et un
Ou utiliser des boucles for et append : cas récursif (qui fait appel à la fonction elle-même).
ITC2 SQL Q. Fortier

Pour les exemples, on considère une base de données avec 3 SELECT DISTINCT directeur FROM film, acteur
tables dont les schémas relationnels sont : WHERE directeur = nom
• film (id, titre, annee, directeur, budget, recette)
• acteur (id, nom) • [GROUP BY expr
• casting (id_film, id_acteur) [HAVING condition]]
Regroupe tous les enregistrements ayant la même valeur
Une clé d’une table est un ensemble minimal d’attributs per- expr en un seul enregistrement. Seuls les groupes vérifi-
mettant d’identifier de façon unique chaque enregistrement. ant condition sont renvoyés.
La clé primaire d’une table est une clé dont on garantit l’unic- Les fonctions d’agrégations (dans un SELECT ou
ité même après ajout dans la table. HAVING) s’appliquent alors pour chaque groupe :
Une clé étrangère est un attribut (ou ensemble d’attributs) COUNT(attribut) (nombre d’enregistrements non NULL),
faisant référence à une clé primaire d’une autre table. COUNT(*) (nombre d’enregistrements), SUM(attribut),
MAX(attribut), AVG(attribut) (moyenne), ...
Syntaxe générale de SELECT, dans cet ordre ([...] indiquant
Nombre de films réalisés chaque année depuis 2000 :
une commande optionnelle) :
SELECT annee, COUNT(*)
FROM film
SELECT [DISTINCT] expr1 [AS alias1], expr2, ...
WHERE annee >= 2000
FROM table1 [AS alias1], table2, ...
GROUP BY annee;
[WHERE condition]
[GROUP BY expr
[HAVING condition]] Directeurs ayant rapporté au moins 1 milliard :
[ORDER BY expr [DESC]]
[LIMIT entier SELECT directeur FROM film
[OFFSET entier]] GROUP BY directeur
HAVING SUM(recette) >= 1000000000
• SELECT [DISTINCT] expr1 [AS alias1], expr2, ...
Renvoie une table dont les colonnes correspondent à • [ORDER BY expr [DESC]]
expr1, expr2... Trie les enregistrements selon expr, croissant par défaut
expr1, expr2... sont des expressions, pouvant contenir (décroissant si DESC est utilisé).
des attributs, calculs et fonctions. Si un attribut attr Acteurs triés par le nombre de films joués :
est ambigu (car il est le même dans 2 tables t1 et t2), il
SELECT nom, COUNT(*) AS nb_films
faut le préfixer par son nom de table, par ex. [Link]. FROM acteur JOIN casting ON [Link] = id_acteur
* est un raccourci pour selectionner toutes les colonnes. JOIN film ON [Link] = id_film
AS renomme une colonne pour, par exemple, y faire GROUP BY nom
référence ensuite. ORDER BY nb_films DESC
DISTINCT supprime les doublons.
Obtenir tous les acteurs (sans doublon) : • [LIMIT n
SELECT DISTINCT nom FROM acteur; [OFFSET p]]
Films avec leur profit : Affiche seulement les n premiers enregistrements (en com-
SELECT titre, recette - budget FROM film; mençant à partir du (p + 1)ème). Souvent utilisé après
• FROM table1 [AS alias1], table2, ... un ORDER BY.
Tables d’où les valeurs sont sélectionnées. Deuxième film à plus gros budget :
table1, table2 est la table correspondant au produit SELECT titre FROM film
cartésien de table1 et table2. ORDER BY budget DESC
table1 JOIN table2 ON colonne1 = colonne2 réalise LIMIT 1 OFFSET 2;
la jointure de table1 et table2, où la colonne1 de
table1 est identifiée avec colonne2 de table2. On peut • Sous-requêtes : il est possible d’utiliser un SELECT ren-
mettre plusieurs JOIN à la suite. voyant une seule valeur à l’intérieur d’un autre SELECT,
Tous les directeurs et acteurs ayant travaillé ensemble : dans une condition ou un calcul. Tous les acteurs du film
à plus gros budget :
SELECT directeur, nom FROM film
JOIN casting ON [Link] = id_film SELECT nom FROM acteur
JOIN acteur ON id_acteur = [Link] JOIN casting ON id_acteur = [Link]
JOIN film ON id_film = [Link]
• [WHERE condition] WHERE titre = (SELECT titre FROM film
Ne considère que les enregistrements vérifiant condition. ORDER BY budget DESC LIMIT 1)
condition peut contenir des attributs, calculs, AND, OR,
<, <=, !=, LIKE, IN... • Opérateurs ensemblistes :
Tous les directeurs qui sont aussi acteurs : Étant donné deux requêtes de la forme SELECT ...
 renvoyant deux relations table1 et table2 de même livre emprunté emprunt dans bibliotheque
schéma relationnel, il est possible d’obtenir leur union,
intersection et différence avec UNION, INTERSECT, MINUS.
Exemple : emprunte

table1 table2
attr1 attr2 attr3 attr1 attr2 attr3 emprunteur
a1 a2 a3 a1 a2 a3
b1 b2 b3 c1 c2 c3 3 relations binaires

attr1 attr2 attr3 • On peut spécifier le lien entre une entité et une associa-
a1 a2 a3 tion avec un couple (n, p) indiquant le nombre minimum
b1 b2 b3 et maximum de fois que l’entité peut apparaître dans l’as-
c1 c2 c3 sociation (p = ∗ s’il n’y a pas de maximum).
Résultat de Exemples :
SELECT * FROM table1 UNION SELECT * FROM table2; – Un livre a été écrit par au moins une personne, sans
limite supérieure. D’où la cardinalité (1, ∗) pour le
lien entre l’entité livre et l’association « écrit ».
attr1 attr2 attr3
– Une personne peut avoir écrit un nombre quelconque
b1 b2 b3
de livre. D’où la cardinalité (0, ∗).
Résultat de
– Si on suppose qu’une personne peut emprunter au
SELECT * FROM table1 MINUS SELECT * FROM table2
plus 5 livres, alors le lien entre l’entité personne et
l’association « emprunt » est de cardinalité (0, 5).
Modèle entité-association
livre
• Une entité est un ensembles d’objets similaires que l’on
(0, ∗) (1, ∗) auteur
titre écrit
souhaite stocker. nom
nom_auteur
Exemple : Livre, auteur...

• Une association (ou : relation) est une relation entre

plusieurs entités. • Types possibles d’association entre deux entités :
Une association est binaire si elle met en relation deux – 1 − 1 (one-to-one) : La borne supérieure vaut 1 pour
entités. les 2 entités.
Exemple : Un auteur écrit un livre. Exemple : L’association « dirige » est de type 1 − 1
pour directeur_bibliotheque et bibliotheque.
• Représentation sous forme de diagramme : – 1 − ∗ (one-to-many) : La borne supérieure vaut 1
pour une entité et ∗ pour l’autre.
Exemple : Chaque livre est écrit par un unique au-
livre teur, mais chaque auteur a pu écrire plusieurs livres.
auteur – ∗ − ∗ (many-to-many) : La borne supérieure vaut ∗
titre écrit
nom des deux côtés.
nom_auteur
Exemple : L’association « est de type » entre la ta-
ble des pokémons et des types est de type ∗ − ∗ (à
• Une relation n-aire peut être transformée en relation bi-
chaque pokémon peut correspondre plusieurs types
naire en introduisant une nouvelle entité pour la relation.
et plusieurs pokémons peuvent avoir le même type).
Exemple :
• Pour concevoir une base de donnée :

livre emprunt bibliotheque – Utiliser une table par entité.

– Pour chaque association entre a et b :
∗ Si association 1 − 1 : Fusionner les tables a et b.
∗ Si association 1 − ∗ : Ajouter un attribut (clé
emprunteur étrangère) à b faisant référence à un a.
∗ Si association ∗ − ∗ : Ajouter une table ayant 2
Une relation 3-aire clé étrangère pour faire référence à a et b.
ITC2 Dictionnaire Q. Fortier

Python Description Complexité

Ajout (ou modification) d’une
d[k] = v O(1) en moyenne
association de k à v
d[k] Accès à la valeur de clé k O(1) en moyenne
len(d) Nombre de clés de d O(1) en moyenne
for k in d: Parcourir les clés k de d O(n) où n est le nombre de clés
k in d Test si k est une clé de d O(1) en moyenne
[Link]() Copie de d O(n) où n est le nombre de clés

• Un dictionnaire est une structure de données qui à chaque plexité O(n).

clé associe une valeur. Il possède les opérations suivantes :
– Ajouter une association (clé, valeur). Solution : Sans dictionnaire, on pourrait compter com-
– Supprimer une association (clé, valeur). bien de fois apparaît chaque élément de L mais cela
– Obtenir les valeurs associée à une clé donnée. demanderait une complexité O(n2 ).
• Les dictionnaires de Python sont implémentés par table de
hachage, ce qui demande une fonction de hachage pour les def frequent(L):
clés. Les types de base immuables (non modifiables) comme d = {} # d[e] = nombre d'occurences de e dans L
int ou string ont une fonction de hachage déjà définie. for e in L:
Les types mutables (modifiables) comme list ou dict ne if e in d:
doivent pas être utilisés comme clé d’un dictionnaire, mais d[e] += 1
else:
peuvent être utilisés comme valeur.
d[e] = 1
• Exemple d’utilisation de dictionnaire : max = 0
for k in d:
d = {"rouge": (255, 0, 0), "jaune": (255, 255, 0)} if d[k] > max:
# "rouge" est une clé de valeur associée (255, 0, 0) max = d[k]
d["rouge"] # donne (255, 0, 0) res = k
d["blabla"] # donne une erreur return res
"rouge" in d # renvoie True
for k in d:
print(k) # affiche "rouge" et "jaune"
• Au lieu de la représentation par matrice/liste d’un graphe
len(d) # nombre de clés G, on peut représenter G par un dictionnaire d, où d[v] est
la liste (ou l’ensemble) des voisins du sommet v.
• Exercice : Écrire une fonction inverse(d) renvoyant un dic- Exemple :
tionnaire d2 « inverse » de d, c’est-à-dire tel que : d[k] = v
⇐⇒ d2[v] = k. 0 3 5
def inverse(d):
d2 = {} 2
for k in d: 4
d2[d[k]] = k 1
return d2

d = {0 : [1, 2], 1: [0, 2], 2: [0, 1],

• Exercice : Écrire une fonction frequent(L) renvoyant l’élé- 3: [4], 4: [3], 5: []}
ment le plus fréquent dans une liste L de taille n, en com-
ITC2 Programmation dynamique Q. Fortier

• Une fonction f est récursive si elle s’appelle elle-même. • Pour résoudre un problème de programmation dynamique :
Elle est composée de : 1. Chercher une équation de récurrence. Souvent, cela
– Un (ou plusieurs) cas de base où f renvoie directe- demande d’introduire un paramètre.
ment une valeur, sans appel récursif. 2. Déterminer le(s) cas de base(s). Il faut qu’appliquer
– Un (ou plusieurs) appel récursif à f avec des argu- plusieurs fois l’équation de récurrence ramène à un cas
ments plus petits que ceux de l’appel initial, qui garan- de base.
tit de se ramener au cas de base.
3. Stocker en mémoire (dans une liste, matrice ou dictio-
Exemple : Calcul de n! = n × (n − 1)!. nnaire) les résultats des sous-problèmes pour éviter de
les calculer plusieurs fois.
def fact(n):  
if n == 0: # cas de base n
• Exemple : Calcul de en utilisant la formule de Pascal
return 1
  k 
return n*fact(n - 1) # appel récursif
    
n n−1 n−1 n
= + et les cas de base = 1 et
k k − 1 k 0
Attention : une fonction récursive peut ne pas terminer
 
n
= 0 si n 6= 0.
(appels récursifs infinis), de même qu’un while peut faire 0
boucle infinie.
 
i
On utilise une matrice M telle que M[i][j] contienne .
j
• La fonction suivante calcule les termes de la suite de Fi-
bonacci (u0 = u1 = 1, un = un−1 + un−2 ) : def binom(n, k):
M = [[0]*(k + 1) for _ in range(n + 1)]
def fibo(n): for i in range(0, n + 1):
if n == 0 or n == 1: M[i][0] = 1
return 1 for i in range(1, n + 1):
return fibo(n - 1) + fibo(n - 2) for j in range(1, k + 1):
M[i][j] = M[i - 1][j - 1] + M[i - 1][j]
return M[n][k]
Cependant, la complexité est très mauvaise (exponen-
tielle)... En effet, si C(n) = complexité de fibo(n), alors
C(n) = C(n − 1) + C(n − 2) +K ce qui est une équation • La mémoïsation est similaire à la programmation dy-
| {z } | {z } namique mais en utilisant une fonction récursive plutôt que
f ibo(n−1) f ibo(n−2)
des boucles.
récurrente linéaire d’ordre 2 (du même type que celle véri-
Pour éviter de résoudre plusieurs fois le même problème
fiée par la suite de Fibonacci) que l’on peut résoudre pour
(comme pour Fibonacci), on mémorise (dans un tableau ou
trouver C(n) ∼ Arn .
un dictionnaire) les arguments pour lesquelles la fonction
Le soucis vient du fait que le même sous-problème est résolu
récursive a déjà été calculée.
plusieurs fois, ce qui est inutile et inefficace.
• Version mémoïsée du calcul de la suite de Fibonacci :

def fibo(n):
d = {} # d[k] contiendra le kème terme de la suite
def aux(k):
if k == 0 or k == 1:
return 1
if k not in d:
d[k] = aux(k - 1) + aux(k - 2)
return d[k]
return aux(n)

Appels récursifs de la version naïve • Mémoïsation du calcul de coefficient binomial :

de fibo(7)

def binom(n, k):

• La programmation dynamique stocke les résultats des d = {}
sous-problèmes pour éviter de les calculer plusieurs fois. def aux(i, j):
if j == 0: return 1
def fibo(n): if i == 0: return 0
L = [1, 1] # L[i] = ième terme de Fibonacci if (i, j) not in d:
for i in range(n - 1): d[(i, j)] = aux(i - 1, j - 1) + aux(i - 1, j)
[Link](L[i] + L[i + 1]) # récurrence return d[(i, j)]
return L[n] return aux(n, k)
• Problème du sac à dos. Résolution par mémoïsation :
Entrée : un sac à dos de capacité c, des objets o1 , ..., on de
poids w1 , ..., wn et valeurs v1 , ..., vn . On suppose que les
def knapsack_memo(c, w, v):
poids sont strictement positifs.
dp = {}
Sortie : la valeur maximum que l’on peut mettre dans le
def aux(i, j):
sac. if i == 0 or j == 0:
Soit dp[i][j] la valeur maximum que l’on peut mettre dans return 0
un sac de capacité i, en ne considérant que les objets o1 , ..., if (i, j) not in dp:
oj . dp[(i, j)] = aux(i, j - 1)
dp[i][0] = 0 if w[j - 1] <= i:
dp[i][j] = max( dp[i][j − 1] , dp[i − wj ][j − 1] + vj ) x = v[j - 1] + aux(i - w[j - 1], j - 1)
| {z } | {z } dp[(i, j)] = max(dp[(i, j)], x)
sans prendre oj en prenant oj ,si i−wj ≥0 return dp[(i, j)]
Résolution par programmation dynamique : return aux(c, len(w))

def knapsack(c, w, v):

"""
Renvoie la valeur maximum que l'on peut mettre
dans un sac à dos de capacité c.
Le ième objet a pour poids w[i] et valeur v[i].
"""
n = len(w) # nombre d'objets
dp = [[0]*(n + 1) for i in range(c + 1)]
# dp[i][j] = valeur max dans un sac de capacité i
# où j est le nombre d'objets autorisés
for i in range(1, c + 1):
for j in range(1, n + 1):
if w[j - 1] <= i:
x = v[j - 1] + dp[i - w[j - 1]][j - 1]
dp[i][j] = max(dp[i][j - 1], x)
else:
dp[i][j] = dp[i][j - 1]
return dp[c][n]
ITC2 Apprentissage automatique Q. Fortier

Algorithmes de classification
• Un algorithme de classification consiste à associer à chaque
donnée une classe (ou : étiquette).
Exemple : à chaque image, on veut associer l’objet
représenté par l’image.

• On distingue deux types d’algorithmes de classification :

– Supervisé : on possède des données d’entraîne- x
ment pour lesquelles on connaît les classes. On
veut ensuite prédire les classes de nouvelles données La classe de x est prédite comme
(données de test). étant bleue (ici, k = 3 et il y a deux
Exemple : algorithme des plus proches voisins. classes : bleu et rouge)
– Non supervisé : pas de données d’entraînement.
Exemple : algorithme des k-moyennes.
• Exercice : Écrire une fonction voisins(x, X, k) renvoyant
• Les algorithmes d’apprentissage ont besoin d’une notion de la liste des k plus proches voisins de x dans X.
distance entre les données. Pour cela, on se ramène à Rk .
Ainsi, si une donnée de voiture possède une vitesse maxi-
mum de 200 km/h, consomme 10 litres au 100km etpèse def voisins(x, X, k):
200 I = [] # indices des k plus proches voisins dans X
1500 kg, on peut la représenter par le vecteur  10 . for i in range(k): # ajout du ième minimum
1500 jmin = 0
Pour une image : on passe d’une matrice de pixels avec n for j in range(len(X)):
if d(x, X[j]) < d(x, X[jmin]) and j not in I:
lignes, p colonnes à un vecteur de taille np.
jmin = j
[Link](jmin)
• On représente classiquement l’ensemble des données (donc
return I
de vecteurs de Rp ) par une matrice X dont les lignes sont les
données et les colonnes sont les attributs (coordonnées des
vecteurs). • Exercice : Écrire une fonction maj(L) renvoyant l’élément
le plus fréquent de la liste L, en complexité linéaire.
• On peut utiliser
v la distance euclidienne entre deux données
u p def maj(L):
C = {} # C[e] = nombre d'occurrences de e dans L
: d(x, y) = t (xi − yi )2
uX
for e in L:
i=1
if e in C:
C[e] += 1
def d(x, y): else:
s = 0 C[e] = 1
for i in range(len(x)): kmax = L[0]
s += (x[i] - y[i]) ** 2 for k in C:
return s ** 0.5 if C[k] > C[kmax]:
kmax = k
return kmax
• Pour éviter que les données ne soient trop influencées par les
attributs qui ont des valeurs plus grandes, on peut standard-
iser (ou : normaliser) les données. On soustrait à chaque Complexité : O(n), où n est la taille de L.
attribut sa moyenne et on divise par l’écart-type. • Exercice : Écrire une fonction knn(x, X, Y, k) renvoyant
la classe prédite par l’algorithme des k plus proches voisins
pour la donnée x et les données d’entraînement X et Y.
Algorithme des k plus proches voisins
• Soit k ∈ N. L’algorithme des k plus proches voisins def knn(x, X, Y, k):
""" Prédit la classe de x avec l'algorithme KNN
prédit la classe d’une nouvelle donnée x de la façon suivante:
x : nouvelle donnée
1. Calculer les distances de x à toutes les données d’en- X : données d'entraînement
traînement. Y : étiquettes des données d'entraînement
k : nombre de voisins à considérer
2. Trouver les k données d’entraînement les plus proches
"""
de x (en termes de distance). V = voisins(x, X, k)
3. Trouver la classe majoritaire c ∈ Y parmi ces k données return maj([Y[i] for i in V])
les plus proches de x.
4. Prédire que x est de classe c. • Supposons que l’on possède des données X avec des éti-
 quettes Y et qu’on veuille savoir si KNN est un bon classi- • La variance (ou : moment d’inertie) V (X) d’un ensemble
fieur pour ces données. de vecteur X est définie par

Pour cela, on partitionne les données en deux ensembles :

X
V (X) = d(x, X)2
– Ensemble d’entraînement Xtrain (de classes Ytrain ) :
x∈X

données parmi lesquelles on va chercher les k plus

proches voisins. La variance mesure la variation par rapport à la moyenne :
plus V (X) est petit, plus les vecteurs de X sont proches du
– Ensemble de test Xtest (de classes Ytest ) : données util- barycentre X.
isées pour évaluer le modèle, en comparant les classes Objectif : trouver un partitionnement (clustering) de X en k
prédites par KNN avec les classes réelles. sous-ensembles X1 , . . . , Xk (classes ou clusters) minimisant
k
• La précision d’un modèle est la proportion de données de
l’inertie I : I =
X
V (Xi )
test bien classées par rapport au nombre total de données.
i=1
Dit autrement : on veut associer à chaque donnée x une
def precision(k):
classe k telle que l’inertie I soit minimum.
n = len(X_test)
Plus l’inertie est petite, plus les données sont proches du
p = 0
for i in range(n): centre de leur classe et plus le partitionnement est bon.
if predict(X_test[i], k) == Y_test[i]:
p += 1 Algorithme des k-moyennes
return p/n
Objectif : partitionnner X en classes X1 , ..., Xk .
• La matrice de confusion est une matrice carrée dont les 1. Soit c1 , ..., ck des vecteurs choisis aléatoirement.
lignes et les colonnes sont les classes possibles. La case (i, j) 2. Associer chaque donnée x à la classe Xi telle que
contient le nombre de données de test de classe i qui ont été d(x, ci ) soit minimale.
prédites comme appartenant à la classe j. 3. Recalculer les centres des classes ci = Xi .
Exemple : Dans la matrice suivante, on voit que 21 données 4. Si les centres ont changé, revenir à l’étape 2.
de classe 0 ont été prédites comme appartenant à la classe
0, 2 données de classe 1 ont été prédites comme appartenant
à la classe 2... Attention : dans l’algorithme des k-moyennes, k est le nom-
bre de classes alors que dans l’algorithme des plus proches
array([[21, 0, 0], voisins, k est le nombre de voisins.
[ 0, 29, 1],
[ 0, 2, 23]])
def calculer_centres(classes):
centres = []
• Pour choisir la valeur de k dans l’algorithme des k plus for i in range(len(classes)):
proches voisins, on peut afficher la précision en fonction de k [Link](centre(classes[i]))
pour choisir la valeur de k qui donne la meilleure précision. return centres

def plus_proche(x, centres):

imin = 0
Algorithme des k moyennes for i in range(len(centres)):
• Le centre (ou : isobarycentre) d’un ensemble de vecteurs if d(x, centres[i]) < d(x, centres[imin]):
1X
n imin = i
x1 , . . . , xn est le vecteur x = xi . return imin
n i=1
Exercice : Écrire une fonction centre(X) renvoyant le cen- def calculer_classes(X, centres):
tre de la liste de vecteurs X. classes = [[] for i in range(len(centres))]
for x in X:
classes[plus_proche(x, centres)].append(x)
def centre(X): return classes
n, p = len(X), len(X[0])
x = [0] * p def kmoyennes(X, centres):
for i in range(n): centres2 = None
for j in range(p): while centres != centres2:
x[j] += X[i][j] centres2 = centres
for j in range(p): classes = calculer_classes(X, centres2)
x[j] /= n centres = calculer_centres(classes)
return x return classes
ITC2 Jeux à deux joueurs Q. Fortier

• Un puit t dans un graphe orienté est un sommet qui n’a pas

de successeur (il n’existe pas d’arête allant vers t).

• Théorème : Tout graphe orienté acyclique G possède un

puit.
Preuve : Soit v un sommet de G. On fait partir un chemin
depuis v en se déplaçant vers un successeur à chaque étape.
Comme G est acyclique, ce chemin ne peut pas revenir deux
fois au même sommet. Comme le nombre de sommets est
fini, ce chemin doit forcément arriver à un puit.

Graphe des configurations d’un jeu

• Un graphe G = (V, E) est biparti s’il existe une partition de domineering
V = VA t VB telle que toute arête de E a une extrémité
dans VA et une extrémité dans VB .
6A 5A 4A 3A 2A 1A

0 1 2 7

6B 5B 4B 3B 2B 1B

3 4 5 6 Graphe des configurations d’un jeu

de Nim avec, initialement n = 6.
Graphe biparti, avec une partition Pour déterminer cmplètement une
VA = {0, 4, 5, 2} et VB = {1, 3, 6, 7} configuration, on indique le joueur
dont c’est le tour.

1 • Soit G = (V, E) un graphe biparti acyclique, avec V =

VA t VB .
0 2 – Le jeu commence en un sommet initial v ∈ A.
– Une partie est un chemin commençant en v dont les
Graphe non biparti arêtes sont choisies alternativement par Alice et Bob.
– L’ensemble PA des puits de VA sont les situations où
Alice perd.
– Une stratégie pour Alice est une fonction f : VA \
PA → VB telle que ∀v ∈ VA , (v, f (v)) ∈ E.
• On s’intéresse à un jeu à deux joueurs (Alice et Bob), qui se Une stratégie consiste donc à choisir un coup à jouer
joue chacun son tour. On suppose qu’Alice commence. Un pour chaque configuration possible.
joueur a perdu lorsqu’il n’a plus de coup possible.
– Une stratégie gagnante pour Alice est une stratégie
Remarque : Les règles peuvent changer suivant le jeu auquel
f qui permette à Alice de gagner, quel que soit la
on joue.
stratégie de Bob.
– v ∈ V est une position gagnante pour Alice si elle
• Exemples de jeux : possède une stratégie gagnante pour une partie qui
commence en v.
– Le jeu de Nim : il y a n allumettes. Chaque joueur – L’attracteur A d’Alice est l’ensemble des position
peut retirer 1, 2 ou 3 allumettes. Le joueur qui retire gagnantes pour Alice.
la dernière allumette a perdu.
Définitions sont similaires pour Bob en échangeant A et B.
– Le jeu du domineering est un jeu de plateau où Alice • On peut déterminer l’attracteur A d’Alice de proche en
place un domino vertical et Bob un domino horizontal. proche, en calculant l’ensemble Ak des positions gagnantes
Un joueur qui ne peut plus jouer perd. pour Alice en k coups :
– A0 = PB (gagnants pour Alice).
• Le graphe des configurations d’un jeu est un graphe ori- – Si k est pair : Ak+1 = {u ∈ VA | ∃(u, v) ∈ E, v ∈ Ak }
enté dont les sommets sont les configurations possibles du – Si k est impair : Ak+1 = {u ∈ VB | ∀(u, v) ∈ E, v ∈
jeu et les arêtes sont les coups possibles. Ak }
 S’il y a n sommets, un chemin possède au plus n − 1 arêtes for w in G[v]:
n−1 if not aux(w):
d’où : A = Ak . d[v] = False
[
return d[v]
k=0
return [v for v in G if aux(v)]
Exemple :
• Une heuristique pour un jeu est une fonction qui à une
VA 0 1 2 3 configuration associe une valeur dans R et qui estime à quel
point la configuration v est favorable à un joueur : plus h(v)
est grand, plus v est favorable à Alice et inversement.
Exemple : dans le jeu du domineering, on peut utiliser h(v)
VB 4 5 6 7 = nombres de possibilités pour Alice - nombres de possibil-
ités pour Bob.
A0 = {7}, A1 = {2}, A2 = {4}, A3 = {0, 1}. Attention : Aussi bien dans A∗ que min-max, utiliser une
Ainsi l’attracteur A d’Alice est {0, 1, 2, 4, 7}. heuristique permet d’accélerer la recherche mais le résultat
On peut aussi en déduire une stratégie gagnante qui consiste n’est pas forcément optimal.
à jouer sur un attracteur si possible : f (0) = 4, f (1) = 4, • L’algorithme de calcul des attracteurs est trop lent si le
f (2) = 7. graphe des configurations est trop grand (échec, go...).
• (Formulation récursive équivalente à la précédente) Un som- L’algorithme min-max permet d’accélerer la recherche avec
met v est un attracteur dans l’un des trois cas suivants : une heuristique et en ne parcourant que les configurations
– v ∈ PB . atteignable en au plus p coups. Il donne une valeur à chaque
– v ∈ VA et il existe un attracteur w tel que (v, w) ∈ E. sommet de l’arbre de proche en proche :
– v ∈ VB et pour tout (v, w) ∈ E, w est un attracteur. – La valeur des sommets à profondeur p et ceux sans
successeurs.
D’où la fonction récursive (par mémoïsation pour éviter des – La valeur des sommets à profondeur p − 1 est le maxi-
calculs inutiles), où G est représenté par dictionnaire d’ad- mum (si Alice soit jouer) ou le minimum (si Bob doit
jacence et fA est une fonction indiquant si un sommet ap- jouer) des valeurs des successeurs.
partient à VA : – Ainsi de suite, jusqu’à calculer la valeur de la racine.
def attracteurs(G, fA):
d = {} # d[v] = True si v est un attracteur
def aux(v): # détermine si v est un attracteur def minmax(s, h, v, p, j):
if v not in d: succ = [minmax(s, h, w, p - 1, 1 - j) for w in s(v, j)]
succ = [aux(w) for w in G[v]] if succ == [] or p == 0:
if len(G[v]) == 0: return h(v)
d[v] = not fA(v) if j == 0:
elif fA(v):
# test s'il existe (v, w) € E avec w attracteur
return max(succ)
d[v] = False else:
for w in G[v]: return min(succ)
if aux(w):
d[v] = True
else:
Une fois la valeur de chaque configuration calculée, Alice
# test si pour tout (v, w) € E, w est attracteur choisit le coup dont la valeur est la plus élevée (le plus fa-
d[v] = True vorable).

Alice
1
(max)

Bob
−∞ 0 1
(min)

Alice
(max)

−2 −∞ −∞ −1 −1 0 1 0 1 1

Arbre min-max rempli de bas en haut, avec le coup optimal pour Alice entouré.
2 Programme du second semestre
2.1 Méthodes de programmation et analyse des algorithmes
On formalise par des leçons et travaux pratiques le travail entrepris au premier semestre concernant la disci-
pline et les méthodes de programmation.
Même si on ne prouve pas systématiquement tous les algorithmes, on dégage l’idée qu’un algorithme doit se
prouver et que sa programmation doit se tester.

Notions Commentaires
Instruction et expression. Effet de bord. On peut signaler par exemple que le fait que l’affectation soit une
instruction est un choix des concepteurs du langage Python et
en expliquer les conséquences.
Spécification des données attendues en On entraîne les étudiants à accompagner leurs programmes et
entrée, et fournies en sortie/retour. leurs fonctions d’une spécification. Les signatures des fonctions
sont toujours précisées.
Annotation d’un bloc d’instructions Ces annotations se font à l’aide de commentaires.
par une précondition, une postcondi-
tion, une propriété invariante.
Assertion. L’utilisation d’assertions est encouragée par exemple pour vali-
der des entrées. La levée d’une assertion entraîne l’arrêt du pro-
gramme. Ni la définition ni le rattrapage des exceptions ne sont
au programme.
Explicitation et justification des choix Les parties complexes de codes ou d’algorithmes font l’objet de
de conception ou programmation. commentaires qui l’éclairent en évitant la paraphrase. Le choix
des collections employées (par exemple, liste ou dictionnaire)
est un choix éclairé.
Terminaison. Correction partielle. Cor- La correction est partielle quand le résultat est correct lorsque
rection totale. Variant. Invariant. l’algorithme s’arrête, la correction est totale si elle est partielle et
si l’algorithme termine.
On montre sur plusieurs exemples que la terminaison peut se
démontrer à l’aide d’un variant de boucle.
Sur plusieurs exemples, on explicite, sans insister sur aucun for-
malisme, des invariants de boucles en vue de montrer la correc-
tion des algorithmes.
Jeu de tests associé à un programme. Il n’est pas attendu de connaissances sur la génération automa-
tique de jeux de tests ; un étudiant doit savoir écrire un jeu de
tests à la main, donnant à la fois des entrées et les sorties cor-
respondantes attendues. On sensibilise, par des exemples, à la
notion de partitionnement des domaines d’entrée et au test des
limites.
Complexité. On aborde la notion de complexité temporelle dans le pire cas en
ordre de grandeur. On peut, sur des exemples, aborder la notion
de complexité en espace.

2.2 Représentation des nombres

On présente sans formalisation théorique les enjeux de la représentation en mémoire des nombres. Ces no-
tions permettent d’expliquer certaines difficultés rencontrées et précautions à prendre lors de la program-
mation ou de l’utilisation d’algorithmes de calcul numérique dans les disciplines qui y recourent.

Notions Commentaires
Représentation des entiers positifs sur La conversion d’une base à une autre n’est pas un objectif de for-
des mots de taille fixe. mation.
Représentation des entiers signés sur Complément à deux.
des mots de taille fixe.

© Ministère de l’enseignement supérieur, de la recherche et de l’innovation, 2021 Informatique — Filières MP, PC, PSI, PT
[Link] 6/10
 Entiers multi-précision de Python. On les distingue des entiers de taille fixe sans détailler leur im-
plémentation. On signale la difficulté à évaluer la complexité des
opérations arithmétiques sur ces entiers.
Distinction entre nombres réels, déci- On montre sur des exemples l’impossibilité de représenter cer-
maux et flottants. tains nombres réels ou décimaux dans un mot machine
Représentation des flottants sur des On signale la représentation de 0 mais on n’évoque pas les
mots de taille fixe. nombres dénormalisés, les infinis ni les NaN.
Notion de mantisse, d’exposant. Aucune connaissance liée à la norme IEEE-754 n’est au pro-
gramme.
Précision des calculs en flottants. On insiste sur les limites de précision dans le calcul avec des flot-
tants, en particulier pour les comparaisons. Le comparatif des
différents modes d’arrondi n’est pas au programme.

2.3 Bases des graphes, plus courts chemins

Il s’agit de définir le modèle des graphes, leurs représentations et leurs manipulations.
On s’efforce de mettre en avant des applications importantes et si possible modernes : réseau de transport,
graphe du web, réseaux sociaux, bio-informatique. On précise autant que possible la taille typique de tels
graphes.

Notions Commentaires
Vocabulaire des graphes. Graphe orienté, graphe non orienté. Sommet (ou nœud) ; arc,
arête. Boucle. Degré (entrant et sortant). Chemin d’un sommet
à un autre. Cycle. Connexité dans les graphes non orientés.
On présente l’implémentation des graphes à l’aide de listes d’ad-
jacence (rassemblées par exemple dans une liste ou dans un dic-
tionnaire) et de matrice d’adjacence. On n’évoque ni multi-arcs
ni multi-arêtes.
Notations. Graphe 𝐺 = (𝑆, 𝐴), degrés 𝑑(𝑠) (pour un graphe non orienté),
𝑑+ (𝑠) et 𝑑− (𝑠) (pour un graphe orienté).
Pondération d’un graphe. Étiquettes On motive l’ajout d’information à un graphe par des exemples
des arcs ou des arêtes d’un graphe. concrets.
Parcours d’un graphe. On introduit à cette occasion les piles et les files ; on souligne les
problèmes d’efficacité posés par l’implémentation des files par
les listes de Python et l’avantage d’utiliser un module dédié tel
que [Link].
Détection de la présence de cycles ou de la connexité d’un
graphe non orienté.
Recherche d’un plus court chemin dans Algorithme de Dijkstra. On peut se contenter d’un modèle de
un graphe pondéré avec des poids posi- file de priorité naïf pour extraire l’élément minimum d’une col-
tifs. lection. Sur des exemples, on s’appuie sur l’algorithme A* vu
comme variante de celui de Dijkstra pour une première sensi-
bilisation à la notion d’heuristique.

© Ministère de l’enseignement supérieur, de la recherche et de l’innovation, 2021 Informatique — Filières MP, PC, PSI, PT
[Link] 7/10
3 Programme du troisième semestre
3.1 Bases de données
On se limite volontairement à une description applicative des bases de données en langage SQL. Il s’agit de
permettre d’interroger une base présentant des données à travers plusieurs relations. On ne présente pas
l’algèbre relationnelle ni le calcul relationnel.

Notions Commentaires
Vocabulaire des bases de données : On présente ces concepts à travers de nombreux exemples. On
tables ou relations, attributs ou co- s’en tient à une notion sommaire de domaine : entier, flottant,
lonnes, domaine, schéma de tables, en- chaîne ; aucune considération quant aux types des moteurs SQL
registrements ou lignes, types de don- n’est au programme. Aucune notion relative à la représentation
nées. des dates n’est au programme ; en tant que de besoin on s’appuie
sur des types numériques ou chaîne pour lesquels la relation
d’ordre coïncide avec l’écoulement du temps. Toute notion re-
lative aux collations est hors programme ; on se place dans l’hy-
pothèse que la relation d’ordre correspond à l’ordre lexicogra-
phique usuel. NULL est hors programme.
Clé primaire. Une clé primaire n’est pas forcément associée à un unique attri-
but même si c’est le cas le plus fréquent. La notion d’index est
hors programme.
Entités et associations, clé étrangère. On s’intéresse au modèle entité–association au travers de cas
concrets d’associations 1 − 1, 1 − ∗, ∗ − ∗. Séparation d’une as-
sociation ∗ − ∗ en deux associations 1 − ∗. L’utilisation de clés
primaires et de clés étrangères permet de traduire en SQL les as-
sociations 1 − 1 et 1 − ∗.
Requêtes SELECT avec simple clause Les opérateurs au programme sont +, -, *, / (on passe outre les
WHERE (sélection), projection, renom- subtilités liées à la division entière ou flottante), =, <>, <, <=, >,
mage AS. >=, AND, OR, NOT.
Utilisation des mots-clés DISTINCT,
LIMIT, OFFSET, ORDER BY.
Opérateurs ensemblistes UNION,
INTERSECT et EXCEPT, produit carté-
sien.
Jointures internes 𝑇1 JOIN 𝑇2 … On présente les jointures en lien avec la notion de relations entre
JOIN 𝑇𝑛 ON 𝜙. Autojointure. tables. On se limite aux équi-jointures : 𝜙 est une conjonction
d’égalités.
Agrégation avec les fonctions MIN, MAX, Pour la mise en œuvre des agrégats, on s’en tient à la norme
SUM, AVG et COUNT, y compris avec SQL99. On présente quelques exemples de requêtes imbriquées.
GROUP BY.
Filtrage des agrégats avec HAVING. On marque la différence entre WHERE et HAVING sur des
exemples.
Mise en œuvre
La création de tables et la suppression de tables au travers du langage SQL sont hors programme.
La mise en œuvre effective se fait au travers d’un logiciel permettant d’interroger une base de données à
l’aide de requêtes SQL. Récupérer le résultat d’une requête à partir d’un programme n’est pas un objectif.
Même si aucun formalisme graphique précis n’est au programme, on peut décrire les entités et les as-
sociations qui les lient au travers de diagrammes sagittaux informels.
Sont hors programme : la notion de modèle logique vs physique, les bases de données non relation-
nelles, les méthodes de modélisation de base, les fragments DDL, TCL et ACL du langage SQL, les tran-
sactions, l’optimisation de requêtes par l’algèbre relationnelle.

© Ministère de l’enseignement supérieur, de la recherche et de l’innovation, 2021 Informatique — Filières MP, PC, PSI, PT
[Link] 8/10
3.2 Dictionnaires et programmation dynamique
Les dictionnaires sont utilisés en boîte noire dès la première année ; les principes de leur fonctionnement sont
présentés en deuxième année. Ils peuvent être utilisés afin de mettre en mémoire des résultats intermédiaires
quand on implémente une stratégie d’optimisation par programmation dynamique.

Notions Commentaires
Dictionnaires, clés et valeurs. On présente les principes du hachage, et les limitations qui en
découlent sur le domaine des clés utilisables.
Usage des dictionnaires en program- Syntaxe pour l’écriture des dictionnaires. Parcours d’un diction-
mation Python. naire.
Programmation dynamique. Propriété La mémoïsation peut être implémentée à l’aide d’un diction-
de sous-structure optimale. Chevau- naire. On souligne les enjeux de complexité en mémoire.
chement de sous-problèmes. Exemples : partition équilibrée d’un tableau d’entiers positifs,
Calcul de bas en haut ou par mémoïsa- ordonnancement de tâches pondérées, plus longue sous-suite
tion. Reconstruction d’une solution op- commune, distance d’édition (Levenshtein), distances dans un
timale à partir de l’information calcu- graphe (Floyd-Warshall).
lée.
Mise en œuvre
Les exemples proposés ne forment une liste ni limitative ni impérative. Les cas les plus complexes de
situations où la programmation dynamique peut être utilisée sont guidés. On met en rapport le statut
de la propriété de sous-structure optimale en programmation dynamique avec sa situation en stratégie
gloutonne vue en première année.

3.3 Algorithmique pour l’intelligence artificielle et l’étude des jeux

Cette partie permet notamment de revisiter les notions de programmation et de représentation de données
par un graphe, qui sont vues en première année, en les appliquant à des enjeux contemporains.

Notions Commentaires
Algorithme des 𝑘 plus proches voisins Matrice de confusion. Lien avec l’apprentissage supervisé.
avec distance euclidienne.
Algorithme des 𝑘-moyennes. Lien avec l’apprentissage non-supervisé.
La démonstration de la convergence n’est pas au programme.
On observe des convergences vers des minima locaux.
Jeux d’accessibilité à deux joueurs On considère des jeux à deux joueurs (𝐽1 et 𝐽2 ) modélisés par des
sur un graphe. Stratégie. Stratégie graphes bipartis (l’ensemble des états contrôlés par 𝐽1 et l’en-
gagnante. Position gagnante. semble des états contrôlés par 𝐽2 ). Il y a trois types d’états finals :
Détermination des positions gagnantes les états gagnants pour 𝐽1 , les états gagnants pour 𝐽2 et les états
par le calcul des attracteurs. Construc- de match nul.
tion de stratégies gagnantes. On ne considère que les stratégies sans mémoire.
Notion d’heuristique. Algorithme min- L’élagage alpha-beta n’est pas au programme.
max avec une heuristique.
Mise en œuvre
La connaissance dans le détail des algorithmes de cette section n’est pas un attendu du programme.
Les étudiants acquièrent une familiarité avec les idées sous-jacentes qu’ils peuvent réinvestir dans des
situations où les modélisations et les recommandations d’implémentation sont guidées, notamment
dans leurs aspects arborescents.

© Ministère de l’enseignement supérieur, de la recherche et de l’innovation, 2021 Informatique — Filières MP, PC, PSI, PT
[Link] 9/10
A Langage Python
Cette annexe liste limitativement les éléments du langage Python (version 3 ou supérieure) dont la connais-
sance est exigible des étudiants. Aucun concept sous-jacent n’est exigible au titre de la présente annexe.
Aucune connaissance sur un module particulier n’est exigible des étudiants.
Toute utilisation d’autres éléments du langage que ceux que liste cette annexe, ou d’une fonction d’un mo-
dule, doit obligatoirement être accompagnée de la documentation utile, sans que puisse être attendue une
quelconque maîtrise par les étudiants de ces éléments.

Traits généraux
— Typage dynamique : l’interpréteur détermine le type à la volée lors de l’exécution du code.
— Principe d’indentation.
— Portée lexicale : lorsqu’une expression fait référence à une variable à l’intérieur d’une fonction, Python
cherche la valeur définie à l’intérieur de la fonction et à défaut la valeur dans l’espace global du module.
— Appel de fonction par valeur : l’exécution de 𝑓(𝑥)évalue d’abord 𝑥 puis exécute 𝑓 avec la valeur calcu-
lée.

Types de base
— Opérations sur les entiers (int) : +, -, *, //, **, % avec des opérandes positifs.
— Opérations sur les flottants (float) : +, -, *, /, **.
— Opérations sur les booléens (bool) : not, or, and (et leur caractère paresseux).
— Comparaisons ==, !=, <, >, <=, >=.

Types structurés
— Structures indicées immuables (chaînes, tuples) : len, accès par indice positif valide, concaténation
+, répétition *, tranche.
— Listes : création par compréhension [𝑒 for 𝑥 in 𝑠], par [𝑒] * 𝑛, par append successifs ; len, ac-
cès par indice positif valide ; concaténation +, extraction de tranche, copie (y compris son caractère
superficiel) ; pop en dernière position.
— Dictionnaires : création {𝑐1 : 𝑣1 , …, 𝑐𝑛 : 𝑣𝑛 }, accès, insertion, présence d’une clé 𝑘 in 𝑑, len,
copy.

Structures de contrôle
— Instruction d’affectation avec =. Dépaquetage de tuples.
— Instruction conditionnelle : if, elif, else.
— Boucle while (sans else). break, return dans un corps de boucle.
— Boucle for (sans else) et itération sur range(𝑎, 𝑏), une chaîne, un tuple, une liste, un dictionnaire
au travers des méthodes keys et items.
— Définition d’une fonction def 𝑓(𝑝1 , …, 𝑝𝑛 ), return.

Divers
— Introduction d’un commentaire avec #.
— Utilisation simple de print, sans paramètre facultatif.
— Importation de modules avec import module, import module as alias, from module import 𝑓, 𝑔, …

— Manipulation de fichiers texte (la documentation utile de ces fonctions doit être rappelée ; tout pro-
blème relatif aux encodages est éludé) : open, read, readline, readlines, split, write, close.
— Assertion : assert (sans message d’erreur).

© Ministère de l’enseignement supérieur, de la recherche et de l’innovation, 2021 Informatique — Filières MP, PC, PSI, PT
[Link] 10/10