Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

DEVUIP Service scolarit´ e Ann´ ee : 2012/2013 Semestre 2 PARCOURS : Licence LI

DEVUIP Service scolarit´ e Ann´ ee : 2012/2013 Semestre 2 PARCOURS : Licence LIMI201 & LIMI211 UE J1MI2013 : Algorithmes et Programmes ´ Epreuve : Devoir Surveill´ e Terminal Date : Lundi 10 juin 2013 Heure : 8 heures 30 Dur´ ee : 1 heure 30 Documents : non autoris´ es ´ Epreuve de M. Alain Griffault SUJET + CORRIGE Avertissement – La plupart des questions sont ind´ ependantes. – ` A chaque question, vous pouvez au choix r´ epondre par un algorithme ou bien par un programme python. – Les indentations des fonctions ´ ecrites en Python doivent ˆ etre respect´ ees. – L’espace laiss´ e pour les r´ eponses est suf- ﬁsant (sauf si vous utilisez ces feuilles comme brouillon, ce qui est fortement d´ econseill´ e). Question Points Bonus Points Score Mise en bouche 7 0 Algorithmes de rang 13 1 Total: 20 1 Exercice 1 : Mise en bouche (7 points) (a) (1 point) Deux nombres sont oppos´ es si leur somme est ´ egale ` a 0. Deux nombres sont inverses si leur produit est ´ egal ` a 1. ´ Ecrire un algorithme sontInvOuOpp(a,b) o` u a et b sont deux nombres, qui retourne Vrai si a et b sont inverses ou oppos´ es, Faux sinon. Solution: Deux solutions parmi d’autres. def sontInvOuOpp (a , b ) : return a+b==0 or a∗b==1 Algorithme 1: SontInvOuOpp(a,b) Donn´ ees : Deux nombres a et b retourner (a+b=0) OU (a*b=1); (b) (2 points) ´ Ecrire un algorithme existeInvOuOppConsecutifs(T) o` u T est un tableau de nombres, qui retourne Vrai si T contient deux nombres cons´ ecutifs oppos´ es ou inverses, Faux sinon. Solution: Deux solutions parmi d’autres. def existeInvOuOppConsecutifs (T) : for i in range ( len (T) −1): i f sontInvOuOpp (T[ i ] ,T[ i +1]): return True return False Algorithme 2: ExisteInvOuOppConsecutifs(T) Donn´ ees : Un tableau T de nombres pour i=0 ` a len(T)-2 faire si sontInvOuOpp(T[i],T[i+1]) alors retourner True; retourner False; UE J1MI2013 : Algorithmes et Programmes DS Terminal, Ann´ ee 2012/2013 (c) (2 points) ´ Ecrire un algorithme existeInvOuOpp(T) o` u T est un tableau de nombres, qui retourne Vrai si T contient deux nombres, ayant des indices diﬀ´ erents, oppos´ es ou inverses, Faux sinon. Solution: Deux solutions parmi d’autres. def existeInvOuOpp (T) : for i in range ( len (T) −1): for j in range ( i +1, len (T) ) : i f sontInvOuOpp (T[ i ] ,T[ j ] ) : return True return False Algorithme 3: ExisteInvOuOpp(T) Donn´ ees : Un tableau T de nombres pour i=0 ` a len(T)-2 faire pour j=i+1 ` a len(T)-1 faire si sontInvOuOpp(T[i],T[j]) alors retourner True; retourner False; (d) (2 points) ´ Ecrire un algorithme nbInvOuOpp(T) o` u T est un tableau de nombres, qui retourne le nombre de paires d’indices (i,j) telles que : d’une part i<j ; d’autre part T[i] et T[j] soient des nombres oppos´ es ou inverses. Solution: Deux solutions parmi d’autres. def nbInvOuOpp(T) : nb = 0 for i in range ( len (T) −1): for j in range ( i +1, len (T) ) : i f sontInvOuOpp (T[ i ] ,T[ j ] ) : nb = nb+1 return nb Algorithme 4: NbInvOuOpp(T) Donn´ ees : Un tableau T de nombres nb ←0; pour i=0 ` a len(T)-2 faire pour j=i+1 ` a len(T)-1 faire si sontInvOuOpp(T[i],T[j]) alors nb ←nb+1; retourner nb; Exercice 2 : Algorithmes de rang (13 points) Le probl` eme de la s´ election consiste ` a trouver dans un tableau de nombres l’´ el´ ement dit de rang i. Pour cet exercice, du fait que les indices d’un tableau T sont compris entre 0 et longueur(T)-1, nous admettrons que l’´ el´ ement de rang 0 est le plus petit ´ el´ ement du tableau, et que l’´ el´ ement de rang longueur(T)-1 est le plus grand. Exemple : Soit T = [8, 6, 53, 8, 2, 9, 3, 10], alors : – Les ´ el´ ements de rang <0 sont ind´ eﬁnis. – L’´ el´ ement de rang 0 est 2. – L’´ el´ ement de rang 1 est 3. – L’´ el´ ement de rang 2 est 6. – L’´ el´ ement de rang 3 est 8. – L’´ el´ ement de rang 4 est 8. – L’´ el´ ement de rang 5 est 9. – L’´ el´ ement de rang 6 est 10. – L’´ el´ ement de rang 7 est 53. – Les ´ el´ ements de rang >7 sont ind´ eﬁnis. Page 2 sur 9 UE J1MI2013 : Algorithmes et Programmes DS Terminal, Ann´ ee 2012/2013 Remarque 1 : Une solution simple au probl` eme de la s´ election consiste ` a utiliser un algorithme quelconque de tri, puis de retourner l’´ el´ ement de rang souhait´ e. Algorithme 5: Rang(T,rang) Donn´ ees : Un tableau T de nombres, et rang un entier R´ esultat : Si rang est un indice, alors T[rang] apr` es avoir tri´ e T si rang<0 OU rang≥longueur(T) alors retourner nil; Trier(T); retourner T[rang]; Remarque 2 : Il est facile de se persuader qu’il n’est pas utile de trier tout le tableau pour avoir une solution au probl` eme de la s´ election. Dans cet exercice, nous allons adapter des algorithmes de tri vus en cours aﬁn d’obtenir des algorithmes de rang plus eﬃcaces que le pr´ ec´ edent. Dans toute la suite de l’exercice, vous pourrez utiliser la fonction classique Echange(T,i,j) qui ´ echange les valeurs du tableau T indic´ ees par i et j. def echange (T, i , j ) : TMP = T[ i ] T[ i ] = T[ j ] T[ j ] = TMP Algorithme 6: Echange(T,i,j) Donn´ ees : Un tableau T de nombres, et deux indices i et j R´ esultat : T[i] et T[j] ´ echang´ es aux ←T[i]; T[i] ←T[j]; T[j] ←aux; (a) Solution adapt´ ee du tri par s´ election vu en cours. def t r i S e l e c t i o n (T) : for i in range ( len (T) ) : iMin = i for j in range ( i +1, len (T) ) : i f T[ j ]<T[ iMin ] : iMin = j i f iMin!= i : echange (T, i , iMin ) Algorithme 7: TriSelection(T) Donn´ ees : Un tableau T de nombres R´ esultat : Le tableau T tri´ e en ordre croissant pour i=0 ` a longueur(T)-1 faire iMin ←i; pour j=i+1 ` a longueur(T)-1 faire si T[j] <T [iMin] alors iMin ←j; si i ̸= iMin alors Echange(T,i,iMin); Il semble ´ evident qu’une fois la valeur d´ esir´ ee bien plac´ ee dans le tableau, il est inutile de continuer le tri. Page 3 sur 9 UE J1MI2013 : Algorithmes et Programmes DS Terminal, Ann´ ee 2012/2013 i. (2 points) ´ Ecrire un algorithme rangSelection(T,r) fortement inspir´ e de l’algorithme ou du programme python triSelection(T) qui r´ esout le probl` eme de la s´ election. Ne pas oublier de s’assurer que le rang d´ esir´ e correspond ` a un indice du tableau. Solution: Deux solutions parmi d’autres. def rangSelection (T, r ) : i f r<0 or r>=len (T) : return None for i in range ( r +1): iMin = i for j in range ( i +1, len (T) ) : i f T[ j ]<T[ iMin ] : iMin = j i f iMin!= i : echange (T, i , iMin ) return T[ r ] Algorithme 8: RangSelection(T,r) Donn´ ees : Un tableau T de nombres, et un indice r R´ esultat : L’´ el´ ement de rang r du tableau T si r<0 OU r ≥longueur(T) alors retourner nil; pour i=0 ` a r faire iMin ←i; pour j=i+1 ` a longueur(T)-1 faire si T[j] <T [iMin] alors iMin ←j; si i ̸= iMin alors Echange(T,i,iMin); retourner T[r]; ii. (1 point) Compl´ eter le tableau des complexit´ es en fonction de n=longueur(T) et du rang r. Rappel : Les complexit´ es ne d´ ependent pas de valeurs particuli` eres des param` etres n et r, mais de valeurs particuli` eres contenues dans le tableau. Solution: TriSelection(T) RangSelection(T,r) Temps (meilleur des cas) Ω(n2) Ω(n × r) Temps (pire des cas) O(n2) O(n × r) Espace (meilleur des cas) Ω(1) Ω(1) Espace (pire des cas) O(1) O(1) Non demand´ e : Il est facile d’am´ eliorer (un peu) la solution en s´ electionnant les valeurs minimales (comme ici) lorsque r < n/2, et en s´ electionnant les valeurs maximales lorsque r ≥n/2. Les complexit´ es s’expriment alors en rempla¸ cant r par min(r, n −r). (b) Solution adapt´ ee du tri ` a bulle vu en cours. def t r i B u l l e (T) : for i in range ( len (T) −1 ,0 , −1): for j in range ( i ) : i f T[ j ]>T[ j +1]: echange (T, j , j +1) uploads/Litterature/ dst-2013-corrige.pdf