Ce module met en jeu les connaissances et le savoir-faire qu'on doit attendre d'un apprenant à la fin du premier cycle universitaire. Il a pour objectif de donner à l'apprenant des connaissances sur les algorithmes et structures de données incontournables dans les logiciels. Les algorithmes de tri et les structures de données dynamiques seront au centre du contenu. Au terme de ce module l'apprenant doit également disposer des connaissances nécessaires pour élaborer systématiquement les algorithmes, analyser et évaluer la complexité des algorithmes, et choisir les algorithmes et structures de données appropriés dans un problème donné. Les connaissances et compétences fournies ici doivent façonner la réflexion pour aborder les problèmes dans divers domaines professionnels. Dans le cadre du projet DDI l'apprentissage des concepts se fera directement sur le projet choisi.
- Bases mathématiques de l'analyse de la complexité: sommation, relations de récurrence, notation asymptotique, etc.
- Introduction à la complexité des algorithmes: Dimensions de la complexité (temps et espace)
- Algorithmes de tri: Tri par insertion, tri par fusion, tri rapide, tri bulle, tri sur le tas, ripple sort
- Structures de données dynamiques: Rappel sur les tableaux et les structures de données statiques; pointeurs et listes linéaires chaînées; listes chaînées simples et listes chaînées doubles
- Structures de données complexes: Arbres, files d'attente (FIFO), files d'attente avec priorité
- Algorithmes de recherche: arbres de recherche binaires, arbres de recherche équilibrés (balanced), tableaux de hachage
- Techniques de conception d'algorithmes: Diviser-et-maîtriser
- Implémentation d'algorithmes et de structures de données
- Algorithmes et structures de données de traitement des graphes: recherche en profondeur (depth first search); recherche en largeur (breadth first search)
- Les environnements intégrés de développement (Integrated Development Environment, IDE): Outils de développement intégrés
- Exploration et apprentissage d'un environnement: Ex. Ecclipse, CodeBlocs, etc.