Algorithmes niveau 1

• Vincent Danjean
• Benjamin Wack

Contact : Prénom.Nom@imag.fr

Note : une partie des documents proposés ici a été rédigée par Jean-Marc Vincent, ou s'inspire fortement de ses documents pour la Licence 3 Informatique.

1. Analyse d’algorithmes 10/10 B
   • Cours : Coût d’un algorithme, au pire, en moyenne
   • Algorithmes classiques : recherche de maximum, recherche séquentielle, dichotomie
   • Exercices :
     • Feuille d’exercices et des corrigés pour le calcul de complexité et pour le coût moyen (attention aux renumérotations…)
     • Comparer pratiquement les 3 algorithmes de calcul des nombres de Fibonnacci.
   • Compléments :
     • À propos de coûts et de sommes
     • À propos de comparaisons de fonctions (aussi dispo en version PDF, pour s'entraîner voir l'exercice 11)
     • Deux graphiques pour visualiser les notions de comparaisons de fonctions et de borne supérieure asymptotique
   • Pour préparer la séance 2
2. Trier 7/11 V
   • Cours : Le problème du tri
   • Algorithmes classiques : Tri par sélection, insertion, segmentation
   • Exercices :
     • Visiter ce site, implémenter les différents tris proposés et les tester
   • TP : implémentation des tris classiques
     • Fichiers à récupérer
3. Diviser pour Régner 21/11 B
   • Cours : récursivité, Master Theorem
   • Algorithmes classiques : Exponentiation rapide, tri par fusion, algorithme de Karatsuba
   • Exercices :
     • Le majoritaire
     • Implanter les 2 méthodes de calcul de la fonction puissance et les comparer
4. Type Abstrait, structures séquentielles 19/12 B
   • Cours : Notion de type abstrait
   • Algorithmes classiques : Pile, File, FAP
   • Exercices :
     • Simulations mutuelles
   • TP : simulations mutuelles
     • Fichiers à récupérer
5. Arbres binaires de recherche 16/01 matin B
   • Cours : Arbres, structures discriminantes
   • Algorithmes classiques : Arbres binaires de recherche
   • Exercices :
     • Annales Problèmes exercices 35, 37 et 54

6. Structures ordonnées 30/01 V

   • Cours : Files à priorité, structure de tas
   • Algorithmes classiques : Tri par tas
   • Exercices papier :
     • Annales Problèmes exercices 14, 19, 27, 30 et 52
   • TP : programmation d'une FAP et/ou du tri par tas
     • Correction FAP
7. Hachage 06/03 V
   • Cours : Recherche d’un élément
   • Algorithmes classiques : Table de hachage, algorithme de Karp-Rabin
   • Exercices :
     • analyse en moyenne (exercices corrigés)
   • TP : programmation et utilisation d'une table de hashage
     • sujet
8. Programmation dynamique 03/04 B
   • Cours : Programmation dynamique
   • Algorithmes classiques : Plus Longue Sous-Suite Commune
9. Graphes et chemins 22/05 V
   • Cours : Cheminements dans les graphes, connexité et plus courts chemins
   • Algorithmes classiques : Algorithme de Tarjan, algorithme de Dijkstra
10. Algorithmes gloutons 05/06 B
    • Cours : Couverture de graphe par un arbre, algorithmes gloutons, algorithme de Huffman
    • Algorithmes classiques : Algorithmes de Prim et algorithme de Kruskal

Pour toute remarque sur cette page, vous pouvez envoyer un message électronique à Benjamin_point_Wack_arobase_imag_point_fr.