Descriptif du cours
Objectifs
Connaissances en algorithmique :
- notion de type abstrait,
- maîtrise des structures de données classiques,
- connaissance des algorithmes associés,
- capacité à étudier la complexité de ces algorithmes,
- raisonnement sur un type abstrait.
Compétences en programmation Python :
- implémentation de structures de données,
- codage des algorithmes associés,
- manipulation de fichiers.
Contenu de la formation
Nous nous intéressons à la représentation de données complexes et à l'étude des principales structures de données utilisées : pile, file, enregistrement, tableau, table de hachage, etc.
On considère ensuite les algorithmes associés à ces structures et à la notion de complexité algorithmique (qui permet de quantifier les ressources, temps et mémoire, nécessaires à l'exécution de ces algorithmes).
Dans cette démarche, les aspects théoriques du cours sont mis en pratique en Python (notamment à travers les dictionnaires de Python) et le découpage fonctionnel assimilé aux semestres précédents est systématiquement mis en œuvre. La manipulation de fichiers en Python est également étudiée.
Planning des séances
Cours 1/6, mardi 13 septembre 2011
- Présentation et organisation du cours,
- introduction à l'algorithmique,
- découpage fonctionnel,
- notions de complexité,
- types abstraits : Entier et Pile.
TP 1/9, mardi 13 septembre 2011
- Boucles for et while de python,
- boucles simples et boucles imbriquées,
- production de figures géométriques,
- découpage fonctionnel en procédures python avec paramètres.
TP 2/9, mardi 20 septembre 2011
- Révisions sur la manipulation de tableaux en Python,
- révisions sur la production d'aléatoire en Python,
- mise en œuvre du type abstrait Entier.
Cours 2/6, mardi 27 septembre 2011
- Types abstraits : enregistrements et tableaux,
- premiers algorithmes sur les tableaux.
TP 3/9, mardi 27 septembre 2011
- Fin des implémentations des entiers,
- implémentation Python des piles,
- premiers exercices sur les piles.
TP 4/9, mardi 4 octobre 2011
- Suite des exercices sur les piles,
Cours 3/6, mardi 11 octobre 2011
- Algorithmes avancés sur les tableaux et complexité,
- recherche dichotomique.
TP 5/9, mardi 11 octobre 2011
- Suite et fin des exercices sur les piles.
TP 6/9, mardi 18 octobre 2011
- Enregistrements en Python,
- mise en œuvre des tableaux en Python,
- implémentation des premiers algorithmes sur les tableaux.
Cours 4/6, mardi 25 octobre 2011
Interrogation écrite.
TP 7/9, mardi 25 octobre 2011
Poursuite de l'implémentation des algorithmes dédiés aux tableaux.
Cours 5/6, mardi 8 novembre 2011
Méthodes de tri et complexité.
TP 8/9, mardi 8 novembre 2011
- Implémentation d'algorithmes de recherche dans les tableaux.
TP 9/9, mardi 15 novembre 2011
- Implémentation des méthodes de tri sur les tableaux.
Exercices bonus pour les plus rapides :
- Production de tableaux aléatoires et mesure des temps d'exécution de chaque algorithme,
- utilisation de tableaux d'enregistrements et implémentation des algorithmes pour ces types de données,
- comparaison expérimentale des méthodes de tri, mesure des temps de calcul, écriture dans un fichier, visualisation à l'aide de gnuplot,
- conjecture de Syracuse,
- décryptage d'un texte codé.
Cours 6/6, mardi 22 novembre 2011
Interrogation écrite. Les documents sont interdits.
Voir aussi...
- Introduction à l'algorithmique
Cours d'initiation à l'algorithmique : langage de description, utilisation de boucles, types abstraits, algorithmes sur les tableaux, notions de complexité et de calculabilité.
- Notes de cours sur le langage Python
Introduction à la programmation en Python : sa syntaxe générale, quelques librairies utiles et la manipulation de fichiers en Python.
- Travaux pratiques en Python
Séances de programmation en Python 3.
