Paie tes lettres

1 · Dis ce que l'article prouve

Débutant

Que démontrent Chandran et Gajjala ?

Trouver le code préfixe le moins cher est NP-difficile quand les coûts des lettres font partie des données La recette de Huffman donne de mauvais codes quand 0 et 1 coûtent pareil Aucun algorithme rapide n'existe même quand les coûts sont fixés d'avance

2 · Trouve le code le moins cher

Trois symboles de fréquences 20, 12 et 9. La lettre 0 coûte 83, la lettre 1 coûte 84. Chaque mot coûte la somme de ses lettres, multipliée par la fréquence de son symbole.

Intermédiaire

Quel code est le moins cher ?

(0, 10, 11) (10, 0, 11) (1, 00, 01)

3 · Réconcilie les deux résultats

Pour chaque couple fixé de coûts entiers, par exemple 1 et 2, un algorithme exact et rapide existe déjà.

Expert

Pourquoi la preuve de NP-complétude ne le contredit-elle pas ?

Parce que ces algorithmes rapides sont faux Parce que, dans la preuve, M grandit avec les données Parce que la preuve n'utilise que des fréquences toutes égales

4 · Situe la difficulté

La recette de Huffman trouve rapidement la longueur pondérée minimale d'un code.

Expert

Qu'est-ce qui, selon l'article, reste NP-complet ?

Choisir, parmi les codes de cette longueur minimale, celui qui a le moins de 1 pondérés Calculer cette longueur minimale elle-même Vérifier qu'un code donné atteint un coût annoncé

Lettres payées

—