Au  terme de ce cours, l'étudiant ou l'étudiante aura acquis une connaissance spécifique au génie logiciel des structures de données et des algorithmes. Comprendre et utiliser l'analyse asymptotique afin de choisir judicieusement les structures de données appropriées et le type d'algorithme optimal pour résoudre efficacement un problème tout en respectant les contraintes imposées et les ressources disponibles.

Au terme de ce cours, l'étudiant ou l'étudiante sera en mesure de choisir parmi une multitude de structures de données de base (tableau, file, pile ou liste) ou plus avancées (structures en arbre, graphes, tables de hachage) afin de résoudre différents problèmes plus ou moins complexes. Il sera aussi en mesure de les combiner et de les adapter afin de faire face à différentes situations.

L’étudiant ou l'étudiante sera aussi en mesure de choisir le type d’algorithmes et d’analyser ses performances globales pour différents problèmes de base qui impliquent, par exemple, la recherche dans des graphes, l’optimisation combinatoire ou la recherche dans des chaînes de caractères.

Note sur les préalables : pour le programme de baccalauréat en informatique distribuée, le cours MAT210 est préalable ou concomitant (il peut être suivi en même temps) seulement pour les sessions d'hiver et d'été 2024.

À la fin de ce cours, l’étudiant(e) aura assimilé les notions suivantes :

• structures de données élémentaires : liste, pile, queue, tableau, arbre, graphe, etc.;
• techniques d’analyse de performance des algorithmes;
• techniques de base de conception d’algorithmes : récursivité, algorithmes gloutons, programmation dynamique, etc.;
• algorithmes de recherche et d’extraction de l’information;
• algorithmes de tri classiques.

À la fin du cours, l’étudiant(e) sera capable de :

• analyser la performance des algorithmes pour faire un choix réfléchi entre divers algorithmes;
• choisir des structures de données judicieuses et implanter des algorithmes de manière à obtenir de bonnes performances;
• concevoir des algorithmes simples en utilisant les techniques classiques de conception;
• analyser les résultats et faire des améliorations algorithmiques si possible et nécessaires.

- Un cours magistral par semaine (3 heures). Des exemples seront faits en classe pour permettre aux étudiants(es) d’assimiler les concepts théoriques.

- Une séance de travaux pratiques par semaine (1 heure approximativement*).

- Une séance de laboratoire par semaine (2 heures approximativement*).

Le temps pour la séance de travaux pratique peut varier (plus ou moins de temps) d'une semaine à l'autre dépendant de la théorie et des exercices faits en TP.  Ces heures sont fournies à titre indicatif seulement, mais la période de laboratoire au complet (séance de TP et labo) sera de 3 heures totales.

Modalités pour les différents groupes:

Tous les cours et séances de laboratoires sont en présence.

Introduction, calcul d’ordre asymptotique et analyse des algorithmes (5 heures^[1])

1. Introduction à l’algorithmique.
2. Algorithmes et programmes.
3. Efficacité des algorithmes.
4. Calcul d’ordre des algorithmes et notations asymptotiques : O, Theta, Omega
5. Estimation de l’ordre du temps de calcul.
6. Baromètres.
7. Estimation de l’ordre de la mémoire de travail.

Algorithmes récursifs (5 heures)

1. Règles de conception de fonctions récursives.
2. Optimisation de fonctions récursives.
3. Preuves de convergence.
4. Équations de récurrence.
5. Analyse des algorithmes récursifs.
6. Méthode générale.

Structures de données (11 heures)

1. Tableaux.
2. Listes.
3. Piles.
4. Queues.
5. Arbres binaires de recherche (arbres k-d).
6. Arbres rouge-noir.
7. Arbres AVL.
8. Graphes.
9. Tables de hachage.

 Recherche dans les graphes (4 heures)

1. Arbres de jeux : algorithme MinMax et élagage alpha/bêta.
2. Autres optimisations des arbres de jeux.
3. Algorithme de Dijkstra
4. Recherche du meilleur en premier (« best-first search »)
5. Algorithmes A*

  Optimisation combinatoire (7 heures)

1. Théorie des classes.
2. Programmation dynamique.
3. Séparation et évaluation.
4. Algorithmes « retour en arrière ».
5. Algorithmes gloutons.
6. Algorithmes non-déterministes^[2]
7. Programmation linéaire^[2]

Recherche d’une sous-chaîne de caractère dans un texte (3.5 heures)

1. Algorithme naïf.
2. Algorithme Rabin-Karp.
3. Algorithme Boyer-Moore.
4. Algorithme Knuth-Morris-Pratt.
5. Algorithmes utilisant une notion de distance.

Sujets spéciaux (3.5 heures)

NOTE : Tous les cours sont d'une durée de 3 heures et 30 minutes par semaine (incluant une pause de 30 minutes).

 ^[1]    Ces heures sont des heures approximatives d’enseignement pour chaque sujet et incluent le temps alloué à l’examen intra-trimestriel.

 ^[2]    Ces sujets pourraient être remplacés par d'autres sujets en cours de session.

L’étudiant utilisera un outil de développement logiciel intégré (IDE) tel que : ECLIPSE, INTELLIJ ou VSCODE afin de développer des logiciels en JAVA.

Pour la réalisation des travaux de laboratoires, les étudiants pourront utiliser un ordinateur MAC ou PC.

À noter:

• Une moyenne inférieure à 55% dans les évaluations individuelles (examens intra et final) entraîne automatiquement un échec au cours. Ceci est une condition nécessaire mais non suffisante pour réussir ce cours.
• Il y a deux laboratoires de 15%, répartis sur plusieurs séances.  Ce ne sont pas plusieurs petits laboratoires.

Les travaux remis en retard ne seront pas corrigés et l’étudiant(e) se verra attribué(e) la note zéro (0).

Aucune documentation obligatoire.

Suggérées

CORMEN, T., C. LEISERSON et R. RIVEST, Introduction to Algorithms. Third edition, Cambridge (MA), MIT Press, McGraw Hill, 2009.

CORMEN, T., C. LEISERSON et R. RIVEST, Introduction à l’algorithmique. 2^e éd., Paris, Dunod, 2002.

BRASSARD, G. and BRATLEY, P. Fundamental of Algorithmic. Englewood Cliffs (N.J.), Prentice-Hall, 1996.

Site moodle de log320.