Info 11

FORMULAIRE D’INFORMATIQUE
Classe de PCSI - Année 2022-2023
Python et Spyder : histoire et fonctionnement de l’interface (p.2)

Variables et opérations informatiques (p.4)
Entiers et flottants (p.5)
Tableaux et listes (p.6)
Tuples (p.7)
Chaı̂nes de caractères (p.8)
Dictionnaires (p.9)
Instructions conditionnelles (p.10)
Instructions itératives (p.12)
Fonctions Python (p.13)
Algorithmes classiques (p.14)
Autres algorithmes assez classiques (p.15)
Bibliothèques et modules (p.16)
Bibliothèque matplotlib.pyplot (p.17)
Algorithmes dichotomiques (p.18)
Algorithmes récursifs (p.20)
Algorithmes de tri (p.23)
Algorithmes gloutons (p.28)
Manipulation de fichiers texte (p.29)
Manipulation de fichiers image (p.30)
Représentation de nombres (p.33)
Méthodes de programmation (p.34)
Terminaison et correction d’un algorithme (p.35)
Complexité (p.36)
Graphes : Généralités (p.40)
Graphes : Parcours de graphes (p.44)
Graphes : Plus court chemin (p.47)
Lycée de l’Essouriau FORMULAIRE D’INFORMATIQUE Les Ulis
PYTHON ET SPYDER
ALGORITHME
Un algorithme est une suite finie d’opérations élémentaires constituant un schéma de calcul ou de résolution
de problème.
Faire de l’algorithmique, c’est donc décomposer un problème complexe en des sous-problèmes de plus en
plus simples jusqu’à arriver aux actions élémentaires que connaı̂t l’ordinateur.
LE LANGAGE DE PROGRAMMATION PYTHON

Une fois conçu, on traduit l’algorithme dans un langage de programmation (Java, C, C++, PHP, Python,
Maple, Scilab, Pascal, etc) qui convertit les instructions en langage machine et permet ainsi à l’ordinateur
d’exécuter l’algorithme.
Attention : un langage de programmation n’est pas un logiciel !
Python est le langage de programmation au programme des CPGE scientifiques. Ce langage a été développé
par le mathématicien hollandais Guido Von Russom à la fin des années 80 - début des années 90. Celui-ci a
nommé le langage en référence à la troupe d’humoristes britanniques des Monthy Python.
Python est un langage de haut niveau, c’est-à-dire un langage de programmation orienté vers les problèmes
à résoudre, permettant d’écrire facilement des programmes à l’aide de mots usuels (en anglais) et de symboles
mathématiques. A contrario, un langage de bas niveau se rapproche du langage machine (dit binaire) et permet
de programmer à un niveau très avancé, ce qui induit des temps de calculs réduits pour un problème donné
par rapport à un langage de haut niveau. La contrepartie dans l’utilisation d’un langage de bas niveau est la
longueur du code qui est en général bien plus importante.
L’INTERFACE SPYDER
Pour travailler en Python, il suffit d’écrire de simples fichiers textes (extension « *.py ») et de les interpréter.
Cependant, pour faciliter l’interface Python-utilisateur on utilise souvent un environnement de développement
pour faciliter la programmation comme les logiciels Pyzo, Spyder, Emacs ou Idle.
L’environnement Spyder se décompose comme tous les autres environnements en plusieurs fenêtres.
Il faut bien faire la différence entre les différentes fenêtres, l’interpréteur et l’éditeur :
• L’éditeur sera l’endroit où vous écrirez vos pro-

grammes en langage Python.
• L’interpréteur/console sera l’endroit où vous
exécuterez vos programmes, où vous taperez vos
calculs, où vous pourrez tester l’écriture d’une
ligne de commande.
• Je vous conseille de laisser à votre disposition la
fenêtre de l’explorateur de variables et celle
de l’inspecteur d’objets.
ATTENTION : Écrire un programme est différent de l’exécuter ! ! !

I Écrire un nouveau programme en cliqueant sur « fichier » puis « nouveau fichier ».
I Sauvegarder votre programme avec un nom sans espace, sans tiret et sans accents, apostrophes, symboles...
I Une fois votre programme écrit, n’oubliez pas de le sauvegarder avant de l’exécuter (avec F5 ou I ).
Fabien DÉLEN [email protected] 2 PCSI 2022-2023

QUELQUES COMMANDES PYTHON

Rappelons que dans le langage Python les sauts de ligne, les indentations les majuscules et les espaces ont
leur importance. Voici quelques autres commandes indispensables
I La commande # sert à écrire des commentaires sur une seule ligne.
I Si les commentaires ont lieu sur plusieurs lignes, on les écrit entre """. . .""" (triples guillemets).
I La commande \ sert pour aller à la ligne dans l’éditeur sans que l’interpréteur lui aille à la ligne.
(cela sert surtout lorsque nous avons une longue ligne de code et que nous voulons la voir complète à l’écran.)
I La commande print() permet d’écrire un texte ou d’afficher un résultat.
Attention : par défaut un programme n’affiche pas ce qu’il calcule sans la commande print().
I La commande input() permet de demander à l’utilisateur de saisir/définir une variable.

Attention, si l’on saisit une variable, il faut précéder cette commande du mot clef eval() afin d’éviter que la
variable définie soit interprétée comme une chaı̂ne de caractères.
I Rappelons quelques raccourcis claviers sous Windows :
CTRL+C : Copie un morceau de texte préalablement sélectionné (grisé) sous un éditeur.
CTRL+X : Coupe un morceau de texte sélectionné, mis dans le « presse-papiers », et peut être ensuite collé.
CTRL+V : Colle un morceau de texte qui aura préalablement été mis de côté via un copié ou un coupé.
CTRL+S : sauvegarde le fichier sur lequel on travaille sur quasiment tous les éditeurs.
CTRL+Z : annule une action sur quasiment tous les éditeurs.
CTRL+Shift+Z : annule une annulation ...
QUELQUES COMMANDES SPYDER COMPLÉMENTAIRES

I Il est possible de scinder le même fichier en plusieurs cellules de sorte à pouvoir les exécuter de façon
indépendantes au lieu de ré-exécuter toutes les instructions depuis le début.
Dans l’exemple ci-contre, le

fichier a été séparé en 3 cel-
lules. La cellule active est la
cellule 2 (celle où se trouve
le curseur) et on clique sur
l’onglet indiqué pour n’exé-
cuter que cette cellule.
I Parfois, lors d’écriture de scripts Python on utilise des fichiers annexes pour importer leur contenu, voir même
créer des fichiers directement avec Python. Il est nécessaire que les fichiers utilisés soient dans le répertoire de
travail indiqué par Spyder.
Il suffit de le régler sur le bon dossier comme indiqué ci-dessous.

VARIABLES ET OPÉRATIONS INFORMATIQUES
DÉFINITION D’UNE VARIABLE

I Une variable est une représentation idéale d’une zone de mémoire de l’ordinateur. Il s’agit d’un endroit où
l’on peut stocker une valeur, y accéder et changer cette valeur.
Une variable se caractérise par son nom (qui permet de l’identifier), une valeur (qu’il faut lui affecter) et type.
I L’affectation est l’instruction qui permet d’assigner une valeur à une variable. Si cette dernière n’existe
pas encore, on parle de déclaration de la variable .
la syntaxe Python dévolue est variable = valeur. signifiant variable←valeur
on peut échanger les valeurs de deux variables avec la syntaxe x,y = y,x
I Le type d’une variable correspond à la nature de celle-ci.
Il en existe de nombreux mais parmi eux certains sont à maitriser.
LES TYPES DE VARIABLES

Voici les différents types de variables qu’il est impératif de connaı̂tre :
Type de variable Syntaxe Python Description Exemple
Entier relatif int Entiers (64 bits) 1981
Nombre à virgule float Nombres décimaux 3.141592
Liste/Tableau list Tableaux formés de variables [1981,3.14,"PCSI"]
Chaı̂ne de caractères str Tableaux formés uniquement de lettres "Essouriau"
Booléens bool Peut prendre deux valeurs True ou False True
Tuple tuple n-uplets (couple, triplet) de variables (True,"e",3.14)
Dictionnaire dict collections d’éléments avec clés et valeurs {clef:valeur,...}
Lorsque l’on définit une variable, il faut donc avoir en tête le type de variable utilisé.
I En cas de doute, vous pouvez utilisez type(x) si vous voulez connaitre le type de votre variable x.
LES OPÉRATIONS SUR LES VARIABLES

Il est important de connaı̂tre les opérations élémentaires que nous pouvons effectuer sur ces variables.
Attention, le résultat de ces opérations peut dépendre du type de la variable considérée.
Opérateur Utilité
+ Addition
- Soustraction
* Multiplication
/ Division
% Modulo (reste de la division euclidienne)
// Quotient(de la division euclidienne)
** Puissance (et surtout pas ∧ !)
+= Rajouter à la variable
-= Enlever à la variable
*= Multiplier à la variable.
/= Diviser à la variable
== et != égal et différent (test)
< et > inférieur et supérieur (test)
<= et >= inférieur ou égal et supérieur ou égal (test)

ENTIERS ET FLOTTANTS
ENTIERS

Entier relatif int Entiers (64 bits) de -2147483648 à 2147483647 1981
I [[−2147483648, 2147483647]] = [[−232 , 232 − 1]], ce qui fait 264 nombres relatifs représentables sur 64 bits.
Néanmoins tout entier relatif x n’étant pas dans cet intervalle est quand même codé sans problème par Python
(pas de dépassement de capacité) sous la forme « d’entier long » (cet entier relatif sera stocké sous la forme
d’une collection de nombres représentatifs sous 64 bits qui seront concaténées pour représenter ce nombre x).
I La commande int(x) transforme le type float en type int (int(2.5) retourne 2)
Exemple. Voici quelques exemples :

Commande dans l’interpréteur Résultat obtenu
3.1-2.5 0.6
1.5**2.1 2.3431044239829237
13%4 1
13//4 3
x=4 puis x+=3 7
x=17 puis x//=3 5
5<4 False
1<=1 True
1+1==2 True
FLOTTANTS

Nombre à virgule float Nombres décimaux 3.141592
I Tout nombre réel x est en fait représenté sur 64 bits à l’aide de sa forme normalisée (signe, exposant
et mantisse), la taille étant limité à 64 bits, le code associé est donc très souvent seulement une (bonne)
approximation du réel x.
I La commande float(x) transforme le type int en type float (float(2) retourne 2.0)

3+3 6
2**3 8
13.0%4 1.0
13/4 3.25
x=4 puis x*=0.5 2.0
0.1+0.2==0.3 False
Le résultat de la dernière ligne du tableau peut paraitre étonnant car mathématiquement l’égalité est vraie et
on s’attend à True mais la représentation de ces deux flottants n’étant qu’approchée, on n’a pas égalité de leur
représentation sur 64 bits ce qui explique le résultat False.
I C’est la raison pour laquelle on bannit le test d’égalité entre deux flottants.

TABLEAUX ET LISTES
LISTES

Liste/Tableau list Tableaux formés de variables [1981,3.14,"PCSI"]
I La commande list(x) transforme le type str en type list (list("texte") retourne ["t","e","x","t","e"])
I La commande [x] transforme le type int ou float en type list (par exemple [3] ou [3.0])

3*[1,2,3] [1,2,3,1,2,3,1,2,3]
[4,5,6]+[1,2,3] [4,5,6,1,2,3]
[1,2]==[2,1] False
[k**2 for k in range(5)] [0,1,4,9,16]
I Liste à une dimension :
Liste vide : L=[]
Définir une liste de petite taille par ses éléments : L=[45,True,-3.0,"texte"].
Définir une liste nulle par répétition L=[0]*n (liste de taille n remplie de 0)
Définir une liste de taille n par compréhension : L=[3**i for i in range(n) if i%2==1]
Longueur d’une liste : len(L)
Aller chercher l’élément n◦ k d’une liste : L[k] , le remplacer par x : L[k]=x , le dernier élément : L[-1]
(ATTENTION : l’index des éléments démarre à 0 ! ! !)
Ajouter un élément x (à la fin) d’une liste L : L.append(x) (L+=[x] à éviter)
Retirer le dernier élément d’une liste L : L.pop()
Retirer l’élément d’indice i d’une liste L et renvoie sa valeur : L.pop(i) (hors-programme)
Élément par élément Indice par indice

1 L =[2 ,5 ,4 ,7 ,6 ,3] 1 L =[2 ,5 ,4 ,7 ,6 ,3]
I Parcourir les éléments d’une liste : for k in range ( len ( L )):
2 for x in L : 2
3 print ( x ) 3 print ( L [ k ])
Remarque : Ne confondez pas l’élément du tableau T[i] avec son indice i.
(pour la première méthode de parcours d’un tableau, il est impossible de récupérer les indices des éléments.)
I Tranches dans une liste :

L[debut:fin] renvoie la liste contenant les éléments de L de L[debut] (inclus) jusqu’à L[fin] (exclus).
L[debut:] renvoie une liste contenant les éléments de la liste L de L[debut] (inclus) jusqu’à la fin.
L[:fin] renvoie une liste contenant les éléments de la liste L du début jusqu’à L[fin] (exclus).
L[:i]+L[i+1:] créé une nouvelle liste sans l’élément d’indice i de L.

I Liste à deux dimensions :

Une liste à deux dimensions est une liste de listes :
1 L =[[ valeur1_1 ,...] ,[ valeur2_1 ,...] ,...]
Vous remarquez qu’il y a des crochets à l’intérieur d’autres crochets, ceci veut dire qu’il y a des listes
imbriquée, il s’agit donc d’une liste ayant d’autres listes comme valeurs.
Chaque imbrication ajoute une dimension à la liste. (listes à trois dimensions, etc...)
Accéder aux éléments d’une liste de listes : L[i][j] (élément d’indice j de la liste d’indice i de L)
Exemple : L[0][0] est le premier élément de la première liste
Exemple : L[1][-2] est l’avant-dernier élément de la seconde liste (liste d’indice 1)
Exemple : L[0] est la première « élément-liste » de L en entier
Parcourir les éléments d’une liste de listes (forcément une double boucle) :
1 L =[[2 ,5 ,4 ,1] ,[5 ,8 ,9] ,[2] ,[4 ,7 ,8 ,6 ,4 ,7 ,8] ,[3 ,6] ,[5] ,[2 ,6 ,5 ,7 ,4]]

1 for l in L : 1 for i in range ( len ( L )):
2 for x in l : 2 for j in range ( len ( L [ i ])):
3 print ( x ) 3 print ( L [ i ][ j ])
Si chaque « élément-liste » a la même longueur on peut alors plutôt parler de « matrice ».

Nombre de « lignes » : n=len(L) et Nombre de colonnes : p=len(L[0])
« Matrice » nulle de taille n × p : M=[[0]*p for i in range(n)]
Ces matrices servent par exemple pour stocker les valeurs des pixels d’une image (noir et blanc/couleur).
I Copie superficielle et en profondeur :

Si L est une liste et si M=L, alors une modification de M entraı̂ne une modification de L (et vice-et-versa).
On parle de copie superficielle.
Rappelons enfin qu’une fonction modifie une liste même sans return, même s’il cette liste est modifiée en
tant que variable locale. C’est ce qu’on appelle l’effet de bord.
Si vous voulez faire évoluer L et M de façon indépendante, la commande M=L.copy() pare le problème.
On parle de copie en profondeur.
Si jamais vous avez oublié la commande copy ce n’est pas grave : M=L.copy() ⇔ M=[l for l in L] ⇔ M=L[:]
TABLEAUX
I Les listes sont des tableaux, ce qui les diffèrent, c’est que les valeurs des listes peuvent être de types
différents (une liste peut contenir un nombre et un texte.)
Ce qui a été expliqué précédemment sur les listes reste valable pour les tableaux.
1 liste =[ " mercredi " ,19 , " septembre " ,2015]
2 tableau =[ " mercredi " ," 19 " ," septembre " ," 2015 " ]
TUPLES
Tuple tuple n-uplets (couple, triplet) de variables (True,"e",3.14)
I Les éléments d’un tuple sont ordonnés et on accède à un élément grâce à sa position en utilisant un numéro
qu’on appelle l’indice de l’élément comme une liste.
I Contrairement aux listes, les tuples ne sont pas modifiables. (moins modulables que les listes, moins utilisés)

CHAÎNES DE CARACTÈRES
Chaı̂ne de caractères str Tableaux formés uniquement de lettres "Essouriau"
I Les chaı̂nes de caractères sont des variables contenants du texte. Elles se disent de type str.
I Les chaı̂nes de caractères s’écrivent entre guillemets " ou apostrophes ’.
I La plupart des opérations définies pour les tableaux s’appliquent aux chaı̂nes de caractères mais pas toutes.
I La commande str(x) transforme le type int,float ou list en type str.

(str(3) retourne "3",str(3.0) retourne "3.0" et str([1,2]) retourne "[1,2]")

3*"Aie " "Aie Aie Aie "
Exemple. Voici quelques exemples : "I am"+"clever" "I amclever"
"ab"=="ba" False
len("Ca va?") 6
I On remarque que l’espace " " compte pour un caractère à part entière ! Quelques autres caractères spéciaux.
Utilité Caractère
Utilité Caractère
Aller à la ligne \n
Afficher un anti-slash \\
Afficher un guillemet \"
Saut de page \f
Afficher une apostrophe \’
I Quelques commandes sur les chaı̂nes :
Chaı̂ne vide : chaine=""
Définir une chaı̂ne de petite taille par ses éléments : chaine="Voilà ce que je voulais vous dire!".
Longueur d’une chaı̂ne : len(chaine)
Élément n◦ k d’une chaı̂ne : chaine[k] , le dernier élément : chaine[-1] (l’index commence à 0 !)
On ne peut pas modifier une chaine, ajouter/retirer des éléments à une chaine !
Exemple : chaine.append("x") renvoie une erreur, comme chaine[k]="z" ou encore chaine.pop().
Même si les chaı̂nes de caractères sont immuables ou non modifiables, pour contourner ce problème
on peut effacer l’ancienne chaı̂ne au profit d’une nouvelle contenant les modifications.
Exemple : chaine="Bomjour!"
Modifier un caractère : chaine=chaine[:2]+"n"+chaine[3:]
Supprimer le dernier caractère : chaine=chaine[:-1]
I Parcourir les éléments d’une chaı̂ne :

1 chaine = " Bonjour à tous ! " 1 chaine = " Bonjour à tous ! "
2 for lettre in chaine : 2 for k in range ( len ( chaine )):
3 print ( lettre ) 3 print ( chaine [ k ])
Remarque : Ne confondez pas l’élément de la chaı̂ne chaine[i] avec son indice i.
(pour la première méthode de parcours d’une chaı̂ne, il est impossible de récupérer les indices des éléments.)
I Tranches dans une chaı̂ne : identiques aux tranches dans une liste.
I Copie superficielle et en profondeur Pas de problème pour les chaı̂nes de caractères.
I Quelques commandes supplémentaires (à ne pas retenir mais elles existent) :
chaine.lower(), chaine.upper(), chaine.find("lettre"), chaine.count("lettre"), chaine.index("lettre")

DICTIONNAIRES
Dictionnaire dict collections d’éléments avec clés et valeurs {clef:valeur,...}
I Un dictionnaire (type dict) est une collection d’éléments composés d’une clé associée à une valeur.
I Contrairement aux listes qui sont délimitées par des crochets, on utilise des accolades pour les dictionnaires.
I Un dictionnaire en Python va permettre de rassembler des éléments (comme des listes ou tuples) mais ceux-ci
seront identifiés par une clé. Analogie à un dictionnaire où on accède à une définition avec un mot.
I Commandes utiles pour un dictionnaire :

Méthode 2 - Ajout un par un des éléments
Méthode 1 - Directement par la liste de ses éléments :
(par exemple le nombre de roues d’un type de véhicule) : 1 dico = {}
2
1 dico = { " voiture " : 4 , " vélo " : 2 , " tricycle " : 3} 3 dico [ " voiture " ]=4
4 dico [ " vélo " ]=2
5 dico [ " tricycle " ]=3
Remarque.
• Ici les clés sont "voiture", "vélo" et "tricycle".
• Les valeurs sont les entiers 4, 2 et 3. Remarque.
• Il n’y a pas d’ordre entre les clefs ! (clefs non numérotées) • Si une clé n’existe pas dans le dictionnaire
• Les clefs peuvent être n’importe quel type de variable elle est créé avec la valeur associée.
sauf des listes. • Si une clé existe déjà dans le dictionnaire,
sa valeur est remplacée.
Exemple. Exemple de dictionnaire avec différents types de variables :
1 dico ={6: " petit " , " violet " : True , False :[1 ,2 ,3]}
1 for key in dico : 1 for key in dico :

Obtenir les clés : Obtenir les valeurs :
2 print ( key ) 2 print ( dico [ key ])
Commandes Description
val=dico[key] Stocke dans val la valeur associée à la clé key dans dico
dico[key]=val Remplace la valeur associée à la clé key par val dans dico (si key était déjà présente)
dico[key]=val Ajoute la clé key et sa valeur associée val dans dico (si key n’était pas présente)
if key in dico: Teste si la clé key est dans dico (complexité en O(1))
if dico[key]==val: Teste si la valeur associée à la clé key est égale à val
COMPARATIF LISTES/TUPLES/CHAÎNES/DICTIONNAIRES
Le tableau ci-dessous regroupe les principales spécificités et différences entre ces 4 types de variables.
On utilisera le plus adapté en fonction de ce qui est demandé.
Tableau Liste Tuple Chaine de caractères Dictionnaire

type list type list type tuple type str type dict
["a",True,7] [3.14,2.71,1,41] ("a",True,7) "Essouriau" { clé : valeur , ... }
modifiable modifiable non modifiable non modifiable modifiable
ordonné ordonné ordonné ordonné non ordonné

INSTRUCTIONS CONDITIONNELLES
Une instruction conditionnelle permet d’exécuter des instructions seulement sous une certaine condition.
En Python, on utilise les mots clefs if, else et elif qui consistent à tester (avec des opérateurs de test) si
une affirmation est vraie ou non.
INSTRUCTIONS CONDITIONNELLES
I L’instruction if ... :
Une condition s’effectue avec le mot clé if ... : (mot anglais qui veut dire « si »).
1 age = eval ( input ( " Tu as quel ^

a ge ? " ))
2
3 if age ==18: # On teste si l ’ age est égal à 18.

4 print ( " Tu es majeur " )
On a besoin d’opérateurs de test pour les conditions, voici les principales :

Opérateur == != < > <= >= or and not
Teste égal non égal inférieur supérieur inférieur ou égal supérieur ou égal ou et non
I L’instruction else:
Le mot clef else: permet d’exécuter une instruction lorsque que la condition du if n’est pas vérifiée. (« else »
signifie « sinon » en anglais.)
a ge ? " ))
2
3 if age ==18:
4 print ( " Tu es majeur . " )
5 else :
6 print ( " Tu n ’ as pas 18 ans . " )
I L’instruction elif ... :

Le mot clef elif: permet d’exécuter 1 age = eval ( input ( " Tu as quel ^
a ge ? " ))
une instruction lorsque que la condi- 2
tion du if n’est pas vérifiée et que 3 if age ==18:

4 print ( " Tu es majeur " )
celle du elif est vérifiée. (« elif », pour
5 elif age ==17:
« else if » soit « sinon si ».) 6 print ( " Encore qq jours et tu seras majeur . " )
Permet d’éviter de multiplier les tests 7 else :
imbriqués avec if. 8 print ( " Tu n ’ as pas 18 , ni 17 ans . " )
I L’instruction if ... in ...

Pour chercher un caractère/un mot dans un « texte »/une chaı̂ne de caractère, on utilise if ... in ... :
(traduire par « si ... est dans ... »). On peut également chercher si un élément est dans une liste, un dictionnaire
ou un tuple.
1 Texte = " J ’ aime ^
e tre en PCSI à l ’ Essouriau "
2 if ’ PCSI ’ in Texte :
3 print ( " Le mot recherché est présente dans le texte demandé . " )
4 else :
5 print ( " Le mot recherché n ’ est pas présent dans le texte demandé . " )

I Instructions imbriquées
Attention au niveau d’indentation lorsque l’on utilise plusieurs boucles imbriquées. Par exemple :
a ge ? " )) 1 age = eval ( input ( " Tu as quel ^
a ge ? " ))
2 2
3 if age <18: 3 if age <18:

4 print ( " Tu es mineur . " ) 4 print ( " Tu es mineur . " )
5 if age <=3: 5 if age <=3:
6 print ( " Tu es un bébé . " ) 6 print ( " Tu es un bébé . " )
7 else : 7 else :
8 print ( " Tu es majeur . " ) 8 print ( " Tu es majeur . " )
I Astuces
Utiliser and ou or permet d’éviter plusieurs if ! par exemple pour x entier, 1 6 x 6 100 et impair on a :
1 if 0 < x and x <=100 and x %2==1:
Si une variable Test est un booléen True ou False, inutile d’utiliser un opérateur d’égalité dans un test.
On peut directement écrire :
1 if Test :
2 print ( " C ’ est vrai ! " )
La valeur du booléen True est reconnue par Python comme égale à celle de l’entier 1 !
Si on fait True==1 on obtient étonnamment True. De même False==0 donne True.

INSTRUCTIONS ITÉRATIVES
Les structures de contrôle itératives ou boucles permettent d’exécuter plusieurs fois de suite une ou
plusieurs instructions. Les deux types à maitriser sont : for et while .
INSTRUCTION ITÉRATIVE for ... in ... :

Les boucles inconditionnelles servent à exécuter une instruction un nombre connu de fois.
I L’instruction for k in range(debut,fin,pas):

range(a,b,h) s’utilise de la façon suivante :
— a est la valeur initiale que le compteur i va prendre. Par défaut si elle n’apparait pas, elle vaut 0.
— b-1 est la limite où la condition s’arrête.
— h est le pas avec lequel i augmente (diminue). Par défaut si elle n’apparait pas le pas vaut +1.
Exemple pour imprimer 10 lignes :
1 for i in range (1 ,11):
2 print ( " J ’ imprime la ligne numéro " ,i , " . " )
Exemples : range(12) donne dans l’ordre les entiers {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11},
range(2,12,2) donne {2, 4, 6, 8, 10} et range(9,2,-1) donne dans l’ordre {9, 8, 7, 6, 5, 4, 3}.
I L’instruction for k in liste: ou for k in chaine:

Si vous devez parcourir du texte (chaı̂ne de caractères), vous pouvez utilisez for ... in ... : , par exemple :
1 prenom = input ( " Entrer votre prénom . " )
2 for i in prenom :
3 if i == " a " :
4 print ( " Votre prénom contient la lettre a . " )
INSTRUCTION ITÉRATIVE while ... :

Les boucles conditionnelles peuvent servir à exécuter une instruction un nombre de fois dépendant de la réali-
sation d’une certaine condition.
On utilise le mot clé while ... : qui peut être traduit par « tant que ... ».
Voici un exemple analogue à celui avec for :
1 i =1
2 while i <=10 :
3 print ( " Je recopie 10 fois la m^
e me ligne . " )
4 i +=1
Notez la nécessité d’une variable aléatoire « muette » i qui s’appelle un compteur . Elle représente en
général le numéro de la boucle que l’on est en train de parcourir et intervient parfois dans le test d’arrêt.
Il est nécessaire de l’incrémenter (i+=1) à chaque boucle afin de pouvoir compter le nombre de boucles.
Un autre exemple où while est incontournable cette fois, sans nécessité d’avoir un compteur :
1 u0 =2000
2 while u0 >0 :
3 print ( " Le terme de la suite vaut " , u0 )
4 u0 = np . log ( u0 )

FONCTIONS PYTHON
FONCTION
I Pour optimiser un algorithme, on va remplacer des bouts de codes qui se répètent par une fonction.
Ainsi, en apprenant à faire des fonctions, vous rendrez votre code plus lisible.
I Quasiment toutes les questions des sujets de concours demandent d’écrire ou d’examiner des fonctions.
I En programmation, les fonctions sont identiques aux fonctions mathématiques.
À une valeur x (ou plusieurs), la fonction va retourner une valeur y (ou plusieurs).
Une fonction en informatique est donc une séquence finie d’instructions, dépendant de paramètres d’entrée
(appelés arguments), et retournant un résultat (renvoi).
1 def fonction ( argument ):
2 intructions
3 return resultat
Le mot clé def pour définir une fonction, puis on nomme la fonction et on termine par (): .
Dans la parenthèse, on a le choix entre mettre une/des variable(s) d’entrée ou aucune !
Tout ce qui appartient à la fonction sera décalé avec une tabulation.
La fonction se termine par return suivi de ce que l’on souhaite retourner.
Noter que lors de l’exécution de l’instruction return la fonction obligatoirement prend fin.
1 # 1) Je définis ma fonction . 1 # 2) J ’ exécute la fonction ( entrée = 3).

2 # ( Fonction lue mais ne pas exécutée !) 2 resultat = carre (3)
3 def carre ( x ): 3
4 y = x **2 4 # 3) J ’ affiche le résultat renvoyé .
5 return y 5 print ( resultat )
1 def exemple (x ,y , z ):
I Entrées et sorties multiples. 2 w1 , w2 , w3 = x + y +z , x * y + y * z + x *z , x * y * z
Voici un exemple qui permet de faire connaissance 3 return w1 , w2 , w3
avec une affectation multiple (triple ici) : 4
5 x ,y , z = exemple (1 ,2 ,3)
PROCÉDURE
I Les procédures sont des fonctions sans return car elles n’ont pas besoin de renvoyer quelque chose.
En fait, elles ne font que réaliser des actions, elles s’arrêtent quand elles les ont toutes accomplies.
I Une procédure ne renvoie rien, donc lors d’un affichage il s’affiche None .
VARIABLES LOCALES/GLOBALES
I Lors de la création d’une fonction Python on est amené à utiliser des variables autres que les entrées pour cal-
culer la sortie attendue. Dans ce cas le programme reconnait ces variables dans la fonction mais pas en dehors.
Ces variables sont dites locales. Si vous voulez utiliser une variable définie dans une fonction après exécu-
tion, il faut le stipuler au début de la fonction à l’aide du mot clef global . (commande hors-programme et
possible que pour une variable définie dans une fonction qui n’est pas en entrée.)
Dans cet exemple, si la variable c est utilisée dans la 1 def fonction ( argument ):
2 global c
fonction, alors le programme reconnaitra la valeur qui
3 intructions
lui a été associée même en dehors de la fonction. 4 return resultat

ALGORITHMES CLASSIQUES
I Calcul de la somme des éléments d’une liste I Calcul du produit des éléments d’une liste
1 def somme ( L ): 1 def somme ( L ): 1 def produit ( L ): 1 def produit ( L ):
2 s =0 2 s =0 2 p =1 2 p =1
3 for k in L : 3 for k in range ( len ( L )): 3 for k in L : 3 for k in range ( len ( L )):
4 s += k 4 s += L [ k ] 4 p *= k 4 p *= L [ k ]
5 return s 5 return s 5 return s 5 return p
I Détermination du max/min I Détermination de l’indice du max/min

1 def maximum ( L ): 1 def minimum ( L ): 1 def maximum ( L ): 1 def minimum ( L ):
2 M = L [0] 2 m = L [0] 2 M = L [0] 2 m = L [0]
3 for k in L : 3 for k in L : 3 imax =0 3 imin =0
4 if k > M : 4 if k < m : 4 for i in range ( len ( L )): 4 for i in range ( len ( L )):
5 M=k 5 m=k 5 if L [ i ] > M : 5 if L [ i ] < m :
6 return M 6 return m 6 M=L[i] 6 m=L[i]
7 imax = i 7 imin = i
8 return imax 8 return i
I Calcul de la moyenne des éléments d’une liste I Calcul de l’écart-type des éléments d’une liste
1 def moyenne ( L ): 1 def Ecart - Type ( L ):
2 s =0 2 m = moyenne ( L )
3 for k in L : 3 e =0
4 s += k 4 for k in L :
5 m = s / len ( L ) 5 e +=( k - m )**2
6 return m 6 return e **0.5
I Présence d’un élément dans une liste/chaı̂ne I Présence d’un élément dans une liste/chaı̂ne
1 def Presence (L , x ): 1 def Presence (L , x ):
2 if x in L : 2 for l in L :
3 return True 3 if l == x :
4 return False 4 return True
5 return False
I Nombre d’occurrences d’un élément I Nombre d’occurrences des éléments (dictionnaire)

1 def Occurrence (L , x ): Naı̈f (quadratique) Optimale (linéaire)
2 occ =0
1 def Occurences ( L ): 1 def Occurences ( L ):
3 for l in L :
2 dico ={} 2 dico ={}
4 if l == x :
3 for x in L : 3 for x in L :
5 occ +=1
4 dico [ x ]= Occurrence (L , x ) 4 if x in dico :
6 return occ
5 return dico 5 dico [ x ]+=1
6 else :
7 dico [ x ]=1
8 return dico
Soit n la longueur de la liste. Pour la version naı̈ve, la complexité est quadratique (O(n2 )), car on a une boucle
de longueur n dans laquelle à chaque étape utilise le programme Occurrence qui a aussi une complexité linéaire.
Pour la version optimale, on a uniquement une boucle de longueur n, chaque étape ne comportant que O(1)
calculs donc la complexité est linéaire (O(n)). L’idée est d’ajouter 1 au nombre d’occurrences de chaque élément
dès que l’on l’aperçoit dans la liste, le type dictionnaire permet de bien gérer cela.

AUTRES ALGORITHMES ASSEZ CLASSIQUES
I Liste des indices des éléments égaux au maximum dans un tableau

1 def Liste_Indices_Max ( T ):
1 def Maximum ( T ):
2 liste_indices =[]
2 M = T [0]
3 M = Maximum ( T )
3 for t in T :
4 for k in range ( len ( T )):
4 if t > M :
5 if T [ k ]== M :
5 M=t
6 liste_indices . append ( k )
6 return M
7 return ( liste_indices )
I Recherche du 2nd maximum dans un tableau I Recherche des deux valeurs les plus proches
(sans le modifier) dans un tableau
1 def Second_Max ( T ): 1 def D e u x _ p l u s _ p r o c h e s _ v a l e u r s ( L ):
2 M = Maximum ( T ) 2 d = abs ( L [0] - L [1])
3 debut =0 3 ind1 , ind2 =0 ,1
4 while T [ debut ]== M : 4 for i in range ( len ( L )):
5 debut +=1 5 for j in range ( i ):
6 M2 = T [ debut ] 6 e = abs ( L [ i ] - L [ j ])
7 for k in range ( debut , len ( T )): 7 if e < d :
8 if T [ k ] > M2 and T [ k ]!= M : 8 d=e
9 M2 = T [ k ] 9 ind1 , ind2 =i , j
10 return M2 10 return [( L [ ind1 ] , L [ ind2 ])
I Calcul des termes d’une suite récurrente I Dépassement d’un seuil s pour une quantité
un+2 = 3un+1 − 2un avec u0 = 4 et u1 = −5 Par exemple trouver n tel que un > s.
1 def u ( n ): 1 def seuil (u , s ):
2 u0 =4 2 n =0
3 u1 = -5 3 while u ( n ) < s :
4 if n ==0: 4 n +=1
5 return u0 5 return n
6 if n ==1:
7 return u1
8 for k in range (2 , n +1):
9 u2 =3* u1 -2* u0
10 u0 = u1
11 u1 = u2
12 return u2
I Moyenne des éléments d’une liste à deux dimensions

1 def moyenne_2D ( L ): 1 def moyenne_2D ( L ):
2 S =0 2 S =0
3 n =0 3 n =0
4 for l in L : 4 for i in range ( len ( L )):
5 n += len ( l ) 5 n += len ( L [ i ])
6 for x in l : 6 for j in range ( len ( L [ i ])):
7 S += x 7 S += L [ i ][ j ]
8 return S / n 8 return S / n

BIBLIOTHÈQUES ET MODULES
Voici certaines bibliothèques/modules de Python. Aucune connaissance n’est exigible (toute commande
sera rappelé) mais il ne faut pas les découvrir aux concours. En particulier, lors de l’épreuve oral Maths 2 de
Centrale.
Afin d’utiliser une bibliothèque ou module dans Python il faut au préalable l’importer dans votre
environnement Spyder. Il y a plusieurs façons de faire, exemple avec la bibliothèque math :
I Importation d’une fonction particulière. from math import sin par exemple, permet d’importer
spécifiquement la fonction sin, (ou cos, ou la constante e, sous ces noms là).
I Importation de toutes les fonctions. from math import * est similaire à l’importation précédente,
mais le joker * est utilisé à la place des noms explicites des fonctions.
I Importation de la bibliothèque. import math importe la bibliothèque, les fonctions sont alors ac-
cessibles par math.sin, math.cos, par exemple.
I Importation de la bibliothèque et alias. On abrège le nom de la bibliothèque avec un alias.
Avec import math as m les fonctions sont alors accessibles par m.sin, m.cos...
La documentation Python est assez bien fournie, pour y accéder il suffit d’écrire help(nom_du_module). Ceci
fonctionne également avec les alias. Par exemple, import math as m ; help(m) fournira de l’aide sur toutes les
fonctions du module. Bien sûr, il est possible d’obtenir de l’aide sur une fonction spécifique comme m.sqrt.
• Module math
Ce module contient les fonctions mathématiques usuelles, ainsi que les constantes e et π.
• Module matplotlib
On utilisera principalement le sous-module pyplot, qui sert à tracer des courbes. On l’importera comme
suit : import matplotlib.pyplot as plt.
• Module numpy
On importera ce module avec l’alias np : import numpy as np. Ce module permet la construction de
tableaux, listes, matrices et récupération de données propres aux listes (taille, nombre d’éléments...)
Sous-module linalg
Le sous-module numpy.linalg (importé comme import numpy.linalg as alg). Ce sous-module
permet de faire de l’algèbre linéaire (espaces vectoriels et leurs applications) du programme de PCSI et
PSI que vous pourrez découvrir ultérieurement. Il permet déjà d’effectuer les opérations matricielles.
Sous-module random
Le sous-module random permet de générer des nombres aléatoires, et plus généralement de traiter de
probabilités. On l’importe ici comme import numpy.random as rd.
• Module time
Permet d’importer la fonction time() qui relève le temps depuis une date donnée.
• Module scipy (Sous-modules optimize, integrate, odeint)
Le module scipy est le module de calcul scientifique. Trois points au programme : résolution d’équations
numériques, intégration de fonctions et résolution d’équations différentielles.
On utilise le sous-module optimize de scipy : import scipy.optimize as sco. La fonction fsolve
est tout indiquée pour résoudre une équation de la forme f (x) = 0.
On utilise le sous-module integrate de scipy : import scipy.integrate as sci. La fonction que
l’on va utiliser est quad. Il suffit d’indiquer la fonction à intégrer et les bornes pour calculer la valeur
de l’intégrale.
L’intégration d’équations différentielles se fait avec le même sous-module, et la fonction odeint (pour
ordinary differential equations integration).
• Autres modules : copy, fractions, polynomial, itertools, tkinter...

BIBLIOTHÈQUE matplolib.pyplot
Le programme de CPGE est clair : aucune des commandes ci-dessous n’est exigible par les élèves de CPGE.
Elle seront toutes rappelées lors des concours.
On se contente ici d’exhiber 3 usages possibles de cette bibliothèque, avec le sous-module pyplot.
TRACÉ D’UN NUAGE DE POINTS

Exemple de syntaxe possible pour tracer le
nuage de points A(−2, 3), B(−1, 0), C(3, 1) 1 # j ’ importe les packages utiles
et D(5, 2). 2 import matplotlib . pyplot as plt
3
On définit la liste des abscisses et la liste des 4 # Définition d ’ une liste d ’ abscisses et d ’ ordonnées
ordonnées puis on effectue les commandes de 5 X =[ -2 , -1 ,3 ,5]
tracé avec plt.plot(X,Y,"x"). 6 Y =[3 ,0 ,1 , -2]
7 plt . plot (X ,Y , " x " ) # Tracé du nuage de points
Le "x" est une option faisant apparaitre les 8 plt . grid () # j ’ affiche le quadrillage
points avec un symbole de croix (on peut le 9 plt . show () # j ’ affiche le tracé
changer en "o", ".", ’v’....)
TRACÉ D’UNE FONCTION
Pour tracer une courbe, définir un liste de points X 1 import numpy as np # j ’ importe les bibliothèques
discrétisant l’intervalle [a, b] de définition de f et 2 import matplotlib . pyplot as plt
3
définir la liste des images Y.
4 def f ( x ): # je définis ma fonction
Pour représenter sin sur [−2π, π] ont peut écrire : 5 return np . sin ( x )
6
7 a = -2* np . pi # je définis l ’ intervalle [a , b ]
8 b =2* np . pi
9 n =100 # je définis le nombre de points
10 # je définis ma liste d ’ abscisses et d ’ ordonnées
11 X =[ a + i *( b - a )/ n for i in range ( n +1)]
12 # je définis ma liste d ’ ordonnées
13 Y =[ f ( x ) for x in X ]
14
15 plt . plot (X , Y ) # je réalise le tracé de f
16 plt . grid () # j ’ affiche le quadrillage
17 plt . show () # j ’ affiche le tracé
• Il existe aussi le module pylab combine la fonctionnalité pyplot (pour le tracé) avec numpy.
HISTOGRAMME
La liste de commandes ci-dessous donne l’histogramme ci-contre :

(histogramme entre 0 et 10 -range=(0,10)- avec 10 intervalles bins=10).
1 import matplotlib . pyplot as pl
2 x = [2 ,2 ,3 ,4 ,4 ,4 ,4 ,5 ,5 ,5 ,6 ,6 ,6 ,6 ,6 ,7 ,7 ,7 ,8 ,8 ,9]
3 pl . hist (x , range =(0 ,10) , bins =10 , color = ’ yellow ’ , edgecolor = ’ red ’)
4 pl . xlabel ( ’ valeurs ’)
5 pl . ylabel ( ’ nombres ’)
6 pl . title ( ’ Exemple d \ ’ histogramme simple ’)
• Possibilité de créer des diagrammes en bâton (boite à moustaches), circulaires (camembert) et bien d’autres !

ALGORITHMES DICHOTOMIQUES
Le programme de CPGE est clair :

• Recherche dichotomique dans un tableau trié.
• Exponentiation rapide.
• On met en évidence une accélération entre complexité linéaire d’un algorithme naı̈f et complexité logarithmique
d’un algorithme dichotomique.
• On met en œuvre des jeux de tests, des outils de validation.
MÉTHODE DU « DIVISER POUR RÉGNER »
I Les algorithmes dichotomiques qui utilisent le principe du « Diviser pour régner » afin de diminuer la
complexité temporelle (en calcul) d’algorithmes.
I L’idée est de passer de la résolution d’un problème de « taille » n à un (ou plusieurs) problème de « taille »
n n n
2 plus rapide à résoudre et d’itérer ce principe. (passer à des problèmes de taille 4 , puis 8 , ...)
Bien entendu, on espère que la résolution de l’ensemble de ces sous-problèmes de taille « petite » soit plus
rapide que le problème initial.
RECHERCHE D’UN ÉLÉMENT DANS UNE LISTE TRIÉE

IPrincipe de la recherche par dichotomie d’un élé- On cherche si 13 appartient à la liste triée :
ment x dans une liste triée par ordre croissant :
— on choisit l’élément d’indice milieu de la liste,
— si jamais ce dernier a une valeur strictement plus grande
que x, on cherche x uniquement parmi les éléments d’in-
dices plus petit dans la liste,
— sinon on cherche x parmi parmi ceux d’indices plus
grands.
— on réitère le processus, si jamais on tombe sur l’élément
x à l’une des étapes alors x était dans la liste triée et
on renvoie True, sinon on renvoie False.
1 def recherche_dicho (x , L ):
2 g = 0
3 d = len ( L ) -1
4 while g <= d :
5 m = ( g + d )//2
6 if L [ m ] == x :
7 return True Dans cet exemple,
8 elif L [ m ] < x :
9 g = m +1 Étape 0 : g = 0 et d = 9 donc m = 4
10 else : Comme 8 < 13 alors g = 4 + 1 = 5 et d = 9.
11 d = m -1
12 return False Étape 1 : g = 5 et d = 9 donc m = 7
Pour une liste de n éléments, au maximum y a p étapes et : Comme 14 > 13 alors g = 7 et d = 9 − 1 = 8.
n ln(n) Étape 2 : g = 7 et d = 8 donc m = 8

p
≈ 1 ⇔ ln(n) − p ln(2) ≈ 0 ⇔ p ≈
2 ln(2) Comme 10 < 13 alors g = 8 et d = 8.
I Complexité asymptotique logarithmique en O(ln(n)). On a m = 8 et L[8] = 13 donc on renvoie True.

EXPONENTIATION RAPIDE
I Soit a un réel et n un entier naturel. Sous Python, la commande a**n renvoie la valeur du nombre an .
On pourrait penser que cette valeur est calculée par Python avec le principe que an = a
| × .{z
. . × a} ainsi :
n fois
1 def Exp (a , n ):
2 y =1
1 def Exp (a , n ):
serait équivalent à 3 for k in range (1 , n +1):
2 return a ** n
4 y *= a
5 return y
Mais il n’en est rien ! Le calcul de an s’effectue à l’aide de l’exponentiation rapide :

— Par exemple a16 = (((a2 )2 )2 )2 . Soit 4 calculs au lieu de 16.
— Si n n’est pas une puissance de 2 ce n’est pas grave : a7 = a4 .a2 .a1 = (a2 )2 .a2 .a = ((a2 ).a)2 .a.
Soit 4 calculs à nouveau au lieu de 7.
 n 2
 a2 si n est pair
I L’algorithme d’exponentiation rapide repose sur le principe suivant : an = n−1 2
 a 2 * a si n est impair
(ou encore il se repose sur l’écriture en base 2 de l’exposant n)
Fonction itérative
Fonction récursive
1 def Exp (a , n ):
1 def Exp (a , n ):
2 y ,z , b =a ,1 , n
2 if n ==1:
3 while m >0:
3 return a
4 q = m //2
4 if n %2==0:
Qui se traduit en Python par : 5 y = Exp (a , n //2)
5 r = m %2
6 if r ==1:
6 return y * y
7 z *= y
7 else :
8 y *= y
8 y = Exp (a ,( n -1)//2)
9 m=q
9 return y * y * a
10 return z
I L’algorithme d’exponentiation rapide est donc basé sur le principe de dichotomie.

Pour un exposant entre 2p et 2p+1 − 1 on aura au maximum p étapes, c’est à dire que pour un exposant de n,
il y a ln(n)
ln(2) étapes, soit une complexité asymptotique logarithmique en O(ln(n)).
I L’algorithme d’exponentiation « basique » quand à lui a une complexité linéaire en O(n).

ALGORITHMES RÉCURSIFS
• Version récursive d’algorithmes dichotomiques.
• Fonctions produisant à l’aide de print successifs des figures alphanumériques.
• Dessins de fractales.
• Énumération des sous-listes ou des permutations d’une liste.
• On évite de se cantonner à des fonctions mathématiques (factorielle, suites récurrentes).
• On peut montrer le phénomène de dépassement de la taille de la pile.
PRINCIPE DES ALGORITHMES RÉCURSIFS

I Les algorithmes récursifs sont des algorithmes qui résolvent un problème en calculant des solutions d’ins-
tances plus petites du même problème. On aura des fonctions qui s’appellent elle-même lors de leur exécution.
L’approche récursive est un des concepts de base en informatique, complémentaire de l’approche itérative
(avec des structures de boucles). Comme les algorithmes récursifs s’appellent eux-même, on rencontre des
problèmes qui leur sont propres.
CALCUL DE n! EN ITÉRATIF ET RÉCURSIF

Tout algorithme peut être écrit sous une forme itérative ou récursive, exemple avec la factorielle :
Version itérative Version récursive

1 def factorielle ( n ): 1 def factorielle ( n ):
2 f =1 2 if n ==0:
3 for k in range (1 , n +1): 3 return 1
4 f *= k 4 return n * factorielle (n -1)
5 return f
On s’aperçoit que la fonction factorielle à l’étape n s’appelle elle-même à l’étape n − 1, d’où la nécessité
de d’initialiser 0! = 1.
CALCUL DE TERMES D’UNE SUITE

I Calcul itératif d’une suite I Calcul récursif d’une suite
un+1 = 12 un − 1 avec u0 = 3 un+1 = 12 un − 1 avec u0 = 3
1 def u ( n ): 1 def u ( n ):
2 u =3 2 if n ==0:
3 for k in range (1 , n +1): 3 return 3
4 u = u /2 -1 4 return u (n -1)/2 -1
5 return u
Le calcul de u(5000) avec la version récursive renvoie RecursionError: maximum recursion depth ex-
ceeded in comparison : on a dépassé la limite de la pile d’exécution c’est à dire le nombre maximal d’appels
récursif autorisé par Python (s’obtient avec sys.getrecursionlimit() de la bibliothèque sys et est modifiable).
Avantages Inconvénients
• Programmation claire • Complexité très sensible à la programmation évoluant rapidement en puissance
• Simple à comprendre (ex : an ), a nombre d’auto-appels récursifs à chaque étape de complexité O(1)
• Limite de la taille de la pile d’exécution
• Preuve et terminaison de l’algorithme plus complexes à montrer
• Création de nouvelles variables locales à chaque exécution (mémoire)
• Les variables étant locales, pour récupérer des infos sur l’exécution, il faut dé-
clarer des variables globales ou les mettre en argument (cf compteurs)

COEFFICIENTS BINOMIAUX
Le but est de calculer les coefficients binomiaux à Une fonction récursive possible est :
l’aide de la formule du triangle de Pascal :
1 def binome (n , p ):
if p ==0 or p == n :

n+1 n n 2
∀n ∈ N, ∀p ∈ [[0, n]], = + 3 return 1
p p p−1
4 return binome (n -1 , p )+ binome (n -1 ,p -1)
:
Remarque : Là encore on voit la dangerosité de la récursivité car dans le pire des cas le nombre d’appels
double pour passer de l’étape n à l’étape n − 1 et donc la complexité asymptotique est exponentielle en O(2n ).
ÉNUMÉRATION DE SOUS-LISTES DANS UNE LISTE

I Soit une liste L d’entiers distincts. On veut lister toutes les sous-listes de L avec k éléments. Soit une
liste L=[1,2,3,4] et k = 2. Nous pouvons attendre deux types de résultats :
— V1 : Les sous-listes sans les permutations possibles : [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
— V2 : Les sous-listes avec toutes les permutations possibles : [[1,2],[2,1],[1,3],[3,1],. . .]
n!
I Il y a Akn = (n−k)! de sous-listes à k éléments parmi n éléments de type V1.
n n!

Il y a k = k!(n−k)! de sous-listes à k éléments parmi n éléments de type V2.
I Le principe de l’algorithme consiste à traiter le cas de base lorsque k = 1 puis à créer par récursivité
l’énumération de plusieurs sous-listes de L en k − 1 éléments et de leur ajouter ce qui leur manque.
On ajoute alors tous les résultats attendus en k éléments dans une liste qui est renvoyée.
• Pour les listes de type V1 : • Pour les listes de type V2

(on retire les listes mal ordonnées à chaque étape) :
1 def Enum_T (L , k ):
2 if k ==1: 1 def Enum_U (L , k ):
3 return [[ l ] for l in L ] 2 if k ==1:
4 sousL =[] 3 return [[ l ] for l in L ]
5 for l in Enum_T (L ,k -1): 4 sousL =[]
6 for elt in L : 5 for l in Enum_T (L ,k -1):
7 if elt not in l : 6 for elt in L :
8 ajout = l +[ elt ] 7 if elt not in l :
9 sousL . append ( ajout ) 8 if L . index ( elt ) > L . index ( l [ -1]):
10 return sousL 9 ajout = l +[ elt ]
10 sousL . append ( ajout )
11 sousL2 =[]
12 for sL in sousL :
13 test = True
14 for i in range ( len ( sL ) -1):
15 if L . index ( sL [ i ]) > L . index ( sL [ i +1]):
16 test = False
17 if test :
18 sousL2 . append ( sL )
19 return sousL2

TRACÉE DE FRACTALES
On veut tracer la figure fractale (objet mathématique qui présente une structure similaire à toutes les échelles)
appelée triangle de Sierpinski.
La figure finale ressemble à celle ci-dessous : 1 # importation du module de tracé graphique

2 from matplotlib import pyplot as plt
3 # fermeture des fen^ e tres graphiques ouvertes
4 plt . close ( ’ all ’)
5
6 def Polygon ( Liste_Points , couleur ) :
7 # fonction de tracé de polygone " plein "
8 X = []
9 Y = []
10 for Point in Liste_Points :
11 # liste des abscisses des points
12 X . append ( Point [0])
13 # liste des ordonnées des points
La fonction Polygon ci-contre permet de tra- 14 Y . append ( Point [1])
15 # remplissage polygone avec couleur
cer une sur une figure un polygone donc
16 plt . fill (X ,Y , color = couleur )
on définit les n sommets en argument 17
sous la forme d’une liste de coordonnées 18 import numpy as np
[[XA ,YA ],[XB ,YB ],. . .,[X... ,Y... ]] de la 19 # Sommets d ’ un triangle équilatéral
couleur voulue. 20 A =[0 ,0]
21 B =[0.5 , np . sqrt (3)/2]
L’exécution de la commande Poly- 22 C =[1 ,0]
gon([A,B,C],’black’) fait afficher à l’écran 23
la figure de gauche ci-dessous (n = 0). 24 # tracé du triangle en noir
25 Polygon ([ A ,B , C ] , ’ black ’)
On écrit ensuite une fonction Sier-
26
pinski(n,A,B,C) qui superpose sur ce triangle 27 def Sierpinski (n ,A ,B , C ):
noir un triangle blanc de sommets adaptés pour 28 if n ==0:
obtenir la figure à l’étape n = 1, pour chaque 29 Polygon ([ A ,B , C ] , ’ black ’)
petit triangle noir va à chaque fois superposer 30 if n >0:
à nouveau le triangle blanc « au centre », étape 31 I =[( A [ k ]+ B [ k ])/2 for k in range (2)]
par étape pour obtenir la fractale voulue (en 32 J =[( B [ k ]+ C [ k ])/2 for k in range (2)]
33 K =[( C [ k ]+ A [ k ])/2 for k in range (2)]
s’arrêtant à la n-ième l’étape).
34 Polygon ([ I ,J , K ] , ’ white ’)
Il faut donc que la fonction Sierpinski s’appelle 35 Sierpinski (n -1 ,A ,I , K )
3 fois à chaque étape !... 36 Sierpinski (n -1 ,I ,B , J )
37 Sierpinski (n -1 ,K ,J , C )
Pour finir on exécute la fonction une unique fois 38
pour faire le tracé (sans print). 39 Sierpinski (n ,A ,B , C )
Figure pour n = 0 Figure pour n = 1 Figure pour n = 2 Figure pour n = 3

ALGORITHMES DE TRI

• Algorithmes quadratiques : tri par insertion, sélection. Tri par partition-fusion. Tri rapide. Tri par comptage.
• On fait observer différentes caractéristiques (stable ou non, en place ou non, comparatif ou non, etc).
ISelon le programme officiel, aucune connaissance n’est exigible sur les algorithmes de tri.
Il n’est pas nécessaire d’apprendre le contenu de ce paragraphe par cœur. Néanmoins comprendre le fonction-
nement des tris permet de contrôler que qu’on a bien acquis les différents principes de programmation.
I Les tris ont chacun leur fonctionnement propre que l’on peut visualiser avec la vidéo YouTube https:
//www.youtube.com/watch?v=kPRA0W1kECg réalisée par Timo Bingmann.
I On s’intéresse surtout à comparer leur complexité temporelle (temps maximal asymptotique d’exécution)
mais aussi leur complexité spatiale (place mémoire maximale prise).
Les algorithmes de tri les moins performants ont une complexité quadratique (en O(n2 )) et les plus performants
en O(n ln(n)) où n est la taille de la liste donnée en entrée.
I On dit qu’un tri est comparatif s’il n’utilise que des comparaisons binaires pour trier la liste. Un bon nombre
de tris sont comparatifs.
I On dit qu’un tri est en place s’il n’utilise qu’un nombre très limité de variables et qu’il modifie directement
la structure qu’il est en train de trier. Ce caractère peut être très important si on ne dispose pas de beaucoup
de mémoire.
I On dit qu’un tri est dit stable s’il préserve l’ordonnancement initial des éléments que l’ordre considère comme
égaux.
TABLEAU COMPARATIF DES TRIS
Nom du tri Complexité En place Stable Comparatif

Tri bulle O(n2 ) oui oui oui
Tri par insertion O(n2 ) oui oui oui
Tri fusion O(n ln(n)) oui non oui
Tri rapide O(n ln(n)) oui non oui

TRI BULLE (Tri utilisant des doubles boucles imbriquées)
Le tri bulle est une stratégie de tri locale, qui consiste à trier une liste d’objets
en portant des œillères. Le principe est de regarder les éléments consécutifs de
la liste deux par deux et de les mettre dans l’ordre.
On part de la fin de la liste et l’on regarde les éléments consécutivement. A la
fin d’un premier passage sur la liste, l’élément le plus petit se retrouve en tête
de liste.
C’est de là que provient le nom : l’algorithme imite la remontée de bulles. Si la
liste est de taille n, après n passages, les n bulles seront remontées et classées
dans l’ordre.
Les flèches représentent les échanges réalisés entre les contenus de cases. Une
croix indique que les éléments étaient déjà triés et qu’il n’y a donc pas eu
d’échange.
Soit L une liste de nombres non triée, on code le tri bulle en deux temps (un algorithme pour effectuer une
étape puis un autre pour la répéter ).
I La fonction remontee_Bulle(L) déplace l’élément le plus petit en première position en suivant le principe
du tri bulle.
1 def remontee_Bulle ( L ):
2 n = len ( L )
3 for i in range (n -2 , -1 , -1):
4 if L [ i +1] < L [ i ]:
5 L [ i ] , L [ i +1]= L [ i +1] , L [ i ]
6 return L
I La fonction Tri_Bulle(L) permet de trier la liste par appels successifs à remontee_Bulle(L[i:n]) ou

bien en une seule fonction directement (pas de tranches de listes à faire) :
1 def Tri_Bulle ( L ):
1 def Tri_Bulle ( L ): 2 n = len ( L )
2 n = len ( L ) 3 for i in range ( n ):
3 for i in range ( n ): 4 for j in range (n -2 ,i -1 , -1):
4 L = L [: i ]+ remontee_Bulle ( L [ i : n ]) 5 if L [ j +1] < L [ j ] :
5 return ( L ) 6 L [ j ] , L [ j +1] = L [ j +1] , L [ j ]
7 return ( L )
I La complexité de Tri_Bulle est quadratique : on fait appel n fois à un algorithme de complexité

linéaire pour une liste de taille n − i, ce qui équivaut à une double boucle triangulaire.
C’est le plus lent des tris, il est en place et stable.

TRI PAR INSERTION (Tri utilisant des double boucles imbriquées)
Le tri par insertion est un algorithme efficace de tri d’un petit nombre d’éléments.
Son principe de fonctionnement est celui qui est souvent utilisé pour trier un jeu de cartes. On commence
avec la main gauche vide et le paquet de cartes retourné sur la table. On retourne ensuite la première carte du
paquet avec la main droite, on l’ajoute à la fin du paquet et on l’amène progressivement à la bonne position
dans la main gauche.
Pour trouver cette bonne position, on compare la carte piochée aux cartes de la main gauche une par une,
de droite à gauche.
Ici la main gauche dans laquelle on insère la nouvelle carte retournée numérotée 5.
A chaque instant, les cartes dans la main gauche sont triées et la main est composée des cartes qui étaient
au-dessus du paquet.
I Fonction insertion(L,x) qui prend en entrée une liste L (triée) et un entier ou flottant x, ajoute x à la liste
et l’amène progressivement à la bonne place selon le principe du tri par insertion.
1 def insertion (L , x ):
2 L . append ( x )
3 place = len ( L ) -1
4 while L [ place ] < L [ place -1] and place >0:
5 L [ place ] , L [ place -1]= L [ place -1] , L [ place ]
6 place -=1
I Fonction Tri_insertion(L) qui effectue le tri par insertion sur une liste L.
On commence par définir une nouvelle liste vide L_triee que l’on triera au fur et à mesure.
1 def Tri_insertion ( L ):
2 L_triee =[]
3 for x in L :
4 insertion ( L_triee , x )
5 return L_triee
I La complexité de insertion est linéaire.
La complexité de Tri_insertion est quadratique : on fait appel n fois à un algorithme de complexité linéaire
pour une liste de taille k pour k allant de 0 à n − 1, ce qui équivaut à une double boucle triangulaire en fait.
Il y a donc au maximum n(n−1) 2 boucles et une complexité quadratique en O(n2 ).

TRI FUSION (Tri utilisant la récursivité)
I La fonction Fusion(L,M) fusionne deux listes L et M déjà triées par ordre

croissant pour renvoyer la liste globale triée.
1 def Fusion (L , M ):
2 # On fusionne les deux listes par ordre croissant
3 N =[] # On part de la liste vide
4 while len ( L )!=0 and len ( M )!=0: # Si liste non vide
5 if L [0] < M [0]: # comparaison entre le 1 er de L et M
6 N . append ( L [0]) # Si c ’ est L , ajouté à N
7 L . pop (0) # Et effacé de L
8 else :
9 N . append ( M [0]) # Si c ’ est M , ajouté à N
10 M . pop (0) # Et effacé de M
11 return N + L + M # On renvoie la liste N , complétée .
12 # ( on ajoute L et M car l ’ une est vide ...)
I la fonction TriFusion(L) qui va trier récursivement la liste L.
• Pour cela, si la liste a un élément ou moins, on n’a rien à faire pour la trier.
• Sinon, on coupe la liste au milieu, on trie chacune de ces deux sous-listes de
façon récursive.
• Puis on les fusionne les deux sous-listes triées grâce à la fonction Fusion.
1 def TriFusion ( L ):
2 n = len ( L )
3 if n <=1:
4 return L
5 return Fusion ( TriFusion ( L [: n //2]) , TriFusion ( L [ n //2:]))
I La complexité de Tri_Fusion est en moyenne en O(n ln(n)).

I C’est un tri efficace, il est en place mais pas stable.

TRI RAPIDE ou « QUICK SORT » (Tri utilisant la récursivité)
I Le tri rapide est une méthode de

tri récursive.
Dans le cadre du tri fusion, la découpe
s’opérait en O(1), et la reconstruction
en O(n). Ici, la découpe va s’opérer en
O(n) et la reconstruction est quasiment
instantanée.
I Le principe est de choisir un pivot,
autour duquel nous allons couper le ta-
bleau.
I Cela consiste donc à mettre tous les
éléments plus petits que le pivot à sa
gauche, et tout les éléments plus grands
que le pivot à sa droite.
I On trie ensuite les sous tableaux
gauche et droit : en recollant les mor-
ceaux, le tableau est trié.
L’algorithme écrit ici n’est pas en « en place » (vu qu’on utilise des tableaux auxiliaires), néanmoins il peut
être écrit de sorte à être en place)
I La fonction Concatene(L,M,N) renvoie la liste 1. Une fonction possible est :

concaténée des éléments de L, M et N dans cet ordre. 1 def concatene (L ,M , N ):
2 return L + M + N
2. Une fonction possible est :

1 def Pivot ( L ):
I La fonction Pivot(L), où L est une liste, qui ren- 2 pivot = L [0]
voie trois listes (G,[L[0]],D) où G est est une liste 3 G , D =[] ,[]
4 for k in range (1 , len ( L )):
contenant les éléments de L strictement plus petit que
5 if L [ k ] < pivot :
L[0] et N est une liste contenant les autres éléments de L. 6 G . append ( L [ k ])
7 else :
8 D . append ( L [ k ])
9 return G ,[ L [0]] , D
3. Une fonction possible est :

I La fonction TriRapide(L) qui va trier L de façon 1 def TriRapide ( L ):
récursive, pour cela si L n’a pas d’éléments, réfléchir à 2 if len ( L )==0:
3 return L
ce qu’il faut renvoyer. Sinon, diviser la liste L grâce à la
4 G ,P , D = Pivot ( L )
fonction Pivot, trier les listes G et D de façon récursive, 5 G = TriRapide ( G )
et combiner le tout, grâce à la fonction Concatene. 6 D = TriRapide ( D )
7 return concatene (G ,P , D )
I Le tri rapide a été inventé par le scientifique C.A.R. Hoare en 1961.
I complexité de Tri_Fusion est en moyenne en Θ(n ln(n)).
I C’est un tri efficace, il est en place (si on n’utilise pas de tableaux auxiliaires) mais pas stable.

ALGORITHMES GLOUTONS

• Rendu de monnaie. Allocation de salles pour des cours. Sélection d’activité.
• On peut montrer par des exemples qu’un algorithme glouton ne fournit pas toujours une solution exacte ou
optimale.
Le but des algorithmes gloutons est de résoudre des problèmes d’optimisation à l’aide d’algorithmes. Un
problème d’optimisation consiste à minimiser ou maximiser une fonction/quantité sur un ensemble.
On peut citer comme exemple :
• le problème du sac à dos : maximiser le contenu (en valeur) d’un sac à dos de volume fixé en le
remplissant d’objets ayant chacun un volume et une valeur qui leur est propre.
• le problème du rendu de monnaie : comment rendre la monnaie à un client avec le moins de pièces/-
billets possible ?
• le problème d’allocation de salles : comment caser le maximum d’heures de cours dans le moins de
salles possibles tout en restant dans une plage horaire la moins ample possible.
• optimisation de trajet : minimiser le temps de trajet entre deux points A et B sur un réseau routier
Tous ces problèmes n’ont pas nécessairement une unique solution et on ne connait pas toujours d’algorithme
optimal pour répondre au problème dans toutes les situations de départ. On développe néanmoins une tactique
via un certain type d’algorithmes appelés algorithmes gloutons dont le principe est de prendre en priorité les
objets « les plus efficaces » pour répondre au problème.
1 def PlusGrandePiece ( montant , systeme ):

Exemple. Problème de rendu de monnaie 2 for l in systeme :
3 if l <= montant +0.001:
Soit un système monétaire de pièces/billets : une liste
4 return l
ordonnées par valeur décroissante. Avec l’Euro, on a :
L=[500,200,100,50,20,10,5,2,1,0.5,0.2,0.1,0.05,0.02,0.01]1. def GloutonPieces ( montant , systeme ):
Pour rendre une somme de (94e76 par exemple) en 2 reste = montant
monnaie, on commence par utiliser la plus grande piè- 3 L =[]
ce/billet que l’on peut utiliser pour payer ce montant. 4 while reste >0.001:
Puis de réitérer ce procédé jusqu’à avoir totalement 5 piece = PlusGrandePiece ( reste , systeme )
6 L . append ( piece )
rendu la monnaie.
7 reste = reste - piece
I On écrit une fonction PlusGrandePiece qui renvoie 8 return L
la plus grande valeur possible pour rendre le montant. Avec les commandes
I On écrit une fonction GloutonPieces qui réitère ce 1 SystemeEuro =[500 ,200 ,100 ,50 ,20 ,10 ,5 ,2 ,1]
procédé jusqu’à avoir rendu tout le montant. 2 SystemeEuro +=[0.5 ,0.2 ,0.1 ,0.05 ,0.02 ,0.01]
I On rajoute 0, 0001 (nombre inférieur à la plus petite 3
4 print ( GloutonPieces (94.76 , SystemeEuro ))
unité de valeur ) à chaque test sur les flottants pour
éviter les problèmes de représentation des nombres dus on obtient comme résultat
aux arrondis dans les calculs. 1 [50 , 20 , 20 , 2 , 2 , 0.5 , 0.2 , 0.05 , 0.01]
Remarque.
Dans un système monétaire [10,9,2,1] et pour un montant 18, cet algorithme n’est pas optimal, en effet, on
a été trop gourmand en prenant directement une pièce de 10e (la plus grande pièce possible), et du coup on ne
pourra plus tomber sur la solution optimale (2 pièces de 9e) car il reste 8e à payer (avece 4 pièces de 2e).
Pour cette raison, on dit que c’est un algorithme glouton.

MANIPULATION DE FICHIERS TEXTE
Selon le programme de CPGE, aucune des commandes ci-dessous n’est à connaitre par cœur.
Ouvrir un fichier avec Python se fait à l’aide de la commande open . Techniquement, on créé un objet
Python (dont le nom est complètement indépendant de celui du fichier texte) qui est un pointeur vers le fichier.
contenu=open("nom_fichier.txt",options à ajouter )
La commande open est assorti d’options, qui dépend de ce que l’on veut faire avec le fichier une fois ouvert :
• mode lecture (option "r") si on souhaite uniquement lire le fichier, accéder au contenu sans le modifier ;
• mode écriture (option "w") si on souhaite uniquement écrire des choses dans le fichier ;
• mode en ajout (option "a") si on veut uniquement ajouter du contenu à un fichier en contenant déjà.
Commandes ou syntaxes clés Description

1 contenu = open ( " nom_fichier . txt " ," r " )
2 chaine = contenu . read () Ouvre le fichier texte nom_fichier.txt en mode lecture,
3 contenu . close () sous le nom contenu. Stocke le contenu dans la variable de
type chaı̂ne de caractères chaine, puis ferme le fichier.
contenu.read(666) Si on souhaite ne pas lire l’intégralité du fichier, on peut
préciser un entier dans read, et on ne lira qu’un nombre de
caractères correspondant à l’argument.
Si on fait un nouveau read ensuite, la lecture reprendra au
caractère où on s’est arrêté au read précédent.
contenu.readline() permet de lire une ligne du fichier (\n en fin de ligne com-
pris). Le curseur de lecture du fichier est maintenant au dé-
but de la ligne suivante.
contenu.readlines() Créé une liste contenant les différentes lignes du fichier texte
(\n en fin de ligne compris).
1 contenu = open ( " nom_fichier . txt " ," a " )
2 contenu . write ( " blablabla " )
3 contenu . write ( " bliblibli " ) Permet d’ouvrir le fichier nom_fichier.txt en mode ajout.
4 contenu . write ( " blobloblo " ) écrit les textes blablabla, bliblibli, blobloblo dans le
5 contenu . close () fichier, puis ferme le fichier.
les différents textes seront écrits les uns à la suite des autres
à la fin du fichier
1 contenu = open ( " nom_fichier . txt " ," w " )
2 contenu . write ( " Texte intéressant " ) Permet de créer un fichier accessible à l’écriture.
3 contenu . close () Efface et remplace le fichier de même nom s’il existait déjà.
1 with open ( " data . txt " ," r " ) as contenu : Autre syntaxe plus courte qui permet de s’émanciper du
2 print ( contenu . read ())
problème de fermeture du fichier avec le mot clé with.
Remarque. ATTENTION !
• On ne peut pas ouvrir un fichier simultanément en mode lecture et écriture : il faut le refermer avant.
Remarque. ATTENTION !
• L’option "w" créé automatiquement un nouveau fichier texte dans lequel écrire.
• Mais surtout va écraser un fichier texte déjà existant portant le même nom.
• Si on veut modifier le contenu d’un fichier existant, il faut absolument utiliser l’option "a").

MATRICE DE PIXELS ET IMAGES

• Algorithmes de rotation, de réduction ou d’agrandissement.
• Modification d’une image par convolution : flou, détection de contour, etc.
• Les images servent de support à la présentation de manipulations de tableaux à deux dimensions.
Selon le programme de CPGE, aucune des commandes ci-dessous n’est à connaitre par cœur.
En revanche vous devez savoir sous quelle forme est stockée une image dans un fichier.
IMAGES MATRICIELLES = MATRICES(LISTES 2D) DE PIXELS

Il existe deux types d’images : les images vectorielles et les images matricielles :
• Les images vectorielles sont (re-)construites à partir d’équations mathématiques et basées sur des
formes géométriques. Zoomer ou dézoomer sur une image vectorielle relance le calcul pour affiner la
représentation en fonction de la résolution de l’écran. Les formes paraissent lisses (format .svg) Pas au
programme de CPGE.
• Les images matricielles, au programme de CPGE, sont des tableaux 2D de points qu’on appelle pixels.
Zoomer sur une image matricielle met en évidence la discrétisation des contours.
Les formats classiques d’images matriciels sont .bmp, .jpg, .png.
Image png en résolution 390 × 250 Image png en résolution 195 × 125
Image png en résolution 78 × 50 Image png en résolution 39 × 25

EXEMPLE DE COMMANDES D’IMPORT DE FICHIERS IMAGES
1 Img = imageio . imread ( " noir_et_blanc . png " ). tolist () # Convertit une image en liste
2
3 # Nombre de colonnes ( w ) et nombre de lignes ( h )
4 print ( ’w = ’ , len ( Img [0]) , ’ h = ’ , len ( Img ))
5
6 plt . imshow ( Img , cmap = ’ gray ’ , clim =(0 ,255)) # Création de l ’ image comme figure
7 plt . title ( " Titre à compléter " ) # Titre de la figure
8 plt . show () # Ouvre une fen^ e tre et affiche l ’ image
IMAGES EN NOIR ET BLANC

I La matrice de pixels, ou plutôt tableau 2D des pixels est notée ligne par ligne sous la forme :
1 Img =[[178 ,234 ,... ,97] ,[56 ,0 ,... ,111] ,... ,[154 ,2 ,... ,255]]
I La couleur de chaque pixel est codée sur un octet (c’est-à-dire 8 bits donc 28 = 256 octets possibles), et
représente donc une nuance de gris parmi 256 possibles. On appelle cette valeur la luminosité du pixel :
• la valeur 0 code la couleur noire ,
• la valeur 255 code la couleur blanche ,
• les valeurs intermédiaires codent des nuances de gris de plus en plus claires à mesure que la valeur
augmente.
I Un pixel est donc un entier accessible via la commande Img[i][j] (i-ème ligne et j-ème colonne).
IMAGES EN COULEUR (Non exigibles ! )

I Pour les images en couleur, on les code également par une matrice de pixels comme celles en niveaux de gris.
I Dans une image couleur, on associe à chaque pixel un triplet de 3 couleurs : rouge, vert, bleu.
Chacune des 3 couleurs est donnée par un entier entre 0 et 255 (qu’on représente chacun sur un octet).
I Ce codage s’appelle RGB pour Red Green Blue et où pour chacune de ces couleurs :
• la valeur 0 indique qu’on met 0% du « pot de cette couleur ».
• la valeur 255 indique qu’on met 100% du « pot de cette couleur ».
Chaque pixel est donc représenté par un triplet d’octets codant un entier entre 0 et 255.
Voici quelques exemples pour bien comprendre le codage des couleurs :

couleur R G B Octet 1 Octet 2 Octet 3
noir 0 0 0 0000 0000 0000 0000 0000 0000
blanc 255 255 255 1111 1111 1111 1111 1111 1111
rouge 255 0 0 1111 1111 0000 0000 0000 0000
vert 0 255 0 0000 0000 1111 1111 0000 0000
bleu 0 0 255 0000 0000 0000 0000 1111 1111
violet 132 122 191 1000 0100 0111 1010 1011 1111
I Les images couleur sont donc stockées sous la forme d’un tableau image à trois dimensions.
I Chaque valeur de couleur associée au pixel correspond au triplet d’octets stocké dans image[i][j].
(pixel en RGB : [image[x][y][0] = Red, image[x][y][1] = Green, image[x][y][2] = Blue])

QUELQUES EXEMPLES D’ALGORITHMES DE MODIFICATION D’IMAGE
Ces algorithmes ne sont pas à apprendre par cœur mais sont classiques lors de la manipulation d’image.
1 def dim ( Img ):
I Récupérer la résolution de l’image
2 return ( len ( Img [0]) , len ( Img ))
I Appliquer un effet de seuil

1 def noir_et_blanc ( image , s ):
I Négatif d’une image en niveau de gris
2 w , h = dim ( image )
1 def inversion ( image ): 3 for y in range ( h ):
2 w , h = dim ( image ) 4 for x in range ( w ):
3 for y in range ( h ): 5 p = image [ y ][ x ]
4 for x in range ( w ): 6 if p <= s :
5 image [ y ][ x ]=255 - image [ y ][ x ] 7 image [ y ][ x ]=0
6 return image 8 else :
9 image [ y ][ x ]=255
10 return image
I Éclaircir une image en niveaux de gris

I Assombrir une image en niveaux de gris 1 def eclaircir ( image ):
1 def assombrir ( image ): 2 w , h = dim ( image )
2 w , h = dim ( image ) 3 for x in range ( w ):
3 for x in range ( w ): 4 for y in range ( h ):
4 for y in range ( h ): 5 if image [ y ][ x ]*2 <256:
5 image [ y ][ x ]= image [ y ][ x ]//2 6 image [ y ][ x ]= image [ y ][ x ]*2
6 return image 7 else :
8 image [ y ][ x ]=255
9 return image
I Enlever le rouge sur une image couleur

I Effet miroir horizontal sur une image
1 def no_rouge ( image ):
1 def flip ( M ):
2 w , h = dim ( image )
2 w , h = len ( M [0]) , len ( M )
3 for x in range ( w ):
3 for i in range ( h ):
4 for y in range ( h ):
4 for j in range ( w //2):
5 R ,G , B = image [ y ][ x ]
5 M [ i ][ j ] , M [ i ][ w -1 - j ]= M [ i ][ w -1 - j ] , M [ i ][ j ]
6 image [ y ][ x ]=[0 , G , B ]
6 return image
7 return image
I Détecter les concours sur une image N&B

I Faire tourner une image de 90◦
1 def energie ( M ):
1 def rotate ( image ):
2 w , h = len ( M [0]) , len ( M )
2 w , h = len ( image [0]) , len ( image )
3 e = [[0 for j in range ( w )] for i in
3 image2 =[[0 for j in range ( h )] for i in
4 range ( h )]
4 range ( w )]
5 for i in range (1 ,h -1):
5 for i in range ( h ):
6 for j in range (1 ,w -1):
6 for j in range ( w ):
7 vx = ( M [ i +1][ j ] - M [i -1][ j ])//2
7 image2 [ j ][ i ]= image [ i ][ w -1 - j ]
8 vy = ( M [ i ][ j +1] - M [ i ][ j -1])//2
8 image = image2
9 e [ i ][ j ] = ( abs ( vx )+ abs ( vy ))
9 return image
10 return e

REPRÉSENTATION DE NOMBRES
ENTIERS NATURELS
ENTIERS RELATIFS
NOMBRES RÉELS

MÉTHODE DE PROGRAMMATION
La signature est l’ensemble des paramètres (avec leurs noms, positions, valeurs par défaut et annotations),
ainsi que l’annotation de retour d’une fonction. (informations décrites à droite du nom de fonction.)
Exemple. Voici une même fonction mais dont les types des variables ont été modifiées dans les spécifications.
Spécification 1 : Spécification 2 :
1 def addition ( a : int , b : int ) -> int : 1 def addition ( a : list , b : list ) -> list :
2 return a + b 2 return a + b
La signature des deux fonctions ci-dessus sont (a:int, b:int) -> int et (a:list, b:list) -> list.
Cela ne gêne en rien l’exécution de la fonction si les variables entrées ne sont pas du bon type.
Les annotations sont des commentaires permettant d’expliquer la démarche/logique du code écrit et
rappelant le but du script écrit dans le but d’être bien compris par une personne extérieur.
Placé en tête d’une fonction, l’annotation sert à décrire l’usage de la fonction (accessible avec la commande
help).
Exemple. Voici une même fonction mais dont les types des variables ont été précisés dans les annotation.
Sans annotation : Avec annotation
1 def addition (a , b ): 1 def addition (a , b ):
2 return a + b 2 " Return the sum of the two numbers ‘a ‘ and ‘b ‘ "
3 return a + b
La commande help(addition) renverra alors le texte Return the sum of the two numbers ‘a‘ and ‘b‘.
La commande d’annotation assert est l’un des outils qui peuvent permettre de détecter en cours d’exé-
cution d’un code des erreurs qui conduiraient à un mauvais résultat via un test à réaliser.
Cela permet détecter les erreurs et de sortir de la fonction en indiquant quel type d’erreur a été commis.
Exemple.
1 def f ( L ): La commande f([1,2,3]) renvoie 1

2 print ( L [0]) mais la commande f([]) renvoie
IndexError: list index out of range
Lorsque la liste est vide, il y a une erreur. On peut faire en sorte de vérifier si la liste est vide avant d’appeler
L[0] et de renvoyer un message souhaité si elle est vide, ce qui arrêtera l’exécution du code.
1 assert booleen , " message si False "
On modifie alors la fonction et le message d’erreur renvoyé est celui de l’échec du test de assert :
1 def f ( L ): La commande f([1,2,3]) renvoie 1

2 assert type ( L )== list , " Pas une liste " la commande f([]) renvoie maintenant
3 assert len ( L ) >0 , " Liste vide " AssertionError: Liste vide et la commande
4 print ( L [0]) f(3) renvoie maintenant
AssertionError: L n’est pas une liste

TERMINAISON ET CORRECTION

• La correction est partielle quand le résultat est correct lorsque l’algorithme s’arrête, la correction est totale si
elle est partielle et si l’algorithme termine.
• On montre sur plusieurs exemples que la terminaison peut se démontrer à l’aide d’un variant de boucle.
• Sur plusieurs exemples, on explicite, sans insister sur aucun formalisme, des invariants de boucles en vue de
montrer la correction des algorithmes.
To be completed...

COMPLEXITÉ

• On aborde la notion de complexité temporelle dans le pire cas en ordre de grandeur.
• On peut, sur des exemples, aborder la notion de complexité en espace.
QUELQUES ORDRES DE GRANDEUR

Le tableau suivant présente le n maximal tel qu’un algorithme nécessitant f (n) opérations élémentaires pour
s’exécuter sur l’entrée n en moins d’une minute (en supposant 109 opérations élémentaires par seconde).
√
f (n) ln(n) n n n2 n3 2n n! nn
nmax très très gros 3, 6 × 1021 6 × 1010 244948 3914 35 13 10
Voici le temps d’exécution pour un problème de taille n = 106 sur un ordinateur à 109 opérations par seconde :
O(1) Temps constant 1 ns Le temps d’exécution ne dépend pas des données traitées, ce qui est
assez rare !
O(ln(n)) Logarithmique 1 µs En pratique, cela correspond à une exécution quasi instantanée. Bien
souvent, pour des algorithmes dichotomiques c’est log2 (n) que l’ont
voit apparaı̂tre.
O(n) Linéaire 1 ms Le temps d’un tel algorithme ne devient supérieur à 1 min que pour
des données de taille comparable à celle des mémoires vives actuelles.
O(n ln(n)) Quasi-linéaire 10 ms Le temps d’exécution est légèrement supérieur au cas linéaire.
O(n2 ) Quadratique 1/4h Cette complexité est acceptable pour n < 100 mais pas au delà.
O(nk ) Polynômial 30 ans Il n’est pas rare de voir des complexités en O(n3 ) ou O(n4 ).
O(2n ) Exponentielle 1030000 Un algorithme de telle complexité est impraticable, sauf pour des
ans données très petites.
DÉFINITION ET NOTATIONS DE LANDAU

I La complexité est la mesure de l’efficacité d’un programme pour un type de ressources :
• complexité temporelle : temps de calcul CPU (processeur) : nombre d’opérations élémentaires
réalisés par le processeur, ce qui est lié directement au temps de calcul.
• complexité spatiale : espace mémoire nécessaire : mémoire RAM ou sur disque dur ...
I La complexité temporelle asymptotique est l’étude de l’ordre de grandeur de la complexité pour des
entrées de grande taille « dans le pire des cas » (lorsque la variable entrée nécessite le maximum d’opérations
dans chaque étape de l’algorithme).
Remarque. En pratique, la complexité temporelle est plus importante que la complexité spatiale.
I On exprime la complexité en fonction de n, la taille de l’entrée (longueur de la liste, de la chaı̂ne de
caractères, de l’entier lui-même ou bien du nombre de chiffres de l’entier entré).
I Les notations de Landau (O(ln(n)), O(n), O(nk ) où k ∈ N, O(2n )) sont les mieux adaptées pour l’exprimer.
I On note C(n) la complexité d’un algorithme (nombre d’opérations élémentaires effectuées dans l’algorithme).

COMPLEXITÉ DES COMMANDES DE BASE

I Toute ligne de code écrite comporte des commandes élémentaires et chaque commande a sa propre complexité.
I En général, leur exécution coûte O(1) en complexité. (pas toutes : voir ci-après pour les listes)
Opérations syntaxe Complexité

d’affectation a=2 O(1)
sur les entiers +,-,*,//,% O(1)
sur les flottants +,-,*,/,** O(1)
sur les booléens not,or,and O(1)
de comparaison ==,!=,<,>,<=,>= O(1)
d’affichage print() O(1)
Remarque. Ce n’est pas parce que la syntaxe d’une instruction est courte qu’elle a une complexité en O(1) ! ! !
Remarque. Pour de très grands entiers n, le temps d’exécution de *,//,% est légèrement plus élevé que +,-.
Néanmoins dans la pratique on ne compte qu’une « opération » pour chacune de ces commandes.
Remarque. De même, le temps d’exécution de ** sur les flottants est plus élevé que celui des autres opérations
(mais raisonnable grâce à l’algorithme d’exponentiation rapide).
I Cas particulier des commandes sur les listes

En Python, il est tout à fait possible faire des opérations sur tout une liste L à l’aide d’un seule commande. Il
faut avoir à l’esprit que ce ne sont pas des opérations élémentaires (elles ont chacune leur propre complexité),
et certaines cachent un travail important pour le processeur !
Opération Exemple Complexité
Accès direct L[5] O(1)
Affectation L[-1]=10 O(1)
Longueur len(L) O(1)
Ajout en fin de liste L.append(3.14) O(1)
Suppression en fin de liste L.pop() O(1)
Suppression d’un élément L.pop(7) O(n) (commande hors-programme)
Concaténation L1+L2 O(n1 + n2 ) (longueurs des deux listes)
Concaténation (bis) L+[x] O(n) où n = len(L)
Extraction de tranche L[1:100] O(n), où n = longueur de la tranche.
Copie profonde M=L[:] ou M=L.copy() O(n), où n = len(L).
Répétition [0]*n O(n)
Création par compréhension [k**2 for k in range(n)] O(n) si l’expression est évaluée en temps constant
Recherche de x dans L x in L O(n), où n est la longueur de la liste créée.
Recherche de x dans D x in D O(1), où D est un dictionnaire.
Remarque.
I On préfèrera donc L.append(x) à L+=[x] et on évitera d’utiliser L.pop(i) alors que L.pop() on peut.
I Idem pour les tranches, ou les copies de listes, on évite si on peut faire autrement.
(Dans les algorithmes de tri par exemple.)
I Les commandes analogues sur les chaı̂nes de caractères ou dictionnaires ont la même complexité.
Attention à l’exception de la commande x in D de complexité O(1) grâce aux fonctions de hachages (voir cours
de PSI).

COMPLEXITÉ SPATIALE
I C’est la mesure de l’espace mémoire maximal occupé durant l’exécution de l’algorithme.
I On définit l’unité d’espace mémoire comme la taille d’une structure de données particulières.
I On mesure la complexité en espace par le nombre n d’unités de mémoire occupées lors de l’exécution de
l’algorithme.
Tableau de nombres de longueur Unité d’espace mémoire Espace mémoire occupé par le tableau
n taille d’un entier/flottant O(n)
5n taille d’un entier/flottant O(n)
m×n taille d’un flottant/flottant O(n × m)
Exemple. Une image en 4K est une image rectangulaire de 4000 pixels sur 8000 pixel. Chaque pixel a un code
RGB stocké sur un triplet d’entiers entre 0 et 255.
La complexité spatiale de cette image (en bits) est : 4000 × 8000 × 3 × 8 = 7, 68 × 108 bits.
La complexité spatiale de cette image (en Mo) est : 4000 × 8000 × 3 : 106 = 7, 68 × 108 = 96 Mo.
EXEMPLES AVEC ALGORITHMES ITÉRATIFS
• Un premier exemple montrant 4 façons de calculer la même quantité avec différentes complexités :
Calcul mathématique Code Python Complexité
n × 2 × (1 + n) × n 1 n = 100
Sn = Res = n *2*(1+ n )* n /2 O(1)
2 2
Sn = n2 (n + 1) 3 print ( Res )
n
X
Sn = 2×n×i
1 Res = 0
i=1
n
X 2 n = 100
Sn = 2n × i 3 for i in range (1 , n +1): O(n)
i=1 4 # Somme des termes de 1 à n
n(n + 1) 5 Res = Res + 2* n * i
Sn = 2n × 6 print ( Res )
2
Sn = n2 (n + 1)
Xn X n
Sn = (i + j)
i=1 j=1 1 Res = 0
n X
n n X
n
X X 2 n = 100
Sn = i+ j 3 for i in range (1 , n +1):
i=1 j=1 i=1 j=1 4 # Somme des termes de 1 à n O(n2 )
n n
X X n(n + 1) 5 for j in range (1 , n +1):
Sn = n×i+ 6 Res = Res + i + j
2
i=1 i=1 7 print ( Res )
Sn = n × n(n+1)
2 +n× n(n+1)
2
Sn = n2 (n + 1)
1 Res = 0
n n
X X 2 n = 100
Sn = n×i+ n×j 3 for i in range (1 , n +1):
i=1 j=1 4 Res += n * i O(n)
Sn = n × n(n+1)
2 +n× n(n+1)
2
5 for j in range (1 , n +1):
Sn = n2 (n + 1) 6 Res += n * j
7 print ( Res )

EXEMPLES AVEC ALGORITHMES RÉCURSIFS

(
un + 1 si un < 1
• Voici un exemple simple : u0 = 1 et ∀n > 1, un+1 = un .
sinon
2
Code Python Complexité de l’algorithme
1 def rec ( n ):
2 if n ==0: Soit C(n) la complexité de rec à l’appel n :
3 return 1
4 else : C(0) = 1
5 U = rec (n -1) C(n + 1) = C(n) + 5
6 if U < 1:
(Suite arithmétique)
7 U = U + 1
8 else : C(n) = 5n + 1
9 U = U / 2 ⇒ Complexité linéaire en O(n)
10 return U
1 def rec ( n ):
2 if n ==0: Soit C(n) la complexité de rec à l’appel n :
3 return 1
4 else : C(0) = 1
5 if rec (n -1) < 1: C(n + 1) = 2C(n) + 5
6 U = rec (n -1) + 1 (Suite arithmético-géométrique)
7 else : C(n) + 5 = 2n (C(0) + 5) ⇔ C(n) = 6 × 2n + 5
8 U = rec (n -1) / 2 ⇒ Complexité exponentielle en O(2n )
9 return U
Remarque.
I Tout commande compte pour une ou plusieurs « opération(s) » (même l’affectation =).
I Le but n’est pas d’évaluer exactement le nombre d’opérations mais de savoir si celui-ci est en O(1), O(ln(n)),
O(n), O(n2 ), ou O(2n ).
I Pour les algorithme récursifs, l’idée est surtout de savoir combien de fois ils font appel à eux-même à l’étape
précédente mais aussi combien d’opérations sont faites entre deux appels successifs.
EXEMPLES AVEC ALGORITHMES DICHOTOMIQUES

• Voici un exemple avec l’algorithme d’exponentiation rapide. On évalue la complexité à l’étape 2n (et pas n).
Code Python Complexité de l’algorithme
1 def Quick_exp (a , n ): Soit C(2n ) la complexité de rec à l’appel 2n :
2 if n ==1:
3 return a C(0) = 1
4 if n %2==0: C(2n+1 )
= C(2n ) + 7
5 y = Quick_exp (a , n //2) (Suite arithmétique)
6 return y * y
7 else :
C(2n ) = 7n + 1
8 y = Quick_exp (a ,( n -1)//2) C(n) = 7 log2 (n) + 1
9 return y * y * a ⇒ Complexité logarithmique en O(ln(n))
Remarque.
I L’idée est compter ici le nombre total d’appels p à la fonction en fonction de n.
n
I L’algorithme s’appelle jusqu’à ce que 2p ≈ 1 soit p ≈ log2 (n) donc la complexité est en O(ln(n)).

GRAPHES : GÉNÉRALITÉS
LES TYPES DE GRAPHES

I Graphes non orientés
• Un graphe non orienté d’ordre n noté G est un ensemble de n
points ou sommets, reliés entre eux ou non par des lignes appelées
arêtes.
• L’ ordre d’un graphe est donc son nombre de sommets.
• On note souvent G = (S, A) où S est la liste des sommets et A
la liste des arêtes.
Graphe orienté Graphe non orienté
• Les sommets peuvent avoir des noms, être numérotés, etc...
I Graphes orientés
• Un graphe orienté d’ordre n noté G est un
ensemble de n points ou sommets, reliés entre
eux ou non par des flèches appelées arc.
• Un sommet peut être relié à lui-même par une
boucle.
• Un graphe sans boucle est appelé graphe simple.
• Le même graphe admet une infinité de représen-
Trois représentations d’un même graphe
tations.
• Les arcs sont donc des arêtes orientées.
I Graphes pondérés
Un graphe pondéré est un graphe, orienté ou non, pour
lequel chaque arête possède un poids.
Remarque.
• Généralement le poids est un nombre réel positif ou nul.
• On peut mettre le poids à 0 pour signifier que deux sommets
ne sont pas reliés.
• Le poids peut représenter le temps de parcours entre deux
sommets, le prix du parcours... Un exemple de graphe pondéré
LEXIQUE DES GRAPHES

• ordre d’un graphe est le nombre de sommets de ce graphe.
• Un sommet B est adjacent à sommet A, ou B est un voisin de A lorsque que A est relié à B par une
arête/un arc.
• Un sommet qui n’est adjacent à aucun autre est dit isolé.
Exemple. Trois voisinages différents dans des graphes orientés ou non

• Le degré d(s) d’un sommet s est est le nombre d’arêtes/d’arcs (quel que soit leur sens) auxquels il est relié
(une boucle compte deux fois).
Pour un graphe orienté, on définit le degré entrant et le degré sortant.
− On note d− (s) le degré entrant du sommet s : nombre d’arcs ayant s comme extrémité finale.
− On note d+ (s) le degré sortant du sommet s : nombre d’arcs ayant s comme extrémité initiale.
− Le degré du sommet s est donc d(s) = d+ (s) + d− (s)
Dans un graphe, la somme des degrés de chaque sommet est égale au double du nombre d’arêtes.
• Un graphe est complet lorsque toutes les sommets sont deux à deux adjacentes entre eux.
• Dans un graphe non orienté, une chaine de longueur n est une séquence finie de sommets reliés entre eux
par n arêtes. (L’extrémité de chacune est l’origine de la suivante, sauf pour la dernière.)
• Dans un graphe orienté, on parle de chemin et il suit le sens des flèches.
• Un chemin ou une chaı̂ne est qualifié de simple s’il n’emprunte pas deux fois la même arête.
• Un chemin est élémentaire s’il ne passe pas deux fois par le même sommet.
• Si une chaı̂ne/un chemin possède le même sommet de départ et d’arrivée, on dit qu’elle/il est fermé(e).
• Un chemin simple fermé s’appelle une cycle/circuit.
• Pour un graphe pondéré, la longueur/poids d’un(e) chaı̂ne/chemin est la somme des poids qui la compose.
• La distance entre deux sommets d’un graphe est la longueur du chemin/circuit le plus court (s’il y en a un)
reliant ces deux sommets.
• Un graphe non orienté est connexe s’il existe une chaı̂ne entre chaque paire de sommets distincts.
• Pour les graphes orientés on parle de : (mais il semble que ce n’est pas au programme)
− graphe orienté connexe si le graphe non orienté associé est connexe (graphe obtenu en ne tenant pas
compte du sens des arêtes).
− graphe orienté fortement connexe si pour toute paire (A, B) de sommets, il existe un chemin de A
vers B et un chemin de B vers A.
Exemple. Soit G le graphe ci-contre.
• G est non orienté d’ordre 64.
• Le sommet 3 est isolé.
• Le sommet 11 est de degré 3.
• 1 − 9 − 10 − 11 − 19 − 20 − 28 − 29 est une chaine
de longueur 7.
• 54 − 55 − 56 − 64 − 63 − 62 − 54 est un cycle.
• 1 − 2 − 10 − 9 − 1 − 2 − 10 − 9 − 1 n’est pas un
cycle.
• La distance entre 1 et 8 est de 11
• G n’est pas connexe.
• G admet 8 composantes connexes.
(On dit que deux sommets sont dans la même
« composante connexe » lorsqu’il existe un chemin
reliant ses deux sommets.
Le graphe est ainsi séparé en un certain nombre
de composantes connexes distinctes.)

MODÉLISATION DES GRAPHES

I Théorique
Soit S = {s1 , . . . , sn } l’ensemble des sommets d’un graphe G. On appelle A l’ensemble :
— Des arêtes d’un graphe non orienté tel que A = {{si , sj }, si ∈ S, sj ∈ S}
— Des arcs d’un graphe orienté tel que A = {(si , sj ), si ∈ S, sj ∈ S}
On note G = (S, A) le graphe composé de ces sommets et arêtes/arcs.
On note G = (S, A, ω) un graphe pondéré tel que chaque arc/arête a un poids ω(si , sj ).
Remarque.
• On a besoin d’une liste de noms de sommets et d’une liste des arêtes/arcs/sommets voisins.
• Notez que pour {si , sj } (arête) l’ordre ne compte pas alors que pour (si , sj ) (arc) l’ordre compte.
Représentation de G Matrice d’adjacence : Dictionnaire d’adjacence :

1 G = [ 1 G = {
2 [0 ,1 ,0 ,1] , 2 ’A ’: [ ’B ’ , ’D ’] ,
3 [0 ,0 ,0 ,1] , 3 ’B ’: [ ’D ’] ,
4 [0 ,1 ,0 ,0] , 4 ’C ’: [ ’B ’] ,
5 [0 ,1 ,1 ,0] 5 ’D ’: [ ’B ’ , ’C ’]
6 ] 6 }
I Matrice d’adjacence
Soit un graphe de n sommets, d’indices 0, . . . , n − 1.
• La matrice d’adjacence de ce graphe est un tableau G à deux dimensions, de taille n × n, contenant des
booléens G[i][j] (0 ou 1) indiquant si il y a adjacence entre les sommets d’indices i et j.
(Attention : G[i][j] pour un arc de i vers j : i → j et G[j][i] pour un arc de j vers i : j → i)
• Pour les graphes pondérés, on parle de matrice des distances, où le coefficient G[i][j] vaut le poids de
l’arête/arc reliant le somme si au sommet sj .
Remarque. Inconvénient de la matrice d’adjacence :

• La dimension de la matrice est égale à n × n, ce qui peut représenter un important espace en mémoire.
• Pour obtenir les voisins d’un sommet, il faut une utiliser une fonction de coût d’ordre O(n).
• Il faut stocker la correspondance noms/indice des sommets dans un dictionnaire à part.
Le graphe G peut être alors définit par le couple (D,M) où D est le dictionnaire des noms des sommets et M la
matrice adjacence.
I Dictionnaire d’adjacence
Soit un graphe de n sommets ayant des noms distincts.
Le dictionnaire d’adjacence de ce graphe est un dictionnaire où chaque élément est un sommet et la clef
associée est la liste des sommets adjacents à celui-ci.
Remarque.
• On n’a pas besoin de stocker les noms des sommets dans un dictionnaire à part.
• S’il y a peu d’arête, la taille du dictionnaire est bien inférieur à celle de la matrice d’adjacence.
• Pour un graphe pondéré le dictionnaire d’adjacence est un dictionnaire où chaque élément est un sommet
et la clef associée est la liste des sommets adjacents à celui-ci couplé avec le poids de l’arête correspondante.

ALGORITHMES CLASSIQUES SUR LES GRAPHES
I Ordre d’un graphe (matrice) I Ordre d’un graphe (dictionnaire)

1 def Ordre ( G ): 1 def Ordre ( G ):
2 return len ( G ) 2 return len ( G )
I Degré sortant d’un sommet (matrice)

I Degré sortant d’un sommet (dictionnaire)
1 def dplus (G , s ):
1 def dplus (G , s ):
2 dp =0
2 return len ( G [ s ])
3 for j in range ( Ordre ( G )):
4 if G [ s ][ j ]!=0:
5 dp +=1 Remarque.
6 return dp C’est aussi le degré si le graphe n’est pas orienté.
I Degré entrant d’un sommet (matrice) I Degré entrant d’un sommet (dictionnaire)
1 def dmoins (G , s ): 1 def dmoins (G , s ):
2 dm =0 2 dm =0
3 for i in range ( Ordre ( G )): 3 for g in G :
4 if G [ i ][ s ]!=0: 4 if s in G [ g ]:
5 dm +=1 5 dm +=1
6 return dm 6 return dm
I Voisins d’un sommet (matrice)

1 def Voisins (G , s ):
I Voisins d’un sommet (dictionnaire)
2 V =[]
3 for j in range ( len ( L )): 1 def Voisins (G , s ):
4 if G [ s ][ j ]!=0: 2 return G [ s ]
5 V . append ( j )
6 return V

GRAPHES : PARCOURS DE GRAPHES
GRAPHES : PARCOURS EN LARGEUR

I Principe
• Dans le parcours en largeur, on visite les sommets en « cercle concentriques » autour du sommet de départ.
• Le principe peut se décrire ainsi : Les frères avant les fils, une génération après l’autre.
I Exemple
• Début : Sommet A (père). Parcours :
fils de A : B et D (distance 1) A
• fils de B : C (distance 2) A−B−D
fils de D : E (distance 2) A−B−D−C
• fils de C : F (distance 3) A−B−D−C −E
fils de E : F déjà parcouru. A−B−D−C −E−F
• G n’est pas atteignable.
I File et format deque

La liste des sommets à visiter ressemble une file d’attente. On va donc utiliser le concept de file où c’est le
premier élément (celui qui a été inscrit en premier dans la liste) qui va être traité d’abord. Il y a deux opérations :
— mettre un élément dans la file (en dernier donc) : « enfiler » avec L.append(x)
— supprimer un élément de la file (le premier donc) : « défiler » avec L.pop(0)
Selon le programme officiel, aucune connaissance n’est théoriquement exigible sur les files et les modules
nécessaires. Néanmoins il faut avoir souligné l’utilité de tels objets pour le parcours de graphes (en largeur).
Importer le module from collections import deque

Créer une file file=deque([’A’,’B’,’D’])
Enfiler file.append(’F’)
Défiler le premier arrivé file.popleft()
Remarque.
• L’essentiel est de comprendre que la variable file créé avec la commande deque se gère comme une liste sauf
que la commande file.popleft() a une complexité en O(1) tandis que celle de L.pop(0) est en O(len(L)).
• Il existe également des commandes pour enfiler à gauche ou défiler.
I Algorithme itératif
1 def Parcours_Largeur (G , S ) - > list :

• G est la matrice d’adjacente et S l’in- 2 """ Parcours en largeur itératif avec file """
dice/le nom du sommet de départ. 3 Vu =[]
4 file =[ S ] # ou file = deque ([])
• Vu est la liste des sommets vus. 5 while len ( file )!=0:
• file est la liste d’attente des som- 6 s = file . pop (0) # ou s = file . popleft ()
mets à voir. 7 if s not in Vu :
8 Vu . append ( s )
• Voisins(G,s) est une fonction qui 9 for v in Voisins (G , s ):
renvoie la liste des sommets voisins de 10 if v not in Vu :
s dans le graphe G. 11 file . append ( v )
12 return Vu

GRAPHES : PARCOURS EN PROFONDEUR

I Principe
• Le parcours en profondeur d’un graphe à partir d’un sommet consiste à suivre les arêtes arbitrairement,
en marquant les sommets déjà visités pour ne pas les visiter à nouveau.
• La descendance avant les frères. On avance le plus possible et on recule quand on est bloqué. On remonte
alors au premier ancêtre qui a un fils qui n’a pas été visité.
I Exemple
• Début : Sommet A (père).
Fils de A : B et D dans cet ordre.
• Fils de B : C
• Fils de C : E et F dans cet ordre.
• Fils de E non vus : ∅ ⇒ bloqué ⇒ remonte à C.
Second fils de C : F
• Fils de F non vu : ∅ ⇒ bloqué ⇒ remonte à A.
Second fils de A : D.
• Fils de D non vu : on remonte à A.
• Fils de A non vus : ∅ ⇒ on a fini ! Parcours de G à partir de A : [A,B,C,E,F,D].
I Algorithme récursif
• G est la matrice d’adjacente.
• S est l’indice/le nom du sommet de départ. 1 def Parcou rs_Prof ondeur (G ,S , Vu : list ) - > list :
• Vu est la liste des sommets vus. 2 """ Parcours en profondeur récursif """
• Voisins(G,S) est une fonction qui renvoie la 3 if S not in Vu :
liste des sommets voisins de s dans le graphe G. 4 Vu . append ( S )
5 for v in Voisins (G , S ):
Remarque. 6 if v not in Vu :
• La liste initiale Vu=[] est modifiée par effet de 7 Parc ours_Pr ofondeu r (G ,v , Vu )
bord à chaque appel de Parcours_Profondeur. 8
• On atteint vite la limite de la récursivité (pro- 9 Vu =[]

fondeur maximale de récursivité en Python). 10 Parc ours_Pr ofondeur (G , ’A ’ , Vu )
11 print ( Vu )
• Il existe une fonction alternative itérative, à
l’aide d’une pile.
I Pile et format deque
Une pile est un concept informatique basée sur le principe « dernier arrivé, premier sorti ». Pour le parcours en
profondeur, à chaque fois qu’on ait à un sommet que l’on visite pour la première fois, on rajoute à la pile tous
ses voisins non encore visitée et on continue tant que la pile n’est pas vide. Il faut donc savoir créer une pile et
— rajouter un élément en haut de la pile : « empiler » avec L.append(x)
— enlever le dernier élément de la pile : « dépiler » avec L.pop()
Selon le programme officiel, aucune connaissance n’est théoriquement exigible sur les piles et les modules né-
cessaires. Néanmoins il faut avoir souligné l’utilité de tels objets pour le parcours de graphes (en profondeur).
Remarque.
• La syntaxe des piles est la même que celle
Importer le module from collections import deque
des listes (sauf création avec deque.
Créer une pile pile=deque([’A’,’B’,’D’])
• Les piles sont des structures facile à gérer
Empiler pile.append(’F’)
mais très pauvre et toute manipulation éla-
Dépiler le dernier arrivé pile.pop()
borée nécessitera énormément d’empilages et
de dépilages.

I Algorithme itératif
1 def Parcou rs_Prof ondeur (G , S ) - > list :

• pile est la pile/liste des sommets à visiter. 2 """ parcours en profondeur avec pile """
Tant que la pile n’est pas vide, 3 Vu =[]
4 pile =[ S ] # ou pile = deque ([ S ])
— on dépile le dernier sommet de la file, 5 while len ( pile )!=0:
— si jamais ce sommet n’a pas été visité on 6 s = pile . pop ()
l’ajoute à la liste des sommets visités, 7 if s not in Vu :
8 Vu . append ( s )
— puis on fait la liste de ses voisins, 9 for v in Voisins (G , s ):
— enfin on ajoute à la pile ceux que l’on a pas 10 if v not in Vu :
encore visité. 11 pile . append ( v )
12 return Vu
Remarque.
• Cet algorithme ne renvoie pas exactement le même parcours en profondeur que la version récursive : en effet
dans la boucle for v in Voisins(G,s), l’instruction pile.append(v) ajoute les sommets par ordre croissant
d’indice, alors que les appels récursifs les ajoute par ordre décroissant.
• Au final cela ne change pas grand chose : on a quand même parcouru le graphe en profondeur...

GRAPHES : PLUS COURT CHEMIN
ALGORITHME DE DIJKSTRA
I Un graphe pondéré G est un graphe dont les arêtes

ont été affectées d’un nombre appelé poids.
I La longueur d’un chemin devient la somme des poids
de chacun des arcs/arêtes qui le constituent.
I La distance entre 2 sommets est la longueur du (de la)
plus court(e) chemin (chaine) les reliant.
Exemple : La longueur du chemin A − E − F − G est :
` = 14 + 19 + 4 = 37.
Graphe pondéré
I Principe de l’algorithme de Dijkstra (graphes simples et poids des arcs positifs).
• Initialisation : À chaque sommet on attribue un poids ∞ (pas atteints) et 0 pour le sommet de départ.
• Si le plus court chemin reliant le sommet de départ s0 à un autre sommet S passe par les sommets s1 , s2 ,
. . ., sk alors, les différentes étapes sont aussi les plus courts chemins reliant s0 à ces sommets.
• À chaque étape, on choisit un sommet sk du graphe parmi ceux qui n’ont pas encore été atteints tel que
la longueur connue provisoirement du plus court chemin allant de s0 à sk soit la plus courte possible.
Algorithme de Dijkstra partant du sommet A en notant les prédécesseurs.

A B C D E F G H Sommets sélectionnés
0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ A (0)
7 (A) ∞ ∞ 14 (A) ∞ ∞ ∞ B (7)
15 (B) ∞ 14 (A) ∞ ∞ ∞ E (14)
15 (B) ∞ 33 (E) ∞ ∞ C (15)
21 (C) 33 (E) ∞ ∞ D (21)
32 (D) ∞ ∞ F (32)
36 (F ) 45 (F ) G (36)
44 (G) H (44)
I Lecture inverse du plus court chemin entre A et H : H − G − F − D − C − B − A
Initialisation : 1 def Dijkstra ( G : list , S : int ) - > tuple :

• Dictionnaire D avec poids ∞ pour les sommets. 2 import numpy as np
3 d ={ k : np . inf for k in range ( len ( G ))}
Poids de 0 pour le sommet initial.
4 d [ S ]=0
• la liste des sommets traités Vu=[]. 5 P , Vu ={} ,[]
Itération : Tant qu’il reste des sommets à voir, 6 while len ( Vu ) < len ( G ):
• Sélection d’un nouveau sommet S de poids mi- 7 m = np . inf
8 for k in d :
nimum non vu et ajout de S à Vu
9 if d [ k ] < m and k not in Vu :
• Création de la liste des voisins v de S, 10 m,S=d[k],k
• pour chaque voisin v pas encore traité, 11 Vu . append ( S )
si d(S, v) > d(S, x) + d(x, v) alors D[v] est ac- 12 Voisins =[ v for v in d if G [ S ][ v ]!=0]
tualisée et S est le prédécesseur de v. 13 for v in Voisins :
14 if v not in Vu and d [ v ] > d [ S ]+ G [ S ][ v ]:
• Fin : Renvoi du dictionnaire D contenant donc 15 d [ v ]= d [ S ]+ G [ S ][ v ]
les distances du sommet initial à chaque sommet 16 P [ v ]= S
et du dictionnaire P des prédécesseurs. 17 return d , P

ALGORITHME A?

Info 11

Transféré par

Droits d'auteur :

Formats disponibles

Info 11

Transféré par

Informations du document

Titre original

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Info 11

Transféré par

Droits d'auteur :

Formats disponibles

FORMULAIRE D’INFORMATIQUE

Classe de PCSI - Année 2022-2023

Python et Spyder : histoire et fonctionnement de l’interface (p.2)

LE LANGAGE DE PROGRAMMATION PYTHON

• L’éditeur sera l’endroit où vous écrirez vos pro-

ATTENTION : Écrire un programme est différent de l’exécuter ! ! !

Fabien DÉLEN [email protected] 2 PCSI 2022-2023

QUELQUES COMMANDES PYTHON

I La commande # sert à écrire des commentaires sur une seule ligne.

I La commande input() permet de demander à l’utilisateur de saisir/définir une variable.

QUELQUES COMMANDES SPYDER COMPLÉMENTAIRES

Dans l’exemple ci-contre, le

Fabien DÉLEN [email protected] 3 PCSI 2022-2023

VARIABLES ET OPÉRATIONS INFORMATIQUES

DÉFINITION D’UNE VARIABLE

LES TYPES DE VARIABLES

LES OPÉRATIONS SUR LES VARIABLES

Fabien DÉLEN [email protected] 4 PCSI 2022-2023

Type de variable Syntaxe Python Description Exemple

Exemple. Voici quelques exemples :

Type de variable Syntaxe Python Description Exemple

Exemple. Voici quelques exemples :

Fabien DÉLEN [email protected] 5 PCSI 2022-2023

Type de variable Syntaxe Python Description Exemple

Exemple. Voici quelques exemples :

Élément par élément Indice par indice

I Tranches dans une liste :

Fabien DÉLEN [email protected] 6 PCSI 2022-2023

I Liste à deux dimensions :

Élément par élément Indice par indice

 Si chaque « élément-liste » a la même longueur on peut alors plutôt parler de « matrice ».

I Copie superficielle et en profondeur :

Fabien DÉLEN [email protected] 7 PCSI 2022-2023

I La commande str(x) transforme le type int,float ou list en type str.

Commande dans l’interpréteur Résultat obtenu

I Parcourir les éléments d’une chaı̂ne :

Fabien DÉLEN [email protected] 8 PCSI 2022-2023

I Commandes utiles pour un dictionnaire :

1 for key in dico : 1 for key in dico :

Tableau Liste Tuple Chaine de caractères Dictionnaire

Fabien DÉLEN [email protected] 9 PCSI 2022-2023

1 age = eval ( input ( " Tu as quel ^

3 if age ==18: # On teste si l ’ age est égal à 18.

 On a besoin d’opérateurs de test pour les conditions, voici les principales :

I L’instruction elif ... :

tion du if n’est pas vérifiée et que 3 if age ==18:

I L’instruction if ... in ...

Fabien DÉLEN [email protected] 10 PCSI 2022-2023

3 if age <18: 3 if age <18:

Fabien DÉLEN [email protected] 11 PCSI 2022-2023

INSTRUCTION ITÉRATIVE for ... in ... :

I L’instruction for k in range(debut,fin,pas):

I L’instruction for k in liste: ou for k in chaine:

INSTRUCTION ITÉRATIVE while ... :

Fabien DÉLEN [email protected] 12 PCSI 2022-2023

1 # 1) Je définis ma fonction . 1 # 2) J ’ exécute la fonction ( entrée = 3).

Fabien DÉLEN [email protected] 13 PCSI 2022-2023

I Détermination du max/min I Détermination de l’indice du max/min

I Nombre d’occurrences d’un élément I Nombre d’occurrences des éléments (dictionnaire)

Si chaque « élément-liste » a la même longueur on peut alors plutôt parler de « matrice ».

On a besoin d’opérateurs de test pour les conditions, voici les principales :