Ce cours a pour but, d'une part, de proposer une introduction à l'algorithmique, notamment de présenter des algorithmes efficaces illustrant les grandes familles de techniques algorithmiques, et, d'autre part, de présenter les structures de données classiquement utilisées en informatique.

En ce qui concerne l'algorithmique, l'accent sera mis sur :

• la complexité d'un algorithme ;
• les grandes techniques d'algorithmique :
  • Préprocessing
  • Diviser pour régner
  • Programmation dynamique
  • Algorithmes gloutons
• les graphes et leurs parcours classiques.

En ce qui concerne les structures de données, l'accent sera mis sur :

• les listes ;
• les piles et files ;
• les arbres binaires de recherche équilibrés ;
• les tas ;
• les tables de hachage.

• Cours 1 : Introduction à l'algorithmique et à la complexité :
  • Introduction à ce qu'est l'algorithmique
  • Critère d'efficacité d'un algorithme
  • Définition de la complexité d'un algorithme
  • Notation de Landau

  Cours :	( poly 1/page)	( poly 4/page)	( slides passés en cours)
  TD :	( énoncé du TD n°1)

• Cours 2 : Préprocessing :
  • Principe du préprocessing
  • Illustration sur une recherche de chaîne de caractères
  • Algorithme de Knuth-Morris-Pratt
  • Tri de tableaux en complexité linéaire

  Cours :	( poly 1/page)	( poly 4/page)	( slides passés en cours)
  TD :	( énoncé du TD n°2)

• Cours 3 : Diviser pour régner :
  • Principe du "diviser pour régner"
  • Le théorème maître
  • Multiplication de matrices de Strassen
  • Multiplication de nombres de Karatsuba
  • Tri rapide (quicksort)

  Cours :	( poly 1/page)	( poly 4/page)	( slides passés en cours)
  TD :	( énoncé du TD n°3)

• Cours 4 : Programmation dynamique :
  • Principe de la programmation dynamique
  • Un peu de théorie des graphes
  • Algorithme de plus court chemin
  • Algorithme de Dijsktra

  Cours :	( poly 1/page)	( poly 4/page)	( slides passés en cours)
  TD :	( énoncé du TD n°4)

• Cours 5 : Tableaux et listes :
  • Les tableaux : avantages et inconvénients
  • Les listes : avantages et inconvénients
  • Comparaison tableaux - listes

  Cours :	( poly 1/page)	( poly 4/page)	( slides passés en cours)
  TD :	( énoncé du TD n°5)

• Cours 6 : Piles et files :
  • Définition d'une pile
  • Implantation des piles par listes chaînées
  • Implantation des piles par tableaux
  • Piles et récursivité
  • Les files

  Cours :	( poly 1/page)	( poly 4/page)	( slides passés en cours)
  TD :	( énoncé du TD n°6)

• Cours 7 : Les arbres et leurs parcours :
  • Arbres et arbres binaires
  • Parcours en largeur et profondeur
  • Arbres binaires de recherche

  Cours :	( poly 1/page)	( poly 4/page)	( slides passés en cours)
  TD :	( énoncé du TD n°7)

• Cours 8 : Arbres équilibrés et tas :
  • Les arbres AVL
  • Rééquilibrages par rotations
  • Les tas

  Cours :	( poly 1/page)	( poly 4/page)	( slides passés en cours)
  TD :	( énoncé du TD n°8)

• Cours 9 : Tables de hachage :
  • Définition des tables de hachage
  • Gestion des collisions par chaînage
  • Choix des fonctions de hachage
  • Hachage universel
  • Gestion des collisions par adressage ouvert

  Cours :	( poly 1/page)	( poly 4/page)	( slides passés en cours)
  TD :	( énoncé du TD n°9)

• « Introduction à l'algorithmique ». Thomas Cormen, Charles Leiserson, Ronald Rivest, Clifford Stein. Dunod, 1996.
• « Algorithmes ». Donald Knuth. CSLI, 2011.
• « Algorithms ». Sanjoy Dasgupta, Christos Papadimitriou, Umesh Vazirani. McGraw-Hill, 2006.