Algorithmes et programmation

ENSAE - OMI1C4, ENSAE - OMI1C9

Cours animé par Xavier Dupré. Intervenants 2015-2016 : Xavier Dupré, Microsoft France, Pierre Cordier, Effiscience, Yves Gerey, A2iA, Charles de Ravel d’Esclapon, Etaonis, Arthur Renaud, Etaonis, Mehdi Seddar, Artfact, Marc-Antoine Weisser, Supélec

Ce cours s’étale sur 12 séances de travaux dirigés (TD) d’une durée de 2h. Le cours est décrit plus en détail dans cette présentation : ENSAE 1A - Programmation. slideslogo

Le cours est évalué au premier semestre par un examen et aussi Etude d’un algorithme en binôme. Le second semestre et facultatif et est évalué par projet informatique.


TD - les bases

Les six premières séances font les éléments de syntaxe propres à la programmation impérative.

Les programmes sont des assemblages de petites fonctions qui font souvent les mêmes choses. Voici une idée de ces mêmes choses qu’on fait tout le temps et qu’il est important de comprendre.

Le premier jeu qu’on demande d’implémenter à tous ceux qui commencent la programmation :

A la fin des premières séances, on peut réfléchir à l’implémentation d’un algorithme :

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. Il faudra dans tous les cas participer au jeu suivant :


TD - Site web et pratiques logiciels

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...

Deux exercices sont suggérés pour une séance de deux heures à choisir parmi :

  1. Constuire un site web avec Flask, Django ou Falcon
  2. Ecrire un test unitaire pour un exercice d’une séance précédente
  3. Appliquer une des méthodes décrites dans Profiling à un exercice d’une séance précédente
  4. Constuire la documentation d’un module avec Sphinx
  5. Implémenter une nouvelle commande magique sur Jupyter
  6. Concevoir une campagne publicataire avec Mako ou Jinja2

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.

  1. 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.
  2. 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 trois séances à choisir parmi :

Notes

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.

Entretiens d’embauche

Les recruteurs testent de plus en plus 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 O(n^2),
  • la dichotomie, son coût est en O(\ln_2 n).

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. Ce cela ne dépend pas du langage Python. Pour vous exercer :

Et pour apprendre :

Quelques sources d’exercices


TD - calcul matriciel, graphes, données

Les quatre sujets importants des six dernières séances sont la programmation dynamique, la dichotomie, les dataframe, les graphiques. La séance 9, la fin de la séance 10 et la séance 11 ne sont pas indispensables et seront vus plus en détail l’année prochaine. Toutefois, 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 trois 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.

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. La simulation du hasard est revient fréquemment pour éviter qu’un programme retourne toujours les mêmes résultats. Voici quelques exemples :

La dernière séance est une séance notée. Tous les documents sont autorisés. Quelques questions peuvent requérir l’utilisation des outils présentées durant les séances 9 à 12. Toutefois, si tel était le cas, ce serait très proche d’une solution proposée lors des TD.


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 :


Bibliographie

Cheat Sheet

Liens

Livres

Cours

Exercices et jeux

MOOC

Outils

  • PythonTutor : pour suivre pas à pas l’exécution d’un programme (petit)