2023—2024
For the lesson lies in learning
And by teaching I'll be taught
Les versions imprimables consistent en les mêmes transparents, à peu de choses près, que ceux montrés aux cours; la différence principale est que les slides correspondant à plusieurs transparents (sur lesquels on rajoute du texte au fur et à mesure) sont comprimés en un seul transparent.
Certaines feuilles d'exercices existent en version "indices", où des indications ont été rajoutées pour les exercices plus difficiles. N'hésitez pas à les consulter si vous ne vous en sortez pas.
- BUT 1: Initiation au développement
- BUT 3: Qualité algorithmique
- L3: Algorithmique des graphes
- SHNU: Administration d'un système GNU / Linux
Partie programmation
Les transparents ci-dessous concernent la partie programmation (merci à Cyril Nicaud pour la première version de ces transparents).Partie algorithmique
Voici les notes de cours (partie algorithmique) (version du 11/10/2023).Les sujets de TD d'algorithmique:
- Complexité. (indices) (version du 02/10/2023)
- Listes. (indices) (version du 12/10/2023)
- Matrices et chaînes. (indices) (version du 19/10/2023)
- Compromis performances / mémoire (indices) (version du 30/11/2023)
- Récursivité: les bases (version du 30/11/2023)
- Récursivité sur des itérables (version du 21/12/2023)
- installer le module matplotlib, puis vérifier l'installation en exécutant test_matplotlib.py. Si tout s'est bien passé, le programme doit vous montrer un graphique avec les courbes de plusieurs fonctions, et sauvera le résultat dans l'image test.png dans votre répertoire courant.
Pour installer matplotlib:
-
sous les systèmes GNU/Linux dérivés de Debian (Ubuntu, etc.): ouvrez un terminal et tapez
sudo apt-get install python3-matplotlib
ousudo aptitude install python3-matplotlib
- sous Windows: ouvrez un terminal en exécutant la commande cmd, puis tapez les deux commandes suivantes (remplacez python par python3 si nécessaire):
python -m pip install -U pip setuptools python -m pip install matplotlib
- sous Mac: suivre les instructions habituelles pour l'installation des programmes sous Mac.
-
sous les systèmes GNU/Linux dérivés de Debian (Ubuntu, etc.): ouvrez un terminal et tapez
- lisez ce document, qui résume ce que nous devrons connaître des fonctions pour ce TP; elles seront couvertes plus en détails lors du prochain cours de programmation.
Liens utiles
- Télécharger Python: ici (prenez la version 3).
- La documentation de Python 3.
- PythonTutor; n'oubliez pas de préciser la version de Python à utiliser pour exécuter votre code.
- Structure d'un programme Python: modele.py
- "Apprendre à programmer avec Python 3", un livre de référence écrit par Gérard Swinnen disponible gratuitement en PDF.
- Apprendre Python et d'autres langages en s'amusant: CodinGame
- Apprendre Python en s'amusant (niveau avancé): The Python Challenge
- Un programme pour tester votre installation matplotlib: test-matplotlib.py (utilisation: python3 test-matplotlib.py)
- Un programme pour vous aider à comprendre la récursivité : decorecursivite.py (lisez son contenu pour savoir comment le réutiliser pour les fonctions récursives que vous écrirez)
Matériel de cours
Cours | TP |
---|---|
|
|
Quelques références
- High Performance Python: Practical Performant Programming for Humans, de Micha Gorelick et Ian Ozsvald
Notes de cours
- Chapitre 0: Rappels de complexité et programmation orientée objet en Python (version du 20/01/2022)
- Chapitre 1: Notions de base (version du 20/01/2022)
- Chapitre 2: Parcours et applications (version du 20/01/2022)
- Chapitre 3: Graphes pondérés (version du 26/01/2022)
- Chapitre 4: Graphes orientés (version du 06/05/2020)
- Chapitre 5: Plus courts chemins (2) (version du 10/03/2021)
- Chapitre 6: Flots (version du 28/03/2022)
- Chapitre 7: Techniques algorithmiques (version du 25/04/2022)
Algorithmes vus au cours
- Parcours de graphes non orientés et applications
- Arbres couvrants, Dijkstra
- Algorithmes sur les graphes orientés
- Algorithmes pour le calcul de plus courts chemins (2)
- Algorithmes pour le calcul de flots
- Techniques algorithmiques
- Branch and bound
Feuilles de TD
- Rappels d'algorithmique et notions basiques sur les graphes. (version du 20/01/2022)
- Parcours de graphes et applications. (version du 31/01/2022)
- Arbres couvrants de poids minimum. (version du 07/02/2022)
- Plus courts chemins. (version du 08/03/2022)
- Graphes orientés. (version du 08/03/2022)
- Graphes orientés et plus courts chemins. (version du 21/03/2022)
- Flots. (version du 28/03/2022)
- Algorithmes gloutons. (version du 12/04/2022)
- Programmation dynamique. (version du 25/04/2022)
Liens utiles
- Le site de Graphviz et la documentation du langage dot, comprenant la description des options des divers programmes de dessin.
Les notes de cours sont disponibles ici (version du 07/11/2022), en complément des slides ci-dessous.
Slides
- Les bases (imprimable) (version du 31/10/2023)
- Entrées, sorties et pipes (imprimable) (version du 06/11/2023)
- Scripts bash (imprimable) (version du 27/10/2022)
- Outils plus avancés (imprimable) (version du 10/11/2022)
Feuilles de TP
- Les bases d'un système GNU / Linux (version du 31/10/2023)
- Pipes et grep (version du 01/11/2023)
- Premiers scripts bash (version du 07/11/2023)
- Un peu de lecture (version du 08/11/2023)
- Un peu de lecture (2) (version du 29/11/2022)
Vidéos
- Installer Ubuntu sur VirtualBox; téléchargez la dernière version d'Ubuntu et installez VirtualBox
Liens utiles
- Advanced Bash-Scripting Guide: une ressource très complète sur l'écriture de scripts bash.
- RegExr: pour se former aux expressions régulières.