Université du Québec en Outaouais Département d'informatique et d'ingénierie
Sigle : INF4143  Gr. 01
Titre : Algorithmique I
Session : Hiver 2019  Horaire et local
Professeur : Taleb, Mohamed
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.

Descriptif – Annuaire

2. Objectifs spécifiques du cours :

À la fin du cours, les étudiant(e)s devraient être en mesure de :

  • Appliquer les diverses classes d'algorithmes.
  • Utiliser des outils permettant de choisir un type d'algorithme approprié au problème donné.
  • Appliquer les techniques d'analyse d'efficacité des algorithmes.
3. Stratégies pédagogiques :

Le cours se donne sous forme magistrale de trois (3) heures par semaine et le cours est avec des travaux dirigés, pour une durée de quinze (15) semaines.

4. Heures de disponibilité ou modalités pour rendez-vous :

Sur rendez-vous par courriel.

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

Pas de TD la 1re semaine

 08 jan. 2019 
2   

Analyse de l'efficacité des algorithmes

  • Notation asymptotique

TD #1 : jeudi 17 janvier – Analyse de l'efficacité des algorithmes

 15 jan. 2019 
3   

Analyse de l'efficacité des algorithmes (suite)

  • Analyse des algorithmes – Exemples

TD #2 : jeudi 24 janvier – Analyse de l'efficacité des algorithmes (suite)

 22 jan. 2019 
4   

Les algorithmes voraces

  • Notion
  • Arbres sous-tendants minimaux : l'algorithme de Prim
  • Les plus courts chemins : l'algorithme de Dijkstra, Bellman-Ford, graphes acycliques orientés

TD #3 : jeudi 31 janvier – Les algorithmes voraces

 29 jan. 2019 
5   

Les algorithmes voraces (suite)

  • Rangement optimal sur les bandes
  • Heuristiques voraces suboptimales

TD #4 : jeudi 07 février – Les algorithmes voraces (suite)

 05 fév. 2019 
6   

Diviser pour régner

  • Notion
  • La fouille dichotomique
  • Le tri par fusion

TD #5 : jeudi 14 février – Diviser pour régner

 12 fév. 2019 
7   

Diviser pour régner (suite)

  • Le tri de Hoare (Quicksort)
  • La multiplication matricielle : l'algorithme de Strassen

TD #6 : jeudi 21 février – Diviser pour régner (suite)

 19 fév. 2019 
8   

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

TD #7 : jeudi 28 février – La programmation dynamique et exploration des graphes

 26 fév. 2019 
9   

Semaine d’études

 05 mars 2019 
10   

Examen intra

 12 mars 2019 
11   

Algorithmes à retour arrière (« backtracking »)

  • Notion
  • Le problème de huit reines
  • Les cycles hamiltoniens

« Branch and bound »

  • Notion
  • Le commis voyageur

TD #8 : jeudi 21 mars – Algorithmes à retour arrière (« backtracking ») et « Branch and bound »

 19 mars 2019 
12   

La théorie des bornes inférieures

  • Arborescences de décisions pour la fouille et pour le tri
  • Oracles et arguments adversaires

TD #9 : jeudi 28 mars – La théorie des bornes inférieures

 26 mars 2019 
13   

Introduction à la NP-complétude

TD #10 : jeudi 04 avril – Introduction à la NP-complétude

 02 avr. 2019 
14   

Remise et présentation du projet

 09 avr. 2019 
15   

Examen final

 16 avr. 2019 
6. Évaluation du cours :
  • Projet de session, incluant la partie théorique et la partie pratique : 25 %
  • Examen intra : 35 %
  • Examen final : 40 %
7. Politiques départementales et institutionnelles :
8. Principales références :

Volume obligatoire pour le cours :

  1. A. Pelc, Algorithmique I, Notes de cours pour INF4143, UQO.

Volumes recommandés :

  1. M.T. Goodrich, R. Tamassia. Data Structures and Algorithms in Java, 5th edition. John Wiley & Sons, 2010. ISBN 978-0-470-38326-1.
  2. William J. Collins. Data Structures and the Java Collections Framework, 3rd edition, John Wiley & Sons, 2011. ISBN 978-0-470-48267-4.
  3. A. Levitin, Introduction to the Design and Analysis of Algorithms, Addison Wesley, 2007.
  4. E. Horowitz, S. Sahni, Fundamentals of computer algorithms, Computer Science Press, 1978.

Volumes supplémentaires :

  1. G. Brassard, P. Bratley, Algorithmique: conception et analyse, Presses de l'Université de Montréal, 1987.
  2. A.V. Aho, J.E. Hopcroft, J.D. Ullman, Data structures and algorithms, Addison-Wesley, 1983.

Le matériel du cours présenté en classe par le professeur est disponible sur https://moodle.uqo.ca.

9. Page Web du cours :
https://moodle.uqo.ca