\input carnotps.mac
\input psfig.sty
\guillemets
\parindent=0pt\def\indent{\hskip7mm}
\leftskip=1cm
\rightskip=\leftskip

\centerline{\cadreombre\m=0mm{
\grise\g=80\m=3mm\w=\hsize{
\cr
\Gros\bf X 1997, option MP\cr\cr
\Gros\bf Composition d'informatique\cr\cr
corrig{\'e} de M. Quercia ({\tt quercia\char 64 cal.enst.fr})\cr}}}
\SV

\def\q#1{{\sv\goodbreak\hskip-\leftskip\bf Question #1.\par}}
\def\f#1/#2 {\dfrac{#1}{#2}}
\def\({\Bigl(}
\def\){\Bigr)}
\catcode`?=\active\def?{\beginverbatim\let?=\endverbatim\catcode`$=\active}
{\catcode`$=\active\gdef$#1${{\sltt#1}}}

%------------------------------------------------------------------------
\q{1a}
\sv
\line{\hfil
%
\dimendef\u=255\u=5mm
\setbox0=\hbox to \u{\vrule height0.6\u width 0.4pt depth 0.4\u\hfil$\bullet$\hfil}
\setbox0=\vbox to\u{\hrule\hbox{\leaders\box0\hskip8\u\vrule}\vss}
\vbox{\leaders\box0\vskip8\u\hrule}%
%
\hfil\hfil
%
\setbox0=\vbox to 8\u{\offinterlineskip
  \hsize=8\u
  \hrule
  \vfil\line{\hfil\vrule width 2\u height 0.4pt depth 0pt}
  \vfil\line{\hfil\vrule width 4\u height 0.4pt depth 0pt}
  \vfil\vskip0.4pt\vfil\hrule
  \vfil\vfil\vfil\vfil\vskip0.8pt\hrule}
\setbox1=\hbox to 8\u{%
  \vrule height 8\u depth 0pt width 0.4pt
  \hfil\hfil\hfil\hfil\vrule
  \hfil\hfil\vrule depth -4\u
  \hfil\vrule depth -6\u
  \hfil\vrule}
\setbox2=\hbox to 8\u{\vrule height 0.6\u width 0pt depth 0pt
\hskip6\u\hfil$\bullet$\hfil\hfil$\bullet$\hfil}
\setbox2=\vbox to 8\u{\box2\vfil}
\hbox{\box0\hskip-8\u\box1\hskip-8\u\box2}%
\hfil}

%------------------------------------------------------------------------
\q{1b}
Un arbre quaternaire de profondeur $p$ contenant au plus $4^p$ feuilles,
on a $4^p \le N$ soit $p \le \f{\ln N}/\ln4 $ d'o{\`u}
$f(N) = \left\lceil\f{\ln N}/\ln4 \right\rceil$.
Cette minoration est optimale,
\sv
-- dans le sens de l'{\'e}nonc{\'e}~:
pour $p_0\in\N$ il existe $N_0 = 4^{p_0}$ tel que $f(N_0) = p_0$ et il
existe un quadtree {\`a} $N_0$ corps de profondeur $p_0$ obtenu comme au
{\bf 1a} en subdivisant l'univers en $4^{p_0}$ carr{\'e}s et en pla{\c c}ant un corps
dans chaque carr{\'e}~;
\sv
-- dans un sens plus g{\'e}n{\'e}ral~:
pour $N\in\N$ il existe un quadtree {\`a} $N$ corps de profondeur $p=f(N)$
obtenu en divisant l'univers en $4^p$ carr{\'e}s et en pla{\c c}ant les $N$ corps
d'une mani{\`e}re quelconque {\`a} raison d'un seul corps par carr{\'e} (il y a alors
au moins un groupe de 4 carr{\'e}s contenant deux corps car $4^{p-1} < N$).

%------------------------------------------------------------------------
\q{1c}
En adaptant l'exemple du {\bf 1a}, on voit qu'il existe des quadtrees de
profondeur arbitrairement grande contenant seulement deux corps, et de
m{\^e}me, il existe des quadtrees {\`a} $N\ge 2$ corps de profondeur arbitrairement
grande.

%------------------------------------------------------------------------
\q{1d}
On pense que l'auteur demande un {\it majorant\/} de la profondeur et non
une {\it borne sup{\'e}rieure}.
Dans un quadtree de profondeur $p$ il y a au moins un carr{\'e} de c{\^o}t{\'e}
$\f D_{\cal U}/2^{p-1} $ contenant deux corps, donc
$\delta \le\f D_{\cal U}/2^{p-1} $ soit
$p\le 1 + \f{\ln(D_{\cal U}/\delta)}/\ln2 $.

%------------------------------------------------------------------------
\q{1e}
Le plus petit nombre strictement positif repr{\'e}sentable est $2^e$ donc
$\delta \ge 2^e$.
Le plus grand nombre repr{\'e}sentable est $2^e(2^m-1)$ donc
$D_{\cal U} \le 2^e(2^m-1)$.
On en d{\'e}duit $\f D_{\cal U}/{\delta} \le 2^m-1$ et donc
$p\le 1 + \f\ln(2^m-1)/\ln2 $ ce qui implique $p\le m$ car $p$ est entier.
\SV
\vfil\eject
\centerline{\bf Corrig{\'e} en Caml}
%------------------------------------------------------------------------
\q{2abc}

?
  let add v1 v2 = {x=v1.x+.v2.x; y=v1.y+.v2.y};;
  let sub v1 v2 = {x=v1.x-.v2.x; y=v1.y-.v2.y};;
  let scal m u  = {x=m*.u.x; y=m*.u.y};;
  let carre u   = u.x*.u.x +. u.y*.u.y;;
?

%------------------------------------------------------------------------
\q{3}
\valign{&\vfil#\vfil\cr
\hbox{On num{\'e}rote ainsi~: }\cr
{\dimendef\u=255\u=1cm
\def\boite#1{\hbox{%
\vrule width 1.6pt
\vbox to\u{\hsize=\u\hrule\vfil\centerline{#1}\vfil\hrule height 1.6pt}%
\vrule}}
\vbox{\offinterlineskip\tabskip=1mm\halign{&#\cr
\boite2&\boite0\cr\noalign{\vskip1mm}\boite3&\boite1\cr}}}\cr}

%------------------------------------------------------------------------
\q{3ab}
?
  let indice_fille p_c p =
    (if p_c.y > p.y then 1 else 0) + 2*(if p_c.x > p.x then 1 else 0);;

  let position_fille p_c taille i =
    let t = taille/.4.0 in
    match i with
    | 0 -> add p_c {x =   t; y =   t}
    | 1 -> add p_c {x =   t; y = -.t}
    | 2 -> add p_c {x = -.t; y =   t}
    | _ -> add p_c {x = -.t; y = -.t}
  ;;
?

%------------------------------------------------------------------------
\q{4a}
?
  $(* ins{\`e}re un corps dans un quadtree *)$
  let rec insere_corps corps arbre p_c taille = match arbre with
  | Vide -> Feuille(corps)
  | Noeud(cell) ->
     insere_dans_filles corps cell.filles p_c taille;
     arbre
  | Feuille(c) ->
     let f = make_vect 4 Vide in
     insere_dans_filles c     f p_c taille;
     insere_dans_filles corps f p_c taille;
     Noeud{cm_mass=0.0; cm_pos=vecteur_nul; filles=f}

  $(* ins{\`e}re un corps dans un tableau de filles *)$
  and insere_dans_filles corps filles p_c taille =
    let i = indice_fille   p_c corps.pos in
    let p = position_fille p_c taille i  in
    filles.(i) <- insere_corps corps filles.(i) p (taille/.2.0)
  ;;
?


%------------------------------------------------------------------------
\q{4b}

On dit qu'un appel ?insere_corps corps arbre p_c taille? est licite si~:
\sv{\marge{\indent}
-- ?corps? repr{\'e}sente un corps dont les coordonn{\'e}es v{\'e}rifient
\sv
$?  p_c.x? - ?taille?/2 \le ?corps.pos.x? \lt ?p_c.x? + ?taille?/2$\par
$?  p_c.y? - ?taille?/2 \le ?corps.pos.y? \lt ?p_c.y? + ?taille?/2~;$\par
\sv
-- ?arbre? repr{\'e}sente un quadtree adaptatif coh{\'e}rent centr{\'e} en ?p_c? de
taille ?taille?, c'est {\`a} dire que chaque corps v{\'e}rifie les in{\'e}galit{\'e}s
pr{\'e}c{\'e}dentes {\`a} chaque niveau de division, et qu'aucune cellule n'est
inutilement divis{\'e}e~;
\sv
-- la position de ?corps? est distincte de celles de tous les corps contenus
dans ?arbre?.
\sv}

On d{\'e}montre alors {\`a} la fois la correction et la terminaison d'un appel licite
par r{\'e}currence sur ?taille?. Soit $\delta$ la plus courte distance entre deux
corps de ?arbre? ou entre un corps de ?arbre? et ?corps?, telle que d{\'e}finie
en {\bf 1.c}, avec la convention $\delta = +\infty$ si l'arbre est vide.
\sv
{\marge{\indent}

-- Si $?taille? < \delta$~:
par d{\'e}finition de $\delta$, il n'y a aucun corps dans ?arbre? situ{\'e} {\`a} une
distance inf{\'e}rieure {\`a} ?taille? de ?corps?, donc $?arbre? = ?Vide?$.
Dans ce cas, l'appel termine et retourne le r{\'e}sultat correct, ?Feuille(corps)?.
\sv

-- Si la correction et la terminaison sont prouv{\'e}es pour tout appel licite
tel que $?taille? < t$, consid{\'e}rons un appel licite avec $?taille? < 2t$.
\sv
{\marge{\indent}
-- Si $?arbre? = ?Vide?$ il y a terminaison et correction du r{\'e}sultat.
\sv
-- Si ?arbre? est un n\oe ud, ?insere_dans_filles? s{\'e}lectionne la bonne cellule
o{\`u} poursuivre l'insertion et g{\'e}n{\`e}re un appel licite {\`a} ?insere_corps? avec
un c{\^o}t{\'e} $?taille?/2 < t$. Cet appel termine et renvoie un r{\'e}sultat correct
par hypoth{\`e}se de r{\'e}currence, et l'arbre retourn{\'e} est plac{\'e} dans la bonne
fille,  il y a donc encore terminaison et correction du r{\'e}sultat.
\sv
-- Si ?arbre? est une feuille, le premier appel {\`a} ?insere_dans_filles? divise
la cellule en 4 et place le corps d{\'e}j{\`a} pr{\'e}sent dans le bon quadrant de mani{\`e}re
{\'e}vidente. Le deuxi{\`e}me appel {\`a} ?insere_dans_filles? produit alors un appel
r{\'e}cursif {\`a} ?insere_corps? licite, que les corps soient dans le m{\^e}me quadrant
ou non. Comme pr{\'e}c{\'e}dement, on conclut {\`a} la terminaison et {\`a} la
correction du r{\'e}sultat.
\par}}

%------------------------------------------------------------------------
\q{4c}
D'apr{\`e}s le raisonnement pr{\'e}c{\'e}dent, ?insere_corps? effectue un nombre born{\'e}
d'op{\'e}rations avant de s'ap\-pe\-ler {\'e}ventuellement {\`a} travers ?insere_dans_filles?
pour le m{\^e}me corps et le param{\`e}tre $?taille?/2$ car le premier appel
{\`a} ?insere_dans_filles? dans le cas ?Feuille(c)? a une complexit{\'e} constante.
La complexit{\'e} de l'insertion d'un corps dans un arbre est donc domin{\'e}e
par la profondeur de l'arbre, elle m{\^e}me major{\'e}e par $m$.
La complexit{\'e} de l'insertion de $N$ corps dans un arbre vide est domin{\'e}e
par $mN$, donc est un $O(N)$ puisque $m$ est constant. Ce majorant est optimal
car chaque corps est examin{\'e} donc donne lieu {\`a} au moins une op{\'e}ration.

%------------------------------------------------------------------------
\q{5}
?
  $(* ajuste les champs$ cm_mass $et$ cm_pos $et retourne *)$
  $(* le couple (masse,somme pond{\'e}r{\'e}e des positions)  *)$
  let rec mass_pos(arbre) = match arbre with
  | Vide        -> (0.0, vecteur_nul)
  | Feuille(c)  -> (c.mass, scal c.mass c.pos)
  | Noeud(cell) ->
      let m = ref(0.0) and p = ref(vecteur_nul) in
      for i=0 to 3 do
        let (mi,pi) = mass_pos(cell.filles.(i)) in
        m := !m +. mi;
        p := add !p pi
      done;
      cell.cm_mass <- !m;
      cell.cm_pos  <- scal (1.0/. !m) !p;
      (!m,!p)
  ;;

  let barycentres(arbre) = let _ = mass_pos(arbre) in ();;
?

%------------------------------------------------------------------------
\q{6a}
?
  $(* fonction auxilliaire : distance num{\'e}rique et vectorielle *)$
  let distance a b = let d = sub b a in (sqrt(carre(d)),d);;

  $(* fonction auxilliaire : acc{\'e}l{\'e}ration de la masse$ m $plac{\'e}e en$ b $sur$ a $*)$
  let accel a b m = let (r,d) = distance a b in scal (m/.r/.r/.r) d;;

  $(* acc{\'e}l{\'e}ration de l'univers sur un corps *)$
  let rec grav_approx pos arbre taille = match arbre with
  | Vide        -> vecteur_nul
  | Feuille(c)  -> if c.pos = pos then vecteur_nul else accel pos c.pos c.mass
  | Noeud(cell) ->
      let (r,_) = distance pos cell.cm_pos in if taille < r*.theta
      then accel pos cell.cm_pos cell.cm_mass
      else begin
        let acc = ref(vecteur_nul) and t = taille/.2.0 in
        for i=0 to 3 do acc := add !acc (grav_approx pos cell.filles.(i) t) done;
        !acc
      end
  ;;
?

%------------------------------------------------------------------------
\q{6b}
Pour qu'une cellule de taille $D$ soit subdivis{\'e}e, il faut que son centre
de masse soit situ{\'e} {\`a} une distance inf{\'e}rieure {\`a} $D/\theta$ du corps $c$
consid{\'e}r{\'e}, donc cette cellule doit {\^e}tre enti{\`e}rement incluse dans le disque
ferm{\'e} de centre $c$ et de rayon $D/\theta + D\sqrt2$ car le centre de masse
est g{\'e}ographiquement inclus dans la cellule si tous les corps le sont.
Comme toutes les cellules de m{\^e}me taille sont deux {\`a} deux disjointes, la
somme des aires des cellules divisables est major{\'e}e par l'aire du disque
pr{\'e}c{\'e}dent, donc le nombre de ces cellules est major{\'e} par
$K(\theta) = \lfloor \pi(1/\theta + \sqrt2)^2\rfloor$.

%------------------------------------------------------------------------
\q{6c}
Un appel ?grav_approx c arbre t? g{\'e}n{\`e}re au plus $K(\theta)$ appels
?grav_approx c arbre' (t/2^k)? pour tout entier $k$ d'apr{\`e}s ce qui pr{\'e}c{\`e}de
et la profondeur de l'arbre {\'e}tant major{\'e}e par $m$, le nombre total d'appels
{\`a} ?grav_approx? g{\'e}n{\'e}r{\'e}s est major{\'e} par $mK(\theta)$ qui est une constante.
Chacun de ces appels effectue, hors appels r{\'e}cursifs, un nombre born{\'e}
d'op{\'e}rations, donc la complexit{\'e} de ?grav_approx? est born{\'e}e et celle de
?ajuste_approx? est un $O(N)$.
\SV
\centerline{\bf Programmes en Pascal}
\sv
Les prototypes des fonctions demand{\'e}es ne sont pas tous conformes {\`a} la syntaxe
du Pascal en vigueur dans les classes pr{\'e}paratoires~:
une fonction ne peut retourner un r{\'e}sultat non scalaire et les descriptions
de type dans une en-t{\^e}te de proc{\'e}dure ou de fonction
(?function cree_feuille(c:1..N):arbre?) ne sont pas autoris{\'e}es, il faut
donner un nom au type ?1..N?.
Ces restrictions ne sont pas support{\'e}es par tous les compilateurs Pascal,
en particulier le traducteur ?p2c? de la Free Software Foundation a permi
de compiler avec succ{\`e}s toutes les proc{\'e}dures et fonctions qui suivent.

%------------------------------------------------------------------------
\q{2abc}
?
  procedure add(u,v : vecteur; var r: vecteur);
  begin
     r.x := u.x + v.x;
     r.y := u.y + v.y
  end;
    
  procedure sub(u,v: vecteur; var r: vecteur);
  begin
     r.x := u.x - v.x;
     r.y := u.y - v.y
  end;
    
  procedure scal(m: real; u: vecteur; var r: vecteur);
  begin
     r.x := m*u.x;
     r.y := m*u.y
  end;
    
  function carre(u : vecteur): real;
  begin
     carre := u.x*u.x + u.y*u.y
  end;
?
%------------------------------------------------------------------------
\q{3ab}
?
  function indice_fille(p_c,p: vecteur): integer;
  var res: integer;
  begin
     if p_c.y > p.y then res := 1 else res := 0;
     if p_c.x > p.x then res := res + 2;
     indice_fille := res
  end;
  
  function position_fille(p: vecteur; taille: real; i: integer): vecteur;
  var t: real; v: vecteur;
  begin
     t := taille/4.0;
     if i >= 2 then v.x := -t else v.x := t;
     if odd(i) then v.y := -t else v.y := t;
     add(p,v,v);
     position_fille := v
  end;
?
%------------------------------------------------------------------------
\q{4a}
?
  procedure insere_dans_filles(c: 1..N; var a: arbre; p: vecteur; taille: real);
  forward;
    
  procedure insere_corps(c: 1..N; var a: arbre; p: vecteur; taille: real);
  var b: arbre;
  begin
     if a = nil then a := cree_feuille(c)
     else if a^.nature = Noeud then insere_dans_filles(c,a,p,taille)
     else begin
        b := cree_noeud(0.0,vecteur_nul,nil,nil,nil,nil);
        insere_dans_filles(a^.corps,b,p,taille);
        insere_dans_filles(c,b,p,taille);
        dispose(a);
        a := b
     end
  end;
    
  procedure insere_dans_filles;
  var i: integer; q: vecteur;
  begin
     i := indice_fille(p,univers[c].pos);
     q := position_fille(p,taille,i);
     insere_corps(c,a^.filles[i],q,taille/2)
  end;
?
%------------------------------------------------------------------------
\q{5}
?
  procedure mass_pos(a: arbre; var m: real; var pos: vecteur);
  var i: integer;
     mi: real;
   posi: vecteur;
  begin
     if a=nil then begin m := 0.0; pos := vecteur_nul end
     else if a^.nature = Feuille then begin
        m := univers[a^.corps].mass;
        scal(m,univers[a^.corps].pos,pos)
     end
     else begin
        m := 0.0;
        pos := vecteur_nul;
        for i:=0 to 3 do begin
           mass_pos(a^.filles[i],mi,posi);
           m := m + mi;
           add(pos,posi,pos)
        end;
        a^.cm_mass := m;
        scal(1.0/m,pos,a^.cm_pos)
     end
  end;
  
  procedure barycentres(a: arbre);
  var m : real;
     pos: vecteur;
  begin
     mass_pos(a,m,pos)
  end;
?
%------------------------------------------------------------------------
\q{6a}
?
  procedure distance(a,b: vecteur; var r: real; var d: vecteur);
  begin
     sub(a,b,d);
     r := sqrt(carre(d))
  end;
  
  function accel(a,b: vecteur; m: real): vecteur;
  var r : real;
     d  : vecteur;
  begin
     distance(b,a,r,d);
     scal(m/r/r/r,d,d);
     accel := d
  end;
     
  function grav_approx(pos: vecteur; a: arbre; taille: real): vecteur;
  var r,t: real;
        p: vecteur;
        i: integer;
  begin
     if a=nil then grav_approx := vecteur_nul
     else if a^.nature = Feuille then begin
        if pos = univers[a^.corps].pos then grav_approx := vecteur_nul
        else grav_approx := accel(pos,univers[a^.corps].pos,univers[a^.corps].mass)
     end
     else begin
        distance(pos,a^.cm_pos,r,p);
        if taille < r*theta
        then grav_approx := accel(pos,a^.cm_pos,a^.cm_mass)
        else begin
           t := taille/2.0;
           p := vecteur_nul;
           for i:= 0 to 3 do add(p,grav_approx(pos,a^.filles[i],t),p);
           grav_approx := p
        end
     end
  end;
?
%------------------------------------------------------------------------
\SV
\centerline{\bf Programmation}
\sv
Voir le fichier {\tt\jobname.ml} ou {\tt\jobname.p} pour une impl{\'e}mentation
compl{\`e}te du mouvement {\`a}
$N$ corps, avec r{\'e}solution approch{\'e}e du syst{\`e}me diff{\'e}rentiel par une m{\'e}thode
d'Euler d'ordre~2. L'ex{\'e}cution de ce programme fournit le code postscript
de la figure suivante o{\`u} l'on a repr{\'e}sent{\'e} la division de l'univers en
quadtree adaptatif un dixi{\`e}me de seconde avant la collision entre les corps
rouge et bleu~\dots
\sv
\centerline{\psfig{file=I97XM1F.eps,width=8cm}}


\bye
