Objectif
Acquérir les fondements théoriques et pratiques des structures de données et leurs algorithmes dans le but de comprendre comment les justifier, les utiliser et les incorporer dans la résolution des problèmes. L'accent sera mis sur les propriétés fondamentales de ces structures et l'étude de leur complexité (spatiale et temporelle : pire cas, cas moyen et amortie), sans toutefois négliger les aspects reliés à leurs implantations et leurs applications.
Contenu
Introduction à la complexité algorithmique: pire cas, cas moyen et cas amorti. Recherche en table et chaînes de caractères. Listes, piles, files et applications. Arbres : de recherche, AVL, rouge et noir, B-arbres, tas et files de priorité, splay, binomial, Fibonacci, etc. Ensembles disjoints. Graphes: algorithmes de parcours, de cheminement, de flots et géométriques.
Mode(s) de prestation
Présence
Présence de la professeure ou du professeur, de la personne chargée de cours ou de l’équipe pédagogique et des personnes étudiantes à un moment commun dans un lieu de formation déterminé (ex. : salle de classe physique, laboratoire, sortie sur le terrain).
Vidéoconférence
Cours offert simultanément par vidéoconférence à partir d’un site d’enseignement origine, où l’enseignement se fait en présence, sur un ou des sites (lieux de formation) distants identifiés par l’UQAR, selon les procédures et règlements en vigueur. Le cours est suivi de façon simultanée par tous.