Programmation¶

Introduction à la programmation¶

Ce document a pour but de vous donner les quelques notions de base en algorithmique et programmation, qui vous permettront d’aborder sereinement les enseignements à venir d’informatique générale et de calcul scientifique (dit aussi « méthodes numériques »).

Au-delà du cadre strict de ces enseignements,la programmation constitue un outil pratique extrêmement puissant pour résoudre les problèmes techniques posés à l’ingénieur.

Son usage sera donc étendu dans toutes les matières scientifiques et techniques enseignées à l’ESGT, plus particulièrement en traitement du signal et des images, géodésie, topométrie de précision, photogrammétrie, et SIG.

Le but ultime de cette démarche est de vous rendre la programmation suffisamment accessible pour que son emploi devienne pour vous un réflexe naturel.

Les algorithmes proposés feront l’objet d’une traduction en langage Python, qui constituera le langage de référence pour l’ensemble de la programmation que vous mettrez en pratique à l’ESGT.

Définitions fondamentales¶

Nous commençons par quelques définitions d’algorithmique à connaître absolument.

Définitions¶
Algorithme¶: Suite finie d’opérations élémentaires constituant un schéma de calcu ou de résolution d’un problème donné.
Algorithmique¶: Ensemble des techniques impliquées dans la définition des algorithmes.
Programme¶: Réalisation (implémentation) d’un algorithme au moyen d’un langage constitué d’une suite d’instructions.

Exemple 1 : Exemples de langage de programmation C, C++, Fortran 90 et 95, Python, Java…

Composition d’un algorithme¶

Un algorithme est généralement composé de trois étapes essentielles qui sont :

La préparation du traitement ;
La traitement proprepment dit ;
La sortie des résultats.

Nous allons détailler ces différentes étapes.

Préparation du traitement¶

Cette étape consiste à recenser les données nécessaires à la résolution du problème. Ces données peuvent être de plusieurs types - numériques, graphiques ou textuelles.

Exemple 2 : L’algorithme de résolution de l’équation polynomiale $ax^2+bx+c=0$ nécessite d’entrer les données a , b et c correspondant aux coefficients du polynôme du second degré $P(x)=ax^2+bx+c$ .

Cette étape comprend également le recensement de tous les résultats intermédiaires à conserver pour la suite.

Exemple 3 : Dans l’exemple de la résolution de l’équiation polynomiale $P(x)=0$ , il est clair que la valeur du discriminant $∆=b^2-4ac$ doit être conservée.

Le traitement¶

Il s’agit de déterminer toutes les instructions nécessaires au traitement. Reprenons l’exemple de la résolution de l’équation polynomiale $ax^2+bx+c=0$ . La suite des instructions à réaliser comprend :

Le calcul du discriminant $∆=b^2-4ac$ ;

Suivant le signe de $∆$ , le calcul des deux solutions réelles $x_\text{1,2}=(-b \pm \sqrt{Δ})/(2a)$ , de la solution double $x_\text{0}=-b/(2a)$ ou des deux solutions complexes conjuguées $z_\text{1,2}=(-b \pm i\sqrt{-Δ})/(2a)$ .

Sortie des résultats¶

Cette étape importante permet à l’utilisateur de récupérer les données traitées par l’algorithme. Plusieurs sorties sont possibles - sorties à l’écran sous forme de valeurs ou de graphiques, impression ou écriture dans un fichier.

Les instructions¶

Les instructions sont les briques élémentaires des algorithmes qui doivent être assemblées dans un ordre précis. Pour écrire les instructions qui composent un algorithme, il est possible d’utiliser un langage textuel baptisé également pseudo-code. L’intérêt de ce langage textuel est de pouvoir décrire tout algirithme sans référence à un langage de programmation particulier .

Dans la suite, nous donnerons systématiquement la traduction en pseudo-code des instructions présentées. Nous donnerons également une implémentation dans le langage Python afin de se familiariser avec la syntaxe des instructions qui composent ce langage.

Instructions de traitement de données¶

Affectation de données dans une variable¶

Ce type d’instruction permet d’attribuer une valeur ou un ensemble de valeurs à une variable désignées par son identificateur

Exemple 4 : Pseudo-code d’instructions d’affectation

Algorithme : Affectation de données¶

Début
|       #       VALEUR NUMÉRIQUE #
|       d = 5
|       #       LISTE DE VALEURS NUMÉRIQUES #
|       v = [1, 2, 3]
|       #       CHAÎNE DE CARACTÈRES #
|       c = " toto "
Fin

Exemple 5 : Traduction en Python

# Valeur numérique
d=5
# Liste de valeurs numériques
v= [1 ,2 ,3]
# Chaîne de caractères
c="toto"

Lecture des données¶

Cette opération est possible par saisie au clavier ou lecture d’un fichier.

Exemple 6 : Instruction de lecture écrite en pseudo-code

Algorithme : Lecture de données¶

Début
|       Entrer (a)
|       Entrer (b)
|       Entrer (c)
Fin

Exemple 7 : Traduction en Python

a=float(input("Entrer la valeur de a : "))
b=float(input("Entrer la valeur de b : "))
c=float(input("Entrer la valeur de c : "))

Écriture des données¶

Ce type d’instructions s’écrit très simplement en pseudo-code comme indiqué ci-après

Exemple 8 : Instruction d’affichage écrite en pseudo-code

Algorithme : Affichage de données¶

Début
|       Afficher("L'équation n'a pas de solution réelle")
|       Afficher(a)
Fin

Exemple 9 : Traduction en Python

print("L'équation n'a pas de solution réelle")
print(a)

Exercice 1 : Taper le code-source ci-après dans un fichier nommé exples_variables.py et tester le programme correspondant.

# Création de variables
#
hello_str   = " Hello World !"
#
hello_int   = 21
#
hello_bool  = True
#
hello_tuple = (21 , 32)
#
hello_list_1 = [" Hello ," , " ceci " ," est " ," une " ," liste "]
#
hello_list_2 = list ()
hello_list_2. append ( " Hello ," )
hello_list_2. append ( " this " )
hello_list_2. append ( " is ")
hello_list_2. append ( "a" )
hello_list_2. append ( " list " )
#
hello_dict = { " first_name": " Liam " ,     \
                " last_name " :" Fraser " ,  \
                " eye_color " :" Blue "      \
             }
#
# Affichage et détermination du type
#
print (" \ nAffichage et d é termination du type " )
print ( hello_str ,
type ( hello_str ))
print ( hello_int ,
type ( hello_int ))
print ( hello_bool ,
type ( hello_bool ))
print ( hello_tuple , type ( hello_tuple ))
print ( hello_list_1 , type ( hello_list_1 ))
print ( hello_list_2 , type ( hello_list_2 ))
print ( hello_dict ,
type ( hello_dict ))
#
# Affichage des éléments en cas de variables multivaluées
#
print (" \ nAffichage des élé ments en cas de variables multivalu é es ")
print ( hello_tuple [0])
print ( hello_list_1 [3])
print ( hello_dict[" eye_color " ])
#
# Manipulations diverses
#
print (" \ nManipulations diverses ")
print ( hello_list_1 [4])
print ( hello_list_2 [4])
hello_list_1 [4] += " !"
hello_list_2 [4] = hello_list_2 [4] + "!"
print ( hello_list_1 [4])
print ( hello_list_2 [4])
#
print ( hello_tuple [0] + hello_tuple [1])
print ( " Le premier é lé ment de la variable hello_tuple vaut : "+ str(hello_tuple[0]))
print (( " La somme des valeurs de la variable hello_tuple vaut : %2d" )%( hello_tuple[
#
print (( "%s %s has %s eyes ." )%( hello_dict[ " first_name"], hello_dict[" last_name "], h
#
#
# Fin du programme
#
print ( "\ nFin du programme : exples_variables ")

Les structures de contrôles¶

Ces structures très utiles en pratique permettent de compléter les instructions ce calcul proprement dit en introduisant des conditions à respecter. Nous allons étudier deux types de structures de contrôle - les structures alternatives (syn. conditionnelles ) et les structures répétitives.

Les structures alternatives¶

Il s’agit d’un traitement sous condition qui peut s’écrire , en pseudo-code:

Début
|       Si Condition Alors
|       |       Traitement 1
|       Sinon
|       |       Traitement 2
|       FinSi
Fin

Ces structures permettent de créer des imbrications de la façon suivante :

Début
|       Si Condition 1 Alors
|       |       Si Condition 2 Alors
|       |       |       Traitement 2
|       |       Sinon
|       |       |       Traitement 1
|       |       FinSi
|       FinSi
Fin

Début
|       Si Condition 1 Alors
|       |       Si Condition 2 Alors
|       |       |       Traitement 2
|       |       SinonSi Condition 3 Alors
|       |       |       Traitement 3
|       |       Sinon
|       |       |       Traitement1
|       |       FinSi
|       FinSi
Fin

Exemple 10 : Nous donnons ci-après un algorithme de détermination des solutions réelles de l’équation polynomiale $ax^2+bx+c=0$ .

Algorithme : Résolution équation polynomiale du second degré (solutions réelles)¶

Début
|#         —————————————————————————————————————
|#              DÉFINITION DE L ’ ÉQUATION
|#         —————————————————————————————————————
|Entrer( a )
|Entrer( b )
|Entrer( c )
|#         —————————————————————————————————————
|#              CALCUL DU DISCRIMINANT
|#         —————————————————————————————————————
|d ← b^2 − 4ac
|#         —————————————————————————————————————
|#              TESTS SUR LE SIGNE DU DISCRIMINANT
|#         —————————————————————————————————————
|       Si d > 0 Alors                                  # 2 solutions réeles distinctes
|       |       x1 ← (-b+sqrt(d))/(2a)
|       |       x2 ← (-b-sqrt(d))/(2a)
|       |       Afficher("Deux solutions réelles distinctes")
|       |       Afficher (x1)
|       |       Afficher (x2)
|       SinonSi d<0 Alors                               # Pas de solution réélle
|       |       Afficher("Pas de solution réelle")
|       Sinon                                           # Solution réelle double
|       |       x0 ← -b/2a
|       |       Afficher(x0 = -b/2a)
|       FinSi
Fin

Exercice 2 : Modifier l’algorithme précédent pour afficher également les solutions complexes .

La traduction en Python de l’algorithme précédent est donnée ci-après

#
# Chargement des bibliothèques utiles
#
import numpy as np
#
print(" Résolution de l ’équation polynomiale : ax ^2+ bx +c =0 ")
#
# Définition de l ’équation
#
a=float( input (" Entrer la valeur de a : " ))
b=float( input (" Entrer la valeur de b : " ))
c=float( input (" Entrer la valeur de c : " ))
#
# Calcul du discriminant
#
d=b**2-4*a*c
#
# Tests sur le signe du discriminant
#
if d>0:
x1=(-b+np.sqrt(d))/(2*a)
x2=(-b-np.sqrt(d))/(2*a)
print (" Deux solutions réelles : x1= "+str(x1)+" x2= "+str(x2)+" .")
elif d<0:
print (" Pas de solution réelle ")
else :
x =-b/(2*a)
print (" Une solution double : x0 = " + str ( x0 ) + " .")
#
# Fin
#
print (" Fin du programme ")

Exercice 3 : Taper le code-source précédebt dans un fichier nommé equa2deg.py et tester le programme correspondant .

Note

Par défaut, les fonctions mathématique ne font pas partie des instructions du langage Python . Il faut donc préalablement charger une bibliothèque les contenant ; c’est le rôle de l’instuction :

import numpy as np

Cette instruction charge la bibliothèque numpy qui intègre de nombreuses fonctions mathématiques y compris le calcul matriciel. Pour appeler les instructions de cette bibliothèque, il faut compléter son code par un préfixe choisi par l’utilisateur, ici np. Ainsi, pour utiliser la fonction racine carré de la bibliotèque numpy faudra-t-il taper :

x = np.sqrt(4)
print(x)

Note

La structure alternative est ici composée des instructions if, elif et else. On peut remarque qu’il n’existe pas d’instruction du type endiff en Python pour marquer la fin d’une structure alternative. Cette dernière est en effet inutile grâce à la propriété suivante : seules les instructions décalées de 4 espaces vers la droite immédiatemennt après une instruction du type if, elif et else sont prises en compte. Cette propriété spécifique du langage Python demande une attention toute particulière lors de la saisie du code sous peine de ne pas obtenir le résultat escompté.

Note

Les variables x1 , x2 , x0 correspondent à des valeurs numériques enregistrées en mémoire sous forme de flottants. Ce type lui a été conféré implicitement par le langage Python, ces dernières étant définies par un calcul numérique. Il n’est pas possible d’afficher directement une variable de type flottant à l’écran. De ce fait, une conversion en une chaîne de caractères est réalisée au préalable par l’instruction str. Dans l’instruction d’affichage ci-après

print ("Deux solutions réelles : x1= "+str(x1)+" x2= "+str(x2)+".")

Ce sont donc cinq chaînes de caractères qui sont concaténées par l’instruction + pour être affichées à l’écran.

Les structures répétitives¶

Les structures répétitives sont de deux types suivant qu’elle comprennent un compteur ou une condition

Une structure répétitive avec compteur s’écrit en pseudo-code :

Début
|       Pour k variantDe 1 à n Faire
|       |       Traitement
|       FinPour
Fin

De même, une structure répétitive avec condition s’écrit :

Début
|       TantQue (b-a) > p Faire
|       |       Traitement
|       FinTantQue
Fin

Avertissement

Pour que cette dernière structure fonctionne, il faut s’assurer que la condition cese d’être verifiée au bout d’un nombre fini de répétitions. Dans le cas contraire, la structure boucle sur elle-même indéfiniment et nécessite une interruption manuelle du programmeur … !

Exercice4 : Taper dans un fichier nommé aleatoire.py le code-source Python ci-après et le faire exécuter plusieurs fois successivement. Que constatez-vous

from numpy import random
#
print("Programme aléatoire")
#
t=0
n=100
for k in range (1, n+1 ):
        x=random.rand()
        y=(1-x)*random.rand()
        z=1-x-y
        print("Tirage no "+strk(k)" : x = "str(x)+" y = "+str(y)+" z = "+str(z))
if x < 0.5 and y < 0.5 and z < 0.5:
        t=t+1
print("t= "+str(t))
print("Fin du programme")

Exercice 5 : Écrire l’algorithme correspondant au code-source précédent

Note

Il est possible de ne pas importer toutes les instructions d’une bibliothèque. Dans l’exemple précédent, seule l’instruction random de la bibliothèque numpy est importée et utilisable directement sans aucun préfixe par la commande:

from numpy import random

Il est possible d’importer directement toutes les instructions d’une bibliothèque sans devoir ensuite utiliser de préfixe grâce à la commande:

from numpy import *

Note

La commande random.rand() permet de sélectionner une méthode particulière de l’instruction random, en l’occurence, la génération d’une valeur d’une variable aléatoire uniforme. Cette particularité est une marque directe de la nature fondamentale du langage Python basée sur la programmation orientée objet.

Note

L’instruction range(1,n+1) produit une liste de (n+1)-1 =n valeurs entières supérieurs ou égales à 1 et strictement inférieures à n+1 , soit [1,2,...,n]

Note

Les structures répétitives nécessitent également des indentations. À titre d’exercice, comparer les deux programmes suivants :

#
# Programme 1
#
k=0
p=0
for i in range(1, 5):
        k=k+1
p=p+1
#
print("k= ", str(k))
print("p= ", str(p))

#
# Programme 2
#
k=0
p=0
for i in range (1, 5):
        k=k+1
        p=p+1
#
print("k= ", str(k))
print("p= ", str(p))

Exercice 6 - Recherche de l’encadrement de la solution d’une équation par dichotomie

On considère l’algorithme ci-après destiné à trouver un encadrement de la solution d’une équation de la forme $f(x) =0$ pour une précision donnée.

Algorithme Dichotomie¶

Début
|       Entrer(f(x))
|       Entrer(a)
|       Entrer(b)
|       Entrer(p)
|       TantQue(b-a) > p Faire
|       |       m ← (b+a)/2
|       |       Si f(a)f(m) < 0 Alors
|       |       |       b ← m
|       |       Sinon
|       |       |       a ← m
|       |       FinSi
|       FinTantQue
|       Afficher("La solution appartient à l'intervalle [a,b] à p près")
Fin

Écrire le code-source Python correspondant à cet algorithme dans un fichier nommé dichotomie.py

Tester le programme pour $(x)=x-esinx,[a,b] = [1,10]$ et $p=10^{-4}$ .

On utilisera l’instruction while ainsi que la séquence d’instructions permettant de définir une fonction quelconque $x → f(x)$ . Par exemple, la définition de la fonction $f(x)=x-esinx$ est réalisée par la séquence d’instructions :

def f(x):
        return x - np.exp(1) * np.sin(x)

Fonctions¶

Les fonctions en Python permettent de réaliser des suites d’opérations particulières et répétitives. Elles sont très utilisées en calcul scientifique pour découper les algorithmes complexes en une suite d’algorithmes élémentaires plus facile à programmer.

Programmation des fonctions¶

Exemple 11 Programmer une fonction qui calcule la norme euclidienne d’un vecteur $x=[x_1 ,x_2 , ... , x_n]^T$ de $\mathbb{R}^n$ par la relation : $\parallel x \parallel _2 = \sqrt(x^Tx)$

La programmation d’une telle fonction peut se diviser en deux parties :

La programmation d’une première fonction donnant produit scalaire de deux vecteurs de $\mathbb{R}^n$ donnés;
La programmation d’une deuxième fonction utilisant la première pour calculer la norme euclidienne d’un vecteur de $\mathbb{R}^n$ .

Dans un fichier appelé ESGTScipy.py, entrer le code suivant :

import numpy as np

Puis entrer le code des deux fonctions ci-après :

Pour utiliser ces fonctions dans une fenêtre de commandes, vous devez taper au préalable :

>>> from ESGTscipy import *

Tester ensuite vos fonctions sur des vecteurs de votre choix. Tester également l’effet des commandes:

>>> help(ps)
>>> help(normeucl)

Utilisation d’une bibliothèque de fonctions¶

L’utilisation systématique d’une bibliothèque de fonctions permet de mettre à profit l’ensemble des programmes que vous réalisez dans d’autres projets de programmation. Une fois le fichier constituant la bibliothèque - dénommé ici ESGTScipy.py - déoisé dans un répertoire examiné par Python, il est possible de faire appel à votre bibliothèque dans n’importe quel autre code de programmation. L’appel peut se faire en mettant dans l’en-tête de votre nouveau programme :

from ESGTScipy import *

ou en utilisant un préfixe :

import ESGTScipy as cs

Dans ce dernier cas, les fonctions de la bibliothèque ESGTScipy pourront être appelées par la syntaxe suivante :

r=cs.ps(u,v)
L=cs.normeucl(v)

Afin de s’assurer que votre bibliothèque soit accessible par Python, vous devez taper dans l’en-tête de votre programme, les instructions suivantes:

import sys
sys.path.append('[chemin menant au répertoire contenant la bibliothèque]')

Exercices¶

Exercice 7 - Suite de Fibonacci La suite de Fibonacci est définie par :

$\left\{\begin{matrix} F_1 =F_2 =1\\ \forall n\geq 2, F_{n+2} = F_{n+1} + F_n \end{matrix}\right.$

Écrire une fonction qui calcule de $n^e$ terme de la suite de Fibonacci.

Exercice 8 - Factorielle Écrire une fonction qui calcule $n!$ pour $n ∈ \mathbb{N}$ donné.

Exercice 9 - Angle de deux vecteurs Écrire une fonction qui calcule l’angle de deux vecteurs de $\mathbb{R}^2$ ou $\mathbb{R}^3$ .