Informatique et Sciences du Numérique (ISN)

UFR Informatique, Mathématique et Mathématiques Appliquées (IM2AG) Université Joseph Fourier (UJF) Grenoble

Algorithmes classiques

coordination : Jean-Marc Vincent

Quelques problèmes posés en examen

29/09 Séance 1 : Analyse d’algorithmes
- Cours : Coût d’un algorithme: transparents notes
- Algorithme classique : Exponentiation
- Exercices :
  1. Implanter les 2 méthodes de la fonction puissance et les comparer.
  2. Comparer pratiquement les 3 algorithmes de calcul des nombres de Fibonnacci.
  3. Calculer le coût moyen du nombre de traitements dans l’algorithme maximum.
  4. Feuille d’exercice 1 2
- Pour préparer la séance 2
13/10 Séance 2
- Cours : Le problème du tri
- Algorithmes classiques : Tri par sélection, partition-fusion, segmentation
- Exercices :
  1. Visiter le site
  2. Implémenter les différents tris et les tester
- La segmentation pour le quicksort Drapeau hollandais
10/11 Séance 3
- Cours : Recherche d’un élément
- Algorithmes classiques : Table de hachage, algorithme de Karp-Rabin
- Exercices :
  1. Analyse probabiliste
  2. Exercices sur les tables de hachage
24/11 Séance 4
- Cours : Arbres, structures discriminantes
- Algorithmes classiques : Arbres binaires de recherche
- Exercices :
  1. Annales Problèmes/exercices 23, 25 et 42
12/01 Séance 5
- Cours : Files à priorité
- Algorithmes classiques : Tri par tas
- Exercices papier
  1. Annales Problèmes/exercices 2, 7, 15, 18 et 40
- Exercices de mise en oeuvre:
  1. Installer le code
  2. Faire l’expérience pour différentes tailles de tableau, tracer les histogrammes, interpréter (on pourra utiliser gnuplot)
  3. Faire des expériences en augmentant la taille du tableau, comment observer le nlogn
26/01 Séance 6
- Cours : Codage et compression
- Algorithmes classiques : Algorithme de Huffman
- Exercices :
  1. Un peu de lecture article fondateur de Shannon
02/02 Séance 7
- Cours : Chaînes de caractères, automates, pré-traitement
- Algorithmes classiques : Algorithme de Boyer-Moore
- Exercices :
08/03 Séance 8
- Cours : Énumération de parties
- Algorithmes classiques : Algorithme min-max
- Exercices :
22/03 Séance 9
- Cours : Cheminements dans les graphes, connexité et plus courts chemins
- Algorithmes classiques : Algorithme de Tarjan, algorithme de Dijkstra
- Exercices :
03/05 Séance 10
- Cours : Couverture de graphes
- Algorithmes classiques : Algorithmes de Prim et algorithme de Kruskal
- Exercices :