.. include:: special.rst

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.

.. glossary :: 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 :
	1. La préparation du traitement ;
	2. La traitement proprepment dit ;
	3. 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 :math:`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é :math:`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 :math:`P(x)=0`, il est clair que la valeur du discriminant :math:`∆=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 :math:`ax^2+bx+c=0`. La suite des instructions à réaliser comprend :

	- Le calcul du discriminant :math:`∆=b^2-4ac` ;

	- Suivant le signe de :math:`∆`, le calcul des deux solutions réelles :math:`x_\text{1,2}=(-b \pm \sqrt{Δ})/(2a)`, de la solution double :math:`x_\text{0}=-b/(2a)` ou des deux solutions complexes conjuguées :math:`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

.. code-block :: python
	:caption: 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

.. code-block :: python
	:linenos:

	# 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

.. code-block :: python
	:caption: Algorithme : Lecture de données
	
	Début
	|	Entrer (a)
	|	Entrer (b)
	|	Entrer (c)
	Fin

**Exemple 7** : Traduction en Python

.. code-block :: python
	:linenos:

	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

.. code-block :: bash
	:caption: 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 

.. code-block :: python
	:linenos:

	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.**

.. code-block :: python
	:linenos:

	# 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:

.. code-block :: bash
	
	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 :

.. code-block :: bash

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

.. code-block :: bash

	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 :math:`ax^2+bx+c=0`.

.. code-block :: bash
	:caption: 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

.. code-block :: python
	:linenos:
	
	#
	# 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 :

	.. code-block :: python
		:linenos:
	
		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 :

	.. code-block :: python
		:linenos:
	
		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

	.. code-block :: python
		:linenos:
	
		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 :
	.. code-block :: bash

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

De même, une structure répétitive avec condition s'écrit :
	.. code-block :: bash

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

.. warning ::
		
	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**

	.. code-block :: python
		:linenos:
	
		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:

	.. code-block :: python
		:linenos:
	
		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:

	.. code-block :: python
		:linenos:
			
		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 :

	.. code-block :: python
		:linenos:

		#
		# 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))

	.. code-block :: python
		:linenos:
	
		#
		# 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 :math:`f(x) =0` pour une précision donnée.

.. code-block :: bash
	:caption: 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 :math:`(x)=x-esinx,[a,b] = [1,10]` et :math:`p=10^{-4}`.

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

.. code-block :: python
	:linenos:
	
	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 :math:`x=[x_1 ,x_2 , ... , x_n]^T` de :math:`\mathbb{R}^n` par la relation :
:math:`\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 :math:`\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 :math:`\mathbb{R}^n`.

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

.. code-block :: python
	:linenos:
	
	import numpy as np

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

.. automodule:: ps
	:members:

.. automodule:: normeucl
	:members:


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

.. code-block :: python
	:linenos:

	>>> from ESGTscipy import *

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

.. code-block :: python
	:linenos:

	>>> 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 :

.. code-block :: python
	:linenos:
	
	from ESGTScipy import *

ou en utilisant un préfixe :

.. code-block :: python
	:linenos:
	
	import ESGTScipy as cs

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

.. code-block :: python
	:linenos:
		
	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:

.. code-block :: python
	:linenos:
	
	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 :

:math:`\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 :math:`n^e` terme de la suite de Fibonacci.

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

*Exercice 9* - **Angle de deux vecteurs**
Écrire une fonction qui calcule l'angle de deux vecteurs de :math:`\mathbb{R}^2` ou :math:`\mathbb{R}^3`.