Planche 1
PC3
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. Modularité en Java
  2. Modularité en ML
  3. Puissance de la récursivité
  4. Fonctions numériques
  5. Hanoi
  6. QuickSort, tri fusion
  7. Fractales
Planche 3
Modularité en Java

Méthodes: suite d'intructions dont les variables locales ne sont pas accessibles de l'extérieur.




Classes: une classe T est une unité de chargement, contenant un ensemble de variables et d'instructions plus ou moins visibles de l'extérieur.

public visible de toute classe U

private visible seulement dans la classe T

protected visible de tout le paquetage contenant T ou de toute sous-classe U de T.

(défaut) visible de tout le paquetage contenant T




Packages: répertoires contenant des classes.

Planche 4
Modularité en Java --- bis

La notation longue d'un nom de méthode ou de variable contient en préfixe le nom de son paquetage, puis de son module (ou de l'objet le contenant pour les noms non statiques). Par exemple expliquer le sens du préfixe dans System.out.println, System.exit.

On peut se dispenser d'écrire le nom du paquetage avec

import nom_de_paquetage.*;
Un fichier .java peut contenir plusieurs classes T. Le compilateur javac génère autant de fichiers T.class.

Le contrôle est donné à une classe contenant une méthode publique (statique) main. Les classes sont chargées au fur et à mesure de leur utilisation en allant chercher dans le paquetage courant ou selon la variable d'environnement CLASSPATH.

Planche 5
Modularité en Ocaml

.ml Les fichiers d'implémentations contenant une suite de phrases (définitions ou expressions du top-level)

.mli Fichiers d'interface donnant la liste des noms visibles à l'extérieur avec leur type. Le nom du module correspondant a sa première lettre en majuscule. E.g. /usr/local/lib/ocaml/char.mli est l'interface standard du module Char

external code: char -> int = "%identity"
        (* Return the ASCII code of the argument. *)
val chr: int -> char
        (* Return the character with the given ASCII code.
           Raise [Invalid_argument "Char.chr"] if the argument is
           outside the range 0--255. *)
val escaped : char -> string
        (* ... *)
val lowercase: char -> char
val uppercase: char -> char
        (* ... *)
Planche 6
Modularité en Ocaml --- bis

et on écrira 

Char.code 'A';;
- : int = 65
Si on ne veut pas préfixer par le nom du module, on peut ouvrir le module

open Printf;;
printf "bonjour, tout le monde\n";;
Il y a aussi une notion de compilation séparée, de modules paramétriques (foncteurs) qu'on verra plus tard. Le fichier animationtri.ml peut s'exécuter au top-level en faisant couper coller ou en tapant la directive (# faisant partie de l'input)

#use "animationtri.ml";;
On peut aussi le compiler avec la commande Unix

% ocamlc -o animationtri animationtri.ml
Planche 7
Modules graphiques

MacLib est un sous-ensemble de AWT suffisant pour notre cours (écrit par Ph. Chassignet)

  blackColor                       blueColor 
  redColor                         cyanColor 
  greenColor                       magentaColor 
  whiteColor                       yellowColor 
  patCopy                          patXor 
  addPt(Point, Point)              backColor(Color) 
  backColor(int)                   button() 
  buttonState()                    charWidth(char) 
  drawChar(char)                   drawLine(int, int, int, int) 
  drawString(String)               drawText(char[], int, int) 
  emptyRect(Rect)                  equalPt(Point, Point) 
  equalRect(Rect, Rect)            eraseArc(Rect, int, int) 
  eraseOval(Rect)                  erasePolygon(Point[], int) 
  eraseRect(Rect)                  eraseRoundRect(Rect, int, int) 
  foreColor(Color)                 foreColor(int) 
  frameArc(Rect, int, int)         frameOval(Rect) 
  framePolygon(Point[], int)       frameRect(Rect) 
  frameRoundRect(Rect, int, int)   getClick(Point) 
  getDrawingRect(Rect)             getKey() 
  getMouse(Point)                  getPen(Point) 
  getPort()                        getTextRect(Rect) 
  hideAll()                        initMacLib() 
  initQuickDraw()                  insetRect(Rect, int, int) 
  invertArc(Rect, int, int)        invertCircle(int, int, int) 
  invertOval(Rect)                 invertPolygon(Point[], int) 
  invertRect(Rect)                 invertRoundRect(Rect, int, int) 
  keyPressed()                     line(int, int) 
  lineTo(int, int)                 move(int, int) 
  moveTo(int, int)                 newPointArray(int) 
  offsetRect(Rect, int, int)       paintArc(Rect, int, int) 
  paintCircle(int, int, int)       paintOval(Rect) 
  PaintOval(Rect)                  paintPolygon(Point[], int) 
  paintRect(Rect)                  paintRoundRect(Rect, int, int) 
  penMode(int)                     penNormal() 
  penSize(int, int)                pt2Rect(Point, Point, Rect) 
  ptInRect(Point, Rect)            RGBBackColor(RGBColor) 
  RGBForeColor(RGBColor)           sectRect(Rect, Rect, Rect) 
  setDrawingRect(Rect)             setPort(GrafPort) 
  setPt(Point, int, int)           setRect(Rect, int, int, int, int) 
  setText(Frame)                   setTextRect(Rect) 
  showDrawing()                    showText() 
  stringWidth(String)              subPt(Point, Point) 
  sysBeep(int)                     textWidth(char[], int, int) 
  tickCount()                      trackMouse(Point) 
  unionRect(Rect, Rect, Rect)      waitClickDown() 
  waitClickUp()
Planche 8
Modules graphique Caml Graphics est le module graphique d'Ocaml. [Pour Ocaml, il faut charger les fonctions C réalisant le graphique; ocamlgraph est un toplevel à l'X avec le graphique préchargé].

value open_graph: string -> unit
value close_graph: unit -> unit
value clear_graph : unit -> unit
value size_x : unit -> int
value size_y : unit -> int
value rgb: int -> int -> int -> color
value set_color : color -> unit
value black : c
value magenta : color
value plot : int -> int -> unit

value point_color : int -> int -> color
value moveto : int -> int -> unit
value current_point : unit -> int * int
value lineto : int -> int -> unit
value draw_arc : int -> int -> int -> int -> int -> int -> unit
value draw_ellipse : int -> int -> int -> int -> unit
value draw_circle : int -> int -> int -> unit
value set_line_width : int -> unit

value draw_char : char -> unit
value draw_string : string -> unit
value set_font : string -> unit
value set_text_size : int -> unit

value text_size : string -> int * int
value fill_rect : int -> int -> int -> int -> unit
Planche 9
Récursivité

Une fonction peut s'appeler elle-même à l'intérieur de sa définition.
Identique aux définitions par récurrence en mathématiques
ou encore raisonnement par induction.

u0 = u1 = 1, un = un-1 + un-2 pour la suite de Fibonnacci

static int fib (int n) {

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

let rec fib n =
  if n <= 1 then 1
  else fib (n - 1) + fib (n - 2);;
Planche 10
Récursivité -- bis 

static int ack(int m, int n) {

  if (m == 0)
      return n + 1;
  else
      if (n == 0)
          return ack (m - 1, 1);
      else
          return ack (m - 1, ack (m, n - 1));
}
Pourquoi cette fonction termine-t-elle pour tout m, n ?

Trouver les valeurs de ack(0,n), ack(1,n), ack(2,n), ...

Planche 11
Indécidabilité de l'arrêt

On s'intéresse aux classes qui ont toutes une méthode f. Supposons que Turing.termine (o) termine ssi o.f() termine.

class Turing {
  static boolean termine (Object o) { /* contenu secret */ }
}

class Facile {   void f () {  }   }

class Boucle {  void f () { for (int i = 1; i > 0; ++i);  }  }

class Test {
  public static void main (String args[]) {
      Facile o1 = new Facile();
      System.out.println (Turing.termine(o1));
      Boucle o2 = new Boucle();
      System.out.println (Turing.termine(o2));
  }
}
Planche 12
Indécidabilité de l'arrêt --- bis 

class Absurde {
  void f () {
      while (Turing.termine(this))
          ;
   }
class Test {
  public static void main (String args[]) {
      Absurde o3 = new Absurde();
      System.out.println (Turing.termine(o3));
  }
}
Alors Absurde.f() termine ssi Absurde.f() ne termine pas.

Il n'existe pas de programme testant si une fonction termine.



Planche 13
Théorie des fonctions récursives

[ Kleene, Rogers, Yasuhara 1971] Quelles sont donc les fonctions calculables?

Pour calculer, il suffit d'un langage de programmation avec les instructionsS et S' suivantes:

(1) x = 0; x = y+1; x = y;
(2) S S'
(3) if x < y then S else S'
(4) for y do S (faire y fois S)
(5) while x < y do S

Sans (5), on a les fonctions primitives récursives. Exemples:

z = x;
for y do z = z + 1;     z = x + y

z = 0;
for x do 
  for y do
    z = z + 1;          z = x × y
Planche 14
Théorie des fonctions récursives - bis

Montrer que factorielle, fibonacci, max(m,n) sont des fonctions récursives primitives. Quid de ack(m,n) pour m fixé?

On peut montrer que la fonction ack(m,n) croit plus vite que toute fonction récursive primitive.

Il existe d'autres modèles de la calculabilité: les systèmes de Post, le l-calcul de Church, les fonctions récursives de Godel et Kleene, les machines de Turing, les ordinateurs modernes. Tous ces modèles sont équivalents, et il en sera toujours ainsi: Thèse de Church. (cf le cours de Logique de la majeure Math/Info)

Le 2ème théorème de récursion (de Kleene) montre qu'il existe des programmes auto-reproductibles. Trouver un programme en Caml ou Java dont le résultat est son propre texte.

Planche 15
Les tours de Hanoi

C'est l'exemple du raisonnement inductif dépassant le cas des récurrences numériques.

static void hanoi(int n, int i, int j)  {

  if (n > 0) {
      hanoi (n-1, i, 6-(i+j));
      System.out.println (i + " -> " + j);
      hanoi (n-1, 6-(i+j), j);
  }
}
Exercice: faire les tours de Hanoi avec un programme itératif!

Planche 16
QuickSort [Hoare 1960], Tri Fusion 

static void qSort(int g, int d)  {

  if (g < d) {
      v = a[g];
      Partitionner le tableau autour de la valeur v
      et mettre v à sa bonne position m
      qSort (g, m-1);
      qSort (m+1, d);
  }
}
Planche 17
QuickSort -- suite 

static void qSort(int g, int d)  {

  int i, m, x, v;

  if (g < d) {
      v = a[g];
      m = g;
      for (i = g+1; i <= d; ++i)
          if (a[i] < v) {
              ++m;
              x = a[m]; a[m] = a[i]; a[i] = x;
          }
      x = a[m]; a[m] = a[g]; a[g] = x;
      qSort (g, m-1);
      qSort (m+1, d);
  }
}
Complexité? En moyenne, CN » 1,38 N log2 N, très bon.

Planche 18
Récursivité graphique, courbes fractales Gaston Julia et Benoît Mandelbrot (x56?, IBM) en sont les pères fondateurs.

Le flocon de von Koch [1]
La courbe du dragon [1, 2]
La courbe de Hilbert [1]
La courbe de Sierpinsky [1 2 3 4]
Les fougères de Barnsley [1]
Les systèmes de Lindenmayer (arbres) [1]

let rec dragon n x y z t =           and dragon_bis n x y z t =
  if n = 1 then begin                   if n = 1 then begin
    moveto x y;                            moveto x y;
    lineto z t                             lineto z t
  end else begin                        end else begin
    let u = (x + z + t - y) / 2            let u = (x + z - t + y) / 2
    and v = (y + t - z + x) / 2 in         and v = (y + t + z - x) / 2 in
    dragon (n - 1) x y u v;                dragon (n - 1) x y u v;
    dragon_bis (n - 1) u v z t             dragon_bis (n - 1) u v z t
  end                                   end;;
Planche 19
Exercices

Finir le tri animé (tri sélection, insertion, Shell, bulle, QuickSort, Fusion). Regarder les mauvaises séquences du tri Shell.

Dessiner une des courbes fractales (Dragon, Hilbert, Fougère)

This document was translated from LATEX by HEVEA.