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.

Des laboratoires seront proposés au cours du trimestre afin de permettre aux étudiants (es) d’approfondir leurs connaissances et d’expérimenter les algorithmes montrés en classe.

Programmation compétitive (15 points) (6 séances)

Description : Simulation de programmation compétitive avec des problèmes couvrant différents sujets du cours. Il y aura 6 séances de de laboratoire qui seront dédiées à la programmation compétitive. 

Sujets couverts : Analyse asymptotique, structures de données, programmation dynamique, algorithmes glouton, recherche dans les chaines de caractères, conception, algorithmique.

Jeu de plateau (15 points) (6 séances)

Description : Création d’un joueur « CPU » pour un jeu de plateau.

Sujets couverts : Algorithmes min - max et alpha-beta, tables de hachage, heuristiques.

Notes importantes:

Équipe

Les laboratoires se font en équipe de 2 ou de 3.

Pour la programmation compétitive

La présence au laboratoire est obligatoire pour la programmation compétitive.

L’étudiant(e) absent(e) se verra attribuer la note zéro (0).

Pour le jeu de plateau

Lors de la correction du dernier laboratoire (le tournoi du jeu), tous les membres de l’équipe doivent être présents.

L’étudiant(e) absent(e) se verra attribuer la note zéro (0).

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.