Algorithmes et Programmation 3 (2021−2022)

Note : Je suis chargé du groupe de TD/TP “Maths 3”.

Objectifs

• savoir lire et concevoir un algorithme ;
• savoir analyser un algorithme simple pour déterminer sa complexité dans le pire des cas et prouver sa correction ;
• savoir implémenter des algorithmes en Python.

Chapitres

• Codage et complexité. Codage des données, taille d’une donnée, notion de complexité dans le pire des cas d’un algorithme donné, utilisation de la notation $O$.
• Tris naïfs. Exemples d’algorithmes de tris non efficaces (tri à bulle, tri par insertion).
• Récursivité. Introduction des stratégies usuelles de résolution de problèmes par programmation récursive, paradigme “diviser pour régner”. Exemple du tri fusion.
• Programmation dynamique.
• Structures de données. Introduction des notions de piles et files, exemple d’implémentation en Python. Thèmes supplémentaires. Au choix parmi, par exemple :
  • structures de données plus avancées telles que les tas ;
  • algorithmes simples sur les graphes ;
  • algorithmes gloutons.

Travaux pratiques

Premier TP

Pour se connecter aux salles machines et commencer le premier TP, effectuez les étapes suivantes :

1. Si vous n’avez pas encore de compte “salle machine”, lancez l’ordinateur sous Windows puis connectez-vous avec l’identifiant me sans mot de passe pour aller sur internet. ⚠️ Vous n’aurez accès qu’aux sites web d’Université Paris Cité dans cette session invitée !
2. Activer son compte Université Paris Cité (u-paris) : https://activation.app.u-paris.fr qui vous permet de vous inscrire au cours sur Moodle : https://moodle.u-paris.fr/course/view.php?id=2424 et ainsi rendre vos TP.
3. Activer son compte machine pour les salles de la Halle aux Farines : https://comptes.script.univ-paris-diderot.fr/activation_compte/compte_up75.php ⚠️ Notez bien l’identifiant qui apparaît sur la page. C’est avec cet identifiant que vous devrez vous connectez sur les machines. Le mot de passe est celui de votre compte u-paris.
4. (Fortement recommandé) Vous pouvez ensuite redémarrer l’ordinateur sous Linux et vous connecter avec votre compte machine (et votre mot de passe u-paris). Vous devrez peut-être patienter cinq minutes entre le moment où vous activez votre compte machine pour vous connecter.
5. La première feuille de TP est disponible sur Moodle. Téléchargez-la et lisez-là, puis faites les exercices.
6. Vous avez le choix entre plusieurs possibilités pour l’environnement de développement. L’une d’entre elles – VSCode – est détaillée ci-dessous. Les autres options sont notamment Jupyter, Spyder, ou Pyzo. Sur votre machine personnelle, pensez bien à aussi installer Python. La marche à suivre dépend de votre système d’exploitation et est détaillée sur cette page : https://docs.python.org/fr/3/using/index.html (sur Windows, choisissez de préférence l’option “Installateur complet”).
7. Quand vous avez terminé, rendez-vous sur la page Moodle du cours, puis envoyez votre fichier Python (soit .py, soit .ipynb) sur le module “Rendu TP” approprié selon votre groupe et la date.
8. La correction des TP sera disponible sur Moodle sous la forme d’un carnet Jupyter. Pour installer Jupyter sur votre machine, après avoir installé Python, lancez pip install --user jupyterlab dans un terminal, puis jupyter-lab (cf. la documentation).

Visual Studio Code (optionnel)

Visual Studio Code est un Environnement de Développement Intégré (IDE en anglais) moderne. Bien que vous puissiez utiliser l’éditeur de code ou l’environnement de développement de votre choix, Visual Studio Code est riche en fonctionnalité et simple d’usage. C’est cet éditeur que j’utilise en TP quand je projette mon écran d’ordinateur au tableau.

Installation

Pour l’installer, vous avez plusieurs possibilités. Connectez-vous à l’adresse suivante : https://code.visualstudio.com/Download puis :

• Si vous êtes connecté sur l’une des machines Linux de l’université, installez VSCode en mode portable. Choisissez l’option Linux (le pingouin) sur la page de téléchargement, sur la ligne .tar.gz, le bouton 64 bit. Une fois l’archive téléchargée, extrayez-la quelque part dans votre dossier utilisateur, puis créez un dossier nommé data dans le dossier que vous venez de créer. Vous obtiendrez une structure de dossier qui ressemble à ça :

  VSCode-linux-x64/
  ├── ...
  ├── code
  ├── data/
  ├── ...
  

  Vous n’avez besoin d’effectuer cette opération qu’une seule fois. Une fois tout ceci effectué, lancez tout simplement l’exécutable nommé code pour démarrer le logiciel.

• Si vous avez votre propre ordinateur, téléchargez simplement l’installateur et installez le logiciel comme n’importe quel autre.

Utilisation

Comme expliqué dans la feuille de TP, il y a plusieurs possibilités pour programmer en Python :

• Écrire directement le code dans l’interpréteur (non recommandé sauf pour de rapides tests).
• Créer un fichier avec l’extension .py, écrire son code Python dedans, le sauvegarder, puis lancer l’interpréteur Python sur ce fichier. Dans VSCode, cela s’effectue tout simplement en cliquant sur l’icône en forme de triangle dans la barre d’outils en haut à droite.
• Créer un carnet (notebook) Jupyter avec l’extension .ipynb. Cette option permet de découper son code en cellules qui peuvent s’exécuter indépendamment. C’est ce que j’utilise pour les corrections de TP, mais cela demande un peu plus d’entraînement pour bien comprendre. Pour plus d’informations, vous pouvez lire la documentation de VSCode (en anglais). Vous pouvez également lire ce carnet Jupyter d’exemple que j’ai créé.

Voici une illustration de l’exécution de code ligne à ligne dans VSCode. :