Coordonnées

Département d'informatique
Université du Québec à Montréal
CP 8888, Succ. Centre-ville
Montréal (Québec) H3C 3P8
Tél: 514-987-3000, #5516
Bureau: PK-4525
Courriel: blondin_masse[point]alexandre
[arobase]uqam[point]ca

À propos

J'ai complété mon doctorat en mathématiques-informatique sous la supervision des professeurs Srecko Brlek, de l'Université du Québec à Montréal, au Canada, et de Laurent Vuillon, de l'Université de Savoie, en France.

Depuis le 1er août 2014, je suis professeur adjoint à l'Université du Québec à Montréal, au Canada.

Liens utiles

Conception et analyse des algorithmes

Bienvenue sur le site du cours Conception et analyse des algorithmes - INF7440 que j'enseigne à l'automne 2016.

Annonces

12 décembre 2016
  • Ajout de la solution du devoir 3
  • Ajout d'un ancien examen
1er décembre 2016
  • Ajout de l'énoncé du devoir 4
  • Ajout de diapositives présentées en classe
3 novembre 2016
  • Ajout de l'énoncé du devoir 3
7 octobre 2016
  • Ajout de l'énoncé du devoir 2
15 septembre 2016
  • Ajout de l'énoncé du devoir 1
12 août 2016
  • Activation du site

Devoirs et examen

Échéancier

Le tableau ci-bas donne un aperçu de la matière abordée à chaque cours.

Remarque : Je me réserve la possibilité de modifier les sujets abordés au fur et à mesure que le trimestre avance, par exemple si certaines notions demandent plus de temps que prévu.

Semaine Date Contenu
1 8 sept

Introduction

  • Présentation du cours
  • Notation asymptotique
  • Coloration de cartes géographiques
2 15 sept

Analyse d'algorithmes

  • Fouille linéaire
  • Recherche dans un texte
  • Tri par insertion
  • Parcours d'un graphe en largeur
3 22 sept

Diviser-pour-régner

  • Généralités
  • Tri par fusion
  • Résolution de récurrence
4 29 sept

Diviser-pour-régner (suite)

  • Calcul de la distance minimale

Algorithmes gloutons

  • Problème de la monnaie
  • Problème du sac à dos
  • Arbres de recouvrement
5 6 oct

Algorithmes gloutons

  • Monceaux
  • Algorithme de Prim
  • Ensembles disjoints
  • Algorithme de Kruskal
  • Plus courts chemins
6 13 oct

Programmation dynamique

  • Somme maximale
  • Distance d'édition
7 20 oct

Programmation dynamique (suite)

  • Problème du sac à dos
  • Jeu min-max

NP-complétude

  • Problèmes célèbres
8 27 oct

NP-complétude (suite)

  • Les classes P et NP
  • Problèmes NP-complets
  • Réductions
9 3 nov

NP-complétude (suite)

  • Réductions

Séparation et évaluation progressive

  • Problème du sac à dos
10 10 nov

Séparation et évaluation progressive (suite)

  • Problème du voyageur de commerce
  • Transversaux de circuits
11 17 nov

Algorithmes et probabilités

  • Fouille linéaire
  • Partitionnement randomisé
12 24 nov

Algorithmes et probabilités (suite)

  • Échantillonnage
  • Coupe de graphes
13 1er déc

Algorithmique du texte

  • Algorithme naïf
  • Algorithme de Knuth-Morris-Pratt
  • Énumération de palindromes
  • Algorithme de Boyer-Moore
14 8 déc

Sujets divers

  • Coupe de graphes
  • Problèmes NP-intermédiaires
15 15 déc Examen