Formations en Informatique de Lille
Portail pédagogique
Vous êtes ici : FIL > Portail > Licence Info > L2S4 > ASD
Algorithme et structures de données
BCC 2 : faire un choix de modèles et algorithmes adapatés à la résolution de problème

Organisation

Cette unité se déroule au S4 de la L2 INFO. Il s'agit d'une UE obligatoire.

Volume horaire : 1h30 de cours, 1h30 de TD et 1h30 de TP par semaine, pendant 12 semaines.

Objectifs

  • savoir calculer la complexité en temps et en espace d'un algorithme
  • savoir choisir une structure de données adaptée à un problème

Crédits

6 ECTS

Responsable

Mikaël Salson

Mikaël Salson
dernière modification : 23/06/2022 à 16:52:33

Contenu

Complexité en temps et en espace

  • Comptage d’opérations
  • Pire et meilleur des cas
  • Notations de Landau
  • Complexité des algorithmes récursifs, des algorithmes de tri

Structures de données

  • Tables de hachage, pile, file, arbres binaires de recherche
  • Complexité et choix des implantations d’une même structure

Bibliographie

Mikaël Salson
dernière modification : 23/06/2022 à 16:52:33

Évaluation

Cette UE est évaluée :

  • par un contrôle continu au long du semestre (TP et TD) (CC)
  • par un DS intermédiaire au milieu du semestre (DSi)
  • par un DS final (DSf)

La note de l'UE est calculée par : 1/3 × (CC + DSi + DSf)

La note de « seconde chance » est : max(1/3×CC + 2/3×DSf, DSf)

CoursTDTPInformations
1 17/01–23/01

Cours 1 et 2 : Dénombrer les opérations et complexité (PDF, version imprimable)

Pas de TD cette semaine

pas de TP cette semaine

2 24/01–30/01

Suite du cours précédent

TD 1 décompte d'opérations

TP 1 : expérimentateur

3 31/01–06/02

Récursivité et décompte d'opérations

(PDF, PDF imprimable)

  • Quelques algorithmes récursifs
  • Arbre des appels
  • Décompte des opérations avec un arbre

Même TD que la semaine précédente

Même TP que la semaine précédente

Visualisation d'algorithmes de tris (dont le quicksort, cliquez sur QUI dans le menu en haut)

4 07/02–13/02

Suite de la semaine précédente et fiche du TD sur la récursivité

TP 2 : Autour du tri rapide

14/02–20/02
5 21/02–27/02

Structures linéaires

(PDF, PDF imprimable)

  • Tableaux
  • Listes
6 28/02–06/03

Suite de la semaine précédente

Feuille de TD sur les structures linéaires

TP 3 : Itérations sur des listes

7 07/03–13/03

Tables de hachage

(PDF, PDF imprimable)

8 14/03–20/03

Suite du cours sur les tables de hachage

Pas de TD cette semaine

Pas de TP cette semaine

DS 14/03 à 14h portant sur les deux premières feuilles de TD. Document autorisé : une seule feuille A4 (recto/verso), qui peut être manuscrite ou imprimée. Note : les formules présentes dans le formulaire vous seront données dans l'énoncé.

9 21/03–27/03

Feuilles de TD sur les tables de hachage

TP 4 : Filtres de Bloom

10 28/03–03/04

Structures arborescentes

(PDF, PDF imprimable)

  • Arbres et arbres binaires
  • Parcours en profondeur et en largeur
  • Nombre de nœuds et hauteur d'un arbre
  • Arbres complets, parfaits, quasi-parfaits

Suite de la semaine précédente

Suite de la semaine précédente

11 04/04–10/04

Structures arborescentes (suite)

  • Arbres binaire de recherche
  • Tas

Feuille de TD sur les structures arborescentes

TP sur les arbres binaires (l'installation de dot (paquet graphviz) sur votre machine n'est pas indispensable, à la place vous pouvez utiliser GraphvizOnline)

11/04–17/04
18/04–24/04
12 25/04–01/05

Suite de la séance précédente

Suite de la séance précédente

13 02/05–08/05

Suite de la séance précédente

Suite de la séance précédente

14 09/05–15/05

Suite de la séance précédente

TP sur les tries

15 16/05–22/05

DS 17/05 à 8h portant sur la totalité du programme. Document autorisé : une seule feuille A4 (recto/verso), qui peut être manuscrite ou imprimée. Note : les formules présentes dans le formulaire vous seront données dans l'énoncé.

Mikaël Salson
dernière modification : 23/06/2022 à 16:52:33

Équipe pédagogique

Groupe Enseignant⋅e Mail
1 Marie-Émilie Voge marie-emilie.voge@univ-lille.fr
2 Mikaël Salson mikael.salson@univ-lille.fr
3 Pierre Allegraud pierre.allegraud@univ-lille.fr
4 Pierre Fortin pierre.fortin@univ-lille.fr
5 Nicolas Berveglieri nicolas.berveglieri@univ-lille.fr
6 Arnaud Liefooghe arnaud.liefooghe@univ-lille.fr
7 Bilel Derbel bilel.derbel@univ-lille.fr
8 Arnaud Deleruyelle arnaud.deleruyelle@univ-lille.fr
INFO-MATH Pierre Fortin pierre.fortin@univ-lille.fr

Matériel pour les TP

Si vous souhaitez développer sur vos machines vous aurez (probablement) besoin des programmes suivants.

  • Python 3
  • make
  • mkdocs (avec mkdocstrings et mkdocs-material)
  • gnuplot
  • NumPy (sous Linux ou WSL : sudo apt install python3-numpy, ou numpy avec Chocolatey)

Plus tard dans le semestre nous utiliserons également Java et C (que vous devez déjà avoir sur vos ordinateurs).

Installation

Sous Linux

Sous des distributions de la famille Debian (Ubuntu, Mint, etc.)

sudo apt install python3 mkdocs zip make gnuplot python3-pip
pip3 install mkdocstrings mkdocs-material

Attention sous Ubuntu, le paquet pour installer gnuplot s'appelle gnuplot-nox.

Sous Windows

Avec WSL

Le système WSL permet d'installer un Linux sous Windows.

Si vous choisissez une distribution Ubuntu/Debian :

sudo apt update
sudo apt install python3 python3-sphinx zip make gnuplot-nox
Avec Chocolatey

Chocolatey est un gestionnaire de paquets sous Windows qui a priori facilite l'installation d'un certain nombre de logiciels.

Vous pouvez donc utiliser Chocolatey pour installer make, zip, gnuplot. Pour sphinx, vous pouvez l'installer via votre éditeur de texte (par exemple Thonny) s'il gère l'installation de modules Python.