1. Connexité
2. Algorithmes avec matrices de connexion
3. Plus court chemin
4. Exploration
5. de Java vers C
6. Gestion de la mémoire
7. Exercices

let rec chemin d s =
  num.(d) <- true; 
  let p = ref [] in
  List.iter (function x -> 
      if x = s then p := [s];
      if not num.(x) && !p = [] then 
        p := chemin x s)
     graphe.(d);
  if (!p = []) || (d = s) then !p else d :: !p;;

static ListeNoeuds chemin (int d, int s) {
  num[d] = true; 
  for (ListeNoeuds y = graphe[d]; y != null; y = y.suivant) {
    int x = y.nom;
    if (x == s)
        return new ListeNoeuds (s, null);  
    if (!num[x]) {
        ListeNoeuds p = chemin x s;
        if (p != null)
            return new ListeNoeuds (d, p);
    }
  }
  return null;
}

let min = ref nMax;;

let rec visit k = 
  incr id; num.(k) <- !id; min := !id;
  List.iter (function x -> 
      if num.(x) = -1 then begin
        let m = visit x in
        if m < !min then min := m;
        if m >= num.(k) then printf "%d " k
      end else
      if num.(x) < !min then min := num.(x))
     graphe.(k);
  !min;;

---

Composantes fortement connexes

Dans un graphe non orienté, on calcule facilement la connexité. Mais dans un graphe orienté? Commne trouver les composantes fortement connexes? Ie les parties où toute paire de noeuds distincts est reliée par un chemin.

---

Points d'attache

Dans le ch5 du poly, on décrit la notion de point d'attache dans un graphe:

let rec cf_connexe k = 
    incr id; num.(k) <- !id; 
    Pile.empiler k p;
    let min = ref !id in
      List.iter (function x ->
          let m = if num.(x) = -1 then cf_connexe (x) else num.(x) in
          if m < !min then
            min := m)
        graphe.(k);
      if !min = num.(k) then 
        (try while true do
           printf "%d " (Pile.sommet p);
           num.(Pile.sommet p) <- nMax;
           Pile.depiler p;
           if Pile.sommet p = k then raise Exit
           done
         with Exit -> printf "\n");
      !min;;

let fermeture_transitive m =
  let r = Array.copy m and n = Array.length m in
  for k = 0 to n - 1 do
    for i = 0 to n - 1 do
      for j = 0 to n - 1 do
          r.(i).(j) <- r.(i).(j) || (r.(i).(k) && r.(k).(j));
      done;
    done;
  done;
  r;;

let plus_courts_chemins m =
  let r = Array.copy m and n = Array.length m in
  for k = 0 to n - 1 do
    for i = 0 to n - 1 do
      for j = 0 to n - 1 do
          r.(i).(j) <- min (r.(i).(j),  (r.(i).(k) + r.(k).(j)));
      done;
    done;
  done;
  r;;

let rec hamiltonien k s =
  incr id; num.(k) <- !id; 
  let p = ref [] in
  List.iter (function x -> 
      if num.(x) = 0 && num.(k) = nMax - 1 then p := [s];
      if num.(x) = -1 && !p = [] then 
        p := hamiltonien x s)
     graphe.(k);
  decr id; num.(k) <- -1;
  if (!p = []) || (!p = [s]) then !p else k :: !p;;

let nReines n =
  let pos = Array.make n 0 in
  let conflit i1 j1 i2 j2 = i1 = i2 || j1 = j2 ||
                            abs(i1 - i2) = abs (j1 - j2) in
  let compatible i j =
    try for k = 0 to i-1 do
      if conflit i j k pos.(k) then raise Exit
    done;
    true with Exit -> false in

  let rec reines i = if i >= n then 
      imprimerSolution pos
    else
      for j = 0 to n-1 do
        if compatible i j then begin pos.(i) <- j; reines (i+1) end
      done in
  reines 0;;

• Les données dans la mémoire d'un ordinateur. Arc d'une donnée à une autre s'il existe une référence de l'une vers l'autre. Ainsi des listes, des arbres correspondent à des graphes.
  
  Le glaneur de cellule (GC) parcourt ce graphe pour détecter les données inaccessibles, et donc récupérables.
  
  
• Le graphe des appels de procédures dans un programme. Un arc entre deux procédures si une appelle l'autre.
  
  
• Le graphe (non dirigé) des durée de vie des variables. Deux variables ont un arc entre elles ssi elles existent simultanément.
  
  
• Le graphe de dépendances entre modules pour refabriquer un paquetage. (Données des makefile).
  
  
• etc.

int t[10];   /* tableau de 10 entiers */

struct {                    /* cellule de liste */
   int contenu;
   struct liste *suivant;   /* adresse d'une cellule de liste */
} liste;
struct liste *a, *b;
typedef struct liste *Liste;
Liste c, d;

int x;
int *p = &x;     /* l'adresse de x est rangée dans p */
int y = *p;      /* le contenu de ce qui est pointé par p est mis dans y */

Liste nouvelleListe (int x, Liste a) 
{
   Liste b = (Liste) malloc (sizeof (struct liste));
   b -> contenu = x;
   b -> suivant = a;
   return b;
}

• algorithmes géométriques
• algorithmes semi numériques (FFT)
• NP complétude
• algorithmes probabilistes
• asynchronisme (fortement ou faiblement couplé)
• programmation objet

• majeure math-info
  
  
• majeure d'informatique
  
  
• DEA (par exemple, Algo ou SPP)
  
  
• recherche en informatique = un des domaines scientifiques les plus actifs du moment

• Calculer les composantes connexes dans un graphe non orienté
  
  
• Sortie de labyrinthe

This document was translated from L^AT_EX by H^EV^EA.