TIPE - Calcul de complexité et probas

Une petite question sur votre TIPE...

Messages : 0

Inscription : 12 juin 2018 20:08

Profil de l'utilisateur : Élève de lycée

TIPE - Calcul de complexité et probas

Message par Dsmii » 27 juin 2018 18:49

Bonjour,
Bien que mon TIPE ne soit pas exactement orienté option informatique, une question qui est tombée lors de mes oraux blancs portait sur la complexité de mon algorithme. Et comme une de mes fonctions utilise un random.randrange, j'ai pu répondre pour le meilleur cas, mais je me suis retrouvé bien désarmé quant à la complexité en moyenne.
Présentation de la fonction posant problème :
- J'ai à disposition un tableau TAB de taille n*n (en gros, une grille), et je souhaite poser aléatoirement sur cette grille un nombre X d'avions. Bien évidemment, on ne peut pas avoir deux avions sur la même case. Pour déterminer le nombre d'avions déjà posés, on dispose également d'un compteur C. On a également X <= n².
- Pour ce faire, j'ai un pseudo-code du genre :

Code : Tout sélectionner

C = 0
while C != X : 
    (i,j) = rd.randint(0, n), rd.randint (0,n) #On affecte à i et j deux entiers aléatoires de [0, n]
    if not TAB[i][j] :  #Les avions sont étiquetés par un nombre différent de 0, donc si TAB[i][j] == 0, c'est que la case est libre
        TAB[i][j] == C
        C += 1
En meilleur cas, la complexité de la fonction est en O(X), en pire cas, la fonction ne termine pas (bon, là, c'est pire que le pire cas, car la fonction termine presque sûrement à vue de nez), mais comment déterminer une complexité en moyenne ? Sur le sujet d'option info de Centrale 2018, j'ai vu qu'on pouvait calculer dans certains cas l'espérance de la complexité, mais j'ai pas réussi cette question lorsque j'ai passé l'épreuve cette année, et j'ai pas non plus trouvé de corrigé. :mrgreen:
Merci d'avance !

Messages : 0

Inscription : 13 févr. 2018 09:22

Profil de l'utilisateur : Élève de lycée

Re: TIPE - Calcul de complexité et probas

Message par matmeca_mcf1 » 27 juin 2018 22:35

Voici une question intermédiaire qui pourrait vous aider: on regarde les variables aléatoires $ (X_i)_{i\in\mathbb{N}} $ à valeurs dans $ \{0,1\} $. Les $ X_i $ sont des iid de loi $ P(X_i=0)=1-p $ et $ P(X_i=1)=p $ avec $ p\in\rbrack0,1\lbrack $.

Calculer l'espérance de la variable aléatoire $ \tau=\min\{i:X_i=1\} $.
Ancien ENS Cachan (maths) 1999--2003
Enseignant-Chercheur à l'Enseirb-Matmeca (Bordeaux INP) filière matmeca
Les opinions exprimées ci-dessus sont miennes et ne reflètent pas la position officielle de l'école dans laquelle j'enseigne.

Répondre