Au terme de ce cours, l'étudiant aura acquis les techniques de base en conception et manipulation des structures de données ainsi qu'en algorithmie.

Définition des types abstraits de données pour la description et la mise en œuvre des algorithmes. Complexité et techniques d'analyse des algorithmes. Structures de données classiques (listes, files de priorité, arbres, graphes, etc.). Opérations ensemblistes élémentaires. Techniques de tri. Stratégies algorithmiques (diviser pour résoudre, programmation dynamique, algorithme glouton, recherches locales). Graphes orientés et non orientés (représentation, algorithmes de parcours). Structures de données et algorithmes pour le stockage externe. Types de fichiers (définition, supports physiques, organisation, accès).

Séances de laboratoire et travaux pratiques axés sur la résolution de problèmes classiques. Travaux réalisés avec le langage C.

Précision sur le préalable : il concerne les étudiants des profils E, M et P.

Un ordinateur est un outil qui traite de l’information. Le traitement de l’information inclut la manière dont celle-ci est organisée dans l’ordinateur, comment elle peut être manipulée et comment elle peut être utilisée. Ce cours traitera d’une façon systématique cet aspect non négligeable de l’information.

Objectifs spécifiques

L’objectif principal du cours porte sur la définition, l’usage et la manipulation des structures de données fondamentales ainsi que leurs algorithmes associés. Les applications typiques de ces structures de données sont aussi couvertes.

39    heures de cours magistral (enseignement théorique)

36    heures de laboratoire (projet de session)

3      heures de travail personnel (en moyenne) par semaine

À chaque semaine, trois heures de cours magistraux et trois heures de laboratoire sont données. Les cours présentent les divers concepts théoriques alors que les laboratoires donnent la chance aux étudiants d’approfondir leurs connaissances en solutionnant des problèmes concrets. Les différents laboratoires abordent, par le biais de projets stimulants, les principaux sujets du cours tout en amenant l’étudiant à parfaire ses compétences globales en informatique.