À 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.
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
7. Programmation linéaire

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.

L’étudiant utilisera un outil de développement logiciel intégré (IDE) tel que : ECLIPSE ou INTELLIJ 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 qu’une moyenne inférieure à 50% 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.

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.