Page du cours Algorithmique et programmation 3 (L2)

Merci de bien vouloir vous inscrire sur la page moodle correspondante, afin notamment de pouvoir rendre vos TP facilement et de recevoir les annonces du cours. L'inscription devrait désormais fonctionner, si ce n'est pas le cas contactez moi par email.

Le cours aura désormais lieu le mardi de 14h à 15h30 dans la salle BBB AP3. Des vidéos du cours seront disponible environ une journée après le cours, le temps pour le serveur BBB de générer la vidéo. Attention si vous êtes sur Mac, BBB fonctionne mal sous Safari, merci d'utiliser Firefox ou Chrome, notamment pour lire les vidéos.

Voici l'énoncé de l'examen final et son corrigé.

Cours

  1. La première séance aura lieu mardi 9 septembre, de 14h à 14h30 pour les Maths, et de 15h à 15h30 pour les MIASH (amphi 13E, halles). Elle portera sur la complexité et la correction des algorithmes (chapitre 1 du poly). Voici quelques vidéos d'accompagnement, sur la complexité: Je parlerai aussi de correction des algorithmes mardi.
  2. pour le 15/09: Première section du chapitre 2 du poly, à savoir l'algorithme de recherche naïve dans un tableau quelconque, et l'algorithme de recherche dichotomique dans un tableau trié. Voici quelques vidéos d'accompagnement qui devraient arriver vendredi soir: Pour le cours du mardi (14h: Maths; 15h: MIASH), réfléchir aux exercices 2.1 et 2.2.
  3. pour le 22/09: Fin du chapitre 2 du poly, à savoir le tri à bulle et le tri par sélection. Pas de vidéo cette semaine. Vous êtes invités à essayer d'implémenter ces deux tris en Python (sur des listes d'entiers). Voici un exemple d'implémentation de ces tris.
  4. pour le 29/09: chapitre 3 jusqu'à l'algorithme d'Euclide inclus, à l'exception de la preuve de la complexité sur laquelle je reviendrai mardi. Voici une vidéo qui présente les versions récursives de la recherche séquentielle et la recherche dichotomique, vous pouvez déjà en lire le code source. Exercice: modifier la fonction de recherche dichotomique proposée afin que, quand l'élément appartient à la liste, elle donne son indice dans la liste.
  5. pour le 06/10: Fin du chapitre 3 et tri fusion jusqu'à la preuve de sa complexité incluse. Voici quatre vidéos sur le tri fusion, à regarder dans l'ordre.
    1. La première présente de façon informelle la fusion de deux tableaux triés (4min).
    2. La seconde explique le pseudo-code de la fusion de deux tableaux triés (5min).
    3. La troisième présente le tri fusion avec son pseudo-code (7min) et explique rapidement sa correction.
    4. Enfin la quatrième donne la preuve de la complexité du tri fusion (12min) avec une présentation différente de celle du poly (mais je vous conseille de bien comprendre les deux !). Il y a une petite erreur dans la vidéo: K devrait être K'. C'est corrigé dans le tableau.
  6. Le cours du 13/10 aura lieu en semi-présentiel: tous les étudiants qui sont censés être sur le campus cette semaine viennent tous en amphi 13E à 14h, et le cours sera diffusé en direct pour les autres en suivant ce lien, de 14h à 15h30. Merci de vous connecter en précisant votre prénom et nom. L'enregistrement est disponible ici et sur Youtube. Le cours portait sur le paradigme "diviser pour régner", avec une preuve de l'optimalité de la borne en O(nlog n) pour la complexité des tris, puis la description de l'algorithme de multiplication rapide de polynômes, et le calcul de sa complexité.
  7. Le cours du 20/10 aura lieu en semi-présentiel, il porte sur le début du chapitre 5 du poly (programmation dynamique). L'enregistrement est disponible, voici également le tableau.
  8. Le cours du 3/11 a eu lieu à distance, il s'agissait d'une séance de révisions. L'enregistrement est disponible, voici également le tableau.
  9. Le cours du 10/11 a eu lieu à distance, nous avons fini l'algorithme de la plus longue sous-suite et vu le problème de sac à dos et sa résolution en programmation dynamique. Voici le tableau et l'enregistrement vidéo.
  10. Le cours du 17/11 a eu lieu à distance, voici le tableau et la vidéo. On a fait quelques remarques sur le DM puis sur le problème du sac à dos, puis commencé les graphes (définitions de bases, exemples, implémentation).
  11. Le cours du 24/11 a eu lieu à distance, voici la vidéo (le tableau est malheureusement perdu suite à un problème technique). On a vu l'algorithme de parcours en profondeur d'un graphe et prouvé sa correction.
  12. Le cours du 1/12/12 a eu lieu à distance, voici la vidéo et le tableau. On a vu la complexité du parcours en profondeur, l'algorithme de détection de circuits, et l'algorithme de Bellman-Ford. Les notions du poly que nous n'avons pas eu le temps d'aborder (tri topologique, algorithme de Bellman-Ford pour des arêtes de poids négatif et application à la programmation linéaire) ne sont donc pas au programme de l'examen, qui aura lieu en janvier (la date exacte vous sera communiquée dès qu'elle est confirmée).

TD

Les TD commencent la semaine du 7 septembre et sont assurés par les personnes suivantes : Voici les énoncés des TD :

TP

Les TD commencent la semaine du 7 septembre et sont assurés par les personnes suivantes : Voici les énoncés des TP :