À 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.

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.

Évaluations individuelles

Évaluations considérées non individuelles

À noter:

• Une moyenne inférieure à 55% dans les évaluations individuelles (examens intra et final, programmation compétitive) 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 pour un total de 30%, répartis sur plusieurs séances.  Ce ne sont pas plusieurs petits laboratoires.

Tout travail (devoir pratique, rapport de laboratoire, rapport de projet, etc.) remis en retard sans motif valable, c’est-à-dire autre que ceux mentionnés dans le Règlement des études (1er cycle, article 7.2.5/ cycles supérieurs, article 6.5.2) se verra attribuer la note zéro, à moins que d’autres dispositions ne soient communiquées par écrit par l’enseignante ou l’enseignant dans les consignes de chaque travail à remettre ou dans le plan de cours pour l’ensemble des travaux.

Afin de faire valider une absence à une évaluation en vue d’obtenir un examen de compensation, l’étudiante ou l’étudiant doit utiliser le formulaire prévu à cet effet dans son portail MonÉTS pour un examen final qui se déroule durant la période des examens finaux ou pour tout autre élément d’évaluation surveillé de 15% et plus durant la session. Si l’absence concerne un élément d’évaluation de moins de 15% durant la session, l’étudiant ou l’étudiante doit soumettre une demande par écrit à son enseignante ou enseignant.

Toute demande de validation d’absence doit se faire dans les cinq (5) jours ouvrables suivant la tenue de l’évaluation, sauf dans les cas d’une absence pour participation à une activité prévue aux règlements des études où la demande doit être soumise dans les cinq (5) jours ouvrables avant le jour de départ de l’ÉTS pour se rendre à l’activité.

Toute absence non justifiée par un motif majeur (voir articles 7.2.6.1 du RÉPC et 6.5.2 du RÉCS) entraînera l’attribution de la note zéro (0).

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.

Adresse internet du site de cours et autres liens utiles

Site moodle de log320.