Résumé "Graphes et Complexité"
                   (c) 2003-01-11 Fabian M. Suchanek
     http://www.mpi-inf.mpg.de/~suchanek/personal/texts/summaries/gc.txt

Ceci est le résumé du cours "Graphes et Complexité", donné par  M El
Methni et M Caylux en hiver 2002 à l'Université
Pierre-Mendès-France Grenoble.  (Since this text is supposed to be
in French, I could  not avoid using non-ASCII characters, sorry for
that to all foreign readers)

La structure du résumé est la suivante:
* Graphes
  * Introduction
  * Théorie des Graphes
  * Programmation des Graphes
* Complexité
  * Introduction
  * Théorie des Graphes
  * Analyse des programmes

Les programmes listés ci-dessous sont ceux présentés en cours. Le
langage de programmation utilisé est Java. Les programmes servent
pour  communiquer les algorithmes et ne suivent donc pas toujours le
style de Java. Mes propositions sont notées en dessous des
programmes. On admet que tous les fragments de code sont entourés
par une classe  et eventuellement la méthode main. La syntaxe des
programmes a été vérifiée.

J'aimerais bien remercier Aziz Sagna, qui m'a expliqué la
décomposition en éléments simples.

Le lecteur, en lisant le texte ci-dessous, accepte que l'auteur
décline toute responsabilité concernant des informations fausses
ou incomplètes. Si quelqu'un trouve une faute, je lui serais
reconnaissant de bien vouloir me le dire. C'est le seul moyen de 
profiter moi-même de la publication de ce résumé.

Mon e-mail est f.m.suchanek@zweb.de, mais il faut effacer la 
lettre 'z' dans l'adresse.

=====================================================================
                    G R A P H E S
=====================================================================

=====================================================================
                 Introduction
=====================================================================

cf aussi maths.txt (en francais)

Ensemble: Une collection non rangée d'éléments non identiques.
 X = {x1, x2, ..., xn} est l'ensemble de x1 x2, ... xn
 X = {x | déclaration } est l'ensemble de tous les x pour lesquels
     la déclaration est vraie
 Dans toute la suite, les éléments d'un ensemble sont notés par les
 minuscules indexées du nom de l'ensemble.

Cardinalité d'un ensemble: Le nombre d'éléments de cet ensemble.
 |M| = le nombre d'éléments de M

Sous ensemble d'un ensemble M: Un ensemble T tel que tous les éléments
 appartenant à T appartiennent à M. On dit que T est inclu dans M.
        T < M

Application, Fonction: Un classement f qui prend un élément
 appartenant à un ensemble A (ou à plusieurs ensembles) et qui
 redonne un élément appartenant à un ensemble B. On écrit:
 f: A -> B
 f(a)=b, où a appartient à A et b appartient à B

Paramètre: Un élément qu'on donne à une apllication.

Image d'une valeur par rapport à une fonction: Le résultat de la
 fonction pour cette valeur.

Commutativité: La propriété d'une application avec plusieurs paramètres
 de rendre le même résultat, quel que soit la suite des paramètres.
        f(a,b) = f(b,a)

Associativité: La propriété d'une application f avec deux paramètres
 de rendre le même résultat, quel que soit le groupement .
        f(f(a,b),c) = f(a,f(b,c))
 Si une application est associative, on peut enlever les paranthèses
 d'une expression de cette application.

Identité: La fonction f(x)=x.

Surjection: Une fonction f:A->B telle que tout b appartenant à B
 est un image d'un a appartenant à A.

Injection: Une fonction f:A->B telle que deux éléments de A ont
 toujours des images distinctes.

Bijection: Une fonction qui est une injection et une surjection.

Faculté: L'application "!" (notée après le paramètre) qui redonne
 1! = 1
 n! = (n-1)!*n

Union: L'application "\/" qui prend deux ensembles M1 et M2 et
 redonne l'ensemble qui contient les élements qui appartiennent à
 M1 ou à M2 ou à tous les deux. L'union est associative et commutative.

Intersection: L'application "/\" qui prend deux ensembles M1 et M2 et
 redonne l'ensemble qui contient exactement les élements qui
 appartiennent à M1 et à M2. L'intersection est associative et
 commutative.

Exclusion: L'application "-" qui prend deux ensembles M1 et M2 et
 redonne l'ensemble M1 sans les éléments de M2.

Classe de complexité: Un ensemble O de fonctions tel que il y a une
 constante c et une fonction g(x) tels que f(x) =< c*g(x) pour
 toutes les fonctions f appartenant à O. La fonction g décrit alors
 cette classe de fonctions en étant une borne supérieure. On note
 "f appartient à O(g)". Si g1 appartient à O(g2), alors O(g1)
 est un sous ensemble de O(g2).
 Exemples:
 * f(x)=3*x^2 appartient à O(x^2)
 * f(x)=4*x^4+2*x^-1 appartient à O(x^14)
 * f(x)=log(x)*3 appartient à O(x)

Suite, tuple: Une collection rangée d'éléments.
        v = (v[1], v[2], ... v[n])

Couple: Un tuple de deux éléments.

Triple: Un tuple de trois éléments.

Vecteur: Un tuple de nombres réels.
 Annotation: Pour une définition plus générale, cf maths.txt

Matrice: Un tuple de vecteurs qui ont le même nombre d'éléments --
 donc un tableau. Ici, on admet que les matrices contiennent des
 entiers.

Matrice carrée: Une matrice dont le nombre des colonnes est égal au
 nombre des lignes.

Trace: L'application "tr" qui prend une matrice M et redonne
        tr(M) = m[1][1] + m[2][2] + ... m[n][n].

Produit scalaire: L'application "°" qui prend deux vecteurs
 a et b de n éléments et qui rend la valeur
        a°b = a[1]*b[1] + a[2]*b[2] + ... a[n]*b[n]

Puissance de matrice: Le produit scalaire répété d'une matrice carrée.
        A^0 = l'unité
        A^n = A°(A^(n-1))
                        pour toute matrice carrée A et tout entier n>=1

Matrice d'unité: Une matrice carrée I telle que i[y][x]=1 ssi
 y=x, 0 sinon.

Distance: Une application d qui prend deux éléments d'un ensemble X
 et redonne une valeur positive telle que
 * d(x,y) = 0  ssi  x=y                (Séparation)
 * d(x,y) = d(y,x)                (Symétrie)
 * d(x,y) =< d(x,z)+d(z,y)        (Inégalité triangulaire)
 pour tous éléments x,y,z de X.

Produit cartésien: L'application "x" qui prend deux ensembles A et
 B et rend l'ensemble de tous les tuples (a,b) tels que a appartient
 à A et b appartient à B.

Algorithme: Une idée d'une solution systématique.
 Annotation: Cette définition est différente de celles de ia.txt,
 ai.txt et infod.txt, qui disent: "Un algorithme est une suite finie
 d'instructions".


=====================================================================
                Théorie des Graphes
=====================================================================


cf aussi ia.txt (en anglais)
cf aussi infod.txt (en allemand)


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                Les relations
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Relation, Relation binaire: Un sous ensemble du produit cartésien de
 deux ensembles. Soit R la relation, soient E et F les deux ensembles,
 alors on écrit:
 * (x,y) appartient à R
 * x R y
 * R(x,y)
 * x est en relation R avec y
 * x a le support y dans F
 * y a le support x dans E
 pour dire que le couple (x,y) appartient à R. Les deux dernières
 expressions ne sont utilisées que dans ce résumé. On note ~R(x,y)
 le phénomène que (x,y) n'appartient pas à R.

Relation définie sur E: Une relation R < E x E.

Domaine d'une relation R<E x F: Le sous ensemble de ces éléments de E
 qui ont un support dans F.
        dom(R) = {x appartenant à E |
                  Il existe y appartenant à F tq x R y}

Codomaine d'une relation R<E x F: Le sous ensemble de ces éléments
 de F qui ont un support dans E.
        codom(R) = {y appartenant à F |
                    Il existe x appartenant à E tq x R y}

Coupe d'une relation R selon un élément x0: L'ensemble des couples
 de x0 avec ses supports dans F.
        coupe[x0](R) = {(x0,y) | (x0,y) appartient à R}

Réciproque d'une relation R: La relation R^-1 telle que
        R^-1(x,y) ssi R(y,x).

Complément d'une relation R: La relation R' telle que
        R'(x,y) ssi ~R(x,y)

Égalité: La relation =, qui est définie sur l'ensemble de toutes les
 entités.
 Annotation: En effet, la notion de l'égalité est une des rares
             notions qui peuvent être appliquées à tous les objets.
             Les languages de programmation en rendent compte en
             permettant l'opération "==" pour tous les types.

Composition: L'application "o" qui prend deux relations
        R1 < E x F et
        R2 < F x G
 et redonne une relation
        R1 o R2 < E x G
 telle que
        R1 o R2 = {(x,y) appartenant à E x G |
                   il existe z tq R1(x,z) et R(z,y)}
 La composition est associative.

Puissance de relation: La composition répété d'une relation définie
 sur E avec elle-même.
        R^0 = l'égalité \/ (E x E)
        R^n = R o (R^(n-1))
                        pour toute relation R et tout entier n>=1
 R^n est la relation de ces couples (x1,x2) tels qu'on peut aller de
 x1 à x2 en prenant n fois un support d'un support d'un support
 ... de x1.

Distributivité de la composition: Le fait que
 * R o (S \/ T) = (R o S) \/ (R o T)
 * R o (S /\ T) < (R o S) /\ (R o T)
 * (R \/ S) o T = (R o S) \/ (S o T)
 * (R /\ S) o T < (R o T) /\ (S o T)
 pour toutes les relations R, S et T.

Relation réflexive: Une relation R < E x E telle
 que R(x,x) pour tout x appartenant à E.

Relation antiréflexive, relation irréflexive: Une relation
 R < E x E telle que ~R(x,x) pour tout x appartenant à E.

Relation symétrique: Une relation R < E x E telle
 que R(x,y) ssi R(y,x) pour tout (x,y) appartenant à E^2.

Relation transitive: Une relation R < E x E telle
 que
        si R(x,y) et R(y,z) alors R(x,z).

Relation antisymétrique: Une relation R < E x E telle que
        si R(x,y) et R(y,x) alors x=z.

Fermeture réflexive: L'application "r" qui prend une relation
 R < E x E et redonne la relation
        r(R) = R \/ {(x,x) | x appartient à E}
        r(R) = R \/ (R^0 /\ E x E}

Fermeture symétrique: L'application "s" qui prend une relation
 R < E x E et redonne la relation
        s(R) = R \/ {(x,y) | (y,x) appartient à R}
        s(R) = R \/ R^-1

Fermeture transitive: L'application "t" qui prend une relation
 R < E x E et redonne la relation
        t(R) = R \/ {(x,y) | Il existe un n tq
                             (x,y) appartient à R^n}
        t(R) = R^1 \/ R^2 \/ R^3 ...
        R+ = t(R)
        R* = t(R) \/ s(R)

Fermeture et relation: Ssi R est égale à sa fermeture xxxive, alors
 R est elle-même xxxive.

Relation d'équivalence: Une relation R < E x E qui est réflexive,
 transitive et symétrique.

Classe d'équivalence de x0 par R: L'ensemble des supports de x0 par
 la relation d'équivalence R. On le note x0 avec un point en-dessus,
 ce(x0,R).
 Ssi ce(x,R) = ce(y,R) alors R(x,y)

Représentant d'une classe d'équivalence C: Un élément de C.

Ensemble quotient d'une relation R: L'ensemble de toutes les classes
 d'équivalence par R. Cet ensemble est une version "non redondante"
 de E: Au lieu de contenir plusieurs éléments, dont quelques uns sont
 équivalents, il regroupe tous les éléments équivalents comme unités.
 On le note E/R.

Partition d'un ensemble X: Un ensemble d'ensembles {X[1], ...X[n]}
 tel que
        X[1] \/ X[2] \/ ... X[n] = X
        Il n'existe aucun élément qui appartient à deux X[i]
 Toute relation d'équivalence détermine une partition (l'ensemble
 quotient) et toute partition détermine une relation d'équivalence
 (celle qui considère équivalents les éléments d'un ensemble de la
 partition).

// Les relations d'ordre ne se sont pas définies dans ce résumé


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                Les graphes en général
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Paradoxe du journaliste: Le fait qu'il est possible qu'un joueur A
 qui a battu un joueur B qui a battu le joueur C est lui-même battu
 par le joueur C.

Graphe: Un triple de
 * un ensemble S de "sommets" ou "noeuds"
 * un ensemble A d'"arcs" ou "arrêtes"
 * une application phi:A-> S x S
 Un graphe est donc une structure de sommets qui sont liés par des
 arcs. phi associe à chaque arc un noeud de départ et un noeud
 d'arrivé. Si phi(a)=(s,s'), on note a=ss'.

Ordre d'un graphe (S,A,phi): La cardinalité de S, noté par n=|S|.

Taille d'un graphe (S,A,phi): La cardinalité de A, noté par p=|A|.

(n,p)-graphe: Un graphe d'ordre n et de taille p.

Extrémité initiale d'un arc a: Le premier élément du couple phi(a)
 -- donc le noeud de départ de a.

Extrémité finale, extrémité terminale d'un arc a: Le deuxième élément
 du couple phi(a) -- donc le noeud d'arrivé de a.

Boucle: Un arc dont les deux extrémités sont égaux.

Arcs parallels: Deux arcs qui ont les mêmes extremités initiales et
 les mêmes extrémités terminales.

Arc multiple: Un ensemble d'arcs parallèles.

Multiplicité d'un arc multiple: Le nombre d'arcs de cet arc multiple.

k-graphe: Un graphe dont le maximum de multiplicité est égale à k.

Sous-graphe d'un graphe (S,A,phi): Un graphe (S',A',phi) tel que
 * S' < S
 * A' < A
 * phi(a) appartient à S' x S' pour tout a appartenant à A'

Sous-graphe d'un graphe (S,A,phi) engendré par S': Le sous-graphe
 (S',A',phi) tel que A' est l'ensemble des arcs a pour lesquels
 phi(a) appartient à S' x S'.

Graphe partiel d'un graphe (S,A,phi) engendré par A': Le graphe
 (S,A',phi). On note G-a le graphe partiel engendré par A-{a}.

Adjacence de deux arcs: Le phénomène que les deux arcs ont au moins
 une extrémité en commun.

Voisinage de deux sommets, Adjacence de deux sommets: Le phénomène
 que les deux sommets sont les extrémités d'un arc. On note |~(s)
 l'ensemble des voisins du noeud s.

Prédécesseur d'un noeud s: Un noeud s' pour lequel il existe un arc a
 tel que phi(a)=(s',s). On note |~-(s) l'ensemble des prédécesseurs
 du noeud s.

Successeur d'un noeud s: Un noeud s' pour lequel il existe un arc a
 tel que phi(a)=(s,s'). On note |~+(s) l'ensemble des successeurs
 du noeud s.

Arc incident au noeud s vers l'intérieur: Un arc a dont l'extrémité
 finale est s.

Arc incident au noeud s vers l'extérieur: Un arc a dont l'extrémité
 initiale est s.

Démi-degré intérieur d'un noeud s: Le nombre d'arcs incidents à s
 vers l'intérieur, noté par d-(s).

Démi-degré extérieur d'un noeud s: Le nombre d'arcs incidents à s
 vers l'extérieur, noté par d+(s).

Degré d'un noeud s: Le nombre d'arcs qui ont s comme extrémité.
        deg(s) = d(s) = d-(s) \/ d+(s)
 Comme chaque arc est en même temps incident vers l'intérieur et
 incident vers l'extérieur, il est valable:
        SUM d+(s) = SUM d-(s) = p (Lemme des coups de pieds)
        SUM d(s) = SUM d+(s) + SUM d-(s) = 2*p

Noeud pair: Un noeud dont le degré est pair.

Noeud impair: Un noeud dont le degré est impair.
 Le nombre de sommets impairs est pair, comme
        SUM s impair d(s) + SUM s pair d(s) = SUM d(s) = 2*p
        2*p  est pair
        SUM s pair d(s)  est pair
        alors SUM s impair d(s) est pair
        alors le nombre des noueds impairs est pair

Noeud isolé: Un noeud dont le degré est zéro.

Noeud pendant: Un noeud dont le degré est 1.

Arc pendant: Un arc dont une extrémité est pendante.

Chemin: Une suite alternée finie de sommets et arcs
        c = (s[1],a[1],s[2],a[2],...s[k])
 telle que phi(a[i])=(s[i],s[i+1]). On note
        c=[s[1],s[2],...s[k]].
 Pour tout sommet s on admet le chemin c=[s].

Chemin plus arrête: Le chemin constitué par un chemin initial
 auquel on ajoute une arrête et son extrémité finale. On écrit
 c'=c+a.

Extrémité initiale d'un chemin: Son premier élément.

Extrémité finale, extrémité terminale d'un chemin: Son dernier
 élément.

Longueur d'un chemin: Le nombre d'arcs d'un chemin c, noté par l(c).

Chemin simple: Un chemin dans lequel aucun arc ne figure plus d'une
 fois.

Chemin élémentaire: Un chemin dans lequel aucun noeud ne figure plus
 d'une fois. Tout chemin élémentaire est simple, parce qu'un arc
 double implique un noeud double.

Circuit: Un chemin dont les extrémités sont égaux.

Graphe complet: Un graphe simple dont deux sommet quelconques sont
 toujours adjacents (la relation est donc S x S).

Chemin de Hamilton: Un chemin élémentaire qui passe une et une seule
 fois par tous les sommets d'un graphe. Tout graphe complet admet un
 chemin de Hamilton. Démonstration par recurrance:
 * Soit G=(S,A,phi) un graphe complet avec |S|=2. Alors il existe une
   arrête a entre s[1] et s[2]. Alors [s[1],a,s[2]] ou [s[2],a,s[1]]
   est un chemin de Hamilton.
 * Soit G=(S,A,phi) un graphe complet. On ajoute un nouveau sommet s
   de sorte que G+s reste complet. Comme G est complet, il admet
   un chemin de Hamilton [s[1],...s[n]]. Comme G+s est complet, un des
   deux cas suivants est valable:
   * Il existe une arrête de s[n] à s. Alors [s[1],...s[n],s]
     est un chemin de Hamilton
   * Il existe une arrête de s à s[n].
     Si il existe une arrête de s à s[1], alors [s,s[1], ...s[n]]
     est un chemin de Hamilton.
     Sinon, il existe une arrête de s[1] à s.
     Si il existe une arrête de s à s[2], alors [s[1],s,s[2],...s[n]]
     est un chemin de Hamilton.
     Sinon, il existe une arrête de s[2] à s.
     Si il existe une arrête de s à s[3], alors [s[1],s[2],s,s[3],
     ...s[n]] est un chemin de Hamilton.
     ansi de suite
 Annotation: Le problème de trouver un chemin de Hamilton est NP
 complète, voir infod.txt pour les détails.

Sous-chemin d'un chemin [s[1],s[2],...s[k]]: Un chemin [s[i],s[i+1],
 ...s[j]] tel que 0<i<j<k.
 De tout chemin c on peut extraire un chemin élémentaire qui a les
 mêmes extrémités: On efface les sous-chemins de c qui ont les mêmes
 extrémités.

Somme de deux chemins: Le chemin c=[s[1],...s[j], s[j+1],...s[k]] où
 c1=[s[1],...s[j]] est le premier chemin et c2=[s[j+1],...s[k]] est le
 deuxième chemin. On note c=c1+c2.

Chaîne: Une suite de sommets [s[1],...s[k]] telle que pour tout
 i=1..k-1 il y a un arc de s[i] à s[i+1] ou de s[i+1] à s[i].

Somme de deux chaînes: La chaîne c=[s[1],...s[j], s[j+1],...s[k]] où
 c1=[s[1],...s[j]] est la première chaîne et c2=[s[j+1],...s[k]] est la
 deuxième chaîne. On note c=c1+c2.

Inversion d'une chaîne c: La chaîne c^-1 qui commence par la fin de c
 et se termine par son début.

Cycle: Une chaine dont le premier et le dernier sommet sont égaux.

Distance de deux sommets: La longueur du chemin le plus court entre
 ces deux sommets. La distance entre le même sommet est 0, si il n'y a
 pas de chemin entre deux sommets, alors leur distance est infinie.
 On note la distance entre s et s' comme étant d(s,s').

Graphe fortemment connexe: Un graphe orienté dans lequel il existe
 pour tout couple de sommets un chemin de l'un à l'autre. Dans un tel
 graphe, la distance entre deux sommets est une distance dans le sens
 de la définition mathématique du paragraphe "Introduction".

Graphe connexe: Un graphe orienté tel que il existe pour tout couple
 de sommets une chaîne de l'un à l'autre.

Matrice des distances: Une matrice carrée M qui contient à la position
 i,j la distance entre le sommet i et le sommet j. Les éléments
 m[i][i] sont nuls car la distance d'un sommet s à lui-même est 0.
 Par conséquent, la trace de M est 0.

Matrice de la fermeture transitive: Une matrice qui contient à la
 position i,j le nombre 1, si il existe un chemin du sommet i au
 sommet j -- 0 sinon.

Recherche: Une suite de noeuds qui commence par un "noeud de départ"
 et finit par un noeud qui satisfait une certaine condition.

Parcours: Une recherche qui contient tous les noeuds.

Algorithme de Moore: L'algorithme suivant pour la recherche dans
 un graphe:
 1. Prends une suite S qui ne contient que le noeud de départ
 2. Soit i=1
 3. Prend le i-ème noeud de S. Si il satisfait la condition, la
    recherche est finie
 4. Ajoute tous les successeurs de cet i-ème noeud à la fin de S
    -- si ils ne se trouvent pas encore dans S
 5. Incrémente i
 6. Si i est plus grand que la longueur de S, c'est fini
 7. Continue à 3


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                Les graphes orientés
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Graphe orienté: Un 1-graphe. Dans ce cas
 * On désigne les arcs par leur couple d'extrémités, donc comme
   relation
 * L'application phi est l'identité et n'est pas notée
 * Les arcs sont appelés "flèches"

Réunion de deux graphes: Le graphe qui a comme ensemble de sommets
 l'union des deux ensembles de sommets et comme ensemble d'arrêtes
 l'union des deux ensembles d'arrêtes.

Matrice d'adjacence d'un graphe orienté G: La matrice M(G) qui
 représente la relation des arcs de cet graphe. Sa trace est égale
 au nombre des boucles. Le graphe de la transposée de la matrice
 d'adjacence est R^-1. Le graphe de la bit-négation de la matrice
 d'adjacence est R'. Le démi-degré extérieur d+(s) d'un noeud s est
 égal à la somme de sa ligne, d-(s= est égale à la somme de sa
 colonne. Cette représentation prend une place de O(nb_sommets^2).

Matrice des chemins de longueur p: Une matrice qui contient à la
 position i,j le nombre de chemins entre le sommet i et le sommet j,
 qui ont la longueur p. Cette matrice peut être calculé comme étant
 la matrice d'adjacence à la puissance de p. Démonstration par
 recurrance:
 Soit M la matrice d'adjacence, soit m[i][j][x] l'élément à la
 position i,j de M^x.
 * Le cas p=1 revient à la matrice d'adjacence
 * Soit M^(p-1) la matrice des chemins de longueur p-1. Alors
   l'élément m[i][j][p] de la matrice M^p va être:
     m[i][j][p] = SUM k=1..n m[i][k][p-1]*m[k][j][1]
   Donc: Si il existe un chemin de longueur p-1 du noeud i au noeud
   k et si il existe un arc de k à j, le produit va être 1, 0 sinon.

Liste d'adjacence d'un graphe orienté: Une suite qui contient pour
 chaque sommet la suite de ses successeurs. Cette représentation prend
 une place de O(nb_sommets+nb_arrêtes).

Graphe xxx: Un graphe orienté dont la relation est xxx (i.e. réflexif,
 symétrique ou transitif). La symétrie d'un graphe peut être vue dans
 sa matrice d'adjacence.

Fermeture transitive d'un graphe G: Le graphe orienté qui a comme
 relation la fermeture transitive de la relation de G.

Graphe plus arrête: Un graphe G dont on a ajouté un arrête a qui
 n'existait pas. On note G+a = (S, A \/ {a})


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                Les graphes simples
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Graphe simple: Un graphe orienté dont la relation est antiréflexive
 et symétrique.

Matrice d'incidence d'un graphe: Une matrice dont toute ligne
 représente un sommet et dont toute colonne représente un arc.
 L'élément à la position i,j est 1 si l'arc j est incident au
 sommet i.
 // La définition du polycopié parle d'un "sommet incident" (?)

Graphe discret: Un graphe simple sans arrêtes.

Graphe k-régulier: Un graphe simple dont tous les sommets sont de
 degré k.

Graphe cubique: Un graphe 3-régulier.

Complément d'un graphe simple G: Le graphe simple dont la relation est
 la relation complémentaire de la relation de G.

Isomorphisme du graphe (S1,A1) sur un graphe (S2,A2): Une bijection
 de S1 sur S2 telle que deux sommets s,s' de (S1,A1) sont adjacents ssi
 leurs images sont adjacents dans (S2,A2). Par conséquent, il existe
 une bijection f de A1 sur A2 telle que f((s,s'))=(f(s),f(s')).

Isomorphie: La relation qui contient tous les couples de graphes
 entre lesquels il y a un isomorphisme. L'isomorphie est une relation
 d'équivalence. Si deux graphes simples sont isomorphes, alors ils ont
 la même taille et le même ordre et les noeuds correspondants sont du
 même degré.

Invariant d'un graphe G: Un nombre associé à G qui est le même
 pour tout graphe isomorphe à G.

Relation de chaîne d'un graphe simple G: La relation qui contient
 tous les sommets de G entre lesquels il existe une chaîne.
 La relation de chaîne R est une équivalence:
 * Pour tout sommet s il existe la chaîne [s], alors R est
   réflexive
 * Si il existe une chaîne de s1 à s2, la même chaîne existe
   entre s2 et s1, alors R est symétrique
 * Si il existe une chaîne de s1 à s2 et une chaîne de s2 à s3,
   alors il existe une chaîne de s1 à s3, R est transitive

Composantes connexes d'un graphe simple G: La partition de G
 déterminée par sa relation de chaîne. Chaque composante connexe est
 alors un sous graphe connexe maximal de G.

Chemin d'Euler: Un chemin qui passe par toutes les arrêtes d'un
 graphe simple. Un graphe simple admet un chemin d'Euler ssi il est
 connexe et si tous les sommets sont de degré pair.

Géodésique d'un graphe simple (S,A): Une chaîne de s à s' de longueur
 d(s,s').

Diamètre d'un graphe simple connexe: La longueur du plus long
 géodésique.

Excentricité d'un sommet s d'un graphe simple (S,A): Le nombre
 e(s) = max d(s,s') pour s' appartenant à S.

Centre d'un graphe simple G: Un sommet avec une excentricité
 minimum.

Rayon d'un graphe simple G: L'excentricité d'un centre de G.

Point d'articulation d'un graphe simple connexe G: Un sommet s
 tel que G-s est non connexe. s est un point d'articulation ssi
 il existe deux sommets s1 et s2 tels que s appartienne à toute
 chaîne élémentaire joignant s1 et s2. Si s est un point
 d'articulation, alors G-s a au moins 2 composantes connexes.

Pont d'un graphe simple connexe G: Une arrête telle que G-a est
 non connexe. a est un pont ssi a n'appartient à aucun cycle
 élémentaire. a est un pont ssi il existe deux sommets s1 et s2
 tels que a appartient à toute chaîne élémentaire joignant s1
 et s2. Ssi a est un pont, le nombre de composantes connexes
 de G-a est 2. Un graphe dont tous les sommets sont pairs n'admet
 pas de pont: Si il y avait un pont, on pourrait l'enlever et
 obtiendrait deux sous graphes connexes -- dont chaqu'un aurait
 un sommet impair. Mais le nombre de sommets impairs est
 toujours pair. Si un graphe d'ordre n>2 admet un pont, alors
 ce graphe admet un point d'articulation.

Graphe simple cubique: Un graphe simple dont tous les sommets
 sont de degré 3. Un tel graphe G=(S,A) a un nombre pair de sommets:
 SUM s de S: d(s) = 2*|A|
 SUM s de S: 3    = 2*|A|
 |S|*3            = 2*|A|
 alors |S| est pair.
 Si un tel graphe admet un pont, il est au moins d'ordre 10. Si il
 admet un point d'articulation, alors il admet un pont: Un point
 d'articulation aurait 3 arrêtes. Si on enlève ce sommet, il y aura
 forcémment une composante connexe qui était connecté a ce sommet
 par une seule arrête. Cette arrête est le pont.

Graphe non séparable: Un graphe simple qui n'admet aucun point
 d'articulation.

Bloc d'un graphe simple: Un sous graphe non séparable maximal.

Bipartition d'un graphe simple (S,A): Une partition de S en deux
 ensembles S1 et S2 tels que toute arrête a l'une de ses extrémités
 dans S1 et l'autre dans S2.

Graphe biparti: Un graphe simple qui admet une bipartition.
 Un graphe est biparti ssi il ne contient aucun cycle de longueur
 impaire. Démonstration:
 * Si il est biparti, alors il n'existe aucun cycle impair.
   Démonstration par l'absurde: Soit G un graphe biparti qui contient
   un cycle c=[s[1],...s[k],s[1]] avec un k impair. Alors s[1]
   appartient au premier ou au deuxième sous ensemble. Supposons qu'il
   appartient au premier. Alors s[2],s[4],...s[k-1],s[1] appartiennent
   au deuxième sous ensemble -- ce qui mène à une contradiction.
 * Si il n'existe aucun cycle impair, alors le graphe est biparti.
   Si le graphe n'est pas connexe, il suffit d'établir la bipartition
   pour chaque composante connexe. On suppose donc que G=(S,A) est
   connexe. Soit s0 appartenant à S. On considère
   X = { s appartenant à S | il existe une chaîne paire de s0 à s}
   Y = { s appartenant à S | il existe une chaîne impaire de s0 à s}
   Comme G est connexe, S=X\/Y. X/\Y={}, car si il y avait un s auquel
   on peut arriver par une chaîne paire et par une chaîne impaire, on
   aurait un cycle impair. Pour toute arrête a=(s,s'), s et s'
   appartiennent aux sous ensembles différents: Supposons que s
   appartient à X, alors il y a une chaîne paire c de s0 à s. Alors
   c+a est de longueur impaire, alors s' appartient à Y. Par
   conséquent, {X,Y} constitue une bipartition de G.

Arbre: Un graphe simple connexe sans cycle.
 * Tout arbre d'ordre n>=2 possède au moins deux sommets pendants.
   Soit G=(S,A) un arbre, alors G est connexe. Soit c=[s[0],...s[k]]
   une chaîne simple de longueur maximale. s[0] est différent de s[k],
   car G ne contient pas de cycle. d(s[0])>=1 et d(s[k])>=1, car les
   deux appartiennent à la chaîne. Si il était d(s[0])>1, il y aurait
   un s' différent de s[1] tel que a=(s[0],s') appartenirait à A. Par
   conséquent, c+a serait une chaîne plus longue que c, ce qui mène à
   une contradiction. Pareil pour s[k]. Alors s[0] et s[k] sont de
   degré 1.
 * Si G=(S,A) est un arbre, alors il existe une unique chaîne
   élémentaire joignant deux sommets quelconques de G.
   Il y a au moins une chaîne car G est connexe. Si il y en avait
   deux, c et c', alors c+c'^-1 serait un cycle.
 * Si il existe toujours une chaîne unique élémentaire joignant deux
   sommets quelconques de G, alors G est un arbre. Si il existe
   toujours une telle chaîne, alors G est connexe. Si la chaîne est
   unique, alors il n'y a pas de cycle. Alors G est un arbre.
 * Si G=(S,A) est un arbre, alors G est connexe et |S|=|A|+1.
   Démonstration par recurrance:
   * |S|=1, alors |A|=0
   * Supposons que tout arbre d'ordre n admet n-1 arrêtes. Soit
     G un arbre d'ordre n+1. Donc G admet deux sommets pendants. Si on
     en enlève un, on enlève un sommet s0 et une arrête. G-s0 est
     un arbre d'ordre n, qui a donc n-1 arrêtes. Comme on a enlevé
     un sommet et une arrête, G avait n+1 sommets et n arrêtes.
 * Si G=(S,A) est connexe et |S|=|A|+1, alors G est un arbre. Il faut
   montrer que le fait |S|=|A|+1 entraine l'absence d'un cycle.
   Supposons que G contient des cycles. Alors on retire de chaque
   cycle une arrête -- tout en gardant la connexité. Alors le résultat
   G' est un arbre. Par conséquent, G'=(S,A') a |A'|=|S|-1 arrêtes.
   Comme A' est un vrai sous ensemble de A, |A'|<|A| et |S|!=|A+1|.
   Un cycle n'admet donc pas la premisse |S|=|A|+1.
 * Si G=(S,A) est un arbre, alors G est acyclique et si on joint deux
   sommets non adjacents par une arrête, alors G posséde exactement un
   cycle. Le fait d'être un arbre entraine le fait d'être acyclique.
   Puis, tout arbre est connexe, ce qui entraine qu'on obtient un
   cycle si on ajoute une arrête.
 * Si G=(S,A) est acyclique et si l'ajout d'une arrête entraine
   un seul cycle, alors G est un arbre. La dernière premisse implique
   que G est connexe. Un graphe simple acyclique connexe est un arbre.
 Annotation: Cette définition est équivalente à celles de
 ia.txt, ai.txt, cl.txt, infod.txt, lingu.txt et sdl.txt, sauf qu'il
 faudrait désigner une racine.

Forêt: Un graphe simple sans cycle.

Graphe parfait: Un graphe qui ne contient pas deux sommets du même
 degré. Aucun graphe simple n'est parfait. Démonstration par
 l'absurde: Soit G=(S,A) un graphe simple parfait. Comme il y a
 |S|=n sommets, le degré maximum d'un noeud est n-1. Comme tous les
 degrés sont distincts, il y a un noeud du degré 0, il y a un autre du
 degré 1 et ansi de suite jusqu'à un noeud de degré n-1. Ce noeud est
 donc adjacent à tous les autres noeuds -- parmi eux aussi celui de
 degré 0, ce qui mène à une contradiction.
 Application: Dans une soirée mondaine on trouve toujours deux
 personnes ayant le même nombre d'amis présents. On modélise la
 relation d'amitié comme graphe simple. Le nombre d'amis correspond
 donc au degré des noeuds.

Graphe simple biparti complet: Un graphe dont la matrice d'adjacence
 a la forme
 M = 0, ...0, 1, ...1
     ...      ...
     0, ...0, 1, ...1
     1, ...1, 0, ...0
     ...      ...
     1, ...1, 0, ...0
 comme les arrêtes n'existent qu'entre les deux sous ensembles de la
 partition. M^2 a la forme
 M^2 = n, ...n, 0, ...0
       ...      ...
       n, ...n, 0, ...0
       0, ...0, n, ...n
       ...      ...
       0, ...0, n, ...n
 comme il y a n chemins de longueur 2 pour aller d'un noeud d'un sous
 ensemble à un autre noeud du même sous ensemble.

Graphe signé: Un graphe simple dont chaque arrête est munie d'un '+'
 (traduisant une relation favorable entre les sommets) ou d'un '-'
 (traduisant une relation defavorable) . L'absence d'une arrête
 traduit une relation neutre entre deux sommets.
 Les graphes signés sont utilisés pour la modélisation de
 relations sociales entre des personnes.

Arrête négative: Une arrête munie d'un '-'.

Arrête positive: Une arrête munie d'un '+'.

Chaîne positive d'un graphe signé: Une chaîne qui comporte un nombre
 pair d'arrêtes négatives.

Chaîne négative d'un graphe signé: Une chaîne qui comporte un nombre
 impair d'arrêtes négatives.
 Annotation: Cette notation correspond à l'expression (-1)^n, ou
 n est le nombre d'arrêtes négatives de la chaîne.

Graphe équilibré: Un graphe signé dont tous les cycles élémentairs
 sont positifs. Les propositions suivantes sont équivalentes:
 * G=(S,A) est un graphe équilibré
 * Tous ses cycles sont positifs
   Si il y avait un cycle négatif, alors ce cycle ne pourrait pas être
   élémentaire. Donc il contient un sommet double. On coupe le
   cycle en deux cycles. Un des deux cycles doit être négatif. Si il
   est élémentaire, G ne serait pas un graphe équilibré. Si il n'est
   pas élémentaire, on continue à couper.
 * Deux chaînes ayant les mêmes extrémités sont de même signe
   Si les deux chaînes avaient des signes différentes, alors leur
   somme serait un cycle négatif, alors G ne serait pas un graphe
   équilibré.
 * Il existe une partition de S en deux sous ensembles S1,S2 telle que
   * toute arrête positive a ses deux extrémités dans le même sous
     ensemble
   * toute arrête négative va d'un sous ensemble à l'autre
   On construit cette partition de la manière suivante: On place un
   sommet quelconque dans l'ensemble S1. On ajoute ces sommets à S1
   qui n'ont aucune chaîne négative à un sommet appartenant à S1. Les
   autres sommets constituent S2. Il est évident que S=S1 \/ S2. Puis,
   S1 /\ S2 = {}, car si il y avait un sommet qui appartenait aux deux
   ensembles, il aurait en même temps une arrête négative et aucune
   arrête négative à un sommet de S1. Toutes les arrêtes de S1 sont
   positives d'après la construction. Les arrêtes entre S1 et S2 sont
   négatives, car si il y avait une arrête positive, il y aurait
   deux chaînes de signes différentes. Toutes les arrêtes de S2 sont
   positives, car si il y avait une arrête négative, la chaîne
   négative qui part d'une de ses extrémités et mène à S1 complèterait
   une chaîne positive de S1 à S2 -- ce qui est impossible.
   Si on a une telle partition, tout cycle
   * est dans S1 et ne comporte donc que des arrêtes positives
   * est dans S2 et ne comporte donc que des arrêtes positives
   * attraverse les arrêtes entre S1 et S2 un nombre pair de fois.
   Par conséquent, tout cycle est positif, le graohe est équilibré.
 Une situation sociale qui correspond à un graphe équilibré admet
 donc une partition en deux groupes de travail. Un tel graphe traduit
 une situation où chaqu'un a des amis qui sont des amis, donc
 l'absence de relations conflictuelles.


=====================================================================
                Programmation des Graphes
=====================================================================

cf aussi mon cours "Introduction à Java" (ijava.txt, en francais)

Graphe orienté avec attributs: Un graphe orienté dont chaque sommet
 et chaque arrête peut être muni d'attributs (comme une coleur, une
 valeur, un poids ou un numéro). La longueur d'un chemin est redéfinie
 comme étant la somme des valeurs de ses arrêtes. Les graphes traités
 dans ce paragraphe sont des graphes orientés avec attributs.

Arbre couvrant minimal d'un graphe simple: Un arbre qui lie tous
 les sommets tel que la somme des poids des arrêtes est minimale.


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                Les classes utilisées
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

La classe LinkedList:
 Ses parents: java.lang.Object -> java.util.AbstractCollection ->
              java.util.AbstractList ->java.util.AbstractSequentialList
              -> java.util.LinkedList
 Ses interfaces: Cloneable, Collection, List, Serializable
 Ses méthodes:
         void add(int index, Object element)
         boolean add(Object o)
         boolean addAll(Collection c)
         boolean addAll(int index, Collection c)
         void addFirst(Object o)
         void addLast(Object o)
         voidclear()
         Object clone()
         boolean contains(Object o)
         Object get(int index)
         Object getFirst()
         Object getLast()
         int indexOf(Object o)
         int lastIndexOf(Object o)
         ListIterator listIterator(int index)
         Object remove(int index)
         boolean remove(Object o)
         Object removeFirst()
         Object removeLast()
         Object set(int index, Object element)
         int size()
         Object[] toArray()
         Object[] toArray(Object[] a)


La classe Vector:
 Ses parents: java.lang.Object -> java.util.AbstractCollection ->
              java.util.AbstractList -> java.util.Vector
 Ses interfaces: Cloneable, Collection, List, Serializable
 Ses méthodes:
          void add(int index, Object element)
          boolean add(Object o)
          boolean addAll(Collection c)
          boolean addAll(int index, Collection c)
          void addElement(Object obj)
          int capacity()
          void clear()
          Object clone()
          boolean contains(Object elem)
          boolean containsAll(Collection c)
          void copyInto(Object[] anArray)
          Object elementAt(int index)
          Enumeration elements()
          void ensureCapacity(int minCapacity)
          boolean equals(Object o)
          Object firstElement()
          Object get(int index)
          int hashCode()
          int indexOf(Object elem)
          int indexOf(Object elem, int index)
          void insertElementAt(Object obj, int index)
          boolean isEmpty()
          Object lastElement()
          int lastIndexOf(Object elem)
          int lastIndexOf(Object elem, int index)
          Object remove(int index)
          boolean remove(Object o)
          boolean removeAll(Collection c)
          void removeAllElements()
          boolean removeElement(Object obj)
          void removeElementAt(int index)
          void removeRange(int fromIndex, int toIndex)
          boolean retainAll(Collection c)
          Object set(int index, Object element)
          void setElementAt(Object obj, int index)
          void setSize(int newSize)
          int size()
          List subList(int fromIndex, int toIndex)
          Object[] toArray()
          Object[] toArray(Object[] a)
          String toString()

La classe Stack:
 Ses parents: java.lang.Object -> java.util.AbstractCollection
              -> java.util.AbstractList -> java.util.Vector ->
              java.util.Stack
 Ses interfaces: Cloneable, Collection, List, Serializable
 Ses méthodes:
         boolean empty()
         Object peek()
         Object pop()
         Object push(Object item)
         int search(Object o)

La classe ArrayList:
 Ses parents: java.lang.Object -> java.util.AbstractCollection ->
              java.util.AbstractList -> java.util.ArrayList
 Ses interfaces: Cloneable, Collection, List, Serializable
 Ses méthodes:
          void add(int index, Object element)
          boolean add(Object o)
          boolean addAll(Collection c)
          boolean addAll(int index, Collection c)
          void clear()
          Object clone()
          boolean contains(Object elem)
          void ensureCapacity(int minCapacity)
          Object get(int index)
          int indexOf(Object elem)
          boolean isEmpty()
          int lastIndexOf(Object elem)
          Object remove(int index)
          void removeRange(int fromIndex, int toIndex)
          Object set(int index, Object element)
          int size()
          Object[] toArray()
          Object[] toArray(Object[] a)

La classe Collections:
 Ses parents: java.lang.Object -> java.util.Collections
 Ses méthodes:
         static int binarySearch(List list, Object key)
         static int binarySearch(List list, Object key, Comparator c)
         void copy(List dest, List src)
         static Enumeration enumeration(Collection c)
         static void fill(List list, Object o)
         static Object max(Collection coll)
         static Object max(Collection coll, Comparator comp)
         static Object min(Collection coll)
         static Object min(Collection coll, Comparator comp)
         static List nCopies(int n, Object o)
         static void reverse(List l)
         static Comparator reverseOrder()
         static void shuffle(List list)
         static void shuffle(List list, Random rnd)
         static Set singleton(Object o)
         static List singletonList(Object o)
         static Map singletonMap(Object key, Object value)
         static void sort(List list)
         static void sort(List list, Comparator c)
         static Collection synchronizedCollection(Collection c)
         static List synchronizedList(List list)
         static Map synchronizedMap(Map m)
         static Set synchronizedSet(Set s)
         static SortedMap synchronizedSortedMap(SortedMap m)
         static SortedSet synchronizedSortedSet(SortedSet s)
         static Collection unmodifiableCollection(Collection c)
         static List unmodifiableList(List list)
         static Map unmodifiableMap(Map m)
         static Set unmodifiableSet(Set s)
         static SortedMap unmodifiableSortedMap(SortedMap m)
         static SortedSet unmodifiableSortedSet(SortedSet s)


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                Les algorithmes de base
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Code pour le produit scalaire:
 public static int[][] prodscal(int[][] a, int[][] b) {
   int[][] résultat = new int[a.length][b[0].length];
   for(int y=0;y<a.length;y++)
      for(int x=0;x<b[0].length;x++)
         for(int i=0;x<a.length;i++)
            résultat[y][x]+=a[y][i]*b[i][x];
   return(résultat);
 }
 Amélioration: Écrire une classe "Matrice" qui contient cette méthode
               comme méthode non statique.

Code pour la matrice d'adjacence:
 int[][] matrice = new int[nb_sommets][nb_sommets];
 for(int i=0;i<nb_sommets;i++)
    for(int j=0;j<nb_sommets;j++)
        matrice[i][j] = existe_arc(i,j)?1:0;

Code pour la liste d'adjacence:
 import java.util.List;
 import java.util.ArrayList;
 List[] liste = new ArrayList()[nb_sommets];
 for(int i=0;i<nb_sommets;i++)
    for(int j=0;j<nb_sommets;j++)
        if(existe_arc(i,j)) liste[i].add(new Integer(j));

Code pour la matrice des chemins de longueur p:
 public static int[][] nombredechemins(int[][] m, int p) {
   int[][] résultat = new int[m.length][m.length];
   for(int i=0;i<a.length;i++) résultat[i][i]=1;
   while(p-->1) résultat=prodscal(résultat,m);
   return(résultat);
 }
 Amélioration: Déplacer la construction de la matrice d'unité
               dans un constructeur de la classe "Matrice".
               Écrire une classe "MatriceGraphe" qui hérite de
               "Matrice" et contient cette méthode et les méthodes
               suivantes comme des méthodes non statiques.

Code pour la matrice de la fermeture transitive:
 public static int[][] fermeturetransitive(int[][] m) {
   int[][] résultat = new int[m.length][m.length];
   for(int i=0;i<m.length;i++)
       résultat = produitbit(résultat,m);
   return(résultat);
 }

 protected static int[][] produitbit(int[][] a,int[][] b) {
   int[][] résultat = new int[a.length][a.length];
   for(int i=0;i<a.length;i++) résultat[i][i]=1;
   for(int y=0;y<a.lenth;y++)
      for(int x=0;x<b[0].length;x++)
         for(int i=0;x<a.length;i++)
            résultat[y][x]|=a[y][i]&b[i][x];
   return(résultat);
 }


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                La classe Graphe
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Code de la classe Sommet:

   import java.awt.Color;

   public class Sommet {
     public int numéro;
     public double valeur;
     public UnSommet pred;
     public Color couleur;

     /* Construit un sommet */
     public Sommet(int n, double v, Color c) {
       numéro=n;
       valeur=v;
       pred=null;
       couleur=c;
     }

     /* Construit un sommet par des valeurs par défault */
     public Sommet(int n) {
      this(n, 0, Color.black);
     }
   }

   Amélioration: Ne pas déclarer trop d'attributs inutiles. Il vaut
   mieux dériver la classe si on en a besoin. Écrire des méthodes
   accesseurs. Distinguer les attributs utilisés par l'application
   (numéro etc.) et les attributs utilisés par les algorithmes de
   la classe graphe.


Code de la classe UnSommet:

   import java.util.Vector;

   public class UnSommet {
     public Sommet lesommet;
     public Vector lesarrêtes;

     /* Construit UnSommet */
     public UnSommet(Sommet s, Vector a) {
       lesommet=s;
       lesarrêtes=a;
     }

     /* Construit UnSommet sans arrêtes */
     public UnSommet(Sommet s) {
       this(s,new Vector());
     }
   }

   Amélioration: Ne pas distinguer entre UnSommet et Sommet. Cette
   distinction est embrouillante et produit beaucoup de code inutile.
   Les articles des identifieurs ne seraient plus nécessaires. Écrire
   les méthodes standard tostring() et equals().


Code de la classe Arrête:

   import java.awt.Color;

   public class Arrête {
     UnSommet départ;
     UnSommet arrivée;
     double valeur;
     Color couleur;

     /* Construit une arrête complète */
     public Arrête(UnSommet a, UnSommet d, double v, Color c) {
       départ=d;
       arrivée=a;
       valeur=v;
       couleur=c;
     }

     /* Construit une arrête à partir des deux extrémités */
     public Arrête(UnSommet a, UnSommet d) {
       this(d,a,0,Color.black);
     }

   }

   Amélioration: Ne pas déclarer trop d'attributs inutiles. Écrire
   les méthodes standard tostring() et equals().
   La classe devrait implémenter l'interface Comparable pourque
   Collections.sort puisse être utilisé pour Kruskal.

Code de la classe Graphe:

   import java.util.Vector;
   import java.util.Collections;
   import java.util.Stack;
   import java.util.List;
   import java.util.LinkedList;
   import java.awt.Color;

   public class Graphe {

     public Vector lessommets = new Vector();

     /* Ajoute UnSommet */
     void ajoutesommet(UnSommet s) {
       lessommets.add(s);
     }

     /* Ajoute un sommet */
     void ajoutesommet(Sommet s) {
       lessommets.add(new UnSommet(s));
     }

     /* Ajoute une arrête */
     void ajoutearrête(Arrête a) {
       a.départ.lesarrêtes.add(a);
     }

     /* Ajoute une arrête pour deux extrémités */
     void ajoutearrête(UnSommet d, UnSommet a) {
       d.lesarrêtes.add(new Arrête(d,a));
     }

     /* Ajoute une arrête pour deux extrémités,
        données par leur sommets */
     void ajoutearrête(Sommet d, Sommet a) {
       UnSommet ud=null;
       UnSommet ua=null;
       for(int i=0;i<lessommets.size();i++) {
         if(((UnSommet)lessommets.elementAt(i)).lesommet==d)
            ud=((UnSommet)lessommets.elementAt(i));
         if(((UnSommet)lessommets.elementAt(i)).lesommet==a)
            ua=((UnSommet)lessommets.elementAt(i));
       }
       ajoutearrête(ud,ua);
     }

//   Amélioration: Cette méthode prend un temps de O(n).
//   Si on abandonnait la distinction entre Sommet et UnSommet on
//   n'aurait pas ce problème.


     /* Parcours du graphe en largeur d'abord */
     public void parcourslargeur(UnSommet s) {
       for(int i=0;i<lessommets.size();i++)
          ((UnSommet)lessommets.elementAt(i)).lesommet.couleur=
          Color.black;
       Vector file = new Vector();
       file.add(s);
       while(!file.isEmpty()) {
         s = (UnSommet)file.remove(0);
         for(int i=0;i<s.lesarrêtes.size();i++) {
           UnSommet a=((Arrête)s.lesarrêtes.elementAt(i)).arrivée;
           if(a.lesommet.couleur==Color.black) {
             file.add(a);
             a.lesommet.couleur=Color.blue;
           }
         }
         System.out.println(s.lesommet.numéro);
       }
     }

//   Amélioration: Ne pas abuser l'attribut publique coleur,
//   implémenter l'idée du visiteur (visitor design pattern).
//   Pareil pour les méthodes suivantes.

     /* Parcours du graphe en profondeur d'abord */
     public void parcoursprofondeur(UnSommet s) {
       for(int i=0;i<lessommets.size();i++)
          ((UnSommet)lessommets.elementAt(i)).lesommet.couleur=
          Color.black;
       parcoursprofondeurb(s);
     }

     /* Méthode qui aide parcoursprofondeur */
     protected void parcoursprofondeurb(UnSommet s) {
       if(s.lesommet.couleur==Color.black) return;
       s.lesommet.couleur=Color.blue;
       System.out.println(s.lesommet.numéro);
       for(int i=0;i<s.lesarrêtes.size();i++)
          parcoursprofondeurb(((Arrête)s.lesarrêtes.elementAt(i)).
                              arrivée);
     }

     /* Parcours du graphe en profondeur d'abord non récursif. Chaque
        noeud est affiché par son numéro. */
     public void parcoursprofondeurparpile(UnSommet s) {
       for(int i=1;i<lessommets.size();i++)
          ((UnSommet)lessommets.elementAt(i)).lesommet.couleur=
          Color.black;
       Stack pile=new Stack();
       pile.push(s);
       while(!pile.isEmpty()) {
         s=(UnSommet)pile.pop();
         if(s.lesommet.couleur==Color.black) {
           System.out.println(s.lesommet.numéro);
           s.lesommet.couleur=Color.blue;
           for(int i=0;i<s.lesarrêtes.size();i++)
              pile.push(s.lesarrêtes.elementAt(i));
         }
       }
     }


     /* Trouve les chemins les plus courts d'un sommet de départ
        à tous les autres sommets. Les chemins trouvés sont stockés
        dans l'attribut "pred". L'algorithme utilise une file
        d'attente dynamique avec priorité. Il ne fonctionne pas si
        il y a une arrête de valeur négative. La valeur d'un sommet
        stocke la distance de ce sommet au sommet de départ. On
        choisit le sommet s avec la plus petite valeur et on met à
        jour les sommets adjacents: Si un sommet adjacent peut être
        atteindu plus facilement par s, on change sa valeur et son
        prédecesseur et on l'ajoute à la liste des sommets à
        vérifier.*/
     public void dijkstra(UnSommet s) {
       for(int i=0;i<lessommets.size();i++) {
         ((UnSommet)lessommets.elementAt(i)).lesommet.valeur=
            Double.MAX_VALUE;
         ((UnSommet)lessommets.elementAt(i)).lesommet.couleur=
            Color.black;
         ((UnSommet)lessommets.elementAt(i)).lesommet.pred=null;
       }
       LinkedList l=new LinkedList();
       s.lesommet.valeur=0;
       s.lesommet.couleur=Color.blue;
       l.add(s);
       while(!l.isEmpty()) {
         UnSommet pp=supprimepluspetit(l);
         pp.lesommet.couleur=Color.black;
         for(int i=0;i<pp.lesarrêtes.size();i++) {
           Arrête a=(Arrête)pp.lesarrêtes.elementAt(i);
           UnSommet d=a.arrivée;
           if(a.valeur + pp.lesommet.valeur < d.lesommet.valeur) {
              d.lesommet.pred=pp;
              d.lesommet.valeur=a.valeur+pp.lesommet.valeur;
              if(d.lesommet.couleur==Color.blue) l.remove(d);
              d.lesommet.couleur=Color.blue;
              l.add(d);
           }
         }
       }
     }

//   Amélioration: Ne pas abuser les attributs publiques couleur et
//   valeur. Pareil pour toutes les méthodes suivantes.

     /* Trouve le plus petit sommet d'une liste, supprime ce sommet*/
     protected UnSommet supprimepluspetit(LinkedList l) {
       UnSommet pp=null;
       double ppval=Double.MAX_VALUE;
       for(int i=0;i<l.size();i++)
          if(((UnSommet)l.get(i)).lesommet.valeur<ppval) {
            pp=(UnSommet)l.get(i);
            ppval=pp.lesommet.valeur;
          }
       l.remove(pp);
       return(pp);
     }

     /* Trouve les chemins les plus courts d'un sommet de départ
        à tous les autres sommets. Les chemins trouvés sont stockés
        dans l'attribut "pred". L'algorithme fonctionne avec des
        arrêtes négatives, mais pas avec des cycles de somme
        négative. Dans ce cas, false est redonné. La distance d'un
        sommet au sommet de départ est stockée dans sa valeur.
        L'algorithme parcourt toutes les arrêtes. Il met à jour
        les valeurs de leurs extrémités. */
     public boolean bellmanford(UnSommet s) {
       for(int i=0;i<lessommets.size();i++) {
         ((UnSommet)lessommets.elementAt(i)).lesommet.valeur=
            Double.MAX_VALUE;
         ((UnSommet)lessommets.elementAt(i)).lesommet.pred=null;
       }
       boolean changé=true;
       int nombre=0;
       s.lesommet.valeur=0;
       while(changé && nombre < lessommets.size()) {
         changé=false;
         for(int i=0;i<lessommets.size();i++) {
           UnSommet d=(UnSommet)lessommets.elementAt(i);
           for(int j=0;j<d.lesarrêtes.size();j++) {
             UnSommet a=((Arrête)d.lesarrêtes.elementAt(j)).arrivée;
             if(a.lesommet.valeur > d.lesommet.valeur +
               ((Arrête)d.lesarrêtes.elementAt(j)).valeur) {
               a.lesommet.valeur = d.lesommet.valeur +
                 ((Arrête)d.lesarrêtes.elementAt(j)).valeur;
               changé=true;
               a.lesommet.pred=d;
             }
           }
         }
       }
       return(!changé);
     }


     /* Trouve un arbre couvrant minimal, redonne une liste des
        arrêtes participantes. D'abord, chaque sommet constitue un
        arbre, identifié par un nombre stocké dans la valeur du
        sommet. Puis, la plus petite arrête qui joint deux arbres
        différents est trouvée. Les deux arbres sont fusionés. On
        continue jusqu'à ce qu'il n'y a qu'un seul arbre. */
     public List kruska() {
       Vector arrêtes = new Vector();
       LinkedList résultat = new LinkedList();
       for(int i=0;i<lessommets.size();i++) {
         arrêtes.addAll(((UnSommet)lessommets.elementAt(i)).
                          lesarrêtes);
         ((UnSommet)lessommets.elementAt(i)).lesommet.valeur=i;
       }
       Collections.sort(arrêtes);
       for(int i=0;i<arrêtes.size();i++) {
         Arrête a=(Arrête)arrêtes.elementAt(i);
         if(a.arrivée.lesommet.valeur!=a.départ.lesommet.valeur) {
           fusion(a.arrivée, a.départ.lesommet.valeur);
           résultat.add(a);
         }
       }
       return(résultat);
     }

     /* Fait que tous les sommets de l'arbre d'un sommet prennent
        la valeur indiquée.*/
     protected void fusion(UnSommet a, double d) {
       double valinitiale=a.lesommet.valeur;
       a.lesommet.valeur=d;
       for(int i=0;i<a.lesarrêtes.size();i++) {
         Arrête arrête=(Arrête)a.lesarrêtes.elementAt(i);
         if(arrête.arrivée.lesommet.valeur==valinitiale)
            fusion(arrête.arrivée, d);
       }
     }
   }

   Amélioration: Écrire la méthode standard tostring().


=====================================================================
                    C O M P L E X I T É
=====================================================================

=====================================================================
                 Introduction
=====================================================================

cf aussi maths.txt (en francais)

e: 2.718281828

pi: 3.141592653589793238462

R: L'ensemble des nombres réels.

N: L'ensemble des nombres naturels.

SUM n>=n1..n2 f(n): La somme de f(n1) + f(n1+1) + ... f(n2).

SUM n>=n0 f(n): La somme SUM n>=n0..INF f(n).

n!: Le produit 1*2*3*...n
 n! est approximativement égal à (n/e)^n*sqrt(2*n*pi)

C(n,k): Le nombre de sous ensembles de k éléments d'un ensemble de
 n éléments. Il est:
 *  C(n,k)   = n! / k! / (n-k)!
 *  C(n,k)   = C(n,n-k)
 *  C(n,k)   = C(n-1,k) + C(n-1,k-1)
 *  C(n,0)   = 1
 *  C(n,1)   = n
 *  C(n,n-1) = n
 *  C(n,n)   = 1
 *  C(n,k>n) = 0
 *  C(0,k)   = 0
 On note
                   k       <-- sous ensemble
         C(n,k) = C
                   n       <-- grand ensemble

Triangle de Pascal: Le triangle dont le coin et les arrêtes sont 1 et
 dont chaque ligne a comme éléments les sommes des deux nombres en
 dessus:
           1
          1 1
         1 2 1
        1 3 3 1
       .........
 Le nombre à la position n,k est C(n,k)

h(n): SUM k=1..n 1/k

Quotient: Une expression de la forme <expression> / <expression>.

Numérateur: La première expression d'un quotient.

Dénomiateur: La deuxième expression d'un quotient.

Polynôme de x: Une expression de la forme
 <constante>*x^n + <constante>*x^(n-1) + ... + <constante>*x^0

Degré d'un polynôme de x: L'exponent le plus élevé de x dans le
 polynôme.

Terme d'un polynôme de x: Une composante <constante>*x^k.

Ordre d'un terme: L'exponent du terme.

Racine d'une expression de x: Une valeur pour x telle que l'expression
 donne 0.

Division euclidienne d'un polynôme A par un polynôme B: L'algorithme
 suivant, qui simplifie le quotient A/B:
 1. Classe les termes d'ordre décroissant dans chaqu'un des polynômes
 2. Soit A' := A
 3. Écris la ligne principale "A' / B = "
 4. Soit k := degré(A')
 5. TantQue k>=0
    6. c := (terme d'ordre k de A') / (premier terme de B)
    7. Ajoute "+ c" à droite de la ligne principale
    8. Écris B*c en dessous de A'
    9. Calcule A' := A' - B*c et écris-le en dessous
    10. Décrémente k
 11. FinTantQue
 12. Ajoute "+ A' / B" à droite de la ligne principale
 13. Le résultat est l'expression à droite du "="

Détermination des racines d'un polynôme A: L'algorithme suivant,
 qui trouve les racines de A:
 1. Si degré(A)=0, alors
    2. Si A=0, alors tous les réels sont des racines, c'est fini
    3. Sinon il n'y aucune racine, c'est fini
 4. FinSi
 5. Si degré(A)=1, alors
    6. Identifie a*x + b := A
    7. La racine est -b/a, c'est fini
 8. FinSi
 9. Si degré(A)=2, alors
    10. Identifie x^2 + p*x + q := A/a
    11. Les racines sont
        -p/2 + sqrt(p^2/4 - q)
        -p/2 - sqrt(p^2/4 - q), c'est fini
 12. FinSi
 13. Trouve une racine r en essayant quelques valeurs
 14. Effectue une division euclidienne A' := A / (x - r)
 15. Les racines sont r et les racines de A'
 Les racines de 1-x-x^2 sont
 * (1+sqrt(5))/-2
 * (1-sqrt(5))/-2

Réduction d'une expression A: La transformation de A en la forme
 d'un produit, dont chaque facteur est de la forme
     (a*x - b)^k  ou  (b - a*x)^k
 sauf eventuellement le dernier. On procède de la manière suivante:
 1. Pour tout facteur F de A
    2. Si F n'est pas de la forme désirée, alors
       3. Détermine les racines r[i] de F
       4. Si il y en a, alors remplace F par (x-r[1])*...*(x-r[n])*A
          où A est le reste éventuel résultant de l'étape 14
          de l'algorithme de détermination des racines
    5. FinSi
 6. FinPour

Élément simple: Un quotient qui ne peut plus être simplifié.

Décomposition d'un quotient A/B: L'algorithme suivant, qui transforme
 le quotient en une expression de la forme
      <polynôme> + <élémentsimple> + <élémentsimple> ...
 1. Soit R := ""
 2. Si degré(A) >= degré(B), alors
    3. Effectue une division euclidienne C:=A/B
    4. R := partie polynôme de C
    5. Identifie A/B := la partie quotient de C
 6. FinSi
 7. Réduis B
 8. Remplace les facteurs égaux F de B par F^k
 9. Soit z := 'a'
 10. Pour chaque facteur f de B
     11. Si f = (x-r)^k, alors
         12. TantQue k>0
             13. Ajoute à R  +z/(x-r)^k
             14. z := succ(z)
             15. k := k - 1
         16. FinTantQue
     17. FinSi
     18. Si f = (a*x^2+b*x+c)^k, alors
         19. TantQue k>0
             20. z' := succ(z)
             21. Ajoute à R +(z*x+z')/(a*x^2+b*x+c)^k
             22. z := succ(succ(z))
             23. k := k - 1
         24. FinTantQue
     25. FinSi
 26. FinPour
 27. Détermine les variables a..z telles que R = A/B
     Dans le cas 1/(x-r1)/(x-r2) = a/(x-r1) + b/(x-r2), on multiplie
     toute l'équation par (x-r1) et pose x=r1 pour déterminer a.
     On procède pareil pour déterminer b.
 28. Le résultat est R

Règles de dérivation:
 * cos'          = -sin
 * sin'          = cos
 * abs'          = sgn pour tout x!=0
 * (a*f + b*g)'  = a*f' + b*g'
 * (f*g)'        = f'*g+g'*f
 * (f/g)'        = (f'*g - f*g') / g^2
 * (x^z)'        = z*x^(z-1) pour tout z!=0
 * tan'          = 1+tan^2
 * tan'          = 1/cos^2
 * (f^-1)'       = 1/(f' o f^-1)
 * ln(a*x)'      = 1/x
 * arcsin'       = 1/sqrt(1-x^2)
 * arctan'       = 1/(1+x^2)
 * f(g(x))'      = g(x)' * f(z)  avec z=g(x)

Règles de logarithme:
 * a^log(b)      = b^log(a)
 * log b (a)     = log(a)/log(b)
 * log(a*b)      = log(a)+log(b)
 * log(a/b)      = log(a)-log(b)


=====================================================================
                    Théorie de la complexité
=====================================================================


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                Les Fonctions Génératrices
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Suite réelle: Une suite de longueur infinie de nombres réels,
 identifiés par a[n], n appartenant à N et n>=n0.
 n0 est appellé le début de la suite.

Somme de deux suites réelles: La suite réelle dont chaque élément est
 la somme des éléments correspondants des deux suites.

Produit d'une suite par un réel: La suite réelle dont chaque élément
 est l'élément de la suite initiale, multiplié par le réel.

Suite de fonctions réelles: Une suite de longueur infinie de
 fonctions, identifiées par f[n]:R->R, n appartenant à N.

Série génératrice associée à a[n] avec le noyeau f[n]: La fonction
 A(x) = SUM n>=n0  a[n]*f[n](x).
 Annotation: Ce résumé se limite à la notation "série génératrice".
             La notion "fonction génératrice" est synonyme.

Série génératrice ordinaire: Une série génératrice avec un noyeau de
 la forme f[n](x)=x^n.

Série génératrice exponentielle: Une série génératrice avec un noyeau
 de la forme f[n](x)=x^n/n!. Chaque série génératrice exponentielle
 peut être interprétée comme étant une série génératrice ordinaire.

Égalité de séries génératrices ordinaires: La relation qui
 contient tous les couples de séries génératrices ordinaires qui
 sont associées à la même suite réelle.

Forme de somme d'une série génératrice A: La forme
   A(x) = SUM n>=n0  a[n]*f[n](x)

Forme explicite d'une série génératrice A: La forme
   A(x) = <expression>
 où <expression> ne contient pas de somme infinie.

Somme de deux séries génératrices ordinaires: La série génératrice
 ordinaire qui a comme suite réelle la somme des deux suites réelles.
 On note C(x)=A(x)+B(x)

Produit d'une série génératrice ordinaire par un réel: La série
 génératrice ordinaire associée au produit de la suite réelle par
 le réel. On note B(x)=r*A(x)

Produit de convolution de deux séries génératrices ordinaires,
Produit de Cauchy de deux séries génératrices ordinaires: La série
 génératrice ordinaire
             C(x) = SUM n=0..INF c[n]*x^n, où
             c[n] = SUM (0=<k et k=<n)  a[k]*b[n-k], où
             a[n] et b[n] sont les suites des deux séries


~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
                Récurrance
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Relation de récurrance d'une suite réelle a: L'expression de a[n]
 en fonction d'éléments précédents.
 Exemple: a[n] = 3*a[n-1] + a[n/2]^2 + 7

Forme récursive d'une suite réelle: Ses premiers éléments et sa
 relation de récurrance.
 Exemple: a[0] = 10
          a[n] = 5*a[n-1]

Forme explicite d'une suite réelle a: Une expression pour a[n],
 qui ne contient pas d'éléments précédents.
 Exemple: a[n]= 6*n^2 + 2

Solution d'une récurrance sans n/2: La transformation d'une forme
 récursive sans l'indice n/2 en une forme explicite. Soit la suite
 a[n]. On procède de la manière suivante:
 1. Produis les séries génératrices
    1.1. Écris la relation de récurrance
    1.2. Multiplie toute l'equivalence par x^n
    1.3. Détermine le plus petit entier k pour lequel la relation
         de récurrance est applicable
    1.4. Ajoute "SUM n>=k" à gauche et à droite
    1.5. Applique les règles de simplification pour transformer la
         grande somme en plusieures sommes simples
 2. Produis la forme explicite de A(x)
    2.1. Applique les règles de normalisation
    2.2. Remplace toute  "SUM n>=n0 a[n]*x^n"  par "A(x)"
    2.3. Traduis les sommes restantes en des formes explicites
    2.4. Résoud l'équivalence pour obtenir "A(x) = ..."
 3. Produis la forme de somme de A(x)
    3.1. Traduis l'expression à droite en des sommes
    3.2. Applique les règles de simplification à l'invers pour avoir
         une grande somme complexe à droite
 4. Produis la forme explicite de la suite réelle
    4.1. Dans A(x) = SUM n>=n0  a[n]*x^n,
         a[n] est la forme explicite de la suite réelle avec
         a[n]=0 pour n<n0
 Les récurrances suivantes sont déjà résolues:
 * a[0] = 0
   a[n] = a[n-1] + n/2^n
   a[n] = 2 - n/2^n - 2/2^n
 * a[0] = 0
   a[n] = a[n-1] + n*2^n
   a[n] = (n-1)*2^(m+1)+2

Règles de simplification:
         Complexe                      Simple
*   SUM n>=n0 a*f(n)              = a * SUM n>=n0 f(n)
*   SUM n>=n0 f(n)+g(n)           = SUM n>=n0 f(n) + SUM n>=n0 g(n)
*   SUM n>=n0 f(n-k)              = SUM n>=n0-k f(n)
*   SUM n>=n0 f(n+k)              = SUM n>=n0+k f(n)
*   SUM n>=n0 (f1(n)+f2(n))/f3(n) = SUM n>=n0 f1(n)/f3(n)
                                    + SUM n>=n0 f2(n)/f3(n)
*   SUM n>=n0 f(2*n)              = SUM n>=n0 (1+(-1)^n)/2*f(n)

Règles de normalisation:
      Normé                     Non normé
S(x) = SUM n>=n0 s[n]*x^n
*   S(x) - s[n0]*x^n0     = SUM n>=n0+1  s[n]                 *x^n
*   x*S(x)                = SUM n>=n0+1  s[n-1]               *x^n
*   x^k*S(x)              = SUM n>=n0+k  s[n-k]               *x^n
*   (S(x)-S(0))/x         = SUM n>=n0    s[n+1]               *x^n
*   S(x)'                 = SUM n>=n0    (n+1)*s[n+1]         *x^n
*   INT 0->x S(t)*dt      = SUM n>=n0+1  s[n-1]/n             *x^n
*   S(r*x)                = SUM n>=n0    r^n*s[n]             *x^n
*   (1-x)*S(x)    = s[n0] + SUM n>=n0+1  (s[n]-s[n-1])        *x^n
*   S(x)/(1-x)            = SUM n>=0     (SUM k=0..n s[k])    *x^n
*   S(x)*T(x)             = SUM n>=0  (SUM k=0..n s[k]*t[n-k])*x^n
*   S(x)-SUM n=n0..k-1 s[n]*x^n = SUM n>=n0+k s[n]            *x^n

S(x)=SUM n>=n0 s[n]*x^n/n!
*   INT 0->x S(t)*dt = SUM n>=n0+1  s[n-1]                     *x^n/n!
*   S(x)'            = SUM n>=n0    s[n+1]                     *x^n/n!
*   x*S(x)           = SUM n>=n0    n*s[n-1]                   *x^n/n!
*   (S(x)-S(0))/x    = SUM n>=n0    s[n+1]/(n+1)               *x^n/n!
*   S(x)'-S(x)       = SUM n>=n0    (s[n+1]-s[n])              *x^n/n!
*   e^x*S(x)         = SUM n>=0     (SUM k=0..n C(n,k)*s[k])   *x^n/n!
*   S(x)*T(x)        = SUM n>=0 (SUM k=0..n C(n,k)*s[k]*t[n-k])*x^n/n!

Règles de traduction:
       Forme explicite         Forme de somme
*   x/(1-x)^2             = SUM n>=0 n           *x^n
                          = SUM n>=1 n           *x^n
*   x^2/(1-x)^3           = SUM n>=2 C(n,2)      *x^n
                          // Dans le polycopié: x^3/(1-x)^3  (?)
*   x^k/(1-x)^(k+1)       = SUM n>=k C(n,k)      *x^n
*   1+x                   = SUM n>=0 C(1,n)      *x^n
                          = SUM n>=0 (n>1?0:1)   *x^n
*   (1+x)^k               = SUM n>=0 C(k,n)      *x^n
*   1/(1-x)               = SUM n>=0              x^n
*   1/(1-x)^2             = SUM n>=0 (n+1)       *x^n
*   1/(1-x)^k             = SUM n>=0 C(n+k-1,n)  *x^n
                          = SUM n>=0 C(n+k-1,k-1)*x^n
*   1/(1-a*x)             = SUM n>=0 a^n         *x^n
*   1/(1+x)               = SUM n>=0 (-1)^n      *x^n
*   f(a*x)                = SUM<formule pr f>*a^n*x^n
*   1/(1-x^2)             = SUM n>=0             *x^(2*n)
                          = SUM n>=0 (n&1?0:1)   *x^n
                          = SUM n>=0 (1+(-1)^n)/2*x^n
*   ln(1/(1-x))           = SUM n>=1 1/n         *x^n
*   1/(1-x)*ln(1/(1-x))   = SUM n>=1 h(n)        *x^n
                          = SUM n>=0 h(n)        *x^n
*   x/(1-x)^2*ln(1/(1-x)) = SUM n>=0 n*(h(n)-1)  *x^n
*   e^x                   = SUM n>=0              x^n/n!
*   x*e^x                 = SUM n>=1 1/(n-1)!    *x^n
                          = SUM n>=1 n           *x^n/n!
*   x^2*e^x               = SUM n>=2 1/(n-2)!    *x^n
                          = SUM n>=2 n*(n-1)     *x^n/n!
*   x^k*e^x               = SUM n>=k 1/(n-k)!    *x^n
*   1/k!*x^k*e^x          = SUM n>=k C(n,k)      *x^n/n!
*   e^x+e^-x              = SUM n>=0 (1+(-1)^n)  *x^n/n!
                          = SUM n>=0 (n&1?0:2)   *x^n/n!
*   e^(a*x)               = SUM n>=0 a^n         *x^n/n!
*   (e^x-1)/x             = SUM n>=0 1/n         *x^n/n!
*   ln(1+x)               = SUM n>=0 (-1)^(n+1)/n*x^n

Règles de dénormalisation:
    Normé                     Non normé
*   S(x) = (SUM n>=n0+1  s[n]          *x^n) + s[n0]*x^n0
*   S(x) = (SUM n>=n0+1  s[n-1]        *x^n) /x
*   S(x) = (SUM n>=n0+k  s[n-k]        *x^n) /x^k
*   S(x) = (SUM n>=n0    s[n+1]        *x^n) *x+s[n0]
*   S(x) = (SUM n>=n0+1  s[n-1]/n      *x^n)'
*   S(x) = (SUM n>=n0    (s[n]+t[n])   *x^n) - T(x)
*   S(x) = (SUM n>=n0+1  (s[n]-s[n-1]) *x^n  + s[n0])/(1-x)
*   S(x) = (SUM n>=0 (SUM k=0..n s[k]) *x^n) *(1-x)
*   S(x) = INT 0->x (SUM n>=n0 (n+1)*s[n+1]*t^n)*dt
 avec S(x) = SUM n>=n0 s[n]*x^n

Traduction de somme: L'algorithme suivant, qui traduit une forme de
 somme en une forme explicite:
 1. Applique les règles de simplification
 2. Applique les règles de normation
 3. Si il y a une règle de traduction applicable, alors applique-la
 4. Sinon prend un des algorithmes suivants
    // Data-driven
    1. Applique une règle de dénormalisation
    2. Applique les règles de simplification
    3. Applique les règles de normalisation
    4. Applique les règles de traduction
    5. Simplifie l'expression
    // Goal-driven
    1. Choisis la règle de traduction la plus proche
    2. Applique une ou plusieures règles de normalisation à cette
       équation (S(x) est la forme explicite) pour rendre la règle
       encore plus proche
    3. Applique les règles de simplification pour retrouver la somme
       désirée
    4. Applique les règles de traduction aux sommes restantes
    5. Simplifie et résoud l'équivalence pour trouver la forme
       explicite de la somme désirée

Traduction d'expression: L'algorithme suivant, qui traduit une
 expression en plusieures formes de sommes:
 1. Explose l'expression en une somme de termes minimaux
 2. Pour chaqu'un des termes
    3. Factorise les constantes
    4. Factorise les x
    5. Si il y a une règle de traduction applicable, applique-la
    6. Sinon
       7. Applique la décomposition
       8. Traduis chaque terme résultant
    9. FinSi
    10. Applique les règles de normalisation pour se débarrasser des
        eventuels facteurs x^k avant les sommes
 11. FinPour

Calcul d'une somme finie SUM k=1..n f(k): L'algorithme suivant:
 1. Pose (SUM n>=0 f(n)*x^n) /(1-x)
 2. Traduis la somme en sa forme exlicite
 3. Simplifie l'expression
 4. Traduis l'expression en sa forme de somme
 5. La suite réelle de la série génératrice obtenue donne la
    valeur de SUM k=1..n f(k) en fonction de n, car
     (SUM n>=0 f(n)*x^n)/(1-x) = SUM n>=0 (SUM k=0..n f(k)) *x^n

Solution d'une récurrance avec n/2: La transformation d'une forme
 récursive avec l'indice n/2 en une forme explicite. Soit la suite
 t[k]. On procède de la manière suivante:
 1. Écris la relation de récurrance
 2. Pose k=2^n
 3. Remplace tout k par 2^n, simplifie 2^n/2 = 2^(n-1)
 4. Pose a[n] = t[2^n]
 5. Réécris la relation de récurrance avec a[n]
 6. Résoud la récurrance a[n]
 7. Pose t[2^n] = forme explicite de a[n]
 8. Pose n=log2(k)
 9. Remplace tout n par log2(k), simplifie 2^n=k
 Les récurrances suivantes sont déjà résolues:
 * t[n] = 2*t[n/2]+b*n
   t[n] = b*log2(n)*n+n
 * t[n] = a*t[n/2]+b*n
   t[n] = 2*b/(2-a)*n + (1 + 2*b/(a-2)) * n^log2(a)

Solution d'une récurrance avec 2^n: La transformation d'une forme
 récursive avec le terme 2^n en une forme explicite. Soit la suite
 t[n]. On procède de la manière suivante:
 1. Écris la relation de récurrance
 2. Pose a[n] = t[n]*2^n (ou t[n]/2^n) pour éliminer le 2^n
 3. Remplace le t[n] par sa relation de récurrance
 4. Remplace tout t[n-1]*2^n par 2*a[n-1]
 5. Résoud la récurrance a[n]
 6. Calcule t[n] = a[n]/2^n

Fibonacci: La suite réelle f[n] définie par
 f[1]=1
 f[2]=1
 f[n]=f[n-1]+f[n-2]
 f[n]= (((1+sqrt(5))/2)^n - ((1-sqrt(5))/2)^n)/sqrt(5)


=====================================================================
                    Analyse de Programmes
=====================================================================

Règles pour des sommes finies:
 * SUM n=n1..n2 f(n)    = SUM n=0..n2 f(n) - SUM n=0..n1-1 f(n)
 * SUM n=n1..n2 f(n2-n) = SUM n=0..n2-n1 f(n)
 * SUM n=n1..n2 c       = (n2-n1+1)*c
 * SUM k=1..n k         = n*(n+1)/2
 * SUM k=1..n k^2       = n*(n+1)*(2*n+1)/6
 * SUM k=1..n k^3       = (n*(n+1)/2)^2
 * SUM k=1..n (2*k-1)   = n^2
 * SUM k=0..n x^k       = (1-x^(n+1)) / (1-x)
 * SUM k=0..n C(n,k)*x^(n-k)*y^k = (x+y)^n
 * (SUM i=1..n a(i)) * (SUM j=1..m b(j))
   = SUM i=1..n SUM j=1..m a(i)*b(j)
 Plus les règles de simplification

Analyse d'une méthode: L'algorithme suivant, qui détermine la
 complexité de la méthode. Soit le paramètre n.
 1. Si la méthode est récursive avec le cas simple n0,
    alors pose a[n0]=1
 3. Pose a[n]=1
 4. Pour toute action i
    5. Si i est un appel récursif, alors ajoute à a[n] le terme
       "+a[f(n)]", où f(n) est le paramètre actuel en fonction de n
    6. Si i est un appel d'une méthode, alors ajoute sa complexité
       à a[n]
    7. Si i est "for(int j=j1;j<=j2;++j)", alors ajoute
       "+ SUM j=j1..j2 (" à a[n].
    8. Si i est la fin d'une boucle for, alors ajoute ")" à a[n]
 9. FinPour
 10. Remplace tout "SUM j=j1..j2 ()" par "j2-j1+1"
 11. Applique les règles pour les sommes finies pour les éliminer
 12. Résoud la récurrance, si il y en a une
 13. Enlève les constantes de a[n]
 14. a[n] est la complexité de la méthode

Stratégies pour la réduction de la complexité:
 * Diviser pour régner
   On réduit le problème à 2 problemes d'ordre n/2
 * Programmation dynamique
   On stocke les résultats déjà calculés

Programme simple pour Fibonacci:
 public static int fibonacci(int n) {
  if(n<2) return(1);
  return(fibonacci(n-1)+fibonacci(n-2));
 }
 Nombre d'appels:
 a[0]=1
 a[1]=1
 a[n]=a[n-1]+a[n-2]+1
 a[n]=fibonacci(n)*2-1
 a[n]=0.894*1.618^n
 Complexité: O(1,7^n)

Programme avancé pour Fibonacci:
 public static int fibonacci(int n) {
  // Truck: Enregistrer les résultats déjà calculés
  if(n<2) return(1);
  int[] f=new int[n];
  f[0]=1;
  f[1]=1;
  for(int i=2;i<=n;++i) f[i]=f[i-1]+f[i-2];
  return(f[n]);
 }
 Complexité: O(n)
 // On n'a pas besoin du tableau, mais cela ne change pas
 // la complexité

Programme encore plus avancé pour Fibonacci:
 public static int[][] pow(int[][] m, int n) {
  // Élève la matrice m à la puissance n
  // Truck: m^n = (m*m)^(n/2)
  if(n==1) return(m);
  if(n&1==1) return(mult(pow(mult(m,m),n>>1),m));
  else return(pow(mult(m,m),n>>1));
 }
 public static int fibonacci(int n) {
  // Truck: (f[n-1],f[n]) = ( (0,1), (1,1) )^n * (1,1)
  if(n<2) return(1);
  int[][] m={{0,1},{1,1}};
  m=pow(m,n);
  return(m[1][1]);
 }
 Nombre d'appels:
 Ce qui compte est l'appel à pow
 a[n]=1+a[n/2]
 a[n]=log2(n)
 Complexité: O(log2(n))

Programme pour C(n,k):
 public static int c(int n, int k) {
  if(k==0 || k==n) return(1);
  return(C(n-1,k)+C(n-1,k-1));
 }
 Nombre d'appels:
 a[n,n]=1
 a[n,0]=1
 a[n,k]=a[n-1,k]+a[n-1,k-1]+1=2*C(n,k)+1
 Complexité: O(n!/k!/(n-k)!)
 C(n,k) est maximal pour k=n/2, dans ce cas
 a[n,n/2]=2^n/sqrt(n/2*pi)

Programme avancé pour C(n,k):
 public static int c(n,k) {
  // Truck: Utiliser le triangle de Pascal
  int[] a=new int[k];
  a[1]=1;
  for(int y=0;y<n;++y) {
   int v=1;
   for(int x=1;x<Math.min(y,k);++x){
    int w=a[x];
    a[x]+=v;
    v=w;
   }
  }
  return(a[k-1]);
 }
 Complexité: O(n*k)
 Pour le cas k=n/2: O(n^2/2)
 // La méthode du cours utilisait plusieurs tableaux

Problème de la somme maximale: Le problème de trouver dans un tableau
 de n réels la suite dont la somme est la plus grande.

Programme pour la somme maximale:
 public static int[][] sommemaximale(int[] t) {
  int sommemax=Integer.MIN_VALUE;
  int maxi=0;
  int maxj=0;
  for(int i=0;i<t.length;++i) {
   for(int j=i;j<t.length;++j) {
    int somme=0;
    for(int k=i;k<j;++k) somme+=t[k];
    if(somme>sommemax) {
     somme=sommemax;
     maxi=i;
     maxj=j;
    }
   }
  }
  return(new int[]{maxi, maxj})
 }
 Nombre d'actions:
 SUM i=0..n-1 SUM j=i..n-1 (j-i+1) = (n^3+3*n^2+2*n)/6
 Complexité: O(n^3/6)

Programme avancé pour la somme maximale:
 public static int[][] sommemaximale(int[] t) {
  int sommeval=Integer.MIN_VALUE;
  int maxi=0;
  int maxj=0;
  for(int i=0;i<t.length;++i) {
   int somme=0;
   for(int j=i;j<t.length;++j) {
    somme+=t[j];
    if(somme>sommemax) {
     somme=sommemax;
     maxi=i;
     maxj=j;
    }
   }
  }
  return(new int[]{maxi, maxj})
 }
 Nombre d'actions:
 SUM i=0..n-1 SUM j=i..n-1 1 = (n^2+n)/2
 Complexité: O(n^2/2)

Programme encore plus avancé pour la somme maximale:
 public static int sommemaximale(int[] a, int i, int j) {
  // Truck: Diviser le tableau en deux
  // La somme maximale est le maximum de la somme maximale
  // à gauche, à droite et à cheval
  if(i==j) return(a[i]);
  int smax=Integer.MIN_VALUE;
  int s=0;
  for(int k=(i+j)>>1;k>=i;--k) {
   s+=a[k];
   if(s>smax) smax=s;
  }
  for(int k=(i+j)>>1+1;k<j;++k) {
   s+=a[k];
   if(s>smax) smax=s;
  }
  if((s=sommemaximale(a,i,(i+j)>>1))>smax) smax=s;
  if((s=sommemaximale(a,(i+j)>>1+1,j))>smax) smax=s;
  return(smax)
 }
 Nombre d'appels:
 a[0]=0
 a[n]=2*a[n/2]+n
 a[n]=n*log2(n)+n
 Complexité: O(n*log2(n));

Programme encore beaucoup plus avancé pour la somme maximale:
 public static int sommemaximale(int[] a) {
  // Truck: Compter linéairement
  int s=0;
  int smax=Integer.MIN_VALUE;
  for(int i=0;i<a.length;++i) {
   s+=a[k];
   if(s>smax) smax=s;
   if(s<0) s=0;
  }
  return(smax)
 }
 Complexité: O(n);

Problème de la multiplication: Le problème de calculer le produit
 de deux entiers, dont le nombre de chiffres est énorme. Soit n un
 grand entier participant à la multiplication, soit b la base et
 alors m=ln(n)/ln(b). Il y a plusieures approches:
 * Les additions successives: O(n*ln(n)/ln(b)) = O(m*b^m)
 * La méthode de l'école primaire: O(ln(n)^2/ln(b)^2) = O(m^2)
 * L'algorithme de Karatsuba: O(m^1.5)

Algorithme de Karatsuba: Un algorithme pour la multiplication de grands
 entiers, qui base sur le fait que
  a*b = a1*b1*10^m + (a1*b1+a0*b0-(a1-a0)*(b1-b0))*10^(m/2)+a0*b0
 où
 * a et b sont les entiers à multiplier
 * b est la base
 * m est le nombre de chiffres
 * a = a1*10^(m/2) + a0
 * b = b1*10^(m/2) + b0

Problème de la multiplication de matrices: Le problème de calculer
 le produit de deux matrices carrées d'ordre n. Il y a deux approches:
 * La méthode classique: O(n^3)
 * L'algorithme de Strassen: O(n^2.8)

Algorithme de Strassen: Un algorithme pour la multiplication de
 matrices, qui divise les matrices en 4 sous matrices, calcule 7
 petites matrices supplémentaires et assemble le résultat à partir
 de ces petites matrices.