COURS // INF7336 Algorithmes et structures de données
Mes cours favoris
Ce système permet de sélectionner vos cours favoris en prévision de votre inscription qui se fait sur le portail étudiant.
| Trimestre | Cours | Groupe |
|---|
Description du cours
- Cycle : 2
- Nombre de crédits : 3
- Discipline : Informatique
Objectifs
Ce cours vise à approfondir les connaissances des structures de données et des algorithmes et les appliquer à la résolution de problèmes. À la fin de ce cours l'étudiant devra être en mesure de: mettre en oeuvre des structures de données avancées et les algorithmes associés au moyen d'un langage de programmation système orienté objet; choisir des structures de données et des algorithmes adéquats selon les applications; comparer l'efficacité de différentes structures de données et de différents algorithmes; utiliser des bibliothèques publiques ou normalisées.
Sommaire du contenu
Rappels sur les types abstraits de données. Abstraction. Encapsulation. Principes de génie logiciels: qualités d'un logiciel, modularité et généricité.
Introduction à un langage de programmation système orienté objet. Fichiers d'entête et sources. Fondements du langage. Mots réservés. Types de base. Variables et portée. Énoncés, expressions, opérateurs. Contrôle d'exécution. Entrées et sorties. Tableaux. Pointeurs et références. Fonctions et passage de paramètres. Gestion de la mémoire. Mécanisme de classe. Mécanisme de gabarits. Gestion d'erreurs et exceptions. Bibliothèques normalisées.
Algorithmes: complexité temporelle et spatiale; notation grand O; analyse empirique et asymptotique. Études de cas: algorithmes de tri et algorithmes numériques.
Structures de données linéaires: tableaux génériques, piles, files; listes chaînées. Itérateurs de liste.Structures de données avancées. Arbres: binaires de recherche, équilibrés, AVL, rouge-noir, arbres-B. Arbres spécialisés: arbre d'expressions, arbres d'intervalles et codes de Huffman. Itérateurs.
Monceaux. Files prioritaires. Graphes: définitions, représentations. Parcours de graphes: recherche en profondeur ou en largeur; plus courts chemins; arbre de recouvrement minimal. Applications.
Adressages dispersé et tables de hachage. Fonctions de hachage. Collisions. Gestion des collisions. Applications.
Maintenance de logiciels (types de maintenance, techniques de base, remodelage, automatisation des tests de régression).
Techniques et outils pour la gestion de la configuration et l'assemblage de logiciels. Commandes, utilitaires et scriptage. Recherche et manipulation de texte; variables, structures de contrôle, fonctions, expressions régulières et filtrage par motif.
Compilation, code exécutable, compilation croisée, déploiement. Environnements de développement et chaînes de compilation (toolchains). Utilisation de bibliothèques publiques et normalisées.
Modalité d'enseignement
Cours de 3 heures et un laboratoire de 3 heures / semaine.
