– Procurer à l’étudiant une connaissance approfondie des structures de données classiques

– Initier l’étudiant aux structures de données adaptées au contexte multimédias.

– Initier l’étudiant à la théorie de l’information et aux formats de compression multimédias.

– Procurer à l’étudiant une connaissance approfondie des algorithmes opérant sur les structures de données multimédia.

– Initier l’étudiant à divers concepts de programmation.

– Initier l’étudiant aux notions d’analyse de complexité des algorithmes.

Le cours comprend une partie magistrale (3 heures par semaine) et des séances en laboratoire (3 heures par semaine).

Cette section présente le pan de cours prévu. Il est à noter que certaines modifications pourraient être proposées au cours du trimestre.

1. Présentation du cours et introduction (1,5 heure^[1])

2.  Structures de données classiques (15 heures)

• Rôle des algorithmes et analyse asymptotique
• Structures de données de base : liste, pile, file
• Algorithmes de fouille et de tri, arbre de recherche.
• Graphes : définitions, représentations, applications, heuristiques.

 3.  Algorithmique : autres modèles, paradigmes (3 heures)

• Paradigmes : procédural, fonctionnel, objet, hybride.
• Algorithmes gloutons, dynamiques, probabilistes, programmation linéaire.
• Complexité et problèmes NP-complets.
• Calculs parallèles.

4.    Théorie de l’information (6 heures)

• Introduction à la théorie de l’information.
• Compression sans perte des données.
• Compression avec perte des données multimédias (audio, image, vidéo).

5.    Structures de données multimédias (13,5 heures)

• Données texte, graphique, image, animation, vidéo, audio, hypertexte.
• Indexation de contenu multimédia.
• Outils d’analyse et d’édition multimédia.

 * La matière ne sera pas nécessairement présentée dans cet ordre. Toutefois, l’ensemble des sujets sera présenté dans le cadre de ce cours.

[1] Ces heures sont des heures approximatives d’enseignement pour chaque sujet et incluent le temps alloué à l’examen intra timestriel.

L'étudiant se familiarisera avec les outils de développement de logiciels en Java et les patrons de conception. L’étudiant fera des choix de format des images (JPEG, GIF, BMP, etc.) et de représentation des couleurs (RGB, palette, YUV 4:2:0, 4:4:4).

À noter qu’une moyenne pondérée inférieure à 50% dans les examens intra et final entraine automatiquement un échec au cours. 

Les dates de remise des travaux doivent être respectées. Une pénalité sera applicable aux travaux de laboratoire qui ne sont pas remis à temps selon les modalités suivantes : 10% de retard est appliqué dès qu'un retard est constaté et la pénalité augmente de 15% supplémentaire à chaque journée complète de retard. Toutefois pour le dernier projet de laboratoire et pour les devoirs, aucun retard ne sera toléré et tout retard entrainera automatiquement la note de zéro.

Les étudiants ont la responsabilité de valider l'intégrité de la remise de tous leurs travaux (devoirs et laboratoires). De même, ils ont la responsabilité de vérifier que les fichiers remis sont complets.

Aucun document n’est obligatoire.

Complémentaires fortement recommandés

CORMEN, T.H., C.F. LEISERSON & R.J. RIVEST, Introduction to Algorithms. Third Edition, MIT Press, McGraw Hill, 2009. [1]

LI, Z.N., DREW, M.S., Fundamentals of Multimedia. PrenticeHall, Avril 2014.[2]

Complémentaires

BRASSARD, G. et P. BRATLEY, Algorithmique, conception et analyse. Masson, 1987.

CARRANO, F.M. & J.J. PRITCHARD, Data Abstraction and Problem Solving with Java, Walls and Mirrors. Updated Edition, Addison-Wesley, 2004.

SHAFFER, C.A., A Practical Introduction to Data Structures and Algorithm Analysis. Prentice-Hall, 1998.

ROWE, G.W., An Introduction to Data Structures and Algorithms with Java. Prentice-Hall, 1998.

LEWIS, J. & J. CHASE, Java Software and Structures. Pearson (Addison-Wesley), 2004.

SAYOOD, K, Introduction to data compression, 3rd Edition, Morgan Kaufmann, 2006.

SALOMON, D., MOTTA G., BRYANT, D., Data Compression: The Complete Reference, 4th edition, Springer, 2006.

WITTEN, I.H., A. MOFFAT, T.C. BELL, Managing Gigabytes: Compressing and Indexing Documents and Images. 2nd Edition, Academic Press, 1999.

HOFFMAN, R., Data Compression in Digital Systems. Chapman and Hall, 1997.

NELSON, M., La compression de données. Dunod, 1993.

NELSON, M. & J.L. GAILLY, The Data Compression Book. 2nd Edition, M and T, 1996.

EFFORD, N., Digital Image Processing: A Practical Introduction Using Java. Addison Wesley, 2000.

WANG, Y., J. Ostermann, & Y.Q. Zhang, Video Processing and Communications. Prentice-Hall, 2001.

KOSH, H., Distributed Multimedia Database Technologies Supported by MPEG-7 and by MPEG-21. CRC Press, 2003, ISBN 0-8493-1854-8, 257 pages.

[1] Ce livre sera utilisé comme référence pour la partie algorithmique de cours.

[2] Ce livre sera utilisé comme référence pour la partie multimédia de cours.

Le cours est disponible sur moodle.

Site moodle : https://ena.etsmtl.ca