Vous êtes ici : FIL > Portail > Licence Info > L2S4 > ASD

Algorithmes et Structures de Données (ASD)

L'UE ASD fait suite aux UEs API2 et Math-Discrètes dont elle réutilise abondamment les notions abordées.

Responsable

Jean-Stéphane Varré, jean-stephane.varre [@] univ-lille [dot] fr

Volume horaire et organisation

L'UE est organisée en 1h30 de cours, 1h30 de TD et 1h30 de TDM par semaine durant 12 semaines.

Les cours présentent les algorithmes et les structures de données abordées en discutant de l'intérêt que peuvent avoir chacun(e) de ces structures/algorithmes suivant les données que l'on a à traiter.

Les TDs sont l'occasion de bien cerner les outils présentés en cours et aussi le lieu de réflexion pour la résolution de problèmes.

Les TPs permettent d'aborder le problème de l'implantation effective de ces algorithmes et des structures.

Crédits

5 ECTS

dernière modification : 08/02/2018 à 12:03:30

Objectifs

  • Introduire les structures de données de base et les algorithmes qui les accompagnent. Savoir discuter de la complexité d'un algorithme. Connaître les classes de complexité.
  • L'étudiant acquiert les réflexes nécessaires au choix d'une structure de données adaptée au problème qu'il a à résoudre. Il est capable d'identifier le comportement asymptotique des algorithmes.

Contenu

  • Complexité des algorithmes récursifs.
  • Tables de hachage : principes, techniques, complexité.
  • Structures de pile, file : implantation, complexité.
  • Complexité des algorithmes de tri : tri rapide, tri fusion, tri par tas.
  • Structures arborescentes : implantation, complexité, arbres binaires de recherche, un type d'arbre équilibré.

Bibliographie

Introduction à l'algorithmique. Thomas H. Cormen et al. Dunod, 2002. ISBN 978-2100039227.

dernière modification : 07/07/2016 à 09:37:54
Gpe Nature Horaire Salle Enseignant e-mail
Cours Jeudi 10h20-11h50 M1 Chatelet Jean-Stéphane Varré jean-stephane.varre@lifl.fr
1 TD Vendredi 8h30-10h M5 A1 Arnaud Liefooghe arnaud.liefooghe@univ-lille.fr
1 TP Vendredi 10h20-11h50 M5 A11 Arnaud Liefooghe arnaud.liefooghe@univ-lille.fr
2 TD Vendredi 10h20-11h50 M5 A1 Jean-Stéphane Varré jean-stephane.varre@univ-lille.fr
2 TP Jeudi 8h30-10h M5 A12 Jean-Stéphane Varré jean-stephane.varre@univ-lille.fr
3 TD Vendredi 8h30-10h M5 A3 Bilel Derbel bilel.derbel@univ-lille.fr
3 TP Vendredi 10h15-11h45 M5 A13 Bilel Derbel bilel.derbel@univ-lille.fr
4 TD Mardi 8h30-10h M5 A9 Marie-Emilie Voge marie-emilie.voge@univ-lille.fr
4 TP Lundi 13h30-15h M5 A11 Marie-Emilie Voge marie-emilie.voge@univ-lille.fr
5 TD Lundi 13h30-15h00 M5 A3 Pierre Allégraud pierre.allegraud@univ-lille.fr
5 TP Mercredi 8h30-10h M5 A12 Pierre Allégraud pierre.allegraud@univ-lille.fr
6 TD Lundi 8h30-10h00 M5 A1 François Lemaire francois.lemaire@univ-lille.fr
6 TP Mercredi 8h30-10h M5 A13 François Lemaire francois.lemaire@univ-lille.fr
7 TD Mardi 8h30-10h00 M5 A6 Camille Marchet camille.marchet@univ-lille.fr
7 TP Lundi 13h30-15h M5 A13 Camille Marchet camille.marchet@univ-lille.fr

dernière modification : 07/01/2019 à 12:03:16

Les cours débutent la semaine du 14 janvier 2019. Les TDs et TPs débutent la semaine du 21 janvier 2019.

Les contenus des séances de cours n'ayant pas encore eu lieu sont donnés à titre indicatif et se basent sur la progression de l'année précédente. L'avancement pourra être modifié au cours du semestre.

Séance Cours TD TP Remarque
1 du 14/01 au 19/01 Présentation du cours

Analyse de la complexité des algorithmes, illustration sur les tris.

Mercredi:
Que compter ? Analyse des temps et des appels des opérations grâce à un profiler.
Diapositives 1 à 19
Jeudi:
Introduction des notions de pire et meilleurs des cas, calcul de complexité sur la recherche du nombre d'éléments dans un tableau. Décompte du nombre de comparaisons, par l'expérience et exact, sur le tri bulle.
Diapositives 20 à 33
2 du 21/01 au 26/01 Complexité asympotique. Présentation des notations O, Omega et Theta.
TD1 : décompte d'opérations et notations asymptotiques TP1 : expérimentateur
3 du 28/01 au 02/02 Rappels sur la récursivité. Complexité du tri par insertion dichotomique.
4 du 04/02 au 09/02 Equations de partition. Théorème général. Equations linéaires du premier ordre. TD2 : complexité des algorithmes récursifs TP2 : autour du tri rapide
5 du 11/02 au 16/02

Implantation des structures linéaires usuelles.

Listes chaînées. Listes circulaires et autres.
du 18/02 au 23/02 interruption pédagogique hiver
6 du 25/02 au 02/03 Itérateurs, piles et files.

Tables de hachage.

Exemples introductifs. Vocabulaire.
TD3 : structures linéaires TP3 : listes avec itérateurs
7 du 04/03 au 09/03 Adresse ouvert. Hachage en vase clos. Discussion sur le calcul de complexité en moyenne.
8 du 11/03 au 16/03 Résolution des collisions par chaînage.

Complexité moyenne et amortie

Discussion hors programme.
TP4 : filtres de Bloom
9 du 18/03 au 23/03

Structures de données arborescentes

Introduction aux arbres. Arbres binaires. Parcours.
TD4 : autour des tables de hachage
10 du 25/03 au 30/03 Arbres binaires de recherche. Le tas, tris par tas. TP5 : arbres binaires
11 du 01/04 au 06/04 Arbres binaires de recherche équilibrés, AVL. TD5 : structures arborescente
du 08/04 au 20/04 interruption pédagogique de printemps
12 du 22/04 au 27/04 TP6 : trie lundi 22 avril férié
13 du 29/04 au 04/05 mercredi 1er mai férié
14 du 06/05 au 11/05 mercredi 8 mai férié

dernière modification : 17/01/2019 à 13:53:21

L'évaluation s'effectue suivant une procédure de contrôle continu.

Trois notes seront attribuées à chaque étudiant durant le semestre :

  • DS1 et DS2 : deux notes sur 20 de devoirs surveillés,
  • TD : une note sur 20 sur les TP rendus (au nombre de 6, 1 toutes les deux semaines) et d'éventuelles interrogations réalisées durant les TD

La note finale sur 20 (N) est calculée comme une moyenne des trois notes :

N= (DS1+DS2+TD)/3

Le cas échéant, après la session de rattrapage, les notes de DS1 et DS2 sont remplacées par la note obtenue au rattrapage DS3, la note de TD reste acquise.

N= (2*DS3+TD)/3

L'unité acquise apporte 5 ECTS.


dernière modification : 07/07/2016 à 09:37:54