Planche: 1
PC2
Jean-Jacques.Levy@inria.fr
http://www.polytechnique.fr/poly/~levy/
INRIA -- Rocquencourt
tel: 01 39 63 56 89


secrétariat: Catherine Bensoussan
cb@lix.polytechnique.fr
Aile 00, LIX
tel: 54 67

http://w3.edu.polytechnique.fr/informatique/

Planche: 2
Plan

  1. Un peu de Java
  2. Un peu de ML
  3. Tableaux
  4. Tri élémentaire
  5. Graphique
  6. Tri animé
  7. Tri Shell
Planche: 3
Types de données

Primitifs: booléens; numériques
boolean; byte, short, int, long, char, float, double

Références: classes, tableaux, nulle

Objet: instance d'une classe ou d'un tableau. Les objets sont aussi tous instances de la classe générale Object.

Object £ T pour toute classe T (T est une sous-classe de Object)

Une variable de type T primitif contient des valeurs de type T.

Une variable de type classe T contient la référence nulle ou une référence vers un objet de type U ³ T.

Une variable de type tableau de T contient la référence nulle ou une référence vers tout tableau de U ³ T.

Une variable de type Object contient la référence nulle ou une référence vers un objet ou vers un tableau.

Planche: 4
Constantes 

true  false
123  'a'  12.5  314.59e-2  0.27E10}
null
Opérateurs 

=     >     <     !     ~     ?     :

==    <=    >=    !=    &&    ||    ++    --

+     -     *     /     &     |     ^     %     <<    >>    >>>

+=    -=    *=    /=    &=    |=    ^=    %=    <<=   >>=   >>>=
Planche: 5
Variables et durée de vie

Variable de classe (avec le mot-clé static), créée quand la classe est chargée, disparait quand la classe est déchargée.

Variable d'instance (sans le mot-clé static), créée avec l'objet dont elle est un champ, disparait avec l'objet quand il n'est plus référencé.

Elément d'un tableau, créé avec le tableau et disparait quand il n'est plus référencé.

Paramètre de fonctions/méthodes, créé à l'appel de la méthode, prend la valeur de l'expression passée, disparait à la fin de l'exécution de la méthode.

Paramètre de traitement d'exception, créé quand l'exception est attrapée par catch, disparait à la fin du traitement de l'exception.

Variable locale: créée quand on exécute la déclaration, disparait à la fin du bloc correspondant.

Planche: 6
Exemples 

class Date {

  int    j; // jour       j, m, a variables d'instance
  int    m; // mois       
  int    a; // annee      

  Date (int jour, int mois, int annee) {
    j = jour;          // jour, mois, annee, paramètres
    m = mois;
    a = annee;         // equals, toString variables d'instance
  }
  
  public boolean equals (Date d) {
    return j == d.j && m == d.m && a == d.a;
  }

  public String toString () {
    return j + "/" + m + "/" + a;
  }
Planche: 7
Tableaux 

int a[] = new int[20];
int lg = a.length;

static void initialisation (int a[]) {
  for (int i = 0; i < a.length; ++i)
      a[i] = (int) (Math.random() * 100);
}

int[] b = new int[20];  écriture aussi autorisée
a[i] pour obtenir le i+1ème élément de a
a[i] = v pour le modifier.

Les tableaux à 2 dimensions sont des tableaux 1D de tableaux 1D, avec la facilité d'écriture.

int a[][] = new int[20][20];
Planche: 8
Types de données en ML

Primitifs: booléens, numériques, caractères, vide
boolean; int, float, char, unit

Non primitifs: n-uplets, enregistrements, variants, tableaux

Constantes 

true  false
123  12.5  314.59e-2  0.27E10  'a'  ()

[| 1;2  |]   {x=20; y=10}    [ 1;2;3 ]   (1,2)
tableaux, enregistrements, listes, paires

Planche: 9
Opérateurs 

+    *    /    mod  +.   -.   *.   /.   entiers, flottants
land lor  lsl  lsr  lxor      
||   &&   <    <=   <>   =    >    >=   <.   <=.  <>.  =.   >.   >=.    
::   @    ==   !=   :=   !    ^
La fonction associée à un opérateur s'obtient en tapant l'opérateur entre parenthèses. Son type est obtenu par:

(||) ;;
- : bool -> bool -> bool = <fun>
(=) ;;
- : 'a -> 'a -> bool = <fun>
où 'a (lire a) est une variable de type. (Le type de = est dit polymorphe)

Le modificateur <- est une construction syntaxique (et non un opérateur).

Planche: 10
Enregistrements

On déclare le type d'un enregistrement. 

type date = {j: int; m: int; d: int};;
let bastille = {j=14; m=7; a=1789};;
let berlin = {j=11; m=11; a=1989};;
berlin.j, berlin.m, berlin.a pour obtenir les champs.
(On peut aussi utiliser le filtrage qu'on verra plus tard).
bastille.j <- 13 pour modifier un champ modifiable.

Un exemple d'enregistrement avec un champ modifiable est celui des références (au sens de ML):

type 'a ref = { mutable contents: 'a }
ref, !, :=, incr, decr pour construire, accèder au contenu, ou modifier le contenu d'une variable de type 'a ref

Exercice: donner la définition de ref, !, :=, incr, decr.

Planche: 11
Tableaux 

let a = Array.make 20 0;;
let lg = Array.length a;;

let initialisation a =
  for i = 0 to Array.length a - 1 do
     a.(i) <- Random.int 100;
  done;;

let a = Array.init 20 (function i -> Random.int 100);;
a.(i) pour obtenir le i+1ème élément de a
a.(i) <- v pour le modifier.

Array.make_matrix 10 10 0 crée une matrice 100× 100 remplie de zéros.

Planche: 12
Tri

Un tableau contient N nombres ai (0 £ i <N), on veut les trier dans l'ordre croissant (" i  " j    i<j Þ ai < aj).

La bible: Knuth vol3, Sorting and Searching, The art of Computer Programming, Addison Wesley 1973.

Tri sélection
Tri bulle
Tri insertion
Tri Shell
QuickSort
Tri Fusion
Tri par tas
Tri des mécanographes (radix)
...

Autrefois (années 60), il y avait des trieuses. IBM.

Exercice: trouver une ou deux méthodes

Planche: 13
Recherche du minimum dans un tableau 

static int min (int a[]) {
    r = Integer.MAX_VALUE;
    for (i=0; i < a.length; ++i)
        if ( a[i] < r )
            r = a[i];
    return r;
}




let min a = 
  let r = ref max_int in
  for i=0 to Array.length a - 1 do
      if a.(i) < !r  then
          r := a.(i)
  done;
  !r;;
On fait N comparaisons (si N est la longueur du tableau). Le nombre total d'opérations est O(N). Cet algorithme est linéaire (en temps), il a une complexité linéaire.

Planche: 14
Le tri par insertion 

let tri_insertion a =
 let j = ref 0 in
 for i = 1 to Array.length a - 1 do
   let v = ref a.(i) in
      begin
      j := i;
      while !j > 0 && a.(!j - 1) > !v do
        a.(!j) <- a.(!j - 1);
        decr j
      done;
      a.(!j) <- !v;
      end
 done;;
val tri_insertion : 'a array -> unit = <fun>
Complexité?

Planche: 15
Le tri par insertion en Java 

static void triInsertion(int a[]) {

  int   j, v;
  for (int i = 1; i < N; ++i) {
      v = a[i]; j = i;
      while (j > 0  &&  a[j-1] > v) {
          a[j] = a[j-1]; 
          --j;
      }
      a[j] = v;
  }
}
Complexité?

Planche: 16
Le tri Shell [D. L. Shell 1959] 

static void triShell() {

  int h = 1; do h = 3*h + 1; while ( h <= N );
  do {
      h = h / 3;
      for (int i = h; i < N; ++i)
          if (a[i] < a[i-h]) {
              int   v = a[i], j = i;
              do {
                  a[j] = a[j-h];
                  j = j - h;
              } while (j >= h  &&  a[j-h] > v);
              a[j] = v;
          }
  } while ( h > 1);
}
Pas plus que O(N3/2) comparaisons !!
Bon pour de gros fichiers (celui du noyau Maple)

Planche: 17
Quelques primitives graphiques 

  // constantes graphiques
  static int epsilonX, epsilonY, pasX, pasY, x0, y0;
  static int background, foreground, hilite, hilite2;
  static MacLib gc;

static void ouvrirGraphique (int n, int valeurMax) {

  Rect r = new Rect();
  gc = new MacLib();
  gc.initQuickDraw();

  int sizeX = Math.min(500, (n+5) * 10);
  int sizeY = Math.min(400, (valeurMax+5) * 5);
  r.left = 10; r.right = (short)(r.left + sizeX);
  r.top = 10; r.bottom = (short)(r.bottom + sizeY);
  gc.setDrawingRect(r);

  epsilonX = Math.max(7, sizeX / (n + 3));
  epsilonY = Math.max(20, sizeY / valeurMax);
  pasX = Math.max (1, (sizeX - 2 * epsilonX) / n);
  pasY = Math.max (1, (sizeY - epsilonY) / valeurMax);
  x0 = epsilonX; y0 = sizeY - epsilonY;

  foreground = gc.redColor;   background = gc.Whitecolor;
  hilite = gc.blueColor;   hilite2 = gc.yellowColor;
}
Planche: 18
Graphique en Java -- suite 

static void tracerElement (int v[], int i, int color) {
  int xi = x0 + i * pasX;
  int yi = y0 - v[i] * pasY;
  gc.foreColor (color);

  Rect r = new Rect();
  gc.setRect(r, xi, yi, xi+pasX, y0);
  gc.paintRect (r);
}
La documentation sur Maclib se trouve en Informations diverses sur la page Web du cours http://w3.edu.polytechnique.fr/informatique/

Cette bibliothèque est une version simplifiée de AWT. En outre, elle est compatible avec la même bibliothèque en C, Pascal ou ML; elle existe sur stations Unix et sur MacIntosh.

Planche: 19
Graphique en Caml 

open Graphics;;
type repere = {x0:int; y0:int; pas_x: int; pas_y: int;
               epsilon_x: int; epsilon_y: int};;

let hilite = blue and  hilite2 = yellow;;
let bg = background and fg = red;;

let ouvrirGraphique n valeurMax = 
  open_graph "";
  let e_x = max 7 (size_x() / (n+3)) in
  let e_y = max 20 (size_y() / valeurMax) in
  {x0 = e_x;
   y0 = e_y;
   pas_x = max 1 ((size_x() - 2 * e_x) / n);
   pas_y = max 1 ((size_y() - e_y) / valeurMax);
   epsilon_x = e_x;
   epsilon_y = e_y};;
Planche: 20
Graphique en Caml -- suite 

let tracerElement xy v i color =
  let xi = xy.x0 + i * xy.pas_x in 
  let yi = v.(i) * xy.pas_y in
  set_color color;
  fill_rect xi xy.y0 xy.pas_x yi;;
La documentation sur le graphique de Caml se trouve dans le manuel utilisateur en ligne que l'on trouve en Informations diverses sur la page Web du cours http://w3.edu.polytechnique.fr/informatique/

Planche: 21
Exercices en TD

This document was translated from LATEX by HEVEA.