Exercices corrigés — Algorithmique des textes (informatique (MP2I/MPI))
15 exercices avec corrigé rédigé, du plus simple au plus exigeant.
- Facteur, sous-mot, préfixe : compter
- Le pire cas du naïf, compté exactement
- La table du mauvais caractère
- Dérouler Boyer-Moore, et compter
- Le saut qui recule
- Rabin-Karp à la main, et une collision
- Le modulo qui déborde
- Huffman : construire, coder, chiffrer le gain
- Le décodeur qui perd la dernière lettre
- Le plus petit texte qui piège le décodeur \textsc{lzw}
- Probleme – Codes préfixes et inégalité de Kraft
- Probleme – Chercher motifs en une seule passe
- Probleme – \textsc{lzw} complet, et son test
- Probleme – Un banc d'essai : naïf, Boyer-Moore, Rabin-Karp
- Probleme – Aucun compresseur sans perte ne réduit tous les fichiers