Université du Québec en Outaouais Département d'informatique et d'ingénierie
Sigle : INF4143  Gr. 01
Titre : Algorithmique I
Session : Hiver 2016  Horaire et local
Professeur : Moussi, Jean
1. Description du cours paraissant à l'annuaire :

Objectifs

Fournir à l'étudiant des outils pour choisir une solution algorithmique efficace à un problème donné et estimer sa performance. Le sensibiliser à l'importance de choisir la solution la plus adéquate.

Contenu

Critères de choix d'une solution algorithmique de problèmes, complexité d'algorithme versus performance de l'implantation, complexité en pire cas et en moyenne. Principaux types d'algorithmes, leurs qualités et défauts: algorithmes voraces, diviser pour régner, retour arrière, «branch and bound», programmation dynamique; exemples de problèmes résolus par des algorithmes de chaque type et leur analyse. Méthodes d'exploitation des graphes et leurs applications. Bornes inférieures de performance des algorithmes. Problèmes polynomiaux et intraitables, problèmes NP-complets, heuristiques, solutions approximatives. Ce cours comporte des séances obligatoires de travaux dirigés (TD) de deux heures par semaine.
2. Objectifs spécifiques du cours :
  1. Familiariser les étudiants avec diverses classes d'algorithmes.
  2. Fournir des outils permettant de choisir un type d'algorithme approprié au problème donné.
  3. Enseigner les techniques d'analyse d'efficacité des algorithmes.
3. Stratégies pédagogiques :
  1. Cours magistral : théorie et exemples pratiques.
  2. 4 travaux pratiques.
  3. 11 séances de laboratoire.
4. Heures de disponibilité ou modalités pour rendez-vous :
Sur rendez-vous.
5. Plan détaillé du cours sur 15 semaines :
Semaine Thèmes Dates
1    Préliminaires
  • notion d'algorithme et son efficacité
  • analyse en pire cas et en moyenne
 12 jan. 2016 
2    Analyse de l'efficacité des algorithmes
  • notation asymptotique

Laboratoire #1 : Le 21 janvier 2016 - Analyse de l'efficacité des algorithmes

19 jan. 2016 
3    Analyse de l'efficacité des algorithmes (suite)
  • exemples d'analyse des algorithmes

Laboratoire #2 : Le 28 janvier 2016 - Analyse de l'efficacité des algorithmes (suite)

    Devoir #1
 26 jan. 2016 
4    Les algorithmes voraces
  • notion
  • arbres sous-tendants minimaux : l'algorithme de Prim
  • les plus courts chemins : l'algorithme de Dijkstra

Laboratoire #3 : Le 4 février 2016 - Les algorithmes voraces

02 fév. 2016 
5    Les algorithmes voraces (suite)
  • rangement optimal sur les bandes
  • heuristiques voraces suboptimales

Laboratoire #4 : Le 11 février 2016 - Les algorithmes voraces (suite)

    Remise du devoir #1
    Devoir #2
 09 fév. 2016 
6    Diviser pour régner
  • notion
  • la fouille dichotomique
  • le tri par fusion

Laboratoire #5 : Le 18 février 2016 - Diviser pour régner

    Remise du devoir #2
 16 fév. 2016 
7    Diviser pour régner (suite)
  • le tri de Hoare (quicksort)
  • la multiplication matricielle : l'algorithme de Strassen

Laboratoire #6 : Le 25 février 2016 - Diviser pour régner (suite)

23 fév. 2016 
8    Semaine d'études 01 mars 2016 
9    Examen de mi-session 08 mars 2016 
10    La programmation dynamique
  • notion
  • calcul des coefficients binomiaux: le triangle de Pascal
  • les plus courts chemins: l'algorithme de Floyd
  • le commis voyageur

Exploration des graphes

  • exploration en pré-ordre, en en-ordre et en post-ordre des arborescences
  • la fouille en largeur et en profondeur des graphes

Laboratoire #7 : Le 17 mars 2016 - La programmation dynamique et exploration des graphes

    Devoir #3
Distribution des projets de programmation 		15 mars 2016 
11    Algorithmes à retour arrière (« backtracking »)
  • notion
  • le problème de huit reines
  • les cycles hamiltoniens

« Branch and bound »

  • notion
  • le commis voyageur

Laboratoire #8 : Le 24 mars 2016 - Algorithmes à retour arrière (« backtracking »)et « Branch and bound »

    Remise du devoir #3
 22 mars 2016 
12    La théorie des bornes inférieures
  • arborescences de décisions pour la fouille et pour le tri
  • oracles et arguments adversaires

Laboratoire #9 : Le 31 mars 2016 - La théorie des bornes inférieures

    Devoir #4
 29 mars 2016 
13    Introduction à la NP-complétude

Laboratoire #10 : Le 7 avril 2016 - Introduction à la NP-complétude

    Remise du devoir #4
 05 avr. 2016 
14    Exposition des projets

Laboratoire #11 : Le 14 avril 2016 - Révision

 12 avr. 2016 
15    Examen final 19 avr. 2016 
6. Évaluation du cours :
  • Examen de mi-session : 35 %
  • Examen final : 40 %
  • Travaux à la maison : 15 %
  • Projet : 10 %
7. Politiques départementales et institutionnelles :
8. Principales références :
  1. Notes de cours du professeur.
  2. A. Pelc, Algorithmique I, Notes de cours pour INF4143, UQAH, (OBLIGATOIRE).
  3. A. Levitin, Introduction to the Design and Analysis of Algorithms, Addison Wesley, 2007 (recommandé).
  4. G. Brassard, P. Bratley, Algorithmique: conception et analyse, Presses de l'Université de Montréal, 1987.
  5. A.V. Aho, J.E. Hopcroft, J.D. Ullman, Data structures and algorithms, Addison-Wesley 1983.
  6. E. Horowitz, S. Sahni, Fundamentals of computer algorithms, Computer Science Press 1978 (recommandé).
9. Page Web du cours :
https://moodle.uqo.ca