1 – Algorithme glouton de remplissage des faces d'une cassette Note sur la correction Toutes les questions suivantes dépendent de la formule établie `a cette
| Previous PDF | Next PDF |
[PDF] Algorithmique avancée Corrigé de lexamen du 29 janvier 2002
1 – Algorithme glouton de remplissage des faces d'une cassette Note sur la correction Toutes les questions suivantes dépendent de la formule établie `a cette
[PDF] TD dalgorithmique avancée Corrigé du TD 2 : récursivité
TD d'algorithmique avancée Corrigé du TD 2 : récursivité Jean-Michel Montrez que la complexité (en nombre d'additions) de cet algorithme est en Ω(2 n 2 )
[PDF] SUJET + CORRIGE
UE J1BS7202 : Algorithmique et Programmation Épreuve : Examen Date : Jeudi 19 Écrire un algorithme sontInvOuOpp(a,b) o`u a et b sont deux nombres,
[PDF] Algorithmique Avancée et Complexité Fiche TD correction
Algorithmique Avancée et Complexité 2010–2011 Master 1 d'Informatique S Tison Fiche TD correction : Algorithmes gloutons Exercice 1 : Optimal ? Q 1
[PDF] Corrigé de lexamen de rattrapage
Module ''Algorithmique Avancée et Complexité'' Date : 30/01/2012 Corrigé de l' examen de rattrapage
[PDF] Algorithmique avancée 2017 - Département Informatique
Matière 1 : Algorithmique avancée et complexité, écrire un algorithme non naïf de complexité minimale pour trouver dans Corrigé Exercice 1 :
[PDF] exercices corrigés algorithmepdf
Ecrire un algorithme qui demande à l'utilisateur un nombre compris entre 1 et 3 Réécrire l'algorithme précédent, mais cette fois-ci on ne connaît pas d'avance
[PDF] Exercices avec Solutions
En fait, le chargé du TD Exercices Corrigés d'Algorithmique – 1ére Année MI 5 Solution 3 : en utilisant une boucle Tantque + Lecture avant la boucle
[PDF] TD dalgorithmique avancée Corrigé du TD 4 : recherche de l
Corrigé du TD 4 : recherche de l'élément majoritaire Écrivez un algorithme qui calcule le nombre d'occurrences d'une valeur x présentes entre les indices i
[PDF] Algorithmique – Travaux Dirigés - AAATE
Corrigé Exercice 1 – Affectations 1 Considérons les algorithmes ci-dessous (a) Quel Algo – Corrigé TD – 1 il faut forcer la conversion en réel avant la divi-
[PDF] sujet d'examen de biologie animale
[PDF] qcm biologie animale s2
[PDF] examen biologie animale l1
[PDF] oscillateur harmonique quantique correction
[PDF] oscillateur harmonique quantique exercices corrigés pdf
[PDF] exercices corrigés mécanique quantique oscillateur harmonique pdf
[PDF] mécanique quantique solutions des examens corrigés
[PDF] examen corrige de mecanique quantique s5
[PDF] mecanique quantique exercices corrigés pdf s4
[PDF] examen pharmacologie générale
[PDF] exercices corrigés de pharmacologie générale
[PDF] qcm pharmacologie generale corrigé
[PDF] exercice pharmacologie infirmier
[PDF] qcm pharmacologie speciale pdf
Algorithmique avancee
Corrige de l'examen du 29 janvier 2002, 8h00-11h00Jean-Michel Dischler et Frederic Vivien
Aucun document n'est autorise
1 Enregistrement d'un CD sur cassette (21 points)
Nous avons a notre disposition une cassette de 60 minutes : sur chacune de ses faces nous pouvons donc
enregistrer 30 minutes de musique. Nous souhaitons enregistrer sur cette cassette des morceaux provenant
d'un CD contenantnmorceaux pour une duree totale de 78 minutes : nous allons donc devoir choisir quels
morceaux mettre sur la cassette et lesquels ne pas enregistrer, sachant que nous nous imposons qu'un morceau
du CD soit enregistre au plus une fois sur la cassette. Notations.Pour faciliter l'ecriture des algorithmes, nous supposons que tous les morceaux durent unnombre entier de minutes et qu'ils sont tous de duree non nulle! Nous notonsnle nombre de morceaux et,
an d'^etre general,dla duree maximale enregistrable sur unefacede la cassette (dans l'exemple ci-dessus,
d= 30). Finalement, nous notonsdila duree duiemorceau (pour 1in).Le choix des morceaux a enregistre est determine par la politique d'enregistrement. Plusieurs politiques
sont envisageables.1.1 Un maximum de musique, quitte a couper des morceaux(2 points)
Dans cette partie nous cherchons a maximiser la duree totale de musique enregistree sur la cassette,sachant que l'on s'autorise a couper un morceau (et ce autant de fois que necessaire).1.Proposez un algorithme glouton de resolution du probleme. (1 point)
Proposition de notation: si le morceauin'est pas entierement enregistre sur une face de la cassette mais seulement un fragment de longueurf, on pourra utiliser la notation :i(fdi). L'algorithme est presente gure 1.2.Quelle est sa complexite? (1 point) Chacune des deux boucles1.2 Un maximum de musique mais sans couper de morceaux (19 points)
Dans cette partie nous cherchons a maximiser la duree totale de musique enregistree sur la cassette, sachant que l'oninterditde couper un morceau : un morceau gure en entier sur une face ou n'est pasenregistre du tout.1.Relation de recurrence.On noteduree(i;t1;t2) la duree maximale de musique que l'on peut enregis-
trer sur la cassette, sachant que l'on peut mettre au maximumt1minutes de musique sur la premiere face ett2sur la deuxieme, et sachant que l'on n'enregistre que des morceaux parmi lesipremiers. duree(n;d;d) nous donnera donc la solution de notre probleme. Proposez une formule de recurrence denissantduree(i;t1;t2). (3 points)Indication: dans une solution optimale, soit leiemorceau est enregistre sur la premiere face, soit il
est enregistre sur la deuxieme, soit il n'est enregistre sur aucune des deux faces.1Glouton-Coupeur(n,d)
t 1 d t 2 d face 1 ; face 2 ; pouri 1 anfaired0i di i 1 tant quet1>0 etinfaire sid0it1 alors t1 t1d0iface1 face1[ fig
i i+ 1 sinon d0i d0it1
face1 face1[ fi(t1di)g
t 1 0 tant quet2>0 etinfaire sid0it2 alors t2 t2d0iface2 face2[ fig
i i+ 1 sinon d0i d0it2
face2 face2[ fi(t2di)g
t2 0Fig.1 { Algorithme glouton de remplissage des faces d'une cassette.Note sur la correction.Toutes les questions suivantes dependent de la formuleetablie a cette question
ci. Ces questions seront corrigees d'apresvotrereponse a cette question : par exemple, si l'algorithme
que vous proposerez a la question 3a est bien la transcription de votre formule de recurrence sous la
forme d'un algorithme de programmation dynamique, vous obtiendrez le maximum de points a cette question, m^eme si votre formule de recurrence est fausse.Considerons les trois cas :(a)Leiemorceau est enregistre sur la premiere face. Alors, duree(i;t1;t2) =di+duree(i1;t1di;t2)
(avec ce morceau on enregistre une dureedide musique, et il nous reste toujours une duree det2 libre sur la deuxieme face, alors que l'on a utilisediminutes dest1que l'on avait sur la premiere face). Ceci n'est bien evidemment possible que si la duree restant sur la premiere face (t1) est superieure a la duree du morceau (di) :t1di. Nous notons1la duree totale obtenue dans cette conguration :