Licence Info

Apprendre à programmer avec Python 3, Gérard Swinnen, editions Eyrolles (Chapitres 1 à 7, et chapitre 10 en partie). Version électronique téléchargeable.
Introduction à l’algorithmique. Cormen, Leiserson, Rivest et Stein. Disponible à Lilliad.
Documentation officielle de Python.

Mikaël Salson
dernière modification : 05/12/2023 à 19:18:15

É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)

		Cours	TD	TP	Informations
1	16/01–22/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	23/01–29/01	Suite du cours précédent	TD 1 décompte d'opérations	TP 1 : expérimentateur
3	30/01–05/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	06/02–12/02	Suite de la semaine précédente	Suite de la semaine précédente et fiche du TD sur la récursivité	TP 2 : Autour du tri rapide
5	13/02–19/02	Structures linéaires (PDF, PDF imprimable) Tableaux Listes	Suite de la semaine précédente	Suite de la semaine précédente
	20/02–26/02
6	27/02–05/03	Suite de la semaine précédente	Feuille de TD sur les structures linéaires	TP 3 : Itérations sur des listes
7	06/03–12/03	Tables de hachage (PDF, PDF imprimable)	Suite de la semaine précédente	Suite de la semaine précédente
8	13/03–19/03	Suite du cours précédent	Pas de TD cette semaine	Pas de TP cette semaine	DS le 13 mars 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é si nécessaire.
9	20/03–26/03	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	Feuilles de TD sur les tables de hachage	TP 4 : Filtres de Bloom
10	27/03–02/04	Structures arborescentes (suite) Arbres binaire de recherche Tas	Suite de la semaine précédente	Suite de la semaine précédente
11	03/04–09/04		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)
12	10/04–16/04		Suite de la séance précédente	Suite de la séance précédente
	17/04–23/04
	24/04–30/04
13	01/05–07/05		Suite de la séance précédente	Suite de la séance précédente
14	08/05–14/05		Suite de la séance précédente	TP sur les tries
15	15/05–21/05				DS 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é si nécessaire.

Mikaël Salson
dernière modification : 05/12/2023 à 19:18:15

Documents

Ressources utiles

Calculs de complexité

Un document résumant des formules utiles sur les sommes, logarithmes et puissances.
Une vidéo résumant le principe des calculs de complexité et donnant des exemples de différentes classes de complexité.

Anciens DS

Voici quelques DS des années précédentes avec des éléments de correction. Ne regardez les corrections qu'après avoir travaillé sur les DS.

2023

DS intermédiaire – mars 2023, éléments de correction

2022

2021

2019

2018

2017

Équipe pédagogique

Groupe	Enseignant⋅e	Mail
1	Marie-Émilie Voge	marie-emilie.voge@univ-lille.fr
2	Claire Divoy	claire.divoy@univ-lille.fr
3	Pierre Allegraud	pierre.allegraud@univ-lille.fr
4	Mikaël Salson	mikael.salson@univ-lille.fr
5	Antonio Al Serhali	antonio.al-serhali@inria.fr
6	???	???
7	Pierre Fortin	pierre.fortin@univ-lille.fr
8	Hector Kohler	hector.kohler@inria.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, mkdocstrings-python 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 mkdocstrings-python 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, reportez-vous ensuite à la section ci-dessus.

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.

Informatique

Organisation

Objectifs

Crédits

Responsable

Contenu

Complexité en temps et en espace

Structures de données

Bibliographie