Liste des erreurs détectées dans le recueil "Algorithmique et optimisation"

  • Page 15
    Pour la troisième propriété, les deux signes d'inclusion devraient être des signes "inférieur ou égal" au sens lexicographique.

  • Page 16
    Ligne 3, u indice m+3 est u indice m+2, et u indice m (deux fois) est u indice m+3. Fin du quatrième paragraphe (fin de la démonstration), c'est X indice j (et non indice k) qui ne serait pas complet, contredisant la maximalité de v indice i (et non j).

  • Page 21
    Dans le 4ème graphe de la figure 1.6, les arcs issus du sommet C devraient être orientés dans le sens inverse.

  • Page 42
    Pour la complexité de l'algorithme de Hu, on peut faire mieux que O(|V|log|V|). Il suffit de stocker les tâches prêtes comme une liste de listes, chaque sous-liste contenant des tâches de même niveau et ces sous-listes étant chaînées par niveau décroissant. Lorsqu'une tâche u de niveau n se termine et qu'un de ses successeurs v devient prêt, on sait où insérer v en temps constant dans la liste des tâches prêtes: on doit insérer v dans la sous-liste qui suit la sous-liste contenant u si cette sous-liste est de niveau n-1, sinon il faut créer une nouvelle sous-liste et l'insérer juste derrière la sous-liste de niveau n. La complexité de l'algorithme est alors O(|V|).

  • Pages 42-43
    Pour la question 5, pour être parfaitement correct, il faut d'abord remarquer que le niveau maximal des tâches faites à l'instant t est le niveau maximal parmi toutes les tâches effectuées à l'instant t ou après. En effet, considérons une tâche faite à l'instant t ou après, et de niveau maximal. Puisqu'elle est de niveau maximal, tous ces prédécesseurs ont été exécutés avant t strictement. Donc elle est prête et peut être exécutée dès le top t, et d'après l'algorithme, elle ne peut être doublée que par une tâche de même niveau. Il y a donc une tâche de même niveau effectuée au top t. Le reste de la démonstration suit.

  • Page 50
    N'importe quoi! Certes la relation min(a(i),b(j)) <= min(a(j),b(i)) ne définit pas un ordre au sens large, puisque min(a(i),b(j)) = min(a(j),b(i)) n'implique pas i=j, mais on a bien que deux éléments non comparables dans l'ordre partiel défini vérifient min(a(i),b(j)) = min(a(j),b(i)). C'est d'ailleurs la raison pour laquelle tous les ordres totaux extensions de cet ordre partiel conduisent à la même durée d'ordonnancement. Où avais-je la tête...

  • Pages 56
    Pour la question 4, la priorité est A, D, B, C, E, F, G, H, I (E manquait dans la liste).

  • Pages 58 (début de la question 6)
    À la place de ``Si T_i < D_k'', il faut lire ``Si T_i = D_k''. Dans ce cas, c'est effectivement gagné car on sait que D_k est prédécesseur de toutes les tâches de F_{k-1}.

  • Pages 58 (avant-dernière ligne)
    Soient deux tâches Ti et Tj telles que (manque un s a telles).

  • Pages 60
    Les étiquettes qu'on rajoute sont de plus en plus grandes, pas de plus en plus petites, il faut donc les rajouter en tête de liste, pas en queue.

  • Dos de couverture
    La dernière phrase a été tronquée et le paragraphe prend le sens inverse de l'original. La fin de la dernière phrase devrait être: "[...] tout en insistant sur les problèmes de conception (algorithmique ou mise en place d'une méthode d'optimisation) plutôt que sur les problèmes de mise en oeuvre (programmation)".

    N'hésitez pas à me transmettre toutes les erreurs que vous trouvez, fautes de frappe, d'orthographe et de grammaire incluses! Je me souviens avoir noté un "compléxité" quelque part, mais je ne me souviens plus où.