=====================
PROBLEME MAXIMUM     :
=====================

	Quelle est la valeur maximale des elements
	d'une liste ( tableau ) d'entiers.
	
======================
PRODCEDURE - METHODE  :
======================

	exercice : decrire une methode pour resoudre le
	probleme MAXIMUM.

	C'est une consequence de la transitivite de la relation
	de comparaison. On parcours les elements  du tableau en 
        maintenant à jour la valeur de la plus grande valeur 
	rencontré.

(1) comprendre le point cle dans la methode, initialisation.

=======================
PHASE DE CREATION ALGO:
=======================

	Il s'agit de decrire la methode avec un PSEUDO code.

ALGORITHME MAXIMUM( E )
DONNEE 
     E : liste des nombre

VARIABLE
     score : nombre
         i : indice 

(2) faire le bilan des variables : combien, role etc... 
(3) Comment nommer les variables ....

DEBUT
	score = E[ 1 ]
	i = 2
	TQ ( i <=  #E  ) FAIRE
		SI  ( score < E[i] )  ALORS
			score = E[i]
		FSI
	      i = i + 1
	FTQ
        RENVOYER score
FIN

=======================
ANALYSE               :
=======================

	- preuve d'arret ?

		La boucle de minimum s'arrete car la variable i
		croit strictement a chaque iteration.


	- preuve de correction : est-ce que l'algorithme
	determine bien une solution pour chaque *instance* 
	du probleme ?

		La formule :

		score = max{ E[1], E[2], ..., E[i-1] }

		est invriante au travers de chaque iteration.

	c'est une consequence de la formule :

		max ( X union Y ) = max ( max(X), max(Y) )

	ou X, et Y sont deux ensembles de nombres.
	

	- temps de calcul fonction de la taille des instances :
	par exemple :
		- lineaire en n 
		- quadratique en n : n^2
		- cubique en n     : n^3
		- factorielle n    : n! ( a mettre a la poubelle )
		- log(n), n * log(n)

	Pour MAXIMUM le temps de calcul est proportionnel a n, lineaire en la taille de E.

======================
MISE en OEUVRE       :
======================

	Il s'agit de traduire l'algorithme dans un langage 
	de programmation, on parle d'implantation en langage C, bash, 
	python etc...


=======================
OPTIMISATION          :
=======================

	- ameliorer le code, specialiste du langage.
	- "astuce", heuristique.
	- parallelisation ?

=======================
INFORMATIQUE THEORIQUE  :
=======================


	Combien de comparaisons sont faites par MAXIMUM
	pour traiter une instance de taille n ?

		reponse : n - 1

	La boucle de declence des tests pour les indices 2, 3, ..., n+1
	soit (n+1) - 2 + 1 = n tests, et donc n-1 iterations.


- Peut on faire mieux ?

	- non, et ca ce demontre !

exercice : trouver une preuve sur la toile.


Donald E. Knuth, The Art of Computer Programming vol. 3 sorting and searching, voir le 




	Lemme M . Pour une approche fondee sur la comparaison, il est impossible de 
		  determiner le maximum des  elements d'un ensemble de nombres en moins  
                 de ( n - 1 )  comparaisons.

Demonstration.

Apres avoir procede par comparaison, affirmer que la valeur maximale  est s 
c'est dire que pour toute valeur x, on a effectue des comparaisons dont on
peu extraire une chaine :

			x < v1 < v2 < ... < s.


Apres avoir realise k <= n-2 comparaisons :

			x1 < y1 ?
			x2 < y2 ?

			xk < yk ?

On est sur que 2 valeurs, disons a et b, ne figurent pas dans les x1, x2, ..., xk. 
Il est donc impossible de savoir laquelle des deux est la plus grande et encore 
moins de connaitre le maximum. En effet, dans ces conditions, il n'existe pas de
chemin de comparaison d'origine a, donc a est maximum et c'est idem pour b.