Logo ÉTS
Session
Cours
Responsable(s) Stéphane Coulombe

Se connecter
 

Sauvegarde réussie
Echec de sauvegarde
Avertissement
École de technologie supérieure

Responsable(s) de cours : Stéphane Coulombe


PLAN DE COURS

Hiver 2019
GTI310 : Structures de données multimédias (4 crédits)





Préalables
Programme(s) : 7365,7610
             
  Profils(s) : Tous profils  
             
    MAT210 ET LOG121    
             
Unités d'agrément
Total d'unités d'agrément : 64,8 25,0 % 25,0 % 50,0 %




Qualités de l'ingénieur

Qn
Qualité visée dans ce cours  
Qn
  Qualité visée dans un autre cours  
  Indicateur enseigné
  Indicateur évalué
  Indicateur enseigné et évalué



Descriptif du cours

À la fin de ce cours, l’étudiant sera en mesure :

  • de faire des choix judicieux de structures de données et d’algorithmes basés sur une analyse de leur complexité;
  • de concevoir et d’implémenter des algorithmes pour résoudre des problèmes tels la recherche, le tri et la compression de données;
  • de résoudre des problèmes d’analyse d’algorithmes, de représentation et de compression de contenu multimédia.

Rôle des algorithmes et analyse asymptotique. Rappel des types abstraits de données et des structures de données de base : listes, piles, files, arborescences. Techniques de programmation telles la récursivité, et le retour-arrière. Introduction aux arbres binaires. Représentation des structures de données (listes générales et multilistes, arborescences, graphes). Algorithmes de tri (tri rapide, par monceau, pigeonnier) et de recherche (hachage, arbre de recherche). Représentation de données graphiques et d’images. Numérisation des signaux (quantification, échantillonnage, théorème de Nyquist). Algorithmes de compression sans perte (RLE, Huffman, LZW, codage arithmétique) et avec perte. Normes de compression d’images et de séquences vidéo.

Séances de laboratoire : analyser des contenus multimédias à l’aide d’outils logiciels. Concevoir et implémenter des applications permettant de solutionner des problèmes d’optimisation, de tri, de recherche et de codage.




Objectifs du cours

– 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.




Stratégies pédagogiques

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




Utilisation d’appareils électroniques

Il est interdit de capter le cours ou des portions du cours (enregistrement vidéo, enregistrement audio, photographie) en salle de classe ou en laboratoire à moins d'avoir obtenue au préalable la permission de l'enseignant.




Horaire
Groupe Jour Heure Activité
01 Mercredi 13:30 - 17:00 Activité de cours
Vendredi 08:45 - 11:45 Laboratoire



Coordonnées de l’enseignant
Groupe Nom Activité Courriel Local Disponibilité
01 Stéphane Coulombe Activité de cours Stephane.Coulombe@etsmtl.ca A-4474



Cours

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.




Laboratoires et travaux pratiques

Les laboratoires seront composés de projets permettant à l’étudiant de maîtriser et d’approfondir la théorie vue en classe. Il y aura un projet de familiarisation avec les outils multimédias et trois projets touchant l’application de structures de données et algorithmes étudiés en classe.

 

1.      Introduction au multimédia (9 heures) : Permettra à l’étudiant de se familiariser avec des outils d’analyse d’images et de fichiers audio, et de créer un lecteur d’images.

 

2.      Projet relié à la manipulation de fichiers audio (9 heures) : L’étudiant devra effectuer diverses manipulations sur des fichiers audio à l’aide de structures de données de base et d’algorithmes présentés en classe.

 

3.      Projet relié à la théorie des graphes (6 heures) : L’étudiant devra résoudre un problème pratique (un problème d’optimisation par exemple) en appliquant la théorie des graphes et les algorithmes opérants sur les graphes.

 

4.     Projet relié au traitement de données multimédias (12 heures) : L’étudiant devra implanter un système de traitement de données multimédia (codage d’images par exemple) respectant des spécifications précises.

 

 

 NOTE : Si vous éprouvez des difficultés techniques avec le matériel des laboratoires du département, s.v.p. communiquez le problème à support-logti@etsmtl.ca. Consultez le site de cours pour les contenus pour chaque laboratoire.




Utilisation d'outils d'ingénierie

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).




Évaluation
 Travaux de laboratoire (4) 30 %
 Devoirs 10 %
 Examen intra 30 %
 Examen final   30 %

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




Dates des examens intra
Groupe(s) Date
1 20 février 2019



Date de l'examen final
Votre examen final aura lieu pendant la période des examens finaux, veuillez consulter l'horaire à l'adresse suivante : http://etsmtl.ca/Etudiants-actuels/Baccalaureat/Examens-finaux


Politique de retard des travaux
Tout travail (devoir pratique, rapport de laboratoire, rapport de projet, etc.) remis en retard sans motif valable, c’est-à-dire autre que ceux mentionnés dans le Règlement des études (1er cycle, article 7.2.7 b / cycles supérieurs, article 6.5.4 b) se verra attribuer la note zéro, à moins que d’autres dispositions ne soient communiquées par écrit par l’enseignant dans les consignes de chaque travail à remettre ou dans le plan de cours pour l’ensemble des travaux.

Dispositions additionnelles

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.

 

 




Absence à un examen
• Pour les départements à l'exception du SEG :
Dans les cinq (5) jours ouvrables suivant la tenue de son examen, l’étudiant devra justifier son absence d’un examen durant le trimestre auprès de la coordonnatrice – Affaires départementales qui en référera au directeur du département. Pour un examen final, l’étudiant devra justifier son absence auprès du Bureau du registraire. Toute absence non justifiée par un motif majeur (maladie certifiée par un billet de médecin, décès d’un parent immédiat ou autre) à un examen entraînera l’attribution de la note zéro (0).

• Pour SEG :
Dans les cinq (5) jours ouvrables suivant la tenue de son examen, l’étudiant devra justifier son absence auprès de son enseignant. Pour un examen final, l’étudiant devra justifier son absence auprès du Bureau du registraire. Toute absence non justifiée par un motif majeur (maladie certifiée par un billet de médecin, décès d’un parent immédiat ou autre) à un examen entraînera l’attribution de la note zéro (0).



Plagiat et fraude
Les clauses du « Règlement sur les infractions de nature académique de l’ÉTS » s’appliquent dans ce cours ainsi que dans tous les cours du département. Les étudiants doivent consulter le Règlement sur les infractions de nature académique (https://www.etsmtl.ca/docs/ETS/Gouvernance/Secretariat-general/Cadre-reglementaire/Documents/Infractions-nature-academique ) pour identifier les actes considérés comme étant des infractions de nature académique ainsi que prendre connaissance des sanctions prévues à cet effet.  À l’ÉTS, le respect de la propriété intellectuelle est une valeur essentielle et les étudiants sont invités à consulter la page Citer, pas plagier ! (https://www.etsmtl.ca/Etudiants-actuels/Baccalaureat/Citer-pas-plagier).



Documentation obligatoire

Aucun document n’est obligatoire.




Ouvrages de références

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.




Adresse internet du site de cours et autres liens utiles

Le cours est disponible sur moodle.

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