Trame du Cours

Chaque partie correspond à une demi-journée de cours, comportant chacune en moyenne 2 activités (TD/TP).

Avant-Propos

• Organisation du cours.
• Evaluation.

1. Introduction à la programmation et à l’algorithmique

• Intérêt.
• Discussion sur les algorithmes.
• Une brève histoire de l’algorithmique.
• TP : Jeu vidéo en Scratch.
• Langages de programmation.
• Définition formelle de l’algorithmique.
• Introduction au langage Python.
• Types numériques, expressions et objets en Python.
• Variables et assignation.
• TP : Utiliser Python dans Jupyter Notebook.

2. Les bases du langage Python

• Conditions.
• Chaînes de caractères et encodage de caractères.
• Entrée et sortie standard.
• TP : Environnement de Développement Intégré.
• Boucles “Tant Que”.
• Boucles “Pour” et “Bornes”.
• TP : Algorithmes mathématiques simples.
• Discussion sur les différences entre Scratch et Python.
• Retour sur le 1er TP.
• Discussion sur le style, les commentaires et PEP 8.

Travail à la maison : Retours sur Scratch et Python.

3. Programmes numériques simples et techniques de débogage

• Correction du travail à la maison.
• Introduction à la technique “devine-et-vérifie”.
• Introduction à la dichotomie.
• TD : Utilisation de la dichotomie.
• Introduction à l’instrumentation de code.
• Introduction à l’algorithme Newton Raphson.
• TP : Comparaison d’algorithmes ayant le même objectif.
• Histoire des bugs et du débogage dans la culture anglo-saxonne.
• Techniques pour déboguer manuellement un programme sur papier.
• Utilisation d’un “debugger” avec points d’arrêt.
• TP : Déboguer un programme mal écrit et comportant des bugs.

4. Procédures et fonctions

• Procédures : définition et appel.
• Arguments.
• Valeurs par défaut.
• Variables locales et globales.
• Fonctions.
• Spécifications et contrat.
• TD : Fonctions géométriques simples.
• Nombre variable d’arguments
• Retour de plusieurs résultats.
• Un mot sur la récursivité.
• Fonctions lambda.
• Fonctions d’ordre supérieur.
• Programmation impérative et programmation fonctionnelle.
• Un mot sur les méthodes avec l’exemple du type str.
• TP : Fonctions d’ordre supérieur.

Travail à la maison : Retours sur les fonctions et le débogage.

5. Structures de données fondamentales en Python

• Correction du travail à la maison.
• Notion de conteneur.
• Notion d’opérations CRUD.
• Tuples.
• Ranges.
• Lists.
• TD : Opérations matricielles classiques.
• Clonage et copie profonde.
• Sets.
• Dictionaries.
• Technique “Pythonic”: comprehensions.
• TP : Gestion d’un hôpital.
• Structure personnalisée.

6. Résolution de problèmes classiques

• Listes chaînées.
• TP : Manipulation d’une liste chaînée.
• Queue et FIFO.
• Pile et LIFO.
• Comparaison entre FIFO et LIFO.
• TP : Queues de messages simples.
• Rappels sur la théorie des ensembles.
• Rappels sur le calcul matriciel.

Travail à la maison : Ensembles et calcul matriciel.

7. Introduction à la complexité d’algorithme

• Correction du travail à la maison.
• Intuition sur la complexité avec un exemple simple.
• Réflexion sur la complexité temporelle et spatiale.
• Notation $O$.
• Classes de complexité.
• Comparaison des classes de complexité.
• TD : Evaluation de compléxité.
• Limites de l’étude de complexité.
• Approche pragmatique.
• Discussion concernant la parallélisation sur CPU et GPU.
• Discussion sur la distribution de calcul dans un cluster et sur le Cloud.
• Problèmes NP-complet.
• Discussion sur les machines quantiques.
• TP : Benchmark et complexité.

8. Tests, exceptions et assertions

• Gestion d’erreurs avec des codes de retour.
• Notion d’exception.
• Gestion d’exceptions et classes d’exception.
• Programmation offensive et défensive.
• Assertions.
• Invariants : préconditions et post-conditions.
• TP : Exceptions dans une calculatrice.
• Tests et qualité logicielle.
• Tests en boîte transparente par les développeurs.
• Automatisation des tests.
• Tests unitaires.
• Tests pilotant le développement.
• Pyramide de tests.
• TP : Ecriture de tests unitaires.

Travail à la maison : Retour sur la complexité et les tests.

9. Algorithmes de recherche et de tri

• Correction du travail à la maison.
• Algorithmiques classiques.
• Recherche en Python.
• Recherche linéaire.
• Recherche binaire.
• TP : Recherche dans une collection.
• Tri en Python.
• Algorithmes de tri en $O(N^2)$.
• Partition : diviser et conquérir.
• Tri Rapide.
• Tri Fusion.
• TP : Tri de collections.

10. Code modulaire et “Pythonic”

• Modules.
• Tour d’horizon de la librairie standard Python.
• Focus sur les fichiers.
• TP : Initiation aux fichiers.
• Introduction aux paquets et au gestionnaire de paquets pip.
• Discussion sur les licences.
• TP : Courbes avec MatPlotLib et traitement d’images avec NumPy.
• Optionnel : Discussion sur la programmation orientée object.

Travail à la maison : Analyse statistique avec Panda.

11. Introduction aux graphes

• Correction du travail à la maison.
• Discussion sur les hiérarchies.
• Arbre de recherche binaire.
• Insertion et recherche.
• Arbre de recherche N-aire.
• TP : Arbres binaires.
• Discussion concernant les graphes.
• Théorie des graphes.
• Représentations des graphes.
• Parcours en profondeur.
• Parcours en largeur.
• Identification d’un cycle.
• Graphe pondéré : représentation.
• Plus court chemin.
• Chemin critique.
• TP : Graphes.

12. Conclusion

• Retours sur les points essentiels et attendus pour l’examen.
• Conseils pour l’examen.
• Questions/réponses sur l’ensemble du cours.
• Discussion concernant le travail dans une base de code réelle.
• Discussion concernant la recherche opérationnelle et l’algorithmique plus avancée.