Informations administratives
- Cours de niveau 1
- Certificat : DU-ISN-C1.2
- Domaine informatique : Algorithmique
- Responsable : Benjamin Wack
- Intervenants : Benjamin Wack, Vincent Danjean
Volume horaire par certificat
- Heures encadrées :
- 10 h cours
- 10 h travaux dirigés
- Heures non-encadrées :
- 10 h travaux pratiques non encadrés en salle de TP (voir l’organisation type de la journée)
- 20 h travail personnel
Objectif du cours
L’objectif du cours est de donner une culture algorithmique permettant au stagiaire de savoir proposer une solution algorithmique à un problème, savoir l’implanter et savoir l’analyser.
Contenu pédagogique
La démarche pédagogique repose sur 10 séances abordant chacune, à travers un exemple classique, un concept de l’algorithmique. Le programme prévisionnel des 10 séances :
- Coût d’un programme, complexité et performance
- Trier
- Diviser pour régner et tris rapides
- Structures séquentielles
- Structures arborescentes
- Structures ordonnées
- Tables de hachage et analyse en moyenne
- Algorithme d’optimisation, programmation dynamique
- Cheminements dans les graphes
- Algorithmes gloutons
Compétences développées
- Savoir reconnaître et mettre en oeuvre des schémas génériques d’algorithmes (séquence, arbre, graphe…),
- Savoir construire une solution selon une démarche allant du plus simple (algorithme naïf) au plus efficace (diviser pour régner, etc.)
- Savoir comment évaluer la complexité d’une solution algorithmique:
- analyser la complexité au pire, en moyenne avec des hypothèses probabilistes,
- analyser la complexité en utilisant des mesures sur des simulations ou des jeux de test
Bibliographie
- Chapitre 2 de Introduction à la science informatique : Pour les enseignants de la discipline en lycée informatique, Gilles Dowek (coordination de l’ouvrage collectif) Collection Repères pour agir, CRDP Académie de Paris. 2011
- Autres références (non exhaustif)
- Thomas Cormen, Charles Leiserson, Ronald Rivest, and Clifford Stein. Algorithmique. Dunod, 3e edition, 2010.
- Robert Sedgewick and Kevin Wayne. Algorithms. Addison Wesley, 4e edition, 2011.
- Dexter C. Kozen. The Design and Analysis of Algorithms (Monographs in Computer Science). Springer, 1991.
- David Harel and Yishai Feldman. Algorithmics : The Spirit of Computing. Addison Wesley, 2004.