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 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 M5 A12 Jean-Stéphane Varré jean-stephane.varre@univ-lille1.fr
3 TD Vendredi 8h30-10h M5 A8 Bilel Derbel bilel.derbel@univ-lille1.fr
3 TP Vendredi 10h15-11h45 M5 A11 Bilel Derbel bilel.derbel@univ-lille1.fr
4A TD Mardi 8h30-10h M5 A9 Yves Roos yves.roos@univ-lille1.fr
4B TD Mardi 8h30-10h M5 A9 Jean-Stéphane Varré jean-stephane.varre@univ-lille1.fr
4A TP Lundi 13h30-15h M5 A13 Yves Roos yves.roos@univ-lille1.fr
4B TP Lundi 13h30-15h M5 A11 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 M5 A1 François Lemaire francois.lemaire@univ-lille1.fr
6 TP Mercredi 8h30-10h M5 A11 François Lemaire francois.lemaire@univ-lille1.fr

dernière modification : 09/01/2018 à 13:52:12

Les cours débutent la semaine du 15 janvier 2018. Les TDs et TPs débutent la semaine du 22 janvier 2018.

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.

pas de cours
Séance Date Cours TD TP Remarque
1 du 15/01 au 20/01

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

Présentation du cours
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 19 à 33
pas de TD pas de TP
2 du 22/01 au 27/01 Complexité asympotique. Présentation des notations O, Omega et Theta.
Diapositives 34 à 50
TD1 : décompte d'opérations et notations asymptotiques TP1 : expérimentateur
3 du 29/01 au 03/02 Rappels sur la récursivité. Complexité du tri par insertion dichotomique. Diapositives 1 à 22
4 du 05/02 au 10/02 Equations de partition. Théorème général. Equations linéaires du premier ordre. Diapositives 23 à la fin TD2 : complexité des algorithmes récursifs TP2 : autour du tri rapide
5 du 12/02 au 17/02

Implantation des structures linéaires usuelles.

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

Tables de hachage.

Exemples introductifs. Vocabulaire. Diapositives 1 à 9.
TD3 : structures linéaires TP3 : listes avec itérateurs DS intermédiare le vendredi 23 février, de 14h à 16h, bât A5 Documents de cours, TD, TP autorisés, pas de livre, pas de calculatrice.
du 26/02 au 03/03 interruption pédagogique hiver
7 du 05/03 au 10/03 Adresse ouvert. Hachage en vase clos. Discussion sur le calcul de complexité en moyenne. .
8 du 12/03 au 17/03 Résolution des collisions par chaînage. .

Complexité moyenne te amortie

Discussion hors programme.
9 du 19/03 au 24/03

Structures de données arborescentes

Introduction aux arbres. Arbres binaires. Parcours. Arbres binaires de recherche. .
10 du 26/03 au 31/03 Arbres binaires de recherche. Le tas, tris par tas. . Arbres équilibrés, rappels sur les ABR. .
11 du 02/04 au 07/04 AVL. . lundi 2 avril férié
12 du 09/04 au 14/04 Pas de cours.
13 du 16/04 au 21/04 lundi 1er mai férié
du 23/04 au 28/04 interruption pédagogique de printemps
du 30/04 au 05/05 interruption pédagogique de printemps
14 du 07/05 au 12/05 Pas de cours.

dernière modification : 22/02/2018 à 13:46:52

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