1. Premier programme
2. Rappels de Java
3. Tri sélection
4. Tri par insertions
5. Recherche linéaire
6. Hachage et listes de collisions
7. Hachage à adressage ouvert

class PremierProg {
    public static void main (String args[ ]){
        System.out.println ("Bonjour les forts!");
        System.out.println ("fib(20) = " + fib(20));
    }

    static int fib (int n) {
        if (n <= 1) return 1;
        else return fib (n-1) + fib (n-2);
    }
}

javac PremierProg.java

java PremierProg

• déclaration t    x₁ = e₁, x₂ = e₂, ... x_n = e_n;
  
  
  • Octets (8 bits) byte
  • Entiers courts (16 bits) short
  • Entiers (32 bits) int
  • Entiers longs (64 bits) long
  • Réels (32 bits) float
  • Réels longs (64 bits) double
  • Caractères (16 bits) char
  • Booléens boolean
  
  
• Conversions implicites:
  byte ® short ® int ® long ® float ® double
  char ® int
  
  
• Conversions explicites: (t) e

• x = e;
  
  
• { inst₁ inst₂ ... inst_n } où inst₁, inst₂, ...inst_n sont des instructions quelconques (n ³ 0).
  
  
• if (e) instruction
• if (e) instruction₁ else instruction₂
  
  
• while (e) instruction
• for (affectation₁; e; affectation₂) instruction
  
  
• return e;

• déclarations: 2 notations sont tolérées. (Nous préférerons la 1ère; la seconde est pour les fanas C ou C++).
  
  
  • type[ ] nom_du_tableau;
    
    
  • type nom_du_tableau[ ];
  
  
• int[ ] x = {1, 4, 9, 16, 25, 36, 49 };
  
  
• int[ ] x = new int [7];   (7 zéros)
  
  
• x[i] pour le i+1^ème élément
  
  
• x[i] = e; pour modifier le i+1^ème élément
  
  
• x.length est la longueur du tableau x
  
  
• la valeur d'un tableau est l'adresse de l'objet qui le représente.

class PremierProg {
    public static void main (String args[ ]){
       if (args.length != 1)
          System.out.println ("Mauvais nombre d'arguments.");
       else {
          int n = Integer.parseInt (args[0]);
          System.out.println (fib(n));
       }
    }

    static int fib (int n) {
        if (n <= 1) return 1;
        else return fib (n-1) + fib (n-2);
    }
}

static int[ ] tableauAleatoire (int n) {
  int a[ ] = new int[n];
  for (int i = 0; i < a.length; ++i)
      a[i] = (int) (Math.random() * 100);
  return a;
}

static void imprimer (int[ ] a) {
  for (int i = 0; i < a.length; ++i)
    System.out.print(a[i] + " ");
  System.out.println();
}

class TableauIO {
    public static void main (String args[ ]){
       if (args.length != 1)
          System.out.println ("Mauvais nombre d'arguments.");
       else {
          int n = Integer.parseInt (args[0]);
          int[] a = tableauAleatoire (n);
          imprimer (a);
       }
    }

    static int[ ] tableauAleatoire (int n) {
      int a[ ] = new int[n];
      for (int i = 0; i < a.length; ++i)
          a[i] = (int) (Math.random() * 100);
      return a;
    }

    static void imprimer (int[ ] a) {
      for (int i = 0; i < a.length; ++i)
        System.out.print(a[i] + " ");
      System.out.println();
    }

}

• Une classe = un ensemble de variables et de fonctions
  
  
• class identificateur { liste_d'instructions }
  
  
• C.f pour désigner la fonction f de la classe C
  Math.random, Integer.parseInt
  
  
• C.x pour désigner la variable x de la classe C
  Integer.MIN_VALUE, Integer.MAX_VALUE, Float.NaN,
  Byte.MIN_VALUE, Byte.MAX_VALUE,
  System.out, System.err, System.in
  
  
• le nom de la classe est facultatif pour référencer une variable ou une fonction de la classe courante.

• par défaut, on accède aux champs des classes du répertoire courant ("paquetage courant"),
  
  
• on ne peut accéder qu'aux champs publics d'une classe figurant dans un autre paquetage (public).
  
  
• il y a des restrictions d'accès pour les champs déclarés privés (private).

• Les classes sont aussi des types de données
  
  
• Les objets sont les valeurs de type classe.

  class Date {
  
    int    j; // jour    
    int    m; // mois       
    int    a; // annee      
  }
  
  class BogueVirtuel {
    public static void main (String[ ] args) {
  
      Date an0 = new Date();
      an0.j = 1; an0.m = 1; an0.a= 1970;
  
      Date an2000 = new Date();
      an2000.j = 1; an2000.m = 1; an2000.a= 2000;
      
      System.out.println (an0.j + "/" + an0.m + "/" + an0.a);
      System.out.println (an2000.j + "/" + an2000.m + "/" + an2000.a);
    }
  }

• C o;   pour déclarer l'objet o de classe C
  String s; Date s;
  
  
• o.f   pour désigner la méthode f de l'objet o
  s.charAt, s.compareTo, System.out.println, System.err.println
  
  
• o.x   pour désigner le champ x de l'objet o
  d.j, d.m, d.a

• un constructeur est une fonction anonyme (non statique) que l'on peut déclarer dans toute classe et qui retourne un nouvel objet de cette classe.
  
  
• un champ (non statique) correspond à une case mémoire différente pour tout objet instance de cette classe. On peut l'initialiser à la création de l'objet avec un constructeur.

class Date {
  int    j,  m,  a; 

  Date (int jour, int mois, int annee) {
    j = jour; m = mois; a = annee;
  }
      ...
      Date an0 = new Date (1, 1, 1970);
      Date an2000 = new Date (1, 1, 2000);
      ...
    }
}

• dans un constructeur, this désigne l'objet en cours de construction. Son utilisation est facultative quand le contexte n'est pas ambigu.

class Date {
  int    j,  m,  a; 

  Date (int jour, int mois, int annee) {
    this.j = jour; this.m = mois; this.a = annee;
  }
      ...
      Date an0 = new Date (1, 1, 1970);
      Date an2000 = new Date (1, 1, 2000);
      ...

    this = new Date();

    return this;

• un champ static n'existe qu'en un seul exemplaire pour toute la classe.
  
  
• Les méthodes ou champs statiques peuvent être indifféremment écrits sour la forme o.f, o.x ou C.f, C.x (La deuxième manière étant plus claire).

class Date {
  int    j,  m,  a; 
  static int instances = 0;

  Date (int jour, int mois, int annee) {
    j = jour; m = mois; a = annee; ++instances;
  }

  static Date an0 = new Date (1, 1, 1970);
  static Date an2000 = new Date (1, 1, 2000);
  static Date berlin = new Date (10, 11, 1989);
}

• la valeur d'un objet est son adresse.

class Date {
  ...  
  public boolean equals (Date d) {
    return j == d.j && m == d.m && a == d.a;
  }

  public String toString () {
    return j + "/" + m + "/" + a;
  }
}

class Date {
  ...  
  public boolean equals (Date d) {
    return this.j == d.j && this.m == d.m && this.a == d.a;
  }

  public String toString () {
    return this.j + "/" + this.m + "/" + this.a;
  }

ForStatement:
        for ( ForInitopt ; Expressionopt ; ForUpdateopt )
                Statement

ForInit:
        StatementExpressionList
        LocalVariableDeclaration

ForUpdate:
        StatementExpressionList

StatementExpressionList:
        StatementExpression
        StatementExpressionList , StatementExpression

StatementExpression:
        Assignment
        PreIncrementExpression
        PreDecrementExpression
        PostIncrementExpression
        PostDecrementExpression
        MethodInvocation
        ClassInstanceCreationExpression

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

• n comparaisons (si n est la longueur du tableau)
  
  
• nombre total d'opérations est O(n)
  (algorithme linéaire en temps),
  Il a une complexité linéaire.

• On cherche l'emplacement du minimum de a,
  
  
• On échange l'élément de tête de a avec le minimum
  
  
• On recommence sur le tableau moins le premier élément, ...tant que le tableau à traiter n'est pas vide.

• pour échanger les valeurs de deux variables, on effectue une permutation circulaire avec une troisième variable (auxiliaire).

  int x = 1, y = 2;

  int aux = x;
  x = y;
  y = aux;

static void triSelection (int[ ] a) {
    int   i_min, t;

    for (int i = 0; i < a.length - 1; ++i) {
        i_min = i;
        for (int j = i+1; j < a.length; ++j)
           if (a[j] < a[i_min])
               i_min = j; 
        t = a[i_min]; a[i_min] = a[i]; a[i] = t;
    }
}

• n² comparaisons (si n est la longueur du tableau)
  
  
• nombre total d'opérations est O(n²)
  (algorithme quadratique en temps),
  Il a une complexité quadratique.

static void triInsertion (int[ ] a) {
  int   j, v;

  for (int i = 1; i < a.length; ++i) {
      v = a[i]; j = i;
      while (j > 0  &&  a[j-1] > v) {
          a[j] = a[j-1]; 
          --j;
      }
      a[j] = v;
  }
}

• I(a) comparaisons (le nombre d'inversions dans a)
  
  
• nombre total d'opérations est O(n²) dans le cas pire
  (algorithme quadratique en temps),
  Il a une complexité quadratique.
  
  
• bon quand a est presque trié.

static void triShell (int[ ] a) {

  int h = 1; do h = 3*h + 1; while ( h <= a.length );
  do {
      h = h / 3;
      for (int i = h; i < a.length; ++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);
}

static int recherche (String x, String[ ] nom, int[ ] tel) {

  for (int i = 0; i < nom.length; ++i)
      if (x.equals(nom[i]))
          return tel[i];
  return -1;
}

static int rechercheDichotomique (String x, String[ ] nom, int[ ] tel) {
  int   i, cmp, g = 0, d = nom.length-1;
  do {
      i = (g + d) / 2;
      cmp = x.compareTo(nom[i]);
      if (cmp == 0)
          return tel[i];
      if (cmp < 0)
          d = i - 1;
      else 
          g = i + 1;
  } while (g <= d);
  return -1;
}

• Idée: on range l'élément de clé x en position h(x) Î [0,M-1], où h est une fonction ``aléatoire''.
  
  
• Prérequis : avoir une ``bonne'' fonction h.
  Solution, si x = x₀ x₁ ... x_n-1 est une chaîne de caractères :
  h(x) = (x₀ * B^n-1 + x₁ * B^n-2 + ... + x_n-1)  mod M

  
  static int h (String x) {
    int   r = 0;
    for (int i = 0; i < x.length(); ++i)
        r = ((r * B) + x.charAt(i)) % M;
    return r;
  }
  

  Par exemple choisir M premier, et B = 128 ou B = 256.

• Hachage avec listes de collision
• Hachage avec adressage ouvert
• Hachage à 2 niveaux avec adressage ouvert
• Hachage avec chaînage
• Hachage multiple
• Hachage pour cache

final static int M = 63, B = 128;

static Entree[] nom = new Entree[M];

static int rechercher (String x) {
  for (Entree e = nom[h(x)]; e != null; e = e.suivant)
    if (x.equals(e.cle))
      return e.tel;
  return -1;
}
static void inserer (String x, int t) {
  int i = h(x);
  nom[i] = ajouter (x, t, nom[i]); 
}
static Entree ajouter (String x, int t, Entree e) {
  if (e == null) 
    return new Entree (x, t, null);
  else {
    e.suivant = ajouter (x, t, e.suivant);
    return e;
  }
}

static int rechercher (String x) {

  for (int  i = h(x); !nom[i].equals (""); i = (i+1) % M)
    if (x.equals(nom[i]))
      return tel[i];
  return -1;
}

static void inserer (String x, int t) {

  int i = h(x);
  while (!nom[i].equals ("")) 
    i = (i+1) % M;
  nom[i] = x; tel[i] = t;
}

• On peut hacher une grande table (dictionnaire par exemple) de d mots par k fonctions h_i indépendantes, 1 £ i £ k. Et on prend un grand tableau T de n bits où T[j]=1 si h_i(v)=j pour v dans le dictionnaire et 1 £ i £ k.
  
  
• La probabilité pour qu'aucun mot d'un dictionnaire de taille d ne positionne un T[j] donné est
  
  

  p = e

  -a

  où a = d k / n.

  
  La probabilité pour qu'un v arbitraire soit dans le dictionnaire est (1 - p)^k.
  
  Ce qui se minimise pour d=25000, n=400000, k=11 en 0.000458711.
  
  
• C'est la méthode utilisée par la commande spell de Unix.

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