SUJET + CORRIGE PDF

cours-python.pdf

22 mars 2018 3. https://python.sdv.univ-paris-diderot.fr/cours-python.pdf ... Nous pourrions utiliser l'algorithme présenté en pseudo-code dans la figure ...

Python au lycée - tome 1

Ce livre n'est donc ni un manuel complet de Python ni un cours Le but est de découvrir des algorithmes

Exercices avec Solutions

Exercices Corrigés d'Algorithmique – 1ére Année MI 5. EXERCICE 1. Ecrire un algorithme qui demande un nombre à l'utilisateur puis calcule et affiche le

Exercices corrigés

Les scripts du cours. Cours no 1 : « Premiers pas en Python ». 1. Affectez les variables temps et distance par les valeurs 6.892 et 19.7.

ALGORITHME SECONDE Exercice 5.1 Ecrire un algorithme qui

EXERCICES – ALGORITHME SECONDE. Exercice 5.1. Ecrire un algorithme qui demande à l'utilisateur un nombre compris entre 1 et 3 corrigé - retour au cours.

Algorithmique et Programmation classe de Seconde

2 Console variables et algorithmes Exercice 4 : automatismes de calcul ... Dans un programme Python

livre-algorithmes.pdf

termes finissent par y contribuer mais ce n'est pas le cas ici (c'est un bon exercice de le prouver). • Dans la pratique on calcule la somme à un certain

SUJET + CORRIGE

Épreuve : Examen Les indentations des fonctions écrites en Python ... Dans cet exercice nous allons adapter des algorithmes de tri vus.

Algorithmique & programmation en langage C - vol.1 - Archive

1 févr. 2019 En TP (ainsi qu'en examen de TP) nous utiliserons également les commentaires pour indiquer à quel exercice correspond quelle partie du ...

Livre du professeur

Python des activités et exercices. numériques intégrées au manuel. Qu'est-ce que le droit à l'image ? Thème 5 p. 122. Vérifier qu'une image est authentique.

Master BioInformatiqueAnn

ee :2013/2014Semestre de decembre 2013

PARCOURS :Master 1

UE J1BS7202 :Algorithmique et Programmation

Epreuve :Examen

Date :Jeudi 19 decembre 2013

Heure :9 heures

Duree :2 heures

Documents : autorises

Epreuve de M. AlainGriffaultSUJET + CORRIGE

Avertissement

La plupart des questions son tind ependantes.

A chaque question, vous pouvez au choix

repondre par un algorithme ou bien par un programme python.

Les inden tationsdes f onctions ecritesen Python

doivent ^etre respectees. L'espace laiss ep ourles r eponsesest susan t(sauf si vous utilisez ces feuilles comme brouillon, ce qui est fortement deconseille).QuestionPointsScore

Mise en bouche7

Algorithmes de rang14

Liste doublement chainee9

Total:30

Exercice 1 : Mise en bouche (7 points)

(a) (1 p oint)Deux nom bresson topp osessi le ursom meest egale a0. Deux nombres sont inverses si leur produit est egal a1.Ecrire un algorithmesontInvOuOpp(a,b)ouaetbsont deux nombres, qui retourneVraisiaetbsont inverses ou opposes,Fauxsinon.

Solution:Deux solutions parmi d'autres.

defsontInvOuOpp(a ,b): returna+b==0orab==1Algorithme 1:SontInvOuOpp(a,b)Donnees:Deux nom bresa et b retourner(a+b=0) OU (a*b=1);(b)(2 p oints) Ecrire un algorithmeexisteInvOuOppConsecutifs(T)ouTest un tableau de nombres, qui retourneVraisiTcontient deux nombresconsecutifsopposes ou inverses,Fauxsinon.

Solution:Deux solutions parmi d'autres.

defexisteInvOuOppConsecutifs (T): foriinrange ( len (T)1): ifsontInvOuOpp(T[ i ] ,T[ i +1]): returnTrue returnFalseAlgorithme 2:ExisteInvOuOppConsecutifs(T)Donnees:Un tabl eauT de n ombres pouri=0alen(T)-2fairesisontInvOuOpp(T[i],T[i+1])alorsretournerTrue;retournerFalse;(c)(2 p oints) Ecrire un algorithmeexisteInvOuOpp(T)ouTest un tableau de nombres, qui retourne VraisiTcontient deux nombres,ayant des indices dierents, opposes ou inverses,Fauxsinon. UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2012/2013

Solution:Deux solutions parmi d'autres.

defexisteInvOuOpp(T): foriinrange ( len (T)1): forjinrange ( i +1,len (T)): ifsontInvOuOpp(T[ i ] ,T[ j ] ) : returnTrue returnFalseAlgorithme 3:ExisteInvOuOpp(T)Donnees:Un tableau T de nom bres

pouri=0alen(T)-2fairepourj=i+1alen(T)-1fairesisontInvOuOpp(T[i],T[j])alorsretournerTrue;retournerFalse;(d)(2 p oints)

Ecrire un algorithmenbInvOuOpp(T)ouTest un tableau de nombres, qui retourne le nombre de paires d'indices(i,j)telles que : d'une partiSolution:Deux solutions parmi d'autres. defnbInvOuOpp(T): nb = 0 foriinrange ( len (T)1): forjinrange ( i +1,len (T)): ifsontInvOuOpp(T[ i ] ,T[ j ] ) : nb = nb+1 returnnbAlgorithme 4:NbInvOuOpp(T)Donnees:Un tableau T de nom bres nb 0;

pouri=0alen(T)-2fairepourj=i+1alen(T)-1fairesisontInvOuOpp(T[i],T[j])alorsnb nb+1;retournernb;Exercice 2 : Algorithmes de rang (14 points)

Le probleme de la selection consiste a trouver dans un tableau de nombres l'element dit de rangi. Pour cet exercice, du fait que les indices d'un tableauTsont compris entre0etlongueur(T)-1, nous admettrons que l'element de rang0est le plus petit element du tableau, et que l'element de rang longueur(T)-1est le plus grand.

Exemple :SoitT= [8;6;53;8;2;9;3;10], alors :

Les elementsde rang <0sont indenis.

L' elementde rang 0est 2.

L' elementde rang 1est 3.

L' elementde rang 2est 6.

L' elementde rang 3est 8.

L' elementde rang 4est 8.

L' elementde rang 5est 9.

L' elementde rang 6est 10.

L' elementde rang 7est 53.

Les elementsde rang >7sont indenis.

Page 2 sur 10

UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2012/2013 Remarque 1 :Une solution simple au probleme de la selection consiste a utiliser un algorithme

quelconque de tri, puis de retourner l'element de rang souhaite.Algorithme 5:Rang(T,rang)Donnees:Un tabl eauT de n ombres,et rang un en tier

Resultat:Si rang est un indice, alors T[rang] apr esa voirtri eT sirang<0 OU ranglongueur(T)alorsretournernil;Trier(T);

retournerT[rang];Remarque 2 :Il est facile de se persuader qu'il n'est pas utile de triertoutle tableau pour avoir une

solution au probleme de la selection. Dans cet exercice, nous allons adapter des algorithmes de tri vus

en cours an d'obtenir des algorithmes de rang plusecacesque le precedent.

Dans toute la suite de l'exercice, vous pourrez utiliser la fonction classiqueEchange(T,i,j)qui echange

les valeurs du tableauTindicees parietj. defechange(T, i , j ):

TMP = T[ i ]

T[ i ] = T[ j ]

T[ j ] = TMPAlgorithme 6:Echange(T,i,j)Donnees:Un tableau T de nom bres,et deux indices i et j

Resultat:T[i] et T[j] echanges

aux T[i];

T[i] T[j];

T[j] aux;(a)Solution adapt eedu tri par s electionvu en cours. deftriSelection (T): foriinrange ( len (T)): iMin = i forjinrange ( i +1,len (T)): ifT[ j]Resultat:Le tableau T tri een ordre croissant pouri=0alongueur(T)-1faireiMin i; pourj=i+1alongueur(T)-1fairesiT[j]Il semble evident qu'une fois la valeur desireebien placeedans le tableau, il est inutile de continuer

le tri.

Page 3 sur 10

UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2012/2013 i. (2 p oints) Ecrire un algorithmerangSelection(T,r)fortement inspire de l'algorithme ou du programme pythontriSelection(T)qui resout le probleme de la selection. Ne pas oublier de s'assurer que le rang desire correspond a un indice du tableau.

Solution:Deux solutions parmi d'autres.

defrangSelection (T, r ): ifr<0orr>=len (T): returnNone foriinrange ( r+1): iMin = i forjinrange ( i +1,len (T)): ifT[ j]Resultat:L' elementde rang r du tableau T sir<0 OU rlongueur(T)alorsretournernil;pouri=0arfaireiMin i; pourj=i+1alongueur(T)-1fairesiT[j]retournerT[r];ii.(1 p oint)Compl eterle tableau des complexit esen fonction d en=longueur(T)et du rangr.

Rappel : Les complexites ne dependent pas de valeurs particulieres des parametres netr, mais de valeurs particulieres contenues dans le tableau.

Temps (meilleur des cas)

(n2) (nr)Temps (pire des cas)O(n2)O(nr)Espace (meilleur des cas) (1) (1)

Espace (pire des cas)O(1)O(1)Non demande :Il est facile d'ameliorer (un peu) la solution en selectionnant les valeurs minimales

(comme ici) lorsquer < n=2, et en selectionnant les valeurs maximales lorsquern=2. Les complexites s'expriment alors en remplacantrparmin(r;nr).(b)Solution adapt eedu tri abulle vu en cours. deftriBulle (T): foriinrange ( len (T)1,0,1): forjinrange ( i ): ifT[ j]>T[ j +1]: echange(T, j , j+1)Algorithme 9:TriBulle(T)Donnees:Un tableau T de nom bres

Resultat:Le tableau T tri een ordre

croissant pouri=len(T)-1a1 decroissantfairepourj=0ai-1fairesiT[j]>T [j+1]alorsEchange(T,j,j+1);

Il semble evident qu'une fois la valeur desireebien placeedans le tableau, il est inutile de continuer

le tri. i. (2 p oints) Ecrire un algorithmerangBulle(T,r)fortement inspire de l'algorithme ou du programme pythontriBulle(T)qui resout le probleme de la selection. Ne pas oublier de s'assurer que le rang desire correspond a un indice du tableau.

Page 4 sur 10

UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2012/2013

Solution:Deux solutions parmi d'autres.

defrangBulle (T, r ): ifr<0orr>=len (T): returnNone foriinrange ( len (T)1,r1,1): forjinrange ( i ): ifT[ j]>T[ j +1]: echange(T, j , j+1) returnT[ r ]Algorithme 10:RangBulle(T,r)Donnees:Un tableau T de nom breset un indice r

Resultat:L' elementde rang r du tableau T

sir<0 OU rlongueur(T)alorsretournernil;pouri=len(T)-1ar, decroissantfairepourj=0ai-1fairesiT[j]>T [j+1]alorsEchange(T,j,j+1);

retournerT[r];ii.(1 p oint)Compl eterle tableau des complexit esen fonction d en=longueur(T)et du rangr.

Solution:TriBulle(T)RangBulle(T,r)

Temps (meilleur des cas)

(n2) (n(nr))Temps (pire des cas)O(n2)O(n(nr))Espace (meilleur des cas) (1) (1)

Espace (pire des cas)O(1)O(1)Non demande :Il est facile d'ameliorer (un peu) la solution en faisant monter les grosses bulles

(comme ici) lorsquern=2, et en faisant descendre les petites bulles lorsquer < n=2. Les complexites s'expriment alors en remplacantnrparmin(r;nr).(c)Solution adapt eedu tri rapide vu e ncours. Soit la variante suivante de l'algorithme de partition basee sur l'algorithme du drapeau Hollandais vu en cours. Cet algorithmepartitionnele tableau en trois zones : la premiere contient des valeurs strictement inferieures a la valeur du pivot; la seconde contient des valeurs egales a la valeur du pivot; et la troisieme des valeurs strictement superieures a la valeur du pivot.

Page 5 sur 10

UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2012/2013 deftroisPartitionner (T,g ,d): pivot = T[ g ] i = g j = i k = d whilej<= k: ifT[ j ] == pivot : j += 1 elifT[ j ]Resultat:i,j,k tel que T[g..i-1] Echanger(T,j,k); k k-1;retourneri,j,k;Rappel :La complexite, vue en cours, detroisPartitionner(T,g,d)est (dg+ 1). i. (1 p oint)Compl eterle tableau suiv antan de sim ulerl'ex ecutionde troisPartitionner.

T= [17;3;21;13;17;25;4];g= 0;d= 6

Solution:Temps!pivot17

couple d'indices echanges(0,1)(2,6)(1,2)(2,3)(5,5) i0123 j012345 k654

Page 6 sur 10

UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2012/2013 ii. (2 p oints)Cette v ersionamelioreedu tri rapide tire prot des trois zones, en ne faisant pas d'appel recursif sur la zone intermediaire, car les valeurs de cette zone sont correctement placees. deftriRapideRec (T,g ,d): ifgRec(T,g,d)Donnees:Un tabl eauT de n ombres, et deux indices g et d

Resultat:Le tableau T[g..d] tri ee n

ordre croissant sigTriRapideRec(T,g,i-1); TriRapideRec(T,k+1,d);Algorithme 13:TriRapide(T)Donnees:Un tabl eauT de n ombres

Resultat:Le tableau T tri een ordre

croissant

TriRapideRec(T,0,longueur(T)-1);

Ecrire des algorithmesrangRapide(T,r)etrangRapideRec(T,g,d,r)fortement inspires des algorithmestriRapide(T)ettriRapideRec(T,g,d), qui resolvent le probleme de la selection. Ne pas oublier de s'assurer que le rang desire correspond a un indice du tableau.

Solution:Deux solutions parmi d'autres.

defrangRapideRec(T,g ,d, r ): ifgk: rangRapideRec(T,k+1,d, r ) defrangRapide(T, r ): ifr<0orr>=len (T): returnNone rangRapideRec(T,0 , len (T)1,r ) returnT[ r ]Algorithme 14:RangRapideRec(T,g,d,r)Donnees:Un tableau T de nom bres,trois indices g, d et r

Resultat:P ositionnel' elementde rang r du

tableau T sigkalorsRangRapideRec(T,k+1,d,r); Algorithme 15:RangRapide(T,r)Donnees:Un tableau T de nom bres,et un indice r

Resultat:L' elementde rang r du tableau T

sir<0 OU rlongueur(T)alorsretournernil;RangRapideRec(T,0,longueur(T)-1,r);

retournerT[r];iii.(1 p oint)Compl eterle tableau des c omplexitesen fonction de n=longueur(T)et du rangr.

Page 7 sur 10

UE J1MI2013 : Algorithmes et Programmes DS Terminal, Annee 2012/2013

Solution:

TriRapide(T)RangRapide(T,r)

Temps (meilleur des cas)

(n)quotesdbs_dbs5.pdfusesText_10

[PDF] SUJET + CORRIGE

Master BioInformatiqueAnn

PARCOURS :Master 1

UE J1BS7202 :Algorithmique et Programmation

Epreuve :Examen

Date :Jeudi 19 decembre 2013

Heure :9 heures

Duree :2 heures

Documents : autorises

Epreuve de M. AlainGriffaultSUJET + CORRIGE

Avertissement

La plupart des questions son tind ependantes.

A chaque question, vous pouvez au choix

Les inden tationsdes f onctions ecritesen Python

Mise en bouche7

Algorithmes de rang14

Liste doublement chainee9

Total:30

Exercice 1 : Mise en bouche (7 points)

Solution:Deux solutions parmi d'autres.

Solution:Deux solutions parmi d'autres.

Solution:Deux solutions parmi d'autres.

Exemple :SoitT= [8;6;53;8;2;9;3;10], alors :

Les elementsde rang <0sont indenis.

L' elementde rang 0est 2.

L' elementde rang 1est 3.

L' elementde rang 2est 6.

L' elementde rang 3est 8.

L' elementde rang 4est 8.

L' elementde rang 5est 9.

L' elementde rang 6est 10.

L' elementde rang 7est 53.

Les elementsde rang >7sont indenis.

Page 2 sur 10

TMP = T[ i ]

T[ i ] = T[ j ]

Resultat:T[i] et T[j] echanges

T[i] T[j];

Page 3 sur 10

Solution:Deux solutions parmi d'autres.

Temps (meilleur des cas)

Resultat:Le tableau T tri een ordre

Page 4 sur 10

Solution:Deux solutions parmi d'autres.

Resultat:L' elementde rang r du tableau T

Solution:TriBulle(T)RangBulle(T,r)

Temps (meilleur des cas)

Page 5 sur 10

T= [17;3;21;13;17;25;4];g= 0;d= 6

Solution:Temps!pivot17

Page 6 sur 10

Resultat:Le tableau T[g..d] tri ee n

Resultat:Le tableau T tri een ordre

TriRapideRec(T,0,longueur(T)-1);

Solution:Deux solutions parmi d'autres.

Resultat:P ositionnel' elementde rang r du

Resultat:L' elementde rang r du tableau T

Page 7 sur 10

Solution:

TriRapide(T)RangRapide(T,r)

Temps (meilleur des cas)