Équipe pédagogique Jean-Guillaume Dumas Gerd Finke Sylvain Gravier Frédéric Maffray Michel Mollard Myriam Preissmann

Jeux Combinatoires (Semestre 1) Coloration (Semestre 1) Compression (Semestre 2) Contenu du cours Codage avec ou sans perte Compression irréversible Compression ad hoc (télégraphe, modem, fax) RLE (modems, images nb) Codage statistique Notion de source, extension, induction Codage optimal (Shannon, Entropie, Huffman) Codage arithmetique Codage dynamique (Huffman dynamique, Arithmétique dynamique) Heuristiques de réduction d'entropie Codage par dictionnaire : Lempel-Ziv 77, 78, LZW (compress, gzip, GIF) Codage adaptatif (Move-to-Front, Burrows-Wheeler ou BWT -- bzip2, tar) Un peu de compression avec perte (JPEG, MPEG, MP3) Documents (applets de Szopa) Tables ASCII (7 bits) et ASCII étendu. Arbre de Huffman. Huffman adaptatif. Dictionnaire de Lempel-Ziv Welch. Travaux Pratiques et Dirigés RLE. Entropie Fano, Huffman Move-to-front LZ Bibliographie P. Plumé, Compression de données. Eyrolles 1993 J-P. Guillois. Techniques de compression des images. HERMES 1996. D. Salomon. Data Compression. Springer 1997. G. Herd. Data and Image Compression. Wiley 1996. J-G. Dumas, J-L. Roch, É. Tannier et S. Varrette. Théorie des codes : compression, cryptage, correction. Dunod 2007. Algorithmique dans les réseaux (Semestre 2) Problèmes de flot et de coupe Problèmes de routage (postier chinois et voyageur de commerce)