1. Listes -- Arbres
2. Opérations de base
3. Polymorphisme?
4. Abstraction1: représentation des ensembles
5. Abstraction2: paquetage de grands nombres

class Liste {
  int hd; Liste tl;

  Liste (int v, Liste a) {
     hd = v; tl = a;
  }
}

class Liste {
  int indice; int valeur; Liste suivant;

  Liste (int i, int v, Liste a) {
     indice = i; valeur = v; suivant = a;
  }
}

• concaténation
  
  
• image mirroir
  
  
• appartenance

• listes non modifiables Þ clarté
  
  
• listes modifiables Þ efficacité

static Liste append (Liste a, Liste b) {
  if (a == null) return b;
  else return new Liste (a.hd, append (a.tl, b)) ;
}

static Liste nConc (Liste a, Liste b) {
  if (a == null) return b;
  else {
    a.tl = nConc (a.tl, b);
    return a;
  }

static Liste nConcI (Liste a, Liste b) {
  if (a == null) return b;
  else {
    Liste c = a;
    while (c.tl != null) 
      c = c.tl;
    c.tl = b;
    return a;
  }
}

static Liste reverse (Liste x) {
  if (x == null) return null;
  else return append (reverse (x.tl), new Liste (x.hd, null));
}

static Liste mirroir (Liste x) { return mirroir1 (x, null); }

static Liste mirroir1 (Liste x, Liste r) {  // r accumulateur
  if (x == null) return r;
  else return mirroir1 (x.tl, new Liste(x.hd, r));
}

static Liste mirroirI (Liste x) {
  Liste r = null;
  for (; x != null; x = x.tl)
    r = new Liste (x.hd, r);
  return r;
}

static Liste nReverse (Liste x) {
  if (x == null) return null;
  else {
    Liste y = nReverse (x.tl);
    x.tl = null;
    return nConc (y, x);
  }
}

static Liste nReverseI (Liste x) {
  Liste r = null;
  while (x != null) {
    Liste y = x.tl; x.tl = r; r = x; x = y;
  }
  return r;
}

static Liste listeAleatoire (int n) {
  Liste r = null;
  for (int i = 0; i < n; ++i)
     r = new Liste ((int) (Math.random() * 100), r);
  return r;
}

static void imprimer (Liste x) {
  for (Liste y = x; y != null; y = y.tl) 
    System.out.print (y.hd + " ");
  System.out.println ();
}

static Liste lireDansTableau (String[] a) {
  Liste r = null;
  for (int i = a.length - 1; i >= 0; --i)
    r = new Liste (Integer.parseInt (a[i]), r);
  return r;
}

static boolean member (int n, Liste x) {
  if (x == null) return false;
  else return n == x.hd || member (n, x.tl);
}

static boolean equal (Liste x, Liste y) {
  if (x == null) return y == null;
  else if (y == null) return x == null;
  else return x.hd == y.hd && equal (x.hd, y.hd);
}

static boolean eq (Liste x, Liste y) {
  return x == y;
}

class Arbre {
  int val; Arbre fG, fD;

  Arbre (int v, Arbre a, Arbre b) {
    val = v; fG = a; fD = b;
  }
}

class Arbre {
  int val; Arbre[] fils;
  Arbre (int v, Arbre[] a) { val = v; fils = a; }
}

class Arbre {
  int val; ListeArbres fils;
  Arbre (int v, ListeArbres x) { val = v; fils = x; }
}

class ListeArbres {
  Arbre hd; ListeArbres tl;
  ListeArbres (Arbre a, ListeArbres x) { val = v; fils = x; }
}

static void imprimer (Arbre a) {
  if (a != null) {
    System.out.print ("["); imprimer (a.fG);
    System.out.print (" " + a.val + " ");
    imprimer (a.fD); System.out.print ("]"); 
  }
}

static int next;

static Arbre lireDansTableau (String[] s) {
    if (!s[next].equals ("[") ) 
      return null;
    else {
      ++next; Arbre a = lireDansTableau (s);
      int v = Integer.parseInt (s[next]);
      ++next; Arbre b = lireDansTableau (s);
      if (!s[next++].equals ("]") ) {
        System.err.println ("Mauvais arguments."); 
        System.exit (1);
      }
      return new Arbre (v, a, b);
    }
}

static Liste listeDesNoeuds (Arbre a) {
  if (a == null) return null;
  else return append (listeDesNoeuds (a.fG), 
                      append (new Liste (a.val, listeDesNoeuds (a.fD))));
}

static boolean member (int n, Arbre x) {
  if (x == null) return false;
  else return n == x.val || member (n, x.fG) || member (n, x.fD);;
}

static boolean equal (Arbre x, Arbre y) {
  if (x == null) return y == null;
  else if (y == null) return x == null;
  else return x.val == y.val && equal (x.fG, y.fG) && equal (x.fD, y.fD);;
}

• Listes doublement chaînées: pour aller rapidement au(x) prédécesseur(s) dans la liste.
  
  
• Listes gardées: hack pour ne pas avoir à singulariser le cas vide. Analogue des sentinelles pour éviter les débordements dans les tableaux. (Si utilisé pour faire des méthodes non statiques, c'est horrible.)
  
  
• Listes circulaires: autre technique pour accéder au(x) prédécesseur(s).

• Il y a une classe Object de tous les objets.
  
  
• Conversions implicites:
  C ® Object
  C[] ® Object[]
  t[] ® Object
  
  
• Conversions explicites: (t) e où t type quelconque
  
  
• Les variables de types primitifs (byte, short, int, long, float, double, char, boolean) ne sont pas convertibles en Object.
  
  
• Integer(n), Float(x), etc construisent des objets contenant les valeurs n, x, etc, et dont les méthodes intValue(), floatValue(), etc donnent les valeurs n, x, etc.

class Liste {
  Object hd; Liste tl;
  Liste (Object v, Liste a) {
     hd = v; tl = a;
  }

  static Liste append (Liste a, Liste b) {
    if (a == null) return b;
    else return new Liste (a.hd, append (a.tl, b)) ;
  }

  public static void main (String[] args) {
    Liste x = new Liste(new Integer(2), new Liste( new Integer (3), null));
    Liste y = new Liste(new Integer(4), new Liste( new Integer (5), null));
    Liste z = append (x, y);
    int u = ((Integer) z.hd).intValue();
    System.out.println (u);
  }
}

• listes á 2, 10, 4, 2, 1, 6ñ
  
  
• listes sans répétitions á 2, 10, 4, 1, 6ñ
  
  
• listes ordonnées á 1, 2, 4, 6, 10ñ
  
  
• arbres á [ [ 2 ] 10 [ 4 ] ] 2 [  1 [ 6 ] ]ñ
  
  
• arbres de recherche á [ [ [ 1 ] 2 [ 4 ] ] 6 [ 10 ] ]ñ

class Ensemble {
  hd: int; tl: Ensemble;
  Ensemble (int x, Ensemble e) { hd = x; tl = e; }

static boolean vide (Ensemble e) { return e == null; }

static Ensemble ajouter (int x, Ensemble e) {
  if ( e == null || x < e.hd ) return new Ensemble (x, e);
  else if (x == e.hd) return e;
  else if (x > e.hd) return new Ensemble (e.hd, ajouter (x, e.tl));
}

static boolean appartient (int x, Ensemble e) {
  if ( e == null || x < e.hd ) return false;
  else return x == e.hd || appartient (x, e.tl);
}

static Ensemble enlever (int x, Ensemble e) {
  if ( e == null || x < e.hd ) return e;
  else if (x == e.hd) return e.hd;
  else if (x > e.hd) return new Ensemble (e.hd, enlever (x, e.tl));
}

• Little endian: 1794 représenté par la liste á 4, 9, 7, 1ñ
  Pentium
  
  
• Big endian: 1794 représenté par la liste á 1, 7, 9, 4ñ
  IBM 370, PDP-10, Vax, Motorola, PPC.
  
  
• Petit et Grand: MIPS, Alpha

• 1- On normalise u et v en les multipliant par d = ë B/v₁ + 1 û
  
  
• 2- Pour j variant de 0 à m, faire la séquence 3-4-5-6:
  
  
• 3- Si u_j = v₁, alors q' = B-1,
  sinon q' = ë (u_j * B + u_j+1)/v₁ û.
  Tant que q' * v₂ > (u_j * B+u_j+1) * B+u_j+2, décrémenter q'.
  
  
• 4- Remplacer u_j...u_j+n par u_j...u_j+n - q'*v.
  
  
• 5- q_j ¬ q'
  Si résultat précédent négatif, faire 6:
  
  
• 6- Décrémenter q_j et additionner v à u_j...u_j+n
  
  
• 7- q₀ q₁...q_m est le résultat
  u_m+1...u_m+n/d est le reste (car faut dénormaliser)

1. Choisir un nombre aléatoire a tel que a < p
   
   
2. Calculer a^(p-1)/2 mod p
   
   
3. Si a^(p-1)/2 ¬ º1  ou  -1, répondre NON.
   
   
4. Sinon p est premier à 50%.

1. Choisir un nombre aléatoire a tel que a < p
   
   
2. Poser j=0 et z= a^m mod p
   
   
3. Si z=1 ou z=p-1, alors répondre OUI.
   
   
4. Si j>0 et z=1, alors répondre NON.
   
   
5. Faire j=j+1. Si j<b et si z=z² mod p ¹ p-1, revenir en (4). Si z=p-1, alors répondre OUI.
   
   
6. Si j=b et z = p-1 alors répondre NON.

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