Plan

1. piles
2. graphes
3. depth first search
4. Arbres de recouvrement
5. breadth first search
6. connexité dans un graphe non orienté
7. composantes fortement connexes
8. plus court chemin
9. exercices

Piles

C'est un mécanisme général: récursion = itération + pile, qui est à l'origine de la compilation des langages évolués (FORTRAN, ALGOL) en programmes itératifs (assembleur). Dans notre cours, nous préférons l'écriture récursive qui nous semble plus naturelle.

Une pile se représente par un tableau ou une liste (cf ch3 du poly) dont l'interface serait:

type 'a pushdown_stack;;
value make_pushdown_stack: unit -> 'a pushdown_stack;;
value push : 'a -> 'a pushdown_stack -> unit;;
value pop : 'a pushdown_stack -> 'a;;
value top : 'a pushdown_stack -> 'a;;

type 'a pushdown_stack == 'a list ref;;

let make_pushdown_stack() = ref [ ];;

let push x p = p := x :: !p;;

let pop p = match !p with
   [ ] -> failwith "pile vide"
 | x :: p1 -> begin p := p1; x end;;

let top p = match !p with
   [ ] -> failwith "pile vide"
 | x :: p1 -> x;;

Makefiles

tty: tty.zo files-de-caracteres.zo
        camlc -o tty tty.zo files-de-caracteres.zo

tty.zo: tty.ml files-de-caracteres.zi
        camlc -c tty.ml

files-de-caracteres.zo: files-de-caracteres.ml files-de-caracteres.zi
        camlc -c files-de-caracteres.ml

files-de-caracteres.zi: files-de-caracteres.mli
        camlc -c files-de-caracteres.mli

Interfaces avec C et Tk

Declaring primitives

value input : in_channel -> string -> int -> int -> int
            = 4 "input"

Values thus declared primitive in a module interface must not be implemented in the module implementation (the .ml file). They can be used inside the module implementation.

Implementing primitives

value input(channel, buffer, offset, length)
        value channel, buffer, offset, length;
{
    ...
}

Graphes

Un graphe G=(V,E) a un ensemble de sommets V et d'arcs E dans VxV. Un arc v=(n_1,n_2) a pour origine org(v) = n_1 et pour extrémité ext(v) = n_2. Un exemple est le plan des rues de Paris ou le plan du métro.

G=(N,V) est un graphe non orienté ssi (n_1,n_2) dans V implique (n_2,n_1) dans V. Par exemple, les couloirs de l'X.

Un chemin est une suite d'arcs v_1, v_2, ... v_n, telle que n >= 0, org(v_{i+1}) = ext(v_{i}) pour 1 <= i < n. Un circuit est un chemin où ext(v_{n}) = org(v_{1}). Dans un graphe non orienté, un circuit est aussi appelé un cycle. Un arbre est donc un graphe orienté sans cycle, mais il existe des graphes orienté sans cycles plus généraux (dag).

On peut représenter un arbre par sa matrice de connexion M, où m_{i,j}=1 ssi (n_i,n_j) est un arc du graphe. La matrice de connexion d'un graphe non orienté est donc symétrique.

let nMax = 100;;
let graphe = make_matrix nMax nMax false;;
let mk_arc i j = graphe.(i).(j) <- true;;

let graphe = make_vect nMax [];;
let mk_arc i j = graphe.(i) <- j :: graphe.(i);;

Profondeur d'abord, Depth-First Search

R. Tarjan (1972) a montré que c'était une méthode très utile sur les graphes.

let val = make_vect (vect_length graphe) (-1);;

let id = ref (-1);;

let rec dfs k = begin
    incr id;
    val.(k) <- !id;
    do_list 
      (function  x -> if val.(x) = -1 then
            dfs (x))
      graphe.(k)
    end;;

let dfs_all() = begin
  fill_vect val 0 (vect_length graphe) (-1);
  do_vect 
    (function x -> if val.(x) = -1 then
         dfs (x))
    val
  end;;

Arbres de recouvrement

1. d'un noeud de l'arbre à un de ses fils dans l'arbre
2. d'un noeud de l'arbre à un des ses ancètres dans l'arbre
3. d'un noeud de l'arbre à un de ses descendants non direct dans l'arbre
4. d'un noeud à un de ses cousins dans l'arbre

Largeur d'abord, Breadth-First Search

let bfs k = 
    let q = make_emptyQ in begin
    enQ k q;
    while not (is_emptyQ q) do
        let k = deQ (q) in begin
        incr id;
        val.(k) <- !id;
        do_list 
          (function  x -> if val.(x) = -1 then
               begin
               enQ x q;
               val.(x) <-  0
               end)
          graphe.(k)
        end
    done
    end;;

let bfs_all() = begin
  fill_vect val 0 (vect_length graphe) (-1);
  do_vect 
    (function x -> if val.(x) = -1 then
         bfs (x))
    val
  end;;

Quelques problèmes standards

Test de non-cyclicite' dans un graphe orienté.

Tri topologique dans un dag. Par exemple, ce dag représente un système de dépendances (par exemple Makefiles en Unix). Il faut donner l'ordre dans lequel on doit réaliser les opérations, ie trier les noeuds dans un ordre cohérent avec les inverses des arcs.

Planarité (Tarjan). Dessiner un graphe sur un plan.

Connexité dans un graphe non orienté. Problème du labyrinthe.

Trouver un arbre de recouvrement minimum (avec des poids sur les arcs).

Plus court chemin sur les graphes (avec des poids sur les arcs).

Bi-connectivité

Dans un graphe non orienté, existe-t-il 2 chemins différents entre toute paire de noeuds? Un point d'articulation est un point qui sépare le graphe en parties non connexes si on l'enlève. Un graphe sans point d'articulation est un graphe bi-connexe. La procédure suivante retourne le plus petit noeud accessible depuis tout noeud dans l'ordre d'une dfs.

let rec Visit k = begin
    incr id; val.(k) <- !id; 
    let min = ref !id in begin
      do_list
        (function x ->
         if val.(x) = -1 then begin
             let m = Visit (x) in begin
             if m < !min then
                 min := m;
             if m >= val.(k) then
                 printf "%d " k
             end
         end else
         if val.(x) < !min then
             min := val.(x))
        graphe.(k);
      !min
      end
    end;;

Le test de bi-connectivité d'un graphe G=(V,E) se fait donc linéairement sur le temps d'une dfs, ie en O(V+E).

Composantes fortement connexes

Dans un graphe non orienté, on teste facilement la connexité. Mais dans un graphe orienté? La procédure ci-dessous trouve les composantes fortement connexes, ie les parties dont tte paire de noeuds distincts est reliée par un chemin.

let rec Visit k = begin
    incr id; val.(k) <- !id; 
    push k p;
    let min = ref !id in begin
      do_list
        (function x ->
          let m = if val.(x) = -1 then 
                Visit (x) 
            else 
                val.(x) 
            in if m < !min then
                min := m)
         graphe.(k);
      if !min = val.(k) then 
        (try while true do
            printf "%d " (top(p));
            val.(top(p)) <- nMax;
            pop(p);
            if top(p) = k then raise Exit
            done
        with Exit -> printf "\n");
      !min
      end
    end;;

Plus courts chemins

G=(V,E) est munie d'une fonction de valuation sur les arcs w: E -> R. Chaque arc a un poids réel. On veut trouver le plus court chemin entre 2 noeuds donnés.

Il existe une grande différence entre le plus court chemin entre 2 points et le plus court chemin entre tous les points.

Le premier se résoud par une exploration bfs avec une file de priorité: algorithme de Dijkstra en O() si les poids sont tous positifs, algorithme de Ford-Bellman en O() si les poids peuvent être négatifs avec une méthode dite de programmation dynamique.

Le deuxième se résoud par des multiplications de matrices. Le plus court chemin ne pouvant pas avoir plus que card(V) étapes. En O(V^4), on peut faire l'opération matricielle suivante:

d^{n+1}_{i,j} = min(d^n_{i,j}, min_k(d^n_{i,k}+d^n_{k,j}))
d^1_{i,j} = w_{i,j} si existe, infini sinon

On peut réduire ce coût en couplant récurrence sur les noeuds et sur la longueur. Ainsi, en O(V^3), on obtient

d^{k+1}_{i,j} = min_k(min(d^k_{i,j}, d^k_{i,k}+d^k_{k,j}))
d^0_{i,j} = w_{i,j} si existe, infini sinon

On en déduit l'algorithme de Floyd-Warshall pour calculer la fermeture transitive d'un graphe.

Problèmes non traités

Le cours n'est qu'une introduction aux méthodes algorithmiques et à la programmation. Il contient 2 cours habituels dans un cursus normal d'université: programmation et structures de données élémentaires, introduction à l'algorithmique. Les 2 parties peuvent se décliner plus longuement vers la logique et la validation de programme, ou vers la complexité et l'analyse de performances.

Nous n'avons même pas vu qques classiques:

NP complétude

compression

algorithmes probabilistes

algorithmes géométriques

algorithmes semi numériques (FFT)

asynchronisme (fortement ou faiblement couplé)

temps-réel

Majeure de Mathématiques et Informatique (M1)

Deux modules communs:

Calculs et Preuves (J. Stern)

Architecture du calcul (J. Vuillemin)

Un module au choix :

Codes correcteurs (M. Demazure)

Imagerie tridimensionnelle (C. Puech & F. Sillion)

Un enseignement dčapprofondissement au choix :

Arithmétique et cryptographie (F. Morain)

Calculs symboliques (M. Giusti)

Composants programmables (P. Bertin & J.-Y. Parey)

Images: analyse et synthèse (P. Chassignet & F. Sillion)

Interprète Scheme réparti (C. Queinnec)

Majeure dčInformatique (M2)

Quatre modules communs :

Algorithmique et problèmes NP (R. Cori & J.-M. Steyaert)

Langages et compilation (P. Cousot & M. Jourdan)

Structures de la programmation (J.-J. LŽ evy & C. Queinnec)

Systèmes dčexploitation et réseaux dčordinateurs (P. Cousot)

Un module au choix :

Bases de données (S. Abiteboul, J.-M. Steyaert)

Calcul parallèle (P. Cousot & A. Bamberger)

Programmation logique par contraintes (F. Fages)

Enseignements techniques associés :

Programmation en ML

Utilisation dčUnix

Exercices en TD

trouver les ponts dans un graphe non orienté

sortie de labyrinthe

le pb des 8 reines