Apprendre Maple Énumérations d'ensembles finis

 
  Page d'accueilPage d'accueil   RechercherRechercher   Forum de discussionForum de discussion   ContactContact   SommaireSommaire 
  Cours MapleCours Maple   Travaux dirigésTravaux dirigés   Thèmes d'activitésThèmes d'activités   Thèmes d'activitésMaplets
Ecran MapleEcran Maple  TéléchargementTéléchargement  BibliographieBibliographie  LiensLiens  


 

 

Page d'accueil   Thèmes d'activités   << Thème précédent   Thème suivant >>


Énumérations d'ensembles finis
d'après l'épreuve d'informatique ESIM 99 MP

Corrigé du thème

 

La procédure premier (e::list) rend le premier élément d'une liste e.
La procédure
sauf_premier (e::list) rend la liste obtenue en enlevant le premier élément de la liste e.

La procédure sauf_ieme (i::posint,e::list) rend la liste obtenue en enlevant le i-ème élément de la liste e.
La procédure
ieme (i::posint,e::list) rend le i-ème élément de la liste e.
La procédure
ajout (e,L::list(list)) rend la liste de listes obtenue en ajoutant l'élément e comme premier
élément à chacune des listes composant L.

Dans toute la suite, contrairement à l'usage, on représente un ensemble par la liste de ses éléments.

Exemple: L'ensemble e = {a, b, c} sera donc représenté par la liste e = [a, b, c] .

 

La procédure parties (e::list) rend la liste de toutes les parties de l'ensemble e.
La procédure
combinaisons (p::nonnegint,e::list) rend la liste des parties à p éléments de l'ensemble e.
La procédure
permutations (e::list) rend la liste des permutations de l'ensemble e.
La procédure
bijections (e::list,f::list) rend la liste des bijections de l'ensemble e vers l'ensemble f.
La procédure
surjections (e::list,f::list) rend la liste des surjections de l'ensemble e sur l'ensemble f.
La procédure
nb_surjections (n::nonnegint,p::nonnegint) rend le nombre de surjections d'un ensemble
à n éléments sur un ensemble à p éléments.
La procédure
partition (e::list) rend la liste des partitions de l'ensemble e.

 


 

Corrigé:

Énoncé du thème

> premier:=proc(e::list)
        if nops(e)>0 then e[1] else error "l'ensemble doit être non vide" end if;
    end proc;

premier := proc (e::list) if 0 < nops(e) then e[1] ...

> premier([a,b,c,d]);

a

> sauf_premier:=proc(e::list)
        local j,L;
        L:=NULL;
        for j to nops(e) do
            if j<>1 then L:=L,e[j] end if
        end do;
        [L];
    end proc;

sauf_premier := proc (e::list) local j, L; L := NUL...
sauf_premier := proc (e::list) local j, L; L := NUL...

> sauf_premier([a,b,c,d]);

[b, c, d]

> sauf_ieme:=proc(i::posint,e::list)
        local j,L;
        L:=NULL;
        for j to nops(e) do
            if j<>i then L:=L,e[j] end if
        end do;
        [L];
    end proc;

sauf_ieme := proc (i::posint, e::list) local j, L; ...
sauf_ieme := proc (i::posint, e::list) local j, L; ...

> sauf_ieme(3,[a,b,c,d]);

[a, b, d]

> ieme:=proc(i::posint,e::list)
        if 1<=i and i<=nops(e) then e[i] else error "mauvais argument" end if;
    end proc;

ieme := proc (i::posint, e::list) if 1 <= i and i <...

> ieme(3,[a,b,c,d]);

c

> ajout:=proc(e,L::list(list))
        local i,M;
        M:=NULL;
        for i to nops(L) do
            M:=M,[e,op(L[i])]
        end do;
        [M]
    end proc;

ajout := proc (e, L::list(list)) local i, M; M := N...

> ajout(a,[[b,c,d],[alpha,beta],[],[1,2,3,4]]);

[[a, b, c, d], [a, alpha, beta], [a], [a, 1, 2, 3, ...

> parties:=proc(e::list)
        local x,f,part;
        if e=[] then [[]]
        else
            x:=premier(e);f:=sauf_premier(e);
            part:=parties(f);
            [op(part),op(ajout(x,part))]
        end if;
    end proc;

parties := proc (e::list) local x, f, part; if e = ...
parties := proc (e::list) local x, f, part; if e = ...
parties := proc (e::list) local x, f, part; if e = ...
parties := proc (e::list) local x, f, part; if e = ...
parties := proc (e::list) local x, f, part; if e = ...
parties := proc (e::list) local x, f, part; if e = ...

> parties([]);

[[]]

> parties([a]);

[[], [a]]

> parties([a,b]);

[[], [b], [a], [a, b]]

> parties([a,b,c]);

[[], [c], [b], [b, c], [a], [a, c], [a, b], [a, b, ...

> parties([a,b,c,d]);

[[], [d], [c], [c, d], [b], [b, d], [b, c], [b, c, ...

> combinaisons:=proc(p::nonnegint,e::list)
        local x,f;
        if p>nops(e) then []
        else
            if p=0 then [[]]
            else
                x:=premier(e);f:=sauf_premier(e);
                [op(ajout(x,combinaisons(p-1,f))),op(combinaisons(p,f))]
            end if;
        end if;
    end proc;

combinaisons := proc (p::nonnegint, e::list) local ...
combinaisons := proc (p::nonnegint, e::list) local ...
combinaisons := proc (p::nonnegint, e::list) local ...
combinaisons := proc (p::nonnegint, e::list) local ...
combinaisons := proc (p::nonnegint, e::list) local ...
combinaisons := proc (p::nonnegint, e::list) local ...
combinaisons := proc (p::nonnegint, e::list) local ...
combinaisons := proc (p::nonnegint, e::list) local ...
combinaisons := proc (p::nonnegint, e::list) local ...

> combinaisons(1,[a,b]);

[[a], [b]]

> combinaisons(3,[a,b,c,d,e,f]);

[[a, b, c], [a, b, d], [a, b, e], [a, b, f], [a, c,...
[[a, b, c], [a, b, d], [a, b, e], [a, b, f], [a, c,...

> permutations:=proc(e::list)
        local L,i,n,x,ei;
        n:=nops(e);
        L:=NULL;
        if n=1 then [[premier(e)]] else
                for i to n do
                    x:=ieme(i,e);ei:=sauf_ieme(i,e);
                    L:=L,op(ajout(x,permutations(ei)));
                end do;
                [L]
        end if;
    end proc;

permutations := proc (e::list) local L, i, n, x, ei...
permutations := proc (e::list) local L, i, n, x, ei...
permutations := proc (e::list) local L, i, n, x, ei...
permutations := proc (e::list) local L, i, n, x, ei...
permutations := proc (e::list) local L, i, n, x, ei...
permutations := proc (e::list) local L, i, n, x, ei...
permutations := proc (e::list) local L, i, n, x, ei...
permutations := proc (e::list) local L, i, n, x, ei...

> permutations([a,b,c]);

[[a, b, c], [a, c, b], [b, a, c], [b, c, a], [c, a,...

> permutations([a,b,c,d]);

[[a, b, c, d], [a, b, d, c], [a, c, b, d], [a, c, d...
[[a, b, c, d], [a, b, d, c], [a, c, b, d], [a, c, d...
[[a, b, c, d], [a, b, d, c], [a, c, b, d], [a, c, d...

> bijections:=proc(e::list,f::list)
        local L,j,n,p,x,y,e1,fj;
        n:=nops(e);p:=nops(f);
        if n<>p or n=0 then [] 
   
     else
                x:=premier(e);e1:=sauf_premier(e);
                if n=1 then [[cat(`(`,convert(x,string),`,`,convert(premier(f),string),`)`)]] else
                        L:=NULL;
                        for j to p do
                            y:=ieme(j,f);fj:=sauf_ieme(j,f);
                            L:=L,op(ajout(cat(`(`,convert(x,string),`,`,convert(y,string),`)`),bijections(e1,fj)));
                        end do;
                        [L]
                end if;
        end if;
    end proc;

bijections := proc (e::list, f::list) local L, j, n...
bijections := proc (e::list, f::list) local L, j, n...
bijections := proc (e::list, f::list) local L, j, n...
bijections := proc (e::list, f::list) local L, j, n...
bijections := proc (e::list, f::list) local L, j, n...
bijections := proc (e::list, f::list) local L, j, n...
bijections := proc (e::list, f::list) local L, j, n...
bijections := proc (e::list, f::list) local L, j, n...
bijections := proc (e::list, f::list) local L, j, n...
bijections := proc (e::list, f::list) local L, j, n...
bijections := proc (e::list, f::list) local L, j, n...
bijections := proc (e::list, f::list) local L, j, n...
bijections := proc (e::list, f::list) local L, j, n...
bijections := proc (e::list, f::list) local L, j, n...
bijections := proc (e::list, f::list) local L, j, n...
bijections := proc (e::list, f::list) local L, j, n...
bijections := proc (e::list, f::list) local L, j, n...
bijections := proc (e::list, f::list) local L, j, n...
bijections := proc (e::list, f::list) local L, j, n...
bijections := proc (e::list, f::list) local L, j, n...

> bijections([a],[1,2]);

[]

> bijections([a],[1]);

[[`(a,1)`]]

> bijections([a,b,c],[1,2,3]);

[[`(a,1)`, `(b,2)`, `(c,3)`], [`(a,1)`, `(b,3)`, `(...
[[`(a,1)`, `(b,2)`, `(c,3)`], [`(a,1)`, `(b,3)`, `(...

> surjections:=proc(e::list,f::list)
        local L,j,n,p,x,y,e1,fj;
        n:=nops(e);p:=nops(f);
        if n<p or n=0 or p=0 then []
       else
                x:=premier(e);e1:=sauf_premier(e);
                if n=1 then      # car alors n=p=1
                    [[cat(`(`,convert(x,string),`,`,convert(premier(f),string),`)`)]]
   
             else
                    L:=NULL;
                    for j to p do
                        y:=ieme(j,f);fj:=sauf_ieme(j,f);    
                        L:=L,op(ajout(cat(`(`,convert(x,string),`,`,convert(y,string),`)`),surjections(e1,fj))),
                                 op(ajout(cat(`(`,convert(x,string),`,`,convert(y,string),`)`),surjections(e1,f)));
                    end do;
                    [L]
                end if;
       end if;
    end proc;

surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...
surjections := proc (e::list, f::list) local L, j, ...

> surjections([a],[1,2]);

[]

> surjections([1,2,3,4,5,6,7],[a,b,c]):nops(%);

1806

> nb_surjections:=proc(n::nonnegint,p::nonnegint)
        if n<p or n=0 or p=0 then 0
            elif n=1 then 1         # car alors n=p=1
           else p*(nb_surjections(n-1,p-1)+nb_surjections(n-1,p))
        end if;
    end proc;

nb_surjections := proc (n::nonnegint, p::nonnegint)...
nb_surjections := proc (n::nonnegint, p::nonnegint)...
nb_surjections := proc (n::nonnegint, p::nonnegint)...
nb_surjections := proc (n::nonnegint, p::nonnegint)...
nb_surjections := proc (n::nonnegint, p::nonnegint)...
nb_surjections := proc (n::nonnegint, p::nonnegint)...

> nb_surjections(4,2);

14

> nb_surjections(7,3);

1806

 

> partition:=proc(e::list)
      local f,j,k,n,L,M;n:=nops(e);
        if n=1 then RETURN([[e]]) 
        else
   
         L:=NULL;
   
         f:=partition(sauf_premier(e));
            for j to nops(f) do
                M:=ieme(j,f);
                L:=L,[[premier(e)],op(M)];
                for k to nops(M) do
   
                 if nops(M)=1 then
                       L:=L,ajout(premier(e),[ieme(k,M)])
                    else
                        L:=L,[op(sauf_ieme(k,M)),op(ajout(premier(e),[ieme(k,M)]))] 
                    end if;
                end do;
            end do;
        end if;
        [L]
    end proc;

partition := proc (e::list) local f, j, k, n, L, M;...
partition := proc (e::list) local f, j, k, n, L, M;...
partition := proc (e::list) local f, j, k, n, L, M;...
partition := proc (e::list) local f, j, k, n, L, M;...
partition := proc (e::list) local f, j, k, n, L, M;...
partition := proc (e::list) local f, j, k, n, L, M;...
partition := proc (e::list) local f, j, k, n, L, M;...
partition := proc (e::list) local f, j, k, n, L, M;...
partition := proc (e::list) local f, j, k, n, L, M;...
partition := proc (e::list) local f, j, k, n, L, M;...
partition := proc (e::list) local f, j, k, n, L, M;...
partition := proc (e::list) local f, j, k, n, L, M;...
partition := proc (e::list) local f, j, k, n, L, M;...
partition := proc (e::list) local f, j, k, n, L, M;...
partition := proc (e::list) local f, j, k, n, L, M;...
partition := proc (e::list) local f, j, k, n, L, M;...
partition := proc (e::list) local f, j, k, n, L, M;...
partition := proc (e::list) local f, j, k, n, L, M;...
partition := proc (e::list) local f, j, k, n, L, M;...

> partition([a]);

[[[a]]]

> partition([a,b]);

[[[a], [b]], [[a, b]]]

> partition([a,b,c]);

[[[a], [b], [c]], [[c], [a, b]], [[b], [a, c]], [[a...

> p:=partition([a,b,c,d]): for k to nops(p) do op(k,p) end do;

[[a], [b], [c], [d]]

[[c], [d], [a, b]]

[[b], [d], [a, c]]

[[b], [c], [a, d]]

[[a], [d], [b, c]]

[[b, c], [a, d]]

[[d], [a, b, c]]

[[a], [c], [b, d]]

[[b, d], [a, c]]

[[c], [a, b, d]]

[[a], [b], [c, d]]

[[c, d], [a, b]]

[[b], [a, c, d]]

[[a], [b, c, d]]

[[a, b, c, d]]

 

 

 

 

haut de cette page


©  - Alain Le Stang - Navigation optimisée pour une résolution 1024 x 768.