Algorithmique avanc´ee
Examen du 29 janvier 2002, 8h00-11h00
Jean-Michel Dischler et Fr´ed´eric Vivien
Aucun document n’est autoris´e
Remarques et commentaires :
– Commencez par lire le sujet dans son int´egralit´e.
– Les deux probl`emes sont ind´ependants les uns des autres.
– ´Ecrivez lisiblement et en fran¸cais, car les copies seront lues (anonymat oblige) !
– Facilitez la lecture et la compr´ehension des algorithmes propos´es.
– Ce sujet est infaisable en trois heures : sa longueur excessive vous permet de choisir `a quelles
questions vous souhaitez r´epondre, et vous n’avez aucunement besoin de tout faire pour d´ecrocher une
tres bonne note. Le bareme, sur 30 points, est indicatif.
Rappels
Th´eor`eme 1 (R´esolution des r´ecurrences « diviser pour r´egner »).
Soient a ≥ 1 et b > 1 deux constantes, soit f (n) une fonction et soit T (n) une fonction d´efinie pour les
entiers positifs par la r´ecurrence :
ou l’on interprete n/b soit comme (cid:98)n/b(cid:99), soit comme (cid:100)n/b(cid:101).
T (n) = aT (n/b) + f (n),
T (n) peut alors ˆetre born´ee asymptotiquement comme suit :
1. Si f (n) = O(n(logb a)−(cid:15)) pour une certaine constante (cid:15) > 0, alors T (n) = Θ(nlogb a).
2. Si f (n) = Θ(nlogb a), alors T (n) = Θ(nlogb a log n).
3. Si f (n) = Ω(n(logb a)+(cid:15)) pour une certaine constante (cid:15) > 0, et si af (n/b) ≤ cf (n) pour une constante
c < 1 et n suffisamment grand, alors T (n) = Θ(f (n)).
Publicité
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 contenant n morceaux pour une dur´ee 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 enregistr´e au plus une fois sur la cassette.
Notations. Pour faciliter l’´ecriture des algorithmes, nous supposons que tous les morceaux durent un
nombre entier de minutes et qu’ils sont tous de dur´ee non nulle ! Nous notons n le nombre de morceaux et,
afin d’ˆetre g´en´eral, d la dur´ee maximale enregistrable sur une face de la cassette (dans l’exemple ci-dessus,
d = 30). Finalement, nous notons di la dur´ee du ie morceau (pour 1 ≤ i ≤ n).
Le choix des morceaux `a enregistr´e est d´etermin´e par la politique d’enregistrement. Plusieurs politiques
sont envisageables.
1
1.1 Un maximum de musique, quitte `a couper des morceaux (2 points)
Dans cette partie nous cherchons `a maximiser la dur´ee totale de musique enregistr´ee sur la cassette,
sachant que l’on s’autorise `a couper un morceau (et ce autant de fois que n´ecessaire).
1. Proposez un algorithme glouton de r´esolution du probl`eme. (1 point)
Proposition de notation : si le morceau i n’est pas enti`erement enregistr´e sur une face de la cassette
mais seulement un fragment de longueur f , on pourra utiliser la notation : i( f
di
).
2. Quelle est sa complexit´e ? (1 point)
1.2 Un maximum de musique mais sans couper de morceaux (19 points)
Publicité
Dans cette partie nous cherchons `a maximiser la dur´ee totale de musique enregistr´ee sur la cassette,
sachant que l’on interdit de couper un morceau : un morceau figure en entier sur une face ou n’est pas
enregistr´e du tout.
1. Relation de r´ecurrence. On note dur´ee(i, t1, t2) la dur´ee maximale de musique que l’on peut enregis-
trer sur la cassette, sachant que l’on peut mettre au maximum t1 minutes de musique sur la premi`ere
face et t2 sur la deuxi`eme, et sachant que l’on n’enregistre que des morceaux parmi les i premiers.
dur´ee(n, d, d) nous donnera donc la solution de notre probl`eme.
Proposez une formule de r´ecurrence d´efinissant dur´ee(i, t1, t2). (3 points)
Indication : dans une solution optimale, soit le ie morceau est enregistr´e sur la premi`ere face, soit il
est enregistr´e sur la deuxi`eme, soit il n’est enregistr´e sur aucune des deux faces.
Note sur la correction. Toutes les questions suivantes d´ependent de la formule ´etablie `a cette question
ci. Ces questions seront corrig´ees d’apres votre r´eponse a cette question : par exemple, si l’algorithme
que vous proposerez `a la question 3a est bien la transcription de votre formule de r´ecurrence sous la
forme d’un algorithme de programmation dynamique, vous obtiendrez le maximum de points `a cette
question, mˆeme si votre formule de r´ecurrence est fausse.
2. R´esolution r´ecursive. (3 points)
(a) Proposez un algorithme de r´esolution r´ecursive du probl`eme calculant simplement la r´ecurrence
´etablie `a la question pr´ec´edente. (1 point)
(b) Montrez que cet algorithme est de complexit´e super-polynomiale dans le pire cas. (2 points)
Indication : vous pourrez supposer ici que tous les morceaux durent une minute.
3. R´esolution par programmation dynamique « pure ». (4 points)
(a) Proposez un algorithme bas´e sur le principe de la programmation dynamique et r´esolvant notre
probl`eme. Cet algorithme utilisera bien ´evidemment la relation de r´ecurrence pr´ec´edemment
Publicité
´etablie. (3 points)
(b) Quelle est la complexit´e de cet algorithme ? (1 point)
4. R´esolution par recensement. (5 points)
(a) Proposez un algorithme bas´e sur le principe de recensement (variante de la programmation dy-
namique) et r´esolvant notre probl`eme. (3 points)
(b) Quelle est la complexit´e de cet algorithme ? (1 point)
(c) La solution par programmation dynamique « pure » et celle par recensement sont-elles de com-
plexit´es comparables ? Un des deux algorithmes effectue-t-il plus de calculs que l’autre (sans tenir
compte des initialisations) ? (1 point)
5. S´election des morceaux. Jusqu’`a pr´esent, tout ce que l’on a fait, c’est de calculer la dur´ee totale
maximale de musique enregistrable sous les conditions de l’´enonc´e. Nous n’avons pas encore expli-
cit´e comment s´electionner les morceaux qui permettent d’atteindre ce maximum. Modifiez un de vos
algorithmes pour qu’il g´en`ere une telle liste des morceaux (une liste par face). (4 points)
2
´Elections pr´esidentielles aux ´Etats-Unis (9 points)
Le d´ecompte des voix apres une ´election pr´esidentielle aux ´Etats-Unis est un probleme excessivement
sensible et qui doit ˆetre r´esolu le plus rapidement possible. Ce probl`eme se trouve compliqu´e par le fait que
n’importe qui peut recevoir des voix et ˆetre ´elu, les ´electeurs pouvant tout simplement ´ecrire sur leur bulletin
la personne pour laquelle ils votent 1. Dans le pire des cas le nombre de personnes ayant re¸cu au moins une
voix est ´egal au nombre de bulletins !
Notations. Nous notons n le nombre des votes. Ces votes sont stock´es dans le tableau Votes. Pour faciliter
l’´ecriture des algorithmes, nous supposerons que n est une puissance de deux (il existe donc un entier p tel
que n = 2p). Nous supposons ´egalement que la seule op´eration `a notre disposition nous permet de v´erifier si
Publicité
deux ´el´ements sont ou non ´egaux.
Probleme. Nous nous int´eresserons ici uniquement au probleme de savoir si quelqu’un a obtenu la majorit´e
absolue des voix, c’est-`a-dire si quelqu’un a obtenu strictement plus de n/2 voix.
1. Algorithme na¨ıf. (3 points)
(a) ´Ecrivez un algorithme qui calcule le nombre de voix re¸cues par le citoyen x parmi les votes stock´es
entre les indices i et j du tableau Votes. (0,5 point)
(b) Quelle est la complexit´e de cet algorithme ? (1 point)
(c) Au moyen de l’algorithme pr´ec´edent, ´ecrivez un algorithme Majorit´e-Absolue qui v´erifie si,
parmi les citoyens qui ont re¸cu des voix, il en existe un qui a remport´e la majorit´e absolue des
votes enregistr´es dans le tableau Votes. (0,5 point)
(d) Quelle est la complexit´e de cet algorithme ? (1 point)
2. Algorithme « diviser pour r´egner ». (6 points)
(a) Proposez un algorithme Majorit´e-Absolue-DIV construit suivant le paradigme « diviser pour
r´egner ». Cet algorithme divisera en deux le tableau Votes sur lequel il travaille. Cet algorithme
renverra le couple (Vrai, x) s’il existe un citoyen (not´e x) ayant re¸cu la majorit´e absolue des
votes stock´es dans le tableau Votes et renverra le couple (Faux, 0) sinon. (4 points)
(b) Quelle est la complexit´e de cet algorithme ? (2 points)
1Cette information, aussi loufoque qu’elle paraisse, est v´eridique.