Algorithmes et programmation¶
Algorithmes et Programmation (ENSAE)
Plan approximatif du cours : Feuille de route 2020 (1A).
Cours animé par Xavier Dupré depuis 2001.
Le cours est évalué au premier semestre par la construction d’un package python (Réalisation d’un module python par groupe de 3 à 5) et d’un examen. Le second semestre est évalué par projet informatique. Si vous savez déjà programmer, vous devriez aller jusqu’au bout d’un des énoncés des examens précédents en moins de deux heures. L’informatique est plus souvent un outil qu’une matière à part entière. Le paragraphe Les notions qu’il faut avoir comprises ou vues propose deux profils d’utilisation et ce qu’il est suggéré de connaître pour chacun d’entre eux. Le premier réflexe quand on ne sait pas doit être internet et un moteur de recherche. stackoverflow, quora sont des forums d’échanges. Cheat Sheets est un mot qui vous mène très souvent vers un résumé des syntaxes les plus utilisées. Les séances seront un sous-ensemble des contenus proposés ci-dessous. Le cours propose un tour d’horizon des algorithmes et pratiques logicielles à connaître pour un ingénieur full stack.
Une bonne culture informatique est de plus en plus appréciée dans le monde de l’entreprise, l’ingénieur full stack est celui qui maîtrise à la fois un domaine métier, celui pour lequel il a été formé, et les techniques informatiques qu’il sera amené à manipuler au quotidien. Tous les thèmes ne seront pas abordés, les thèmes suivant intéresseront sans doute les plus curieux. Les connaissances en informatique sont hétérogènes après les classes préparatoires, les énoncés sont à choisir en fonction des lacunes.
Au terme du cours, les élèves sauront :
résoudre un problème avec un assemblage d’algorithmes
implémenter un algorithme sur les graphes
construire un module python
maîtriser les bases des outils python permettant de manipuler et représenter les données
TD - Les bases¶
Les premières séances exposent les éléments de syntaxe propres à la programmation impérative et au langage Python.
- Premiers pas en Python
- Variables, boucles
- Dictionnaires, fonctions
- Fichiers, modules, expressions régulières
- Classes, héritages
- Premiers algorithmes
- 1A.1 - Intégrale et la méthode des rectangles
- 1A.1 - Intégrale et la méthode des rectangles - correction
- 1A.1 - Tracer une pyramide bigarrée
- 1A.1 - Tracer une pyramide bigarrée - correction
- 1A.2 - Deviner la langue d’un texte
- 1A.2 - Deviner la langue d’un texte (correction)
- 1A.2 - 2048 - stratégie gagnante
- 1A.2 - 2048 - stratégie gagnante - correction
Les programmes sont des assemblages de petites fonctions qui font souvent les mêmes choses. Les programmeurs expérimentés sont plus rapides en partie parce qu’ils accumulent des bouts de codes qu’ils réutilisent. Voici une idée de ces mêmes choses qu’on fait tout le temps et qu’il est important de comprendre.
- 1A.1 - Liste, tuple, ensemble, dictionnaire, liste chaînée, coût des opérations
- 1A.algo - Calculer le nombre de façons de monter une échelle.
- Algo - Calculs de surface et autres calculs
- Algo - jeux de dictionnaires, plus grand suffix commun
- Exemples classiques
- 1A.1 - D’une structure de données à l’autre
- 1A.1 - Calculer un chi 2 sur un tableau de contingence
- 1A.1 - Histogramme et dictionnaire
- 1A.1 - Simuler une loi multinomiale
- Produit matriciel avec une matrice creuse
- Jeux de coloriage
Au terme de ces six séances, si la programmation est nouvelle pour vous ou si le langage vous paraît encore peu naturel, je vous encourage à faire d’autres exercices comme piocher dans les anciens Examens, à regarder la liste des exercices proposées à Quelques exercices du Project Euler. La plupart de ces notions font déjà partie du programme des classes préparatoires scientifiques.
TD - Algorithmes¶
Ces séances sont centrées autour de l’utilisation de la programmation pour un usage scientifique. On commence par les algorithmes et à la façon d’écrire un algorithme efficace car le principal défaut des algorithmes est leur lenteur. On a souvent des idées pour énumérer les solutions d’un problème et décrire les premières étapes avec les mains. Et puis, on se pose rapidement la question : Comment le faire rapidement ? Il y a deux questions qu’on doit se poser en premier pour entrevoir une solution.
Peut-on réécrire le problème par récurrence ? On aboutit le plus souvent à une solution issue de la programmation dynamique. Le coût est quadratique.
Peut-on couper le problème en deux, construire une solution sur chaque moitié puis recoller les solutions ? On procède de cette façon par dichotomie. Le coût est logarithmique.
Ces deux façons de faire sont présentées durant dans les séances qui suivent :
- Programmation dynamique
- Programmation dynamique
- Arbre, Trie, Graphes
- 1A.algo - Arbre et Trie
- 1A.algo - Arbre et Trie (correction)
- 1A.algo - Parcours dans un graphe (wikipédia)
- 1A.algo - Parcours dans un graphe (wikipédia) - correction
- 1A.algo - Parcours de graphe
- 1A.algo - Parcours de graphe - correction
- 1A.algo - Des problèmes de graphes
- 1A.algo - Quicksort
- 1A.algo - quicksort - correction
- 1A.algo - Spectral Clustering
- 1A.algo - Spectral Clustering - correction
- Optimisation sous contrainte
- Algorithmes en streaming
- Images
Plus on en connaît, plus il devient facile de les assembler pour résoudre des problèmes complexes. Il faut se construire une sorte de culture algorithmique (Survol algorithmique). La relecture du TD sur l’optimisation sous contrainte est conseillée à ceux qui souhaitent optimiser des portefeuilles d’actions. Il est préférable d’avoir fait la séance sur la distance de Jaccard avant de faire celle sur la distance d’édition. L’efficacité d’un algorithme est étroitement liée à la représentation des données choisies. Le trie en est l’illustration. Les recruteurs testent votre capacité à programmer avec des exercices où ils vérifient que vous savez écrire du code et comparer la vitesse de deux algorithmes. Le plus souvent, il existe une façon naïve d’arriver au résultat et il existe un algorithme plus rapide. Il y a deux grandes astuces pour aller plus vite :
la programmation dynamique, son coût est en
,
la dichotomie, son coût est en
.
Le tout est d’exprimer la solution en faisant apparaître l’un ou l’autre ou une combinaison des deux pour les problèmes les plus complexes. La programmation dynamique apparaît souvent quand on considère la solution sous forme récurrente. La dichotomie consiste à résoudre à couper l’ensemble de départ en deux, à résoudre le problème pour les deux sous-ensembles, puis à fusionner les deux solutions. Cela ne dépend pas du langage Python. Pour vous exercer :
Pour finir, un module python qui s’intéresse à la résolution de problème d’optimisation sous contraintes de type simplexe : python-constraint.
S’amuser avec les algorithmes¶
Un peu plus ludique et présentés sous la forme de défis :
Optimisation de la tournée d’un camion poubelle : le camion poubelle doit parcourir toutes les rues d’une ville, comment trouve-t-il le chemin le plus court ?
Quelques sources d’exercices
Google Jam (exemple : Le problème des milkshakes)
TD - calcul matriciel, graphes, données - data science¶
La séance sur les dataframes propose des outils de manipulation et visualisation des données utiles pour tous les projets réalisés à l’école. Ces séances sont centrées sur les outils indispensables pour manipuler facilement les données et faire des calculs rapides. Ces outils sont similaires à ceux qu’on trouve dans de nombreux languages à usage scientifique (R, SciLab, Julia, Octave, …). Ces séances peuvent paraître plus longues car elles s’appuient sur des modules qu’il faut découvrir puis utiliser pour résoudre des exercices. Toutefois, les modules numpy, pandas, matplotlib sont incontournables pour manipuler les données en Python.
- Tech - expressions régulières
- 1A.data - DataFrame et Matrice
- 1A.data - DataFrame et Matrice (correction)
- 1A.data - Décorrélation de variables aléatoires
- 1A.data - Décorrélation de variables aléatoires - correction
- 1A.soft - Calcul numérique et Cython
- 1A.soft - Calcul numérique et Cython - correction
- 1A.data - Visualisation des données
- 1A.data - Visualisation des données - cartes
- 1A.data - Visualisation des données - graphes interactifs
- 1A.data - visualisation des données - correction
Il existe de nombreuses libraires de visualisation des données en Python et elles se sont multipliées depuis l’avènement des notebooks : 10 plotting libraries at PyData 2016.
S’amuser avec des données¶
Une fois qu’on est agile avec les données, on peut facilement explorer, émettre des hypothèses ou résoudre quelques énigmes :
Que font les habitants de Chicago après le travail ? (ceux qui font du vélo tout du moins)
TD - Site web et pratiques logicielles¶
Le langage Python est au programme des classes préparatoires scientifique (Prise en main du logiciel Python) et les étudiants ont déjà vu ou parcouru des exercices algorithmiques (voir MathPrepas, Programmation en Python). Cette partie s’adesse essentiellement à ceux qui ont déjà programmé. On peut se pencher sur d’autres aspects logiciels tels que les tests unitaires, le templating, les sites Web, le scraping, encoding, les notebooks…
Lectures
- Site Web, exemple avec Flask
- Génie logiciel : coder facilement, coder à plusieurs, qualité du code, gestion de projets
- 2A.soft - Git depuis le notebook
- 1A.soft - Exemple de profiling
- Tech - profiling
- 2A.soft - Convert a notebook into a document
- 2A.soft - Custom Magics for Jupyter
- Python et C++, stratégies
Exercices
Deux exercices sont suggérés pour une séance de deux heures à choisir parmi :
Appliquer une des méthodes décrites dans Profiling à un exercice d’une séance précédente
Concevoir une campagne publicataire avec
Les notions qu’il faut avoir comprises ou vues¶
La programmation est incontournable dès qu’on manipule des données. Les logiciels clic-bouton sont utiles pour explorer mais ils permettent difficilement de gérer de grands volumes, d’automatiser un processus de traitement de données et de le mettre en production. Voici les notions qu’il faut avoir comprises.
Pour un profil plutôt analyste¶
Les données servent à comprendre. Les calculs sont moins importants qu’une bonne représentation d’un phénomène qu’on cherche à expliquer.
Ce qu’il faut maîtriser
Les bases du langage Python : boucles, tests, fonctions, listes, dictionnaires, modules, expressions régulières.
Le tri et la recherche dichotomique.
La notion de coût algorithmique.
Le calcul matriciel, les dataframes, les graphes.
Ce qu’il faut connaître
Les classes.
La programmation dynamique.
Pour un profil plutôt ingénieur¶
Les données servent à améliorer un processus de décision quitte à ne plus comprendre comment les variables sont assemblées pour prendre cette décision.
Ce qu’il faut maîtriser
Les bases du langage Python : boucles, tests, fonctions, listes, dictionnaires, modules, expressions régulières.
Les classes,
Le tri, la recherche dichotomique, la programmation dynamique.
La notion de coût algorithmique.
Notion de graphes et de parcours dans un graphe.
Le calcul matriciel, les dataframes, les graphes.
Ce qu’il faut connaître
Les tests unitaires.
Git.
Des exercices de type Google Jam.
Des accélérations du langage comme Cython.
Créer un site web avec Flask, Javacript.
Séance notée¶
La dernière séance est une séance notée. Tous les documents sont autorisés. Les examens passés sont disponibles : Examens. Les examens sont plutôt destinés à ceux qui viennent de commencer la programmation. Si votre pratique est régulière, vous devriez aller trois fois plus vite à la fin de la scolarité.
Getting started¶
Il faut vous reporter à la section En résumé : Anaconda pour installer Python. Certaines séances pratiques utilisent des données depuis ce site. Elles sont facilement téléchargeables avec ces deux modules pyquickhelper et pyensae.
Il faut ensuite un outil pour écrire des programmes. Si la majorité des exemples sont fournis sous forme de notebook mais ce n’est pas le seul environnement de travail ce qu’on surnomme un IDE. Spyder ou PyCharm. Sous Windows, PTVS dispose d’un bon débuggeur.
Bibliographie¶
Cheat Sheet
Python Cheat Sheets, aborde des sujets rares comme les sockets, l’API C, …
Liens
Les trucmuchables en Python (iterable, mutable, immutable, …)
8 Regular Expressions You Should Know (2016/03)
Love Python (2016/03)
The Hitchhiker’s Guide to Python! (2016/06)
Evolution of a salesman: A complete genetic algorithm tutorial for Python
Livres
Apprentissage de la programmation, Gérald Swinnen
Programmation avec le langage Python (PDF, ou version Ellipse), version web et plus récentes : teachpyx.
Teach Yourself Python in 24 Hours, Ivan Van Laningham (le site est visuellement difficile, version PDF)
Précis de recherche opérationnelle, Robert Faure, Bernard Lemaire, Christophe Picouleau
Problem Solving with Algorithms and Data Structures, Brad Miller, David Ranum (version html)
Automate Boring Stuff with Python (2016/03)
Intermediate Python Release (2016/03)
Cours
Apprenez à programmer en Python (openclassrooms)
Python cours et TPs (2016/04)
Le Python en prépas (2016/04)
Algorithmique et programmation en CPGE (2016/04)
Exercices et jeux
Quelques exercices du Project Euler (2016/04)
Countdown to 2016 (2016/08)
The Convex Hull Problem (2016/08)
Rosalind (2016/09)
MOOC
Code Academy Python (utilise Python 2.7)
Outils
PythonTutor : pour suivre pas à pas l’exécution d’un programme (petit)
Intervenants¶
2018-2019 : Xavier Dupré, Microsoft France (professeur), Lucie Neirac, Benoît Choffin, Laboratoire de Recherche en Informatique
2017-2018 : Xavier Dupré, Microsoft France (professeur), Benjamin Donnot, Lucie Neirac, Marc-Antoine Weisser, Supélec
2016-2017 : Xavier Dupré, Microsoft France (professeur), Pierre Cordier, Effiscience, Yves Gerey, A2iA, Charles de Ravel d’Esclapon, Etaonis, Arthur Renaud, Etaonis, Mehdi Seddar, Artfact, Marc-Antoine Weisser, Supélec.
A propos du cours¶
Ce cours a commencé en 2004 et n’a cessé de s’enrichir. Il est animé par Xavier Dupré (ENSAE 1999). Il a pour objectif d’introduire la programmation avec Python, des algorithmes, et de présenter quelques pratiques tirées de l’industrie logicielle. Les deux derniers points sont assez rarement évoqués dans le cursus scolaire français mais revêt de plus en plus d’importance en datascience.