Semaine 14 : jeudi 09 décembre

• Révisions. Examen de 2002 et apportez vos questions.

Semaine 13 : jeudi 02 décembre

• Algorithmique du texte : algorithme de Aho-Corasick, arbre des suffixes, tableau des suffixes, applications (Blast).
• Références spécifiques :
• M. Crochemore, C. Hancart et T. Lecroq. Algorithmique du texte, Vuibert, 2001.
• D. Gusfield. Algorithms on strings, trees and sequences, Cambridge University Press, 1999.

Semaine 12 : jeudi 25 novembre

• Algorithmes aléatoires : transparents. Algorithmique du texte : algorithme naif et algorithme de Morris-Pratt.
• Références spécifiques :
  • Notes de Guy Tremblay sur le voyageur de commerce (section sur le recuit simulé) et sur les heuristiques.
  • M. Crochemore, C. Hancart et T. Lecroq. Algorithmique du texte, Vuibert, 2001.
  • D. Gusfield. Algorithms on strings, trees and sequences, Cambridge University Press, 1999.
  • Un site avec des animations des principaux algorithmes : Exact String Matchings Algorithms.

Semaine 11 : jeudi 18 novembre

• Algorithmes d'approximation et heuristiques : transparents.
• Programmes :
  • Heuristiques pour le TSP : Nearest Neighbor et Branch-and-bound.
  • Deux variantes du Hill-climbing : choix du meilleur voisin et choix du premier bon voisin.
  • Recherche tabou.
• Références spécifiques :
  • R. Neapolitan and K. Naimipour. Foundations of Algorithms Using C++ Pseudo-code (Third Edition) : Section 9.5.
  • Notes de Guy Tremblay sur le voyageur de commerce et sur les algorithmes d'approximation.

Semaine 10 : jeudi 11 novembre

• Exploration déterministe d'un espace combinatoire : branch-and-bound. transparents.
• Programmes (dus à Guy Tremblay pour la plupart) pour le voyageur de commerce:
  • parcours en profondeur
  • heuristique
  • parcours en profondeur+valeur de départ
  • parcours en profondeur best-first
  • parcours en profondeur parallèle
  • parcours en profondeur best-first parallèle
  • parcours en profondeur best-first+valeur de départ
  • (Modifié le 17/11/04) parcours en largeur
  • (Modifié le 17/11/04) parcours en largeur+valeur de départ
  • parcours en largeur best-first
  • parcours en largeur best-first+valeur de départ
• Références spécifiques :
  • R. Neapolitan and K. Naimipour. Foundations of Algorithms Using C++ Pseudo-code (Third Edition) : Chapitre 6.
  • Notes de Guy Tremblay sur le voyageur de commerce et sur les algorithmes branch-and-bound.

Semaine 9 : jeudi 4 novembre

• Exploration déterministe d'un espace combinatoire : retour-arrière et branch-and-bound : transparents.
• Programmes (dus à Guy Tremblay) :
  • Coloration de graphes : coloration.mpd
  • Circuit Hamiltonien : backtrack-hamiltonien.mpd (version plus technique avec manipulation d'un objet Sequence backtrack-hamiltonien-seq.mpd).
  • Le sac à dos 0/1 : backtracking, branch-and-bound.
• Références spécifiques :
  • R. Neapolitan and K. Naimipour. Foundations of Algorithms Using C++ Pseudo-code (Third Edition) : Chapitres 5 et 6.

Semaine 8 : jeudi 28 octobre

• Algorithmes parallèles (suite) : le modèle PRAM.
• Programmes (dus à Guy Tremblay) :
  • Calcul des coefficients binomiaux : version séquentielle et version parallèle.
  • Calcul des préfixes : version récursive, version PRAM et sous-séquence max de valeur max.
  • Calcul du rang d'une liste chaînée : sans barrière de synchronisation, list-ranking.mpd, et avec barrière de synchronisation, barriere.mpd et list-ranking-barriere.mpd.
• Références spécifiques :
  • R. Neapolitan and K. Naimipour. Foundations of Algorithms Using C++ Pseudo-code (Third Edition) : Chapitre 11.
  • notes de G. Tremblay sur PRAM.

Semaine 7 : jeudi 21 octobre

• Algorithmes parallèles (suite) : métrique d'analyse d'algorithmes parallèles, modèle PRAM : Transparents.
• Programmes (dus à Guy Tremblay) :
  • Recherche du minimum (transp. 19) : min-pram.mpd.
  • Recherche du minimum sans problème de synchronisation :
    • avec recopie locale du tableau (transp. 27) min-pram-corrige.mpd,
    • sans recopie locale du tableau (transp. 28) min-pram-2.mpd.
  • Version optimale en coût (transp. 24) : min-pram-opt.mpd
• Références spécifiques :
  • R. Neapolitan and K. Naimipour. Foundations of Algorithms Using C++ Pseudo-code (Third Edition) : Chapitre 11.
  • notes de G. Tremblay sur les métriques et notes de G. Tremblay sur PRAM.
• Quelques exercices : Série 7.

Semaine 6 : jeudi 14 octobre

• Algorithmes voraces (suite et fin ) : Algorithme de tri par renversement, dernière section des transparents
• Introduction aux algorithmes parallèles : Transparents, MPD et paradigmes.
• Programmes vus en cours :
  • Multiplication de matrices : séquentiel, co, process, fork, distribué.
  • Somme des éléments d'un tableau : aucune limite sur processus et taches, on limite le nombre de processus, on limite la taille des taches.
• Références spécifiques : R. Neapolitan and K. Naimipour. Foundations of Algorithms Using C++ Pseudo-code (Third Edition) : Chapitre 11.
• Pour ceux que le problème du tri par renversement a intrigué, vous pouvez trouver beaucoup de matériel sur le site suivant Advanced Algorithms in Computational Biology et dans l'article introductif Evolutionary Puzzles: An Introduction to Genome Rearrangement.
• Exercices : Série 6.

Semaine 5 : jeudi 7 octobre

• Programmation dynamique (suite et fin).
  • Transparents
  • Algorithmes : Sac à dos récursif. Sac à dos PD.
• Algorithmes voraces : Transparents
• Références spécifiques : R. Neapolitan and K. Naimipour. Foundations of Algorithms Using C++ Pseudo-code (Third Edition) : Chapitres 3 et 4 et Annexe C.
• Exercices : Série 5.

Semaine 4 : jeudi 30 septembre

• Programmation dynamique.
  • Transparents
  • Algorithmes : Fibonacci avec mémorisation.
• Références spécifiques : R. Neapolitan and K. Naimipour. Foundations of Algorithms Using C++ Pseudo-code (Third Edition) : Chapitre 3.
• Quelques articles sur la programmation dynamique.
  • D. Hirschberg. A linear space algorithm for computing maximal common subsequences, Communications of the ACM 18(6):341-343, 1975.
  • K-M. Chao. Dymamic programming for analyzing biomolecular subsequences, Rapport technique, National Taiwan Univ., 2003.
  • K. Zhang et al.. A dynamic programming algorithm for haplotype block partitioning, Proc. Natl. Academy Sci. USA, 99(11):7335-7339, 2002.
• Exercices : Série 4.

Semaine 3 : jeudi 23 septembre

• Fin du cours sur la stratégie Diviser-Pour-Régner.
  • Transparents
  • Algorithmes : tri rapide.
• Résolution d'équations de récurrences.
• Références : R. Neapolitan and K. Naimipour. Foundations of Algorithms Using C++ Pseudo-code (Third Edition) : Chapitre 2 et Appendice B.
• Exercices : Série 3.

Semaine 2 : jeudi 16 septembre

• Rappels sur les notions mathématiques reliées à l'analyse d'algorithmes.
  • Principe de l'analyse d'algorithmes et principales mesures de complexité : dans le pire des case, dans le meilleur cas, dans tous les cas et en moyenne.
  • Notations mathématiques : grand O, grand theta et grand omega.
• Approche Diviser-Pour-Régner, premiè partie :
  • Transparents
  • Algorithmes : fouille binaire et tri fusion.
• Références : R. Neapolitan and K. Naimipour. Foundations of Algorithms Using C++ Pseudo-code (Third Edition) : Chapitres 1 et 2.
• Exercices : Série 2.

Semaine 1 : jeudi 9 septembre

• Présentation du cours INF7440.
• Rappels de base sur les algorithmes.
• Survol des paradigmes de programmation séquentiel et parallèle.
• Survol de différentes architectures parallèles.
• Exercices : Série 1.