Classes Préparatoires d’entrée dans

les Grandes Ecoles (CPGE)

Algorithmique et Programmation I

Dr Sibiri TIEMOUNOU

Janvier 2021
Année académique 2020-2021

1
Plan du cours

1. Généralités sur l’algorithmique et la programmation

2. Rappel sur les notions de bases

3. Structures de données

4. Procédures et fonctions

5. Algorithme de tri et de recherche

6. Gestion de fichier

2
26/01/2021
Sommaire

 Objectifs de ce cours

 Comprendre les notions de bases en algorithmique et programmation

 Savoir écrire et écrire un algorithme et le traduire en langage Python

 Maîtriser l’utilisation du langage Python pour réaliser la mise en œuvre d’algorithmes et le

développement d’applications de petite taille.

 Evaluation
 Rapport de TP
 Mini projet (en Python)

3
0. Généralités sur l’Algorithmique et la programmation

4
26/01/2021
0.1 Algorithmique

 Définition
 L’algorithmique est un terme d’origine arabe, comme algèbre, amiral ou zénith.

 C’est un mot dérivé du nom du mathématicien « al Khwarizmi » qui a vécu au 9ème

siècle, était membre d’un académie des sciences à Bagdad

 Un algorithme est une suite d’actions à effectuer pour:

 Réaliser un traitement donné

 Résoudre un problème donné

 Un programme est une série d’instructions pouvant s’exécuter en séquence, ou en

parallèle (parallélisme matériels) qui réalise (implémente) un algorithme

5
0.1 Algorithmique

 Exemples d’algorithmes
 Recettes de cuisine

 Résoudre un système d’équations à plusieurs inconnues

6
0.1 Algorithmique

 Formalisation d’un algorithme

Informations
en entrée

Algorithme informatique
=
procédure de calcul

Rigueur scientifique IMPORTANT !

Sinon, information de sortie erronée
Informations
en sortie

7
0.1 Algorithmique

 Les problèmes fondamentaux en algorithmique

 Complexité
 En combien de temps un algorithme va -t-il atteindre le résultat escompté?

 De quel espace a-t-il besoin?

 Calculabilité
 Existe-t-il des tâches pour lesquelles il n'existe aucun algorithme ?

 Etant donnée une tâche, peut-on dire s'il existe un algorithme qui la résolve ?

 Correction
 Peut-on être sûr qu'un algorithme réponde au problème pour lequel il a été conçu ?

8
0.2 Langage de programmation

 Qu’est-ce qu’un langage de programmation?

 Pour communiquer avec quelqu’un, vous devez parler le même langage
 Avec un ordinateur, difficile de communiquer car ne comprenant que des 0 et 1

 Pour communiquer avec un ordinateur, il faut un interpréteur (ou logiciel)

 Charger de transformer un message en 0 et 1

9
26/01/2021
0.2 Langage de programmation

 Qu’est-ce qu’un langage de programmation?

 Un ordinateur obéit aux ordres que nous lui donnons

 Ces ordres s’appellent des instructions

 Un langage est donc une suite d’instructions

 Exemple :
 Affiche « A » à l’écran
 Affiche une zone où l’utilisateur pourra saisir son nom
 Si l’utilisateur clique sur le bouton « fermer », alors le programme se ferme

 Un langage de programmation permet d’écrire toutes ces instructions (aussi appelé

code source) dans un langage de comprise par le traducteur
 Charger de transformer un message en 0 et 1

10
0.3 Type de langages de programmation

 Quels sont les types de langage ?

 Il existe 2 types de langages

 Langages compilés
 Le code écrit par le développeur est d’abord compilé (conversion du code source
en langage machine) avant d’être exécuter

11
0.3 Type de langages de programmation

 Quels sont les types de langage ?

 Il existe 2 types de langages

 Langages interprétés
 Ces langages n’ont pas besoin de compilation. Le code source est lu et traduite
pour être exécuté

12
0.3 Type de langages de programmation

 Liste de quelques langages couramment utilisés

Langages Type
Python Interprété
C++ Compilé
C Compilé
Java Compilé
HTML/CSS Interprété
PHP Interprété
Javascript Interprété
SQL Interprété

13
0.4 Algorithmie et programmation

 Quel lien entre Algorithmique et langage de programmation ?

 L’algorithmique sert à résoudre les problèmes de monde des vivants grâçe à la logique et surtout de mettre en place
un système d’automisation

 L’algorithme est universel pour quasiment tous les langages de programmation

 Un algorithme peut être codé en C, C++, qu’en Python et d’autres langage

 Le langage de programmation sert entre autre à traduire l’algorithme dans le strict respect dudit langage
14
0.5 Présentation du langage Python

 C’est quoi le langage Python ?

 C’est un langage de programmation inventé par Guido Van Rossum
 La 1ère version est apparu en 1991

 C’est un langage de programmation interprété

 Pas nécessaire de compiler avant de l’exécuter

15
0.5 Présentation du langage Python

 C’est quoi le langage Python ?

 Un des langages les plus utilisés au monde

 Elu Meilleur langage en 2020 (source : IEEE : top 10 des meilleurs langages de
programmation de l’année 2020)

16
0.5 Présentation du langage Python

 Quelles sont les caractéristiques du langage Python?

 Langage facile à apprendre, à comprendre et à écrire
 Il n’ y a pas de pointeurs explicites en Python (contrairement aux langages C/C++)

 Langage Orienté Objet

 Supporte l’héritage multiple et la surcharge des opérateurs

 Langage portable
 fonctionne sous de nombreux systèmes d'exploitation
 Linux, MacOS, Windows

 Doté d’une communauté active

 Utile pour résoudre des problèmes de bugs

17
0.5 Présentation du langage Python

 Qui utilise Python ?

18
0.5 Présentation du langage Python

 Que peut-on faire avec Python?

 Programmation des progiciels (ensemble de plusieurs logiciels pouvant fonctionner
ensemble)

 Très utilisé en robotique (technologie Raspbberry)

 Internet des objets (IoT) et Intelligence artificielle (IA)

19
0.5 Présentation du langage Python

 Distribution de Python et bibliographie

 Site officiel : http://www.python.org
 Manuel de références
 Documentation des bibliothèques de fonctions
 Version actuelle : 3.8.2

 Editeurs IDE Python

 PyCharm
 L’un des meilleurs IDE (très complet et gratuit)

 Sublime Text (ou notepad++)

 Editeurs (très complet et gratuit)
 Spyder
 Véritable environnement développement et très intuitif
 Intégré dans le framework « Anaconda »
 Jupyter notebook
 Environnement dédié à la science des données 20
0.5 Présentation du langage Python

 Comment installer Python?

 En téléchargeant la dernière version sur le site officielle « https://www.python.org/downloads/ »

 Avec cette version, on a principalement accès à l’invite de commande « Python’

 Pour télécharger l’IDE « Spyder », il faudra télécharger le framework « Anaconda » en

utilisant le lien suivant : « https://www.anaconda.com/distribution/#download-section »
en veillant à bien sélectionner la version correspondante à votre système d’exploitation

21
0.5 Présentation du langage Python

 Exemple de code Python

 Commentaires multi lignes

""" commentaire
…
"""

 Commentaires sur une ligne

# commentaire

22
0.5 Présentation du langage Python

 Exemple de code Python

 Appel à des libraires prédéfinies

(bibliothèque standard) ou celles
implémentées par l’utilisateur

 Mot clé : import

 from A import B
 A partir de la librairie A
importer la sous libraire (ou
fonctions) B

23
0.5 Présentation du langage Python

 Exemple de code Python

 Utilisation de variable
 Pas besoin de spécifier son type

 Déclaration et initialisation de
tableau

 Appel de fonctions
24
0.5 Présentation du langage Python

 Distribution de Python et bibliographie

 Bibliographies
 Programmation Python, par Tarek Ziadé, Editions Eyrolles, Paris, 2006, 538 p.,
ISBN 978-2-212-11677-9

 Au coeur de Python, volumes 1 et 2, par Wesley J. Chun, traduction de Python core

programming, 2d edition (Prentice Hall) par Marie-Cécile Baland, Anne Bohy et Luc
Carité, Editions CampusPress, Paris, 2007, respectivement 645 et 385 p., ISBN 978-2-
7440-2148-0 et 978-2-7440-2195-4.

 Python : How to program, par Deitel, Liperi & Wiedermann, Prentice Hall, Upper
Saddle River – NJ 07458, 2002, 1300 p., ISBN 0-13-092361-3,

25
0.6 A propos de la programmation

 Programmer, c’est dur ?

Il faut que je sois un

super-méga
matheux
Ouais, ouais,

 Réponses:
 Non, non et non
 un super-niveau en maths n'est pas nécessaire
 La connaissance en maths dépend du type de logiciels (cryptage, jeux 3D, …)

 Tout ce dont vous aurez besoin en Maths

 Savoir effectuer les calculs de base (addition, multiplication, …)
 Notion de logique (Algorithmique)
26
0.6 A propos de la programmation

 Programmer, c’est dur ?

 Les qualités suivantes sont nécessaires pour être un bon programmeur

Patience Sens de la logique Sérénité

• Le programme ne marche • Pas besoin d’être fort en • Non, on ne tape pas son
jamais du premier cours Maths mais besoin de ordinateur avec un marteau
réfléchir

• Il faut savoir persévérer • Ce n’est pas ça qui résoudra

• Trouver l’algorithmie le programme
répondant à un problème
donné • Un peu de sérénité

27
1. Rappel sur les notions de base

28
26/01/2021
1.1 Retour sur l’algorithmique

 Formalisation d’un algorithme

 L’une des représentations la plus utilisée pour formuler un algorithme, le pseudocode ou
pseudo-langage :Langage de Description Algorithmique(LDA)

 Le pseudo-code n’est pas un langage de programmation mais un moyen d’être très proche
de la programmation, sans être noyé sous la syntaxe d’un langage de programmation.

 Etapes de réalisation d’un algorithme

 Préparation du traitement : Données nécessaires à la résolution du problème

 Traitement : Résolution pas à pas et décomposition du problème en sous-problème si

nécessaire

 Editions des résultats : Impression à l’écran, sauvegarde dans un fichier, etc

29
1.1 Retour sur l’algorithmique

 Langage algorithmique

Algorithme NomAlgorithme Algorithme Bonjour

{Ceci est un commentaire} {Il a juste dit bonjour …

Debut mais en anglais}
… Actions Debut
Fin Afficher(« Hello world »)
Fin

 Il faut avoir une écriture rigoureuse

 Il faut avoir une écriture soignée : respecter l’indentation
 Il est nécessaire de commenter les algorithmes
 Il existe plusieurs solutions algorithmiques à un problème posé
 Il faut rechercher l’efficacité de ce que l’on écrit

 L’un des éléments fondamentaux en Algorithmique est la manipulation des des données à l’aide
des variables 30
1.2 Les variables

 Définition
 Lors de l’exécution d’un algorithme, on va avoir besoin de stocker des données, voire des
résultats. Pour cela, on utilise des variables. On attribue un nom à chaque variable.

 Une variable est donc une zone mémoire qui associe un nom à une valeur qui peut
éventuellement varier au cours du temps

 Il peut s’agir de nombres entiers, de chaine de caractères, …

31
1.2 Les variables

 Déclaration
 Dans le format LDA, Il faut faire précéder la description de l'algorithme par une partie dite
déclarative où l'on regroupe les caractéristiques des variables manipulées

 La partie déclarative est placée (généralement) en tête de l'algorithme et regroupe une ou

plusieurs indications de la forme:

 type variables.

 Instruction d’affectation

 Une fois nommée, il est souvent nécessaire de modifier la valeur de la donnée

référencée par une variable. C’est le rôle de l’instruction d’affectation.

 L’affectation est l’opération qui consiste à attribuer une valeur à une variable.

 La syntaxe est la suivante :

Variable ← expression
32
1.2 Les variables

 Type de variable
 Lorsqu’on déclare une variable, il faut préciser ce que l’on voudra mettre dedans c’est le
type

 Types numériques : entier, réel

 Type alphanumérique : caractère, chaine de caractères

 Type booléen (valeurs logiques VRAI, FAUX)

33
1.2. Les variables

 Instruction de saisie et d’affichage

 Au format LDA, l’instruction de lecture (ou d’affichage) du contenu d’une variable s’écrit:

Lire variable

 Concernant l’instruction d’écriture

affiche variable

 Exemple
 Exprimer un nombre de secondes sous forme d'heures, minutes, secondes. La seule
donnée est le nombre total de secondes que nous appellerons nsec ; les résultats
consistent en 3 nombres : h, m, s

34
1.2. Les variables

 Exemple

35
1.2. Les variables

 Les variables en Langage Python

 La déclaration d’une variable en Python ne requiert pas de type. Ainsi toute variable déclarer doit être
initialisée
nombreVariable = valeur

 Remarques
 Contrairement au langage C, une instruction, en Python, ne se termine pas par un point virgule « ; »

 Même si la déclaration d’une variable ne requiert pas son type, une variable est en réalité typée en
Python :
type Type en Python Exemple
Les entiers int x=2
Les réels float, double a = 5.0
Les chaines de caractères string (str) my flowers are beautiful
Les booléens bool (True, False) is_rich = True
 Pour connaitre le type d’une variable :
type (ma_variable) 36
1.2 Les variables

 Les variables en Langage Python

 Les noms des variables doivent respecter quelques règles:
 Ils ne commenceront pas par un chiffre.

 Le langage C est sensible à la casse (majuscule/minuscule)

Exemple : somme # Somme

 Ils peuvent avoir des lettres, en minuscule ou majuscule et des chiffres

 les caractères spéciaux tels que $, #, @, etc. sont interdits, à l’exception du caractère
« _ » (souligné).

 Ils ne doivent pas être un mot-clé réservé par Python

37
1.2 Les variables

 Les variables en Langage Python

 Pour afficher le contenu d’une variable, on utilise la fonction « print(…) » et une
commande spécifique

 Exemple :
print("my flowers are beautiful ")
nbEtudiant = 15
print("le nombre d’étudiant dans la classe est: ", nbEtudiant)

 Pour récupérer les informations saisies par l’utilisateur sur le clavier, on utilise la fonction
« input(…) ». Pour ce faire, une fois l’information saisie, on va le récupérer et le stocker
dans une variable
# Programme testant si une année, saisie par l'utilisateur, est bissextile ou non
annee = input("Saisissez une année : ") # On attend que l'utilisateur saisisse l'année qu'il désire tester
annee = int(annee) # Risque d'erreur si l'utilisateur n'a pas saisi un nombre

if annee % 400 == 0 or (annee % 4 == 0 and annee % 100 != 0):

print("L'année saisie est bissextile.")
else:
print("L'année saisie n'est pas bissextile.") 38
1.3 Les opérations de bases

 Les opérateurs mathématiques

 Il s’agit des opérations usuelles

 L’addition : +

 La soustraction : -

 La multiplication : *

 La division : /

 Le modulo : mod ( « % » en Python)

 Les opérateurs relationnels (ou booléens)

 < (inférieur) , > (supérieur) , <= (inférieur ou égal) , >= (supérieur ou égal) , =(égal, ==
en Python) , <>(différent de, != en Python)

39
1.3 Les opérations de bases

 Les opérateurs logiques

Types LDA En Python

Négation Non Not
Et logique et and
Ou logique ou or

 Affectation avec opérations

 Addition: +=, ex : a += b  a = a + b
 Soustraction: -=, ex : a -= b  a = a – b
 Multiplication: *=, ex : a *= b  a = a * b
 Division: /=, ex : a /= b  a = a / b
 Modulo: %=, ex : a %= b  a =a % b

40
1.3 Les opérations de bases

 Exemple
 Traduction en Python de l’algorithme convertissant un nombre de secondes sous forme
d’heure, minutes et seconde

41
1.4 Structures de contrôle et boucles
 Structure de contrôles
 Les structures conditionnelles ou alternatives permettent d'écrire dans le programme des
règles comme « Si ceci arrive, alors fais cela » ;

 Elles désignent toute situation n’offrant que deux (ou plusieurs) issues possibles s’excluant
mutuellement

 Syntaxe

Si condition logique alors

# bloc d’instruction 1
sinon
# Blocs d’instruction 2
FinSi

Où « condition logique » peut être soit « VRAI » soit « FAUX ». Il s’agit généralement d’une
comparaison d’une variable à une valeur ou une autre variable

« Finsi » indique la fin de la condition 42

1.4 Structures de contrôle et boucles
 Structure de contrôles
 Le résultat de l’exécution dépendra de la condition logique :

 Si la condition est VRAI alors la première séquence d'instruction sera exécutée et la

seconde sera ignorée;

 Si la condition es FAUX, seule la seconde séquence d'instructions sera effectuée.

 Exemple :

 On considère un jeu dans lequel 2 joueurs A et B doivent présenter un certain

nombre de doigts (0 à 5). Si la somme des nombres de doigts montrés est paire, le
joueur A a gagné sinon c'est le joueur B qui a gagné.

 Le problème est de faire prendre la décision par l'ordinateur.

43
1.4 Structures de contrôle et boucles
 Structure de contrôles
 Exemple : En LDA, on obtient

44
1.4 Structures de contrôle et boucles
 Structure de contrôles
 Remarques :
 Le bloc « sinon » est facultatif dans certains cas

 Une instruction « si … finsi » peut contenir plusieurs autres conditions. On parle

d’imbrication

45
1.4 Structures de contrôle et boucles
 Structure de contrôles en Python
 Syntaxe

Si condition logique alors

if condition :
# bloc d’instruction 1
# bloc d’instruction 1
sinon
else :
# Blocs d’instruction 2
#bloc d’instruction 2
FinSi

 Remarques :

 En python, Il y a « : » à la fin de la condition

 Il n’ y a d’accolades (à la différence du C)

 Veuillez à bien aligner les instructions sous les conditions

 Source du problème d’indentation
 Le bloc « sinon » (ou « else » en Python) est facultatif

46
1.4 Structures de contrôle et boucles
 Structure de contrôles en Python
 Remarques :
 Il est également possible d’avoir des conditions imbriquées. En Python, on peut
utiliser le « elif » pour signifier le « sinon si »
if condition :
# bloc d’instruction 1
elif condition :

#bloc d’instruction 2
else :
#bloc d’instruction 3

 Exemple : Traduction de l’exemple précédent en Python

47
1.4 Structures de contrôle et boucles

 Les boucles
 Exemple introductif :

 Problème: On souhaiterait remplir un fossé. Pour cela on dispose d’un tas de sable et
d’une pelle. Le volume du tas de sable est supposé supérieur au volume du trou à
combler.

 Analyse: Jeter une pelletée de sable dans le fossé tant que le fosse n’est pas plein.

 Cette analyse met en évidence deux éléments :

 1.une action à exécuter (jeter une pelletée de sable),

 2.une condition d’exécution (le fossé n’est pas plein).

 Une boucle est une exécution répétée d’une ou plusieurs des actions et ayant un
mécanisme pour l’arrêter.
48
1.4 Structures de contrôle et boucles

 Les boucles
 On distingue types de boucles :

 La boucle « pour »

 La boucle « tant que »

 La boucle « Faire … tant que »

 Nous verrons uniquement les 2 premières car la dernière n’existe pas en Python

49
1.4 Structures de contrôle et boucles

 Les boucles « pour »

 Cette boucle est utilisée lorsqu'on connait à l’avance le nombre d’itération (nombre de fois
qu’une action sera répétée)

 Syntaxe : (LDA)

 « iterateur » : est une variable de contrôle, initialisée à debut et s’incrémentant à chaque

itération

 L’itération s’arrête lorsque : « Iterateur > fin »

50
1.4 Structures de contrôle et boucles

 Les boucles « pour »

 Exemple :

 Écrire l’algorithme qui affiche la table de multiplication de n.

51
1.4 Structures de contrôle et boucles

 Les boucles « tant que »

 On utilise cette boucle quand on ne connait pas à l’avance le nombre d’itération

 Syntaxe :

 Au moment du premier passage dans la boucle la condition est évaluée; si elle est vérifiée,
la séquence d’instructions est exécutée

 A la fin de l’exécution de cette séquence d’instructions, la condition est de nouveau évaluée

et on répète l’exécution de la séquence d’instructions tant que la condition est vérifiée.

 Dès que la condition devient fausse, l’exécution du programme se poursuit à partir de la

1ère instruction qui suit immédiatement le mot-clé « fintantque »
52
1.4 Structures de contrôle et boucles

 Les boucles « tant que »

 Exemple :

 Écrire l’algorithme qui affiche la table de multiplication de 6.

53
1.4 Structures de contrôle et boucles

 Les boucles « Pour » en Python

 Syntaxe :

for iterateur in sequence:

# Instructions 1
# instruction 2 Attention à l’indentation !!!!
# ….
# instruction N

 La variable « iterateur » n’a pas besoin d’être initialiser. Elle prendra successivement chacune
des valeurs figurant la « séquence » parcourue

 La variable « sequence » est un tableau (ou liste de valeur)

 Pour créer une séquence d’entier entre deux valeurs a et b, on utilise la fonction « range »

 range (a, b, pas) : pas correspond à l’incrémention. Si non spécifier alors « pas = 1 »
54
1.4 Structures de contrôle et boucles

 Les boucles « Pour » en Python

 Exemple : Traduction de l’exemple précedent

55
1.4 Structures de contrôle et boucles

 Les boucles « tant que » en Python

 Syntaxe :

while condition :
# Instructions 1
# instruction 2
# ….
# instruction N

 Exemple :

56
2. Structure de données

26/01/2021
57
3. Procédures et fonctions

26/01/2021
58
4. Algorithme de tri et de recherche

26/01/2021
59
5. Gestion de fichiers

26/01/2021
60
 Fin

2019/2020 L1/ESI 61