Alors oui, ça aura peut-être moins de succès que celui de Maths ou de Physique, mais on verra bien .
J’inaugure donc, avec des exos pas trop durs 
:
Ecrire une fonction permutation qui retourne l’ensemble des permutation de [1;n]:
permutation : 'a list → 'a list list =
Exemple:
#permutation [0;1;2];;
- : int list list =
[[0; 1; 2]; [1; 0; 2]; [1; 2; 0]; [0; 2; 1]; [2; 0; 1]; [2; 1; 0]]
Montrer que le langage des palindromes n’est pas reconnaissable.
Je complète l’exo sur les permutations : faire en sorte qu’on puisse passer d’une permutation à la suivante dans la liste en appliquant une transposition.
j’ai pas compris ta question!
si c’est pour t’envoyer les reponses ce sera ethiquement impossible!!
si c’est pour t’expliquer les enoncés tu es le bienvenu!
maths_surfer a écrit:
j’ai pas compris ta question!
si c’est pour t’envoyer les reponses ce sera ethiquement impossible!!
si c’est pour t’expliquer les enoncés tu es le bienvenu!
Bah : tu connais les sujets Exos Sympas MP(*) de maths et Exos sympa sup/spé[bis] de physique ? Là, c’est pareil, mais en informatique.
Comment générer un élément aléatoire de l’ensemble des permutations de [|1, n|] en une complexité linéaire en n ?
On ne peut pas : vu qu’il existe n ! telles permutations, rien que pour écrire le résultat il nous faudra au moins \log_2(n!) \approx n \log_2(n) bits, ce qu’on aurait du mal à écrire en temps linéaire en n…
Oui c’est le soucis de la complexité exprimée en terme d’opérations elementaires quand on ne prend pas la peine de définir correctement ces dernieres.
Sachant que log (nbre de particules dans l’univers) < 100 et que l’ecriture en vue du renvoi du resultat final est extrement plus rapide que les autres calculs que l’on est amené à faire, on va imaginer que ca ne nous embete pas outre mesure.
Je ne suis pas certain de comprendre ton exo:
Est bien « générer UNE et une seule permutation aléatoirement en temps linéaire »?
Si oui la remarque de V@J n’est pas pertinante dans ce contexte.
Si oui, ce n’est pas totalement trivial car l’algo naif est en n^2.
[spoiler]To shuffle an array a of n elements (indices 0..n-1):
for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
qu’ontrouve ici : en.wikipedia.org/wiki/Fisher%E2% … es_shuffle[/spoiler]
Une autre question moins évident est de trouver un algo qui génère toutes les permutations sans biais (cad avec la meme proba pour chaque permutation).
C’est relativement délicat et piégeux (j’ai vu une simulation numérique merder à cause d’une génération non uniforme de permutations…ca a pris bcp de temps avant d’identifier le problème…)
fakbill a écrit:
Je ne suis pas certain de comprendre ton exo:
Est bien « générer UNE et une seule permutation aléatoirement en temps linéaire »?
Si oui la remarque de V@J n’est pas pertinente dans ce contexte.
En quoi ma remarque n’est-elle pas pertinente ?
Arky : c’est quoi tes opérations élémentaires alors ?
V@J a écrit:
Arky : c’est quoi tes opérations élémentaires alors ?
Par exemple dans ce que donne Fakbill, ce sera la création du tableau, la generation d’entiers aleatoires et les permutations dans le tableau.
D’ailleurs sa reponse (que je trouve encore un peu trop baisée :p) me permet de te repondre plus precisement. Ici, le facteur log(n) proviendrait de l’ecriture en binaire des nombres de 1 a n (dont la longueur est censée augmenter quand n augmente). Dans les faits, un certain nombre de bits est assigné a la representation de chaque nombre (par exemple a la declaration de leur type en C) et ne sera donc pas différent de l’un a l’autre.
Perso je peux faire ce que tu veux en n \ln(n) en utilisant des arbres bicolores ou AVL, mais dans un système ou la lecture/écriture/génération aléatoire de nombre prenne un temps constant, je n’arrive pas à \mathcal{O}(n) opérations quand même…
En quoi ma remarque n’est-elle pas pertinente ?
Car on ne parle pas de générer TOUTES les permutations mais juste UNE permutation. Ca n’est donc pas impossible (et c’est même possible
La réponse à la question :
Comment générer un élément aléatoire de l’ensemble des permutations de [|1, n|] en une complexité linéaire en n ?
est par exemple:
To shuffle an array a of n elements (indices 0..n-1):
for i from n − 1 downto 1 do
j ← random integer with 0 ≤ j ≤ i
exchange a[j] and a[i]
et de pour toute définition raisonnable de la complexité… ou alors je n’y comprends rien.
Ma remarque consistait bien à dire que choisir une permutation uniformément au hasard prenait au moins un temps n \ln(n). Bah oui : par exemple, il y a au plus 2^{k+1} permutations que tu peux représenter avec k caractères binaires ou moins (vu que tu as 2^{k+1}-1 chaînes de k caractères binaires ou moins). Donc tu as au plus 2^{n \ln(n)/2+1} \approx 2 n^{n \ln(2)/2} permutations que tu pourras écrire avec n \ln(n)/2 caractères, et donc une proportion écrasante de permutations que tu devras écrire avec plus de n \ln(n)/2 caractères (car n ! est très grand devant 2 n^{n \ln(2)/2}). En particulier, si tu prends UNE permutation au hasard, avec une probabilité écrasante tu mettras au moins un temps n \ln(n)/2 rien que pour ÉCRIRE le résultat.
Générer toutes les permutations, ça prendrait (en gros) un temps n! (puisqu’il faudrait écrire TOUTES les permutations).
La ruse est que, comme dit par Arky, on considère que \ln(n) = \mathcal{O}(1) ; c’est d’ailleurs ce que tu utilises implicitement quand tu fais j \in_R \{0,1,\ldots,i\} : tu crées un entier avec \log_2(i+1) bits, et la plupart du temps ça prend un temps comparable à \ln(n) à écrire…
(Par ailleurs ton algo rend ma remarque précédente caduque.)
Je ne comprends vraiment pas pourquoi tu pars là dessus.
La question était :
Comment générer un élément aléatoire de l’ensemble des permutations de [|1, n|] en une complexité linéaire en n ?
et là réponse est :
en.wikipedia.org/wiki/Fisher%E2% … es_shuffle
Ce qu’est ‹ n › est on ne peut plus clair dans ce contexte non?? C’est juste le nombre de ‹ int › dans le tableau.
Fakbill : ce que je disais avant que Arky ne précise son propos, c’est qu’il est IMPOSSIBLE de tirer aléatoirement une permutation en temps \mathcal{O}(n) (au sens d’une machine de Turing). Toi, tu dis que ton algo fonctionne en temps linéaire, mais ceci n’est vrai que si tirer un entier entre 1 et n au pif prend un temps \mathcal{O}(1), ce qui est loin d’être évident, et faux en toute généralité : ton algo ne fonctionne PAS en temps linéaire si on dispose d’une simple machine de Turing, car les n opérations en apparence unitaires que tu effectueras prendront en fait un temps \ln(n) en moyenne.
Évidemment, dans le modèle de calcul que propose ensuite Arky, on suppose que la taille de n et la structure de données font que ce tirage aléatoire est en fait un \mathcal{O}(1) : dans un tel modèle de calcul (et UNIQUEMENT dans celui-ci, qui n’est pas le modèle le plus canonique, même s’il fait tout à fait sens), ton algo est linéaire en n. Mais pas a priori.
vi vi vi… 
heu quand même…quand on voit la question, le modèle de calcul le plus canonique n’est pas une machine de Turing…enfin pas pour ma notion de « canonique ».
En pratique, générer un nombre aléatoire entre 1 et N sera en O(1) toujours en considérant que N est un « int » (si on passe en précision arbitraire, la moindre opération va coûter plus cher). Ce sera un Mersenne Twister qu’on remape sur [0,N] par exemple.
En pratique, c’est l’idée mais c’est vrai que fondamentalement on peut se dire que c’est du gachis. En fait le gachis serait en realité d’allouer une taille de memoire et un algorithme d’exploitation adapté à chaque int. Vouloir en faire moins nous prendrait alors plus de temps, ce qui n’est pas viable dans la plupart des utilisations de l’informatique, ou l’efficacité est ce qu’il y a de plus important (apres le fait d’avoir qqch de correct).
Du coup V@J est dans le vrai si on etait dans une situation ideale et generale. Mais 99% des cas entrent dans un meme modele, qu’on peut donc « constantiser », comme l’a fait Fakbill, mais peut-etre en precisant où l’on a fait des abus.
Maintenant que ce point est eclairci, on peut retourner a notre jeu de « qui aura la permutation la plus uniforme en O(n) ? ».
Maintenant que ce point est eclairci, on peut retourner a notre jeu de « qui aura la permutation la plus uniforme en O(n) ? ».
Gni??? Tu veux un shuffle uniforme? Certains algo le sont parfaitement et d’autres pas.
Désolé j’avais pas vu qu’on s’était arrêté là.
Bah en fait après coup je me suis mal exprimé. Je me disais qu’une petite analyse de l’uniformité de ton shuffle pourrait être cool. Du coup je peux la faire histoire de conclure. Pour ça on va supposer que ton tableau est initialement trié.
Pourquoi toutes les permutations sont générées ?
Prenons une permutation arbitraire. Appliquons lui l’algorithme-type de tri par insertion : on a évidemment un tableau trié. Or, appliquer le principe en sens inverse reviens à un cas de ton shuffle. Donc toute les permutations sont générées.
Pourquoi le suffle est-il uniforme ?
Sachant qu’on a bien une proba 1/n pour la première itération, il nous suffit - si on veut pouvoir récurer proprement - de montrer que chaque permutation n’est générée que d’une unique façon.
Imaginons deux procédés différents. On se place à la première étape (qu’on notera l’étape n° k) où ils diffèrent. Alors il est évident que dans les deux tableaux, les valeurs indexées par n-k sont différentes à l’étape k, puis ne bougent plus. Donc les permutations sont différentes.
oui et le gag c’est qu’il est facile de se tromper et de code un shuffle qui n’est pas uniforme…c’est piégeux.
