Page du cours Algorithmique et programmation 3 (L2)
Merci de bien vouloir vous inscrire sur la page moodle correspondante, afin notamment de recevoir les annonces du cours.
Le cours aura lieu le mardi de 14h à 15h30 en amphi 13E (Halle aux farines). Il commence le 7 septembre, une semaine avant les TD et TP.
Cours
Voici le
poly du cours.
- Mardi 7 septembre : Exemple du guessing game, notation O, définition de la complexité d'un algorithme.
- Mardi 14 septembre : Exemple détaillé de correction et complexité: le maximum d'une liste. Optimalité d'une borne de complexité, optimalité d'un algorithme. Recherche séquentielle dans une liste quelconque.
- Mardi 21 septembre : Recherche dichotomique. Tri à bulles.
- Mardi 28 septembre : Tri par sélection. Récursivité : exemples de base, preuve de correction (factorielle, suite de Fibonacci).
- Mardi 5 octobre : Retour sur la suite de Fibonacci: technique de mémoïsation. Récursion terminale : exemple de l'algorithme d'Euclide et du calcul de somme. Code source des exemples présentés.
- Mardi 12 octobre : Complexité de l'algorithme d'Euclide. Tri fusion: fusion de sous-listes, tri fusion.
- Mardi 19 octobre : Complexité du tri fusion. Tout algorithme de tri par comparaison a une complexité au moins en O(n ln n).
- Mardi 26 octobre : Multiplication rapide de polynômes. Début du chapitre 5 (calcul d'une suite récurrente sur deux indices).
- Mardi 9 novembre : Plus grande sous-suite commune.
- Samedi 13 novembre : Examen partiel, voici son corrigé.
- Mardi 16 novembre : Implémentation de la plus longue sous-suite commune, problème du sac à dos.
- Mardi 23 novembre : Graphes non orientés et orientés, implémentation en Python, exemples. Parcours en profondeur.
TD
Les TD commencent la semaine du 13 septembre et sont assurés par les personnes suivantes :
Voici les énoncés des TD :
TP
Pour avoir accès aux machines, merci de bien vouloir activer votre identifiant SCRIPT en suivant ce lien.
Attention à bien noter votre identifiant ! Votre mot de passe sera votre mot de passe UP.
Les TP auront lieu en demi-groupe, la semaine du 13 septembre les personnes dont le nom commence par A-J vont en TP, la semaine du 20 septembre les personnes dont le nom commence par K-Z vont en TP, et on continuera en alternant.
Si les demi-groupes sont déséquilibrés il est possible qu'on fasse des ajustements sur les demi-groupes.
Les TP sont assurés par les personnes suivantes :
Voici les énoncés des TP :