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 [@] lifl [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 : 07/07/2016 à 09:37:54

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 A6 Arnaud Liefooghe arnaud.liefooghe@univ-lille1.fr
1 TP Vendredi 10h20-11h50 SUP 118 Arnaud Liefooghe arnaud.liefooghe@univ-lille1.fr
2 TD Vendredi 10h20-11h50 M5 A7 Jean-Stéphane Varré jean-stephane.varre@univ-lille1.fr
2 TP Jeudi 8h30-10h SUP 118 Jean-Stéphane Varré jean-stephane.varre@univ-lille1.fr
3 TD Vendredi 8h30-10h M5 A8 Gauvain Marquet gauvain.marquet@ed.univ-lille1.fr
3 TP Vendredi 10h15-11h45 M5 A11 Gauvain Marquet gauvain.marquet@ed.univ-lille1.fr
4 TD Mardi 8h30-10h M5 A9 Yves Roos yves.roos@univ-lille1.fr
4A TP Lundi 13h30-15h M5 A13 Yves Roos yves.roos@univ-lille1.fr
4B TP Lundi 13h30-15h M5 A14 Jean-Stéphane Varré jean-stephane.varre@univ-lille1.fr
5 TD Lundi 13h30-15h00 M1 Lebesgue Pierre Allégraud pierre.allegraud@univ-lille1.fr
5 TP Jeudi 8h30-10h M5 A16 Pierre Allégraud pierre.allegraud@univ-lille1.fr
6 TD Vendredi 10h20-11h50 P1 003 François Lemaire francois.lemaire@univ-lille1.fr
6 TP Mercredi 8h30-10h M5 A13 François Lemaire francois.lemaire@univ-lille1.fr

dernière modification : 06/01/2017 à 16:55:52

Les cours débutent la semaine du 9 janvier 2017. Les TDs et TPs débutent la semaine du 16 janvier 2017.

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 Date Cours TD TP Remarque
1 du 09/01 au 14/01

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

Présentation du cours
Jeudi:
Que compter ? Complexité en temps et en espace. Comportement différent de l'algorithme en fonction de la donnée. Notion de pire et meilleur des cas.
Diapositives 1 à 14
Vendredi:
Décompte du nombre de comparaisons, par l'expérience et exact, sur les tris bulle, sélection et insertion.
Diapositives 15 à 35
reprise des enseignements le jeudi 12 janvier
2 du 16/01 au 21/01 Complexité asympotique. Présentation des notations O, Omega et Theta.
Diapositives jusqu'à à la fin
TD1 : décompte d'opérations et notations asymptotiques TP1 : expérimentateur samedi 21 janvier : Journée Portes Ouvertes Lille 1.
3 du 23/01 au 28/01 Rappels sur la récursivité. Complexité du tri par insertion dichotomique. Diapositives 1 à 17
4 du 30/01 au 04/02 Equations de partition. Théorème général. Equations linéaires du premier ordre. Diapositives 22 à la fin TD2 : complexité des algorithmes récursifs TP2 : autour du tri rapide
5 du 06/02 au 11/02

Implantation des structures linéaires usuelles.

Listes chaînées. Listes circulaires et autres. Diapositives 1 à 24.
6 du 13/02 au 18/02 Itérateurs, piles et files.Diapositives 26 à la fin.

Tables de hachage.

Exemples introductifs. Vocabulaire. Diapositives 1 à 15.
TD3 : structures linéaires TP3 : listes avec itérateurs DS intermédiare Documents de cours, TD, TP autorisés, pas de livre, pas de calculatrice.
du 20/02 au 25/02 interruption pédagogique hiver
7 du 27/02 au 04/03 Adresse ouvert. Hachage en vase clos. Discussion sur le calcul de complexité en moyenne. Diapositives 16 à 42.
8 du 06/03 au 11/03 Résolution des collisions par chaînage. Diapositives 45 à la fin.

Complexité moyenne te amortie

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

Structures de données arborescentes

Introduction aux arbres. Arbres binaires. Parcours. Arbres binaires de recherche. Diapositives 1 à 29.
TD4 : autour des tables de hachage
10 du 20/03 au 25/03 Arbres binaires de recherche. Le tas, tris par tas. Diapositives 17 à la fin. Arbres équilibrés, rappels sur les ABR. Diapositives 1 à 4. TP5 : arbres binaires
11 du 27/03 au 01/04 AVL. Diapositives 5 à la fin. TD5 : structures arborescentes
12 15 du 04/04 au 09/04 Pas de cours. TP6 : trie
du 11/04 au 16/04 interruption pédagogique de printemps
du 17/04 au 22/04 interruption pédagogique de printemps
13 du 24/04 au 29/04 Pas de cours.
14 du 01/05 au 06/05 lundi 1er mai férié

dernière modification : 30/03/2017 à 13:48:50

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