Université Montpellier II
Université Montpellier III
DEUG MASS 1999-2000, 4e semestre Module
d'Algorithmique
Examen final du 16 mai 2000
On désire distribuer un ensemble de 9 tâches {T1,...
T9} dont les durées sont respectivement {1h, 4h, 6h, 3h,
8h, 2h, 5h, 7h, 4h}. Il s'agit de les distribuer entre le moins
possible de personnes mais la durée totale pour une personne
ne doit pas dépasser 8h.
- Déterminer la répartition des 9 tâches
permettant de rendre minimum le nombre de personnes nécessaires.
- Comment déterminer cette répartition
si le nombre et la durée des tâches à réaliser
est quelconque? Donnez le principe de la recherche de solution.
- Proposez une heuristique rapide (sans retour arrière).
- Proposez un minorant simple (à calculer)
du nombre de personnes nécessaires.
- Déduisez des questions 3 et 4 une mesure
de la qualité de la solution obtenue.
Voir le corrigé
Donner, sous forme de programme ou de graphe d'états,
une machine de Turing qui, étant donnée une chaine
composée de a et de c met les "a" à gauche
et les "c" à droite:
- l'alphabet est {a, c, B}
- à partir de la chaîne ...BBacaacccBB...
on obtient ...BBaaaccccBB...
- à partir de la chaine ...BBcacacacaBB...
on obtient ...BBaaaaccccBB...
- on peut remarquer que, si l'on a trouvé
une machine de Turing qui transforme une occurence de "ca"
en "ac", on a avancé vers la solution du problème.
- il n'est pas demandé de trouver une solution
minimale, mais il existe une solution avec 4 états.
Voir le corrigé
Soient les algorithmes récursifs quefaisje(n)
et etmoidonc(n). Ces algorithmes représentent
des fonctions prenant un nombre entier comme argument et renvoyant
un autre nombre entier.
fonction quefaisje(n)
si n pair
^1 + quefaisje(n/2)
sinon
^quefaisje((n-1)/2) |
fonction etmoidonc(n)
si n < 0
^0
sinon
selon (n modulo 4)
0 : ^2 + etmoidonc(n/4)
1 : ^1 + etmoidonc((n-1)/4)
2 : ^1 + etmoidonc((n-2)/4)
3 : ^etmoidonc((n-3)/4) |
- Calculez, pour chacune de ces fonctions, la valeur
renvoyée pour n = 0. Que constatez-vous? Proposez des
modifications pour corriger le problème.
- Calculez, pour chacune de ces fonctions, la valeur
renvoyée quand n = 4p+3, en fonction de la valeur renvoyée
pour n = p.
- Même question pour n = 4p, n=4p+1, n=4p+2.
Qu'en concluez vous?
- Combien d'étapes de calcul sont nécessaires
à chacune de ces fonctions pour calculer leur valeur pour
un argument n entier positif?
Voir le corrigé