MALG : Méthodes Algorithmiques en Licence 3 d'Informatique
Responsable: Sophie Pinchinat
Equipe enseignants: Dylan Bellier (Groupes 1 et 2), Mathieu Degre (Groupe 3), Sophie Pinchinat (Groupe 4)
Prérequis souhaités: Algorithmique 1 et Programmation 1 (en L1), Algorithmique 2 et Outils formels pour l'informatique (en L2), Modèles et Algorithmes pour les Graphes (en L3)
Emploi du temps: sur votre ENT
Contrat didactique
Vous devez prendre vos propres notes pendant les séances de cours, et consulter les ouvrages recommandés pour parfaire votre formation.
Vous devez avoir travaillé votre cours avant la séance de TD correspondante et terminer les exercices par vous-même s'ils n'ont pas été traités en séance.
Évaluations
Consignes pour les quiz À LIRE ATTENTIVEMENT
- vous utiliserez un stylo bleu ou noir ; les stylos verts, crayons de bois, etc. ont un trop faible contraste pour le scanner ;
- ne RIEN écrire en dehors des cases réponses et de l'entête à renseigner LISIBLEMENT (c'est un scanner qui va vous identifier !)
- vous renseignerez lisiblement votre nom et numéro d'étudiant sur le sujet ;
- vous n'écrirez RIEN qui soit en dehors de l'entête à renseigner et les cases réponses à cocher ;
- pour décocher une case
- passez cette case au blanco mais ne redessinez pas une case vide (une case raturée sera considérée comme cochée),
- cocher la case que vous souhaitez.
- une case raturée sera considérée comme cochée
- Pensez à apporter du blanco et une montre.
Information et documentation
C'est le contenu de ses ouvrages que vous devez maîtriser, le cours margistral vous aidera à mieux les comprendre
- Introduction à l'algorithmique, T. H. Cormen, C. E. Leiserson, R. L. Rivest, Dunod.
- Introduction to Algorithms. T. Cormen, C. Leiserson, R. Rivest, and C. Stein. Second ed. MIT Press, 2002.
- Algorithms. Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. Mcgraw Hill Book Co, 2006.
- Algorithm Design. Jon Kleinberg, Éva Tardos. Addison Wesley, 2005.
- Autres ouvrages
- Introduction to the Analysis of Algorithms. Robert Sedgewick, Philippe Flajolet, Addison-Wesley Professional, 1995.
- Algorithms, R. Sedgewick, Addison-Wesley, 1983.
- Éléments d'algorithmique, D. Beauquier, J. Berstel, Ph. Chrétienne, Masson, 1992.
- Types de données et algorithmes, C. Froidevaux, M-C. Gaudel, M. Soria, McGraw-Hill-InterEditions, 1990.
- G. Brassard et P. Bratley. Algorithmique. Conception et Analyse Masson-Presses de l'Université de Montréal, 1987.
Ce que nous aborderons ensemble
Les notions abordées dans cette l'Unité d'Enseignement ALGO sont :
- Des rappels sur les ordres de grandeur (1 séance)
- La méthode Diviser pour Régner (2 séances)
- La méthode par Programmation Dynamique (3 séances)
- Les approches gloutonnes (2 séances)
- La Programmation Linéaire (1 séance)
- La notion de problèmes NP-complets (2 séances)
- La technique des Essais Successifs (2 séances) si le temps le permet.
Vous disposez des transparents du cours MALG ainsi que du mini-cours de Programmation Linéaire qui résument les ingrédients essentiels des notions que vous devez vous approprier.
Sujets des TD de l'an passé, ils peuvent un peu changer
Il vous est demandé de terminer les exercices non faits en TD.
Liens utiles pour combler quelques lacunes
Notions standards et fonction classiques, voir la Section 3.2 de Introduction à l'algorithmique, T. H. Cormen, C. E. Leiserson, R. L. Rivest, Dunod, 1994.
Annales