Structures de données et algorithmes

Résumé global

Cours fondamental sur l’organisation, la manipulation et la recherche des données à l’aide de structures de données classiques et des algorithmes associés. Le cours m’a permis d’apprendre à choisir des structures adaptées à un problème donné, à comparer différentes approches algorithmiques et à analyser leur efficacité en temps et en mémoire.

Technologies utilisées

Notions vues dans ce cours

• Révision de Java et des bases de la programmation orientée objet
• Encapsulation, héritage, polymorphisme et composition
• Analyse de la complexité spatiale et temporelle
• Notation grand O : meilleur cas, cas moyen, pire cas
• Tableaux et opérations associées
• Piles et files
• Récursivité et comparaison avec l’itération
• Algorithmes de tri simples : bulles, sélection, insertion
• Algorithmes de tri avancés : rapide, fusion, Shell
• Listes chaînées : simples, doubles, circulaires et triées
• Types abstraits de données et itérateurs
• Arbres binaires et arbres binaires de recherche
• Tas
• Tables de hachage
• Fonctions de hachage et résolution de collisions
• Choix d’une structure de données et d’un algorithme adaptés à un problème

Travaux et éléments évalués

• Travail 1 sur les concepts fondamentaux et l’analyse d’algorithmes
• Travail 2 sur les structures de données et les algorithmes associés
• Implémentations en Java dans Eclipse
• Examen intra
• Examen final