1. Accueil
  2. Info MP/MP*
  3. 2013-2014
  4. TP Maple Algo à l'X

TP Maple Algo à l'X

Soumis par mathemator le 14 Septembre 2013 - 7:37pm

Remise en forme en algo avec les sujets de l'X-ENS de 2013 et 2010 ainsi qu'un memento Maple puis une exploration de la mathématique avec une tortue ou comment aborder le programme de Master II avec des outils informatiques de maternelle...
Les TP au format PDF

et TEX


Étudiez attentivement comment Étienne Ghys traite ce problème sur Image des maths.


Une proposition de correction pour l'épreuve de 2013 :

Maple
#
#          X/ENS   2013
#
 
# question 1 
admet_point_fixe := proc(t::list)
local k;
    for k from 1 to nops(t) do
        if t[k] = k - 1 
        then RETURN(true)
        fi;
    od;
    RETURN(false);
end:
 
 # maple a deux outils fonctionnels : map et select
select(x -> (2*x+1) mod 10 = x,[k$k=1..9]);
 
                                 [9]
 
# test :
t0 := [1,3,5,7,9,1,3,5,7,9]:
admet_point_fixe(t0);
                                 true
 
# question 2
nb_points_fixes := proc(t::list)
local k,cpt;
    cpt := 0;
    for k from 1 to nops(t) do
        if t[k] = k - 1 
        then cpt := cpt +1;
           fi;
    od;
    RETURN(cpt);
end:
  
 
# question 3
itere := proc(t,x,k)
    if k = 0 then t[x+1]
    else itere(t,t[x+1],k-1)
    fi;
end: 
 
 
# question 4
nb_points_fixes_iteres := proc(t::list , k::nonnegint)
local i,cpt;
    cpt := 0;
    for i from 1 to nops(t) do
        if itere(t,i,k) = k - 1 
        then cpt := cpt +1;
        fi;
    od;
    RETURN(cpt);
end:
 
 
 
# question 5
# fonction auxiliaire renvoyant les points fixes
liste_points_fixes := proc(t::list)
local k,L;
    L := NULL;
    for k from 1 to nops(t) do
        if t[k] = k - 1 
        then L := L,k-1
        fi;
    od;
    RETURN([L]);
end:
 
 
# fonction principale
admet_attracteur_principal := proc(t::list)
local L,i,k,P,n,test;
    L := liste_points_fixes(t);
    if nops(L) = 1 then
        P := L[1];
        n := nops(t);
        for i from 1 to n do
            test := false;
            for k from 0 to n do
                if itere(t,t[i],k) = P then test := true 
                fi;
            od;
            if not test then RETURN(false)
            fi;
        od;
        RETURN(true); 
    else RETURN(false);
    fi;
end:
  
#tests 
t1 := [5,5,2,2,0,2,2]:
admet_attracteur_principal(t1);
 
                                 true
 
admet_attracteur_principal(t0);
 
                                false
 
# question 6
temps_de_convergence := proc(t::list,x::nonnegint)
local P;
    if admet_attracteur_principal(t) then
        P:= liste_points_fixes(t)[1];
        if x = P then 0
        else 1 + temps_de_convergence(t,t[x+1])
        fi;
    else ERROR(`pas d'attracteur principal`);
    fi;
end:
 
# tests
temps_de_convergence(t1,4);
 
                                  3
 
temps_de_convergence(t0,4);
Error, (in temps_de_convergence) pas d attracteur principal
 
# question 7
temps_de_convergence_max := proc(t::list)
local maxi,i;
    maxi := temps_de_convergence(t,0);
    for i from 1 to nops(t)-1 do
        maxi := max(maxi, temps_de_convergence(t,i) );
    od:
    RETURN(maxi);
end:
 
 
temps_de_convergence_max(t1);
 
                                  3
 
# question 8
est_croissante := proc(t::list)
local test,k; 
    for k from 1 to nops(t)-1 do
        if t[k]   t[k+1] then RETURN(false); fi;
    od;
    RETURN(true)
end:
 
# test
est_croissante([1,2,3,4,5,6,7,8,7]);
 
                                false
 
# question 9
point_fixe_rec := proc(m0::nonnegint,t::list)
local m,n;
    n := nops(t);
    m := floor(n/2) ;
    if m = 0 then RETURN(t[m+1])
    elif t[m] = m+m0-1 then RETURN(m+m0-1)
    elif t[m] < m +m0-1 then point_fixe_rec(m0,t[1..m-1])
    else point_fixe_rec(m+m0,t[m+1..n])
    fi;
end:

et pour l'épreuve de 2010:

Maple
#
#                  X/ENS 2010
#
 
# préambule
 
> allouer := proc(m)
  [0 $ m]
  end:
 
> taille := proc(t)
  nops(t)
  end:
 
> Tete := proc(L)
   RETURN(L[1])
  end:
 
> Queue := proc(L)
   RETURN(L[2..-1])
  end:
 
#1
 
> evaluation := proc(P,v)
     if taille(P) = 1 then v*P[1]
     else v*(P[1] + evaluation(P[2..-1] , v))
     fi;
  end:
 
> Ptest := [1$5]:
> evaluation(Ptest,2);
 
                                  62
 
> sum(2^k,k=1..5);
 
                                  62
 
 
#2 
 
> valuation := proc(P)
     if taille(P) = 1 and P[1] = 0 then 0
     elif P[1] <> 0 then 1
     else 1 + valuation(P[2..-1])
     fi;
  end: 
 
 
>  valuation([0,0,0,3,2,1]);
 
                                  4
 
 
#3
 
> difference := proc(P1,P2)
    if taille(P1) = taille(P2) then
       if taille(P1) = 1 then [P1[1] - P2[1]]
       else [P1[1]-P2[1],op(difference(P1[2..-1],P2[2..-1]))]
       fi;
    elif taille(P1) > taille(P2) then
       difference(P1,[op(P2),0])
    else difference([op(P1),0],P2)
    fi;
  end:
 
> P1 := [0,1]: P2:=[1]:
> difference(P1,P2);
 
                               [-1, 1]
 
#4
 
>  Compare_neg := proc(P1,P2)
     local v;
     v := valuation(difference(P1,P2));
     if v = 0 then 0
     elif irem(v,2)=0 then signum(difference(P1,P2)[v])
     else -signum(difference(P1,P2)[v])
     fi
  end:
 
>  Compare_neg([0],[0]); 
 
                                  0
 
#5
 
# tri par insertion
 
> insere := proc(Ordre,P,Liste)
     if taille(Liste) = 0 then [P]
     elif Ordre(P,Liste[1])>=0 then [P,op(Liste)]
     else [e[1],op(insere(Ordre,P,Liste[2..-1]))]
     fi;
  end:
 
> insere(Compare_neg,[0,1],[[0,-1],[1]]);
 
                        [[0, 1], [0, -1], [1]]
 
> tri := proc(Ordre,Liste)
     if taille(Liste) = 1 then Liste
     else insere(Ordre,Liste[1],tri(Ordre,Liste[2..-1]))
     fi;
  end:
 
 
# tri fusion
 
> divise := proc(Liste)
    local n;
    n:=taille(Liste);
    if n=0 then RETURN([],[])
    else RETURN([e[1..floor(n/2)],Liste[floor(n/2)+1..-1]])
    fi;
  end:
 
> fusionner := proc(Ordre,L1,L2)
    if taille(L1)=0 then RETURN(L2)
    elif taille(L2)=0 then RETURN(L1)
    elif Ordre(Tete(L1),Tete(L2))>0 then
       [Tete(L1),op(fusionner(Ordre,Queue(L1),L2))]
    else [Tete(L2),op(fusionner(Ordre,Queue(L2),L1))]
    fi
  end:
 
> tri_f := proc(Ordre,L)
    if taille(L)=1 then RETURN(L)
    else fusionner(Ordre,tri_f(Ordre,divise(L)[1]),
       tri_f(Ordre,divise(L)[2]))
    fi
  end:
 
> tri_f(Compare_neg,[[1],[0,-1],[0,1]]); 
 
                        [[0, 1], [0, -1], [1]]
 
> Compare_pos := proc(P1,P2)
    local v;
    v := valuation(difference(P1,P2));
    if v = 0 then 0
    else signum(difference(P1,P2)[v])
    fi
  end:
 
 
> tri(Compare_pos,[[0,1],[0,-1],[1]]);
 
                        [[1], [0, 1], [0, -1]]
 
>  tri_f(Compare_pos,[[0,1],[0,-1],[1]]);
 
                        [[1], [0, 1], [0, -1]]
 
#6
> verifier_permute := proc(permutation,Liste)
    local Liste_neg, Liste_pos, Test, k;
    Liste_neg := tri(Compare_neg,Liste);
    Liste_pos := tri(Compare_pos,Liste);
    for k from 1 to taille(Liste) do
       if (Liste_neg[k]<>Liste_pos[permutation[k]]) then RETURN(false) fi;
    od;
    RETURN(true);
  end:
 
 
> verifier_permute([2,3,1],[[0,1],[0,-1],[1]]); 
 
                                 true
 
#7
> est_echangeur_aux := proc(per,d)
    local a,b,c,n;
    n:=taille(per);
    for c from d + 1 to n - 2 do
      for b from c + 1 to n - 1 do
        for a from b + 1 to n do
           if ((per[geshifilter-c] &lt; per[a]) and (per[a] &lt; per[d]) and (per[d] &lt; per[b]) ) &#10;              then RETURN(false) &#10;           fi;&#10;           if ((per[b] &lt; per[d]) and (per[d]  &lt; per[a]) and (per[a]  &lt; per[c]) ) &#10;              then RETURN(false) &#10;           fi;&#10;        od;&#10;      od;&#10;    od;&#10;    RETURN(true);&#10;  end:&#10;&#10;&gt; est_echangeur_aux([2,4,1,3],2);&#10;&#10;                                 true&#10;&#10;&gt;  est_echangeur_aux([2,4,1,3],1);&#10;&#10;                                false&#10;&#10;#8&#10;&#10;&gt; est_echangeur := proc(per)&#10;    local d,n;&#10;    n := taille(per);&#10;    for d from 1 to n do&#10;       if not est_echangeur_aux(per,d) then RETURN(false) fi;&#10;    od;&#10;    RETURN(true)&#10;  end:&#10;&#10;&gt; est_echangeur([2,4,1,3]);&#10;&#10;                                false&#10;&#10;#9&#10;&#10;&gt; nombre_echangeurs := proc(n)&#10;    local a,k,i;&#10;    a := allouer(n);&#10;    a[1] := 1;&#10;    for k from 2 to n do&#10;      a[k]:=a[k-1];&#10;      for i from 1 to k-1 do&#10;         a[k]:=a[k]+a[i]*a[k-i];&#10;      od;&#10;    od;&#10;    RETURN(a[n])&#10;  end:&#10;&#10;&#10;&gt; nombre_echangeurs(4);&#10;&#10;                                  22&#10;&#10;#10&#10;&#10;&gt; decaler := proc(t,v)&#10;    local n,u,i;&#10;    n:=taille(t);&#10;    u:=allouer(n+1);&#10;    u[1]:=v;&#10;    for i from 2 to n+1 do&#10;      if t[i-1]&lt;v then u[i]:=t[i-1]&#10;      else u[i]:=1+t[i-1]&#10;      fi&#10;    od;&#10;  RETURN(u)&#10;  end:&#10;&#10;&gt;  decaler([1,2,3,4,5,6],4); &#10;&#10;                        [4, 1, 2, 3, 5, 6, 7]&#10;&#10;

[/geshifilter-c] [/][/]