Lycée de l’Essouriau REMISE EN CHAUFFE PYTHON Les Ulis

Le but est de réviser les algorithmes et notions de base du programme d’informatique de PCSI. L’idée est de
d’abord vérifier que l’on connait son cours et passer la question si on est certain à 100% de connaitre la réponse
ou savoir écrire le code demandé en Python. Sinon on se force à l’écrire.

LES VARIABLES
(Compléments sur ces notions aux pages 6 à 9 du formulaire d’informatique de PCSI sur Cahier de Prépa.)
1. Quelle commande permet d’accéder au dernier élément d’une liste (ou chaine de caractères) LC ?
2. Donner 2 différences fondamentales entre les listes et les chaines de caractères, qui fait que l’on pourra
préférer d’utiliser l’une plutôt que l’autre dans un script Python.
3. Donner un avantage, puis un inconvénient des dictionnaires sur les listes/chaı̂nes.
4. Soit x un flottant, on veut vérifier si x est nul. Le test x==0 est-il adéquat ?
Justifier, si vous avez répondu non, quel test feriez-vous ?

LES ALGORITHMES DE TRI

(réponses p.23 du formulaire d’informatique de PCSI sur Cahier de Prépa)
5. Donner les noms des algorithmes de tri que vous connaissez.
6. Donner la complexité de ces tris.
7. Quel est le tri le plus rapide en moyenne ? Quel(s) principe(s) utilise-t-il ?

LES ALGORITHMES « FACILES » CLASSIQUES

L’emploi de la commande if x in L où L est une liste est rigoureusement interdit.
8. Soit texte une chaı̂ne de caractères, écrire une fonction Presence(lettre,texte) qui vérifie si texte
contient le caractère lettre.
9. Soit L une liste de flottants, écrire une fonction moy(L) qui calcule la moyenne des éléments de L.
10. Ajouter dans moy(L) la signature ainsi qu’un test d’assertion qui vérifie que L est bien une liste et qu’elle
est non vide.
11. Soit L une liste de flottants, écrire une fonction Mini(L) qui calcule le minimum des éléments de L.
12. Soit texte une chaine de caractères. Écrire une fonction Tipex(texte,i,lettre) qui renvoie une chaı̂ne
où le caractère d’indice i aura été remplacé par le caractère lettre dans texte.
texte ne doit pas être modifiée.
13. Soit L une liste de flottants. Écrire une fonction Croissante(L) qui teste si L est une liste triée par ordre
croissant ou non (renvoie le booléen adéquat).
14. Écrire une fonction PasDeDoublons(L) qui renvoie une liste contenant les mêmes éléments que ceux de la
liste L mais en un seul exemplaire (complexité attendue en O(len(L))).
L ne doit pas être modifiée.
15. Écrire une fonction RienAVoir(L1,L2) qui renvoie True si les deux listes L1 et L2 n’ont aucun élément
en commun et False sinon (complexité attendue en O(max(len(L1),len(L2)))).
16. Soit D un dictionnaire dont les clefs et les valeurs sont toutes des chaı̂nes de caractères. Écrire une fonction
PlusLong(D) qui renvoie la clef dont la valeur associée est de longueur maximale.
17. Écrire des commandes qui permettent de définir une image blanche de taille h × w (c’est à dire une liste
de h listes de longueur w ne comportant que des 255).

Fabien DÉLEN [Link]@[Link] 1 PSI 2024-2025

Lycée de l’Essouriau REMISE EN CHAUFFE PYTHON Les Ulis

18. Soit texte une chaı̂ne de caractères, écrire une fonction Occurences(texte) qui renvoie un dictionnaire
dont les clefs sont les caractères de texte et la valeur associée le nombre d’occurrences du caractère dans
texte.
19. Soit texte une chaı̂ne de caractères, écrire une fonction EltMajoritaire(texte) qui renvoie l’un des
éléments qui apparait le plus souvent souvent dans cette chaı̂ne.

LES MOINS FACILES MAIS CLASSIQUES

On définit la suite de Fibonacci (Fn )n∈N par F0 = 0, F1 = 1 et ∀n > 2, Fn+2 = Fn+1 + Fn .
20. Écrire une fonction itérative F(n) qui renvoie la n-ième valeur de la suite de Fibonacci.
21. Écrire une fonction récursive F2(n) qui renvoie la n-ième valeur de la suite de Fibonacci.
22. Quelle est la complexité de la fonction F2 écrite ci-dessus ?
23. Écrire une fonction PlusProches(L) qui prend en entrée une liste de flottants et renvoie un couple (tuple)
d’indices distincts de valeurs les plus proches dans cette liste.
24. Écrire une fonction SecondMax(L) qui prend en entrée une liste de flottants et renvoie la valeur du second
maximum de cette liste (la seconde valeur maximale après le maximum).

LES IMAGES
25. Implémenter une fonction dim(img) qui prend en entrée une matrice img (liste de listes) représentant une
image en niveaux de gris (chaque élément est un entier entre 0 et 255 et renvoie le couple (h, w) donnant
la dimension de l’image (h pour hauteur et w pour la largeur).
26. Implémenter une fonction voisins(pixel,img) qui prend en entrée une matrice img et un tuple d’entier
pixel (coordonnées (i, j) du pixel) et renvoie la liste des coordonnées des pixels voisins de ce pixel.
(il y a au plus 4 voisins par pixel et on fera attention aux bords !)

LES GRAPHES
Soit G un graphe non pondéré, codé par son dictionnaire d’adjacence noté G. Les clefs sont les noms des sommets
et les valeurs associées la liste des sommets adjacents au sommet.
27. Quelle commande permet de récupérer l’ordre du graphe ?
28. Écrire une fonction Voisins(G,S) qui permet de renvoyer la liste des sommets voisins du sommet S du
graphe G.
29. Écrire une fonction Isole(G) qui permet de renvoyer la liste des sommets isolés du graphe G.

Soit G un graphe non orienté et pondéré, dont les sommets sont numérotés de 0 à n − 1, (n étant donc l’ordre
du graphe) codé par sa matrice d’adjacente notée G.
30. A quoi correspond la valeur de G[i][j] dans le graphe ?
31. Quelle propriété a la matrice G du fait que le graphe soit non orienté ?
32. Quelle commande permet de récupérer l’ordre du graphe ?
33. Écrire une fonction Voisin(G,S) qui permet de renvoyer la liste des sommets voisins du sommet n◦ S du
graphe G.
34. Écrire une fonction EstComplet(G) qui teste si le graphe G est complet.

Fabien DÉLEN [Link]@[Link] 2 PSI 2024-2025

Lycée de l’Essouriau REMISE EN CHAUFFE PYTHON Les Ulis

CORRECTION
LES VARIABLES
1. Quelle commande permet d’accéder au dernier élément d’une liste (ou chaine de caractères) LC ?
La commande est LC[-1].
2. Donner 2 différences fondamentales entre les listes et les chaines de caractères, qui fait que l’on pourra
préférer d’utiliser l’une plutôt que l’autre dans un script Python.
Les chaı̂nes de caractère sont immuables (on ne peut pas les modifier).
Les listes subissent l’effet de bord (modifiées même à l’intérieur d’une fonction) et les copies sont dynamiques !
Rappel : pour effectuer une copie profonde d’une liste on fait l’instruction L2 = [Link]() ou L2 = L1[:]
ou L2 = [x for x in L1].
3. Donner un avantage, puis un inconvénient des dictionnaires sur les listes/chaı̂nes.
Avantage : la recherche dans un dictionnaire est en O(1) contre O(len(L)) pour une liste.
Inconvénient : il n’y a pas d’ordre dans un dictionnaire, donc pas d’indice non plus ! Rappel : les éléments
d’un dictionnaire sont des couples (clés,valeur)
4. Soit x un flottant, on veut vérifier si x est nul. Le test x==0 est-il adéquat ?
Justifier, si vous avez répondu non, quel test feriez-vous ?
Ce test n’est pas adéquat : un flottant ne sera pas codé informatiquement exactement par le code associé à 0.
Un meilleur test possible serait : abs(x) < 10**(-10) par exemple.
L’idée est d’exprimer que le flottant x est suffisamment petit pour être assimilé à 0, les erreurs d’approxi-
mation dues à la représentation des nombres en binaire sont ainsi évitées.

LES ALGORITHMES DE TRI

5. Donner les noms des algorithmes de tri que vous connaissez.
On a le tri fusion, le tri rapide, le tri bulle, le tri par insertion et le tri par sélection.
6. Donner la complexité de ces tris.
Tri fusion : O(n ln(n)), le tri rapide : O(n ln(n)) en moyenne, tri bulle, par insertion et par sélection : : O(n2 ).
7. Quel est le tri le plus rapide en moyenne ? Quel(s) principe(s) utilise-t-il ?
Le tri fusion en O(n ln(n)) est le plus rapide, il utilise le principe de dichotomie.
Le tri fusion est écrit en général de façon récursive.

LES ALGORITHMES « FACILES » CLASSIQUES

8. Soit texte une chaı̂ne de caractères, écrire une fonction Presence(lettre,texte) qui vérifie si texte
contient le caractère lettre.
1 def Presence ( lettre , texte ):
2 for car in texte :
3 if car == lettre :
4 return True
5 return False

Attention à l’indentation du return False !

Fabien DÉLEN [Link]@[Link] 3 PSI 2024-2025

Lycée de l’Essouriau REMISE EN CHAUFFE PYTHON Les Ulis

9. Soit L une liste de flottants, écrire une fonction moy(L) qui calcule la moyenne des éléments de L.
1 def moy ( L ):
2 S =0
3 for x in L :
4 S += x
5 return S / len ( L )

10. Ajouter dans moy(L) la signature ainsi qu’un test d’assertion qui vérifie que L est bien une liste et qu’elle
est non vide.
1 def moy ( L : list ) - > float :
2 assert type ( L )== list and len ( L )!=0
3 S =0
4 for x in L :
5 S += x
6 return S / len ( L )

11. Soit L une liste de flottants, écrire une fonction Mini(L) qui calcule le minimum des éléments de L.
1 def Mini ( L ):
2 m=L[x]
3 for x in L :
4 if x < m :
5 m=x
6 return m

12. Soit texte une chaine de caractères. Écrire une fonction Tipex(texte,i,lettre) qui renvoie une chaı̂ne
où le caractère d’indice i aura été remplacé par le caractère lettre dans texte.
texte ne doit pas être modifiée.
1 def Tipex ( texte ,i , lettre ):
2 return texte [: i ]+ lettre + texte [ i +1:]

13. Soit L une liste de flottants. Écrire une fonction Croissante(L) qui teste si L est une liste triée par ordre
croissant ou non (renvoie le booléen adéquat).
1 def Croissante ( L ):
2 for i in range ( len ( L ) -1):
3 if L [ i ] > L [ i +1]:
4 return False
5 return True

14. Écrire une fonction PasDeDoublons(L) qui renvoie une liste contenant les mêmes éléments que ceux de la
liste L mais en un seul exemplaire (complexité attendue en O(len(L))).
L ne doit pas être modifiée.
1 def PasDeDoublons ( L ):
2 D ={}
3 L2 =[]
4 for x in L :
5 if x not in D :
6 L2 . append ( x )
7 D [ x ]= True
8 return L2

Fabien DÉLEN [Link]@[Link] 4 PSI 2024-2025

Lycée de l’Essouriau REMISE EN CHAUFFE PYTHON Les Ulis

15. Écrire une fonction RienAVoir(L1,L2) qui renvoie True si les deux listes L1 et L2 n’ont aucun élément
en commun et False sinon (complexité attendue en O(max(len(L1),len(L2)))).
1 def RienAVoir ( L1 , L2 ):
2 D ={}
3 for x in L1 :
4 if x not in D :
5 D [ x ]= True
6 for x in L2 :
7 if x in D :
8 return False
9 return True

16. Soit D un dictionnaire dont les clefs et les valeurs sont toutes des chaı̂nes de caractères. Écrire une fonction
PlusLong(D) qui renvoie la clef dont la valeur associée est de longueur maximale.
1 def Pluslong ( D ):
2 M =0
3 for key in D :
4 if len ( D [ key ]) > M :
5 M = len ( D [ key ])
6 keyM = key
7 return keyM

17. Écrire des commandes qui permettent de définir une image blanche de taille h × w (c’est à dire une liste
de h listes de longueur w ne comportant que des 255).
1 img =[[255 for j in range ( w )] for i in range ( h )]

ou
1 img =[]
2 for i in range ( h ):
3 ligne =[255 for j in range ( w )]
4 img . append ( ligne )

ou
1 img =[]
2 for i in range ( h ):
3 ligne =[]
4 for j in range ( w ):
5 ligne . append (255)
6 img . append ( ligne )

18. Soit texte une chaı̂ne de caractères, écrire une fonction Occurences(texte) qui renvoie un dictionnaire
dont les clefs sont les caractères de texte et la valeur associée le nombre d’occurrences du caractère dans
texte.
1 def Occurrences ( texte ):
2 D ={}
3 for elt in texte :
4 if elt in D :
5 D [ elt ]+=1
6 else :
7 D [ elt ]=1
8 return D

Fabien DÉLEN [Link]@[Link] 5 PSI 2024-2025

Lycée de l’Essouriau REMISE EN CHAUFFE PYTHON Les Ulis

19. Soit texte une chaı̂ne de caractères, écrire une fonction EltMajoritaire(texte) qui renvoie l’un des
éléments qui apparait le plus souvent souvent dans cette chaı̂ne.
1 def EltMajoritaire ( texte ):
2 D = Occurrences ( texte )
3 M =0
4 for key in dico :
5 if D [ key ] > M :
6 M = D [ key ]
7 EltMaj = jey
8 return EltMaj

LES MOINS FACILES MAIS CLASSIQUES

On définit la suite de Fibonacci (Fn )n∈N par F0 = 0, F1 = 1 et ∀n > 2, Fn+2 = Fn+1 + Fn .
20. Écrire une fonction itérative F(n) qui renvoie la n-ième valeur de la suite de Fibonacci.
1 def F ( n ):
2 if n <=1:
3 return n
4 f0 , f1 =0 ,1
5 for k in range (2 , n +1):
6 f2 = f0 + f1
7 f1 = f2
8 f0 = f1
9 return f2

21. Écrire une fonction récursive F2(n) qui renvoie la n-ième valeur de la suite de Fibonacci.
1 def F2 ( n ):
2 if n <=1:
3 return n
4 return F2 (n -1)+ F2 (n -2)

22. Quelle est la complexité de la fonction F2 écrite ci-dessus ?

La complexité de la fonction précédente est exponentielle : le nombre d’appel double quasiment à chaque
étape (en fait la vraie complexité est en O(ϕn ) ou ϕ est le nombre d’or).
23. Écrire une fonction PlusProches(L) qui prend en entrée une liste de flottants et renvoie un couple (tuple)
d’indices distincts de valeurs les plus proches dans cette liste.
L’important est de comprendre la nécessité d’une double boule triangulaire (des indices i < j) et qu’il
s’agit de l’algorithme du minimum sur l’ensemble des couples d’éléments distincts possibles.
1 def PlusProches ( L ):
2 d = abs ( L [0] - L [1])
3 ind1 , ind2 =0 ,1
4 for i in range ( len ( L )):
5 for j in range ( i ):
6 e = abs ( L [ i ] - L [ j ])
7 if e < d :
8 d=e
9 ind1 , ind2 =i , j
10 return [( L [ ind1 ] , L [ ind2 ])

Fabien DÉLEN [Link]@[Link] 6 PSI 2024-2025

Lycée de l’Essouriau REMISE EN CHAUFFE PYTHON Les Ulis

24. Écrire une fonction SecondMax(L) qui prend en entrée une liste de flottants et renvoie la valeur du second
maximum de cette liste (la seconde valeur maximale après le maximum).
L’important est de comprendre que l’on recherche le maximum dans un premier temps, puis que l’on ap-
plique l’algorithme du maximum en écartant les éléments égaux au maximum (notamment pour initialiser
le second maximum M2.
1 def SecondMax ( T ):
2 M = Maximum ( T )
3 debut =0
4 while T [ debut ]== M :
5 debut +=1
6 M2 = T [ debut ]
7 for k in range ( debut , len ( T )):
8 if T [ k ] > M2 and T [ k ]!= M :
9 M2 = T [ k ]
10 return M2

LES IMAGES
25. Implémenter une fonction dim(img) qui prend en entrée une matrice img (liste de listes) représentant une
image en niveaux de gris (chaque élément est un entier entre 0 et 255 et renvoie le couple (h, w) donnant
la dimension de l’image (h pour hauteur et w pour la largeur).
1 def dim ( img ):
2 return ( len ( img ) , len ( img [0]))

26. Implémenter une fonction voisins(pixel,img) qui prend en entrée une matrice img et un tuple d’entier
pixel (coordonnées (i, j) du pixel) et renvoie la liste des coordonnées des pixels voisins de ce pixel.
(il y a au plus 4 voisins par pixel et on fera attention aux bords !)
1 def voisins ( pixel , img ):
2 h , w = dim ( img )
3 i , j = pixel
4 V = []
5 if i >0:
6 V . append ([ i -1 , j ])
7 if j >0:
8 V . append ([ i ,j -1])
9 if i <h -1:
10 V . append ([ i +1 , j ])
11 if j <w -1:
12 V . append ([ i , j +1])
13 return r

Fabien DÉLEN [Link]@[Link] 7 PSI 2024-2025

Lycée de l’Essouriau REMISE EN CHAUFFE PYTHON Les Ulis

LES GRAPHES
Soit G un graphe non pondéré, codé par son dictionnaire d’adjacence noté G. Les clefs sont les noms des sommets
et les valeurs associées la liste des sommets adjacents au sommet.
27. Quelle commande permet de récupérer l’ordre du graphe ?
1 len ( G ) # la longueur du dictionnaire = nombre de sommets ...

28. Écrire une fonction Voisins(G,S) qui permet de renvoyer la liste des sommets voisins du sommet S du
graphe G.
1 def Voisins (G , S ):
2 return G [ S ]

29. Écrire une fonction Isole(G) qui permet de renvoyer la liste des sommets isolés du graphe G.
1 def Isole ( G ):
2 L =[]
3 for S in G :
4 if len ( G [ S ])==0:
5 L . append ( S )
6 return L

Soit G un graphe non orienté et pondéré, dont les sommets sont numérotés de 0 à n − 1, (n étant donc l’ordre
du graphe) codé par sa matrice d’adjacente notée G.
30. A quoi correspond la valeur de G[i][j] dans le graphe ?
G[i][j] correspond au point de l’arête reliant le sommet n◦ i au sommet n◦ j et 0 s’il ne sont pas reliés
(ou +∞ parfois)
31. Quelle propriété a la matrice G du fait que le graphe soit non orienté ?
La matrice est bien entendue symétrique.
32. Quelle commande permet de récupérer l’ordre du graphe ?
1 len ( G ) # la taille de la matrice = nombre de sommets ...

33. Écrire une fonction Voisin(G,S) qui permet de renvoyer la liste des sommets voisins du sommet n◦ S du
graphe G.
1 def Voisins (G , S ):
2 V =[]
3 for j in range ( len ( G )):
4 if G [ S ][ j ]!=0:
5 V . append ( j )
6 return V

34. Écrire une fonction EstComplet(G) qui teste si le graphe G est complet.

1 def EstComplet ( G ):
2 for i in range ( len ( G )):
3 for j in range ( len ( G )):
4 if i == j and G [ i ][ j ]!=0:
5 return False
6 elif i != j and G [ i ][ j ]==0:
7 return False
8 return True

Fabien DÉLEN [Link]@[Link] 8 PSI 2024-2025