Calcul symbolique : Leçon 4
Programmation Itérative

Programmation en Mathematica

Structures de contrôle et programmation itérarive

Mathematica propose les boucles de contrôle classiques For, Do, While, If, Switch ... 
regardez l’aide en ligne !

s=1;
For[i=1,i<10,i++,s=s+x^i ];
s

Programmation Fonctionnelle

Mathematica propose aussi toutes les possibilités de programmation fonctionnelle (Map et Apply en particulier), on verra ce type de programmation plus en détail dans les prochains cours.

Map[f,Range[9]]
Map[f,s]

s
Apply[List,s]
Apply[toto,s]
Apply[Times,s]

Variables locales ... Block et Module

Génération d’une permutation aléatoire

On veut engendrer une permutation aléatoire, c’est à dire produire une liste des  n entiers de  1 à n de telle manière que la probabilité d’obtenir chaque liste soit (1/(n!)).

A l’aide de nombres réels aléatoires

On tire au hasard un tableau T de n nombres réels entre 0 et 1. Pour chaque k, on calcule le nombre d’entrées du tableau T qui sont ≤T[k]. La complexité est en O((n^2)).

t=RandomReal[1,5]

ListLinePlot[Table[Timing[RealPerm1[10i]][[1]],{i,1,20}]]

Mélange de Fisher–Yates (ou de Knuth)

L’algorithme est le suivant
Initialiser T à {1,2,...n}
pour i de 1 à n
   j := nombre aléatoire entier entre 1 et i (inclus)
   	échanger T[i] et T[j] dans T
Retourner T
 
Sa complexité est en O(n)

Comparaison

ListLinePlot[{Table[First[Timing[RealPerm[50 i]]],{i,1,10}],
Table[First[Timing[KnuthPerm1[50 i]]],{i,1,10}]},
PlotStyle->{Thin,Thick}]

En utilisant Sort

Où l’on voit que la procédure de tri implémentée dans Mathematica est très très efficace ....

SortPerm[10]

En utilisant RandomSample

En général, si une fonction est déjà implémentée, il ne faut surtout pas hésiter à l’utiliser ...

Perm[10]

ListLinePlot[
{
Table[First[Timing[Perm[5000 i]]],{i,1,20}],
Table[First[Timing[KnuthPerm1[5000 i]]],{i,1,20}]
},
PlotStyle->{Thick,Thick}]

Comparaison

test[fonction_]:=Table[Timing[fonction[n]][[1]],{n,100,1000,100}]
test[fonction_,min_,max_,pas_]:=Table[Timing[fonction[n]][[1]],{n,min,max,pas}]

n=100000;
Timing[KnuthPerm[n]][[1]]
Timing[SortPerm[n]][[1]]
Timing[SortPermFast[n]][[1]]
Timing[RandomSample[Range[n]]][[1]]

ListPlot[{test[KnuthPerm,10000,200000,10000],test[SortPerm,10000,200000,10000],test[Perm,10000,200000,10000]},Joined->True]

Génération d’une partie à k éléments dans un ensemble à n éléments

Algorithme de génération

En utilisant une permutation aléatoire

SousEnsPerm[30,10]

Avec RandomSample

SousEnsSample[30,10]

Comparaison

A voius de faire des tests sur la rapidité de ces différentes méthodes ...

Chemins 01

Chemins 0-1

A toute suite de 0 et de 1 on peut associer une suite de pas, Nord-Est ou Sud-Est selon que l’on lit 1 ou 0. Ecrire une fonction qui dessinne un chemin 0-1.

Chemins représentant une liste de 0 et de 1

Dessine01[Table[RandomInteger[1],{i,1,20}]]

On considère maintenant des chemins du plan codés sur {0,1,2,3}, chacun de ces entiers représentant un déplacement dans l’une des quatre directions Est, Nord, Ouest et Sud.

Exercices

Exercice : Ecrire une fonction prenant en entrée une liste de 0 et de 1 et qui retourne l’ordonnée du point le plus à droite du chemin correspondant.