Python - algorithmique

Objectifs

Développer une expertise avancée en algorithmique avec Python en maîtrisant la complexité des algorithmes, les structures de données adaptées, la récursivité, les graphes et les arbres, afin d'optimiser les performances des programmes et de résoudre efficacement des problèmes complexes

Programme de la formation

- Complexité des algorithmes : 0,5 jour
Comprendre la notation BigO
Mesurer la complexité d'un algorithme
Premières techniques pour diminuer la complexité d'un algorithme
Travaux pratiques :
Calcul et vérification par la mesure de la complexité de plusieurs algorithmes. Simplification d'un algorithme de complexité quadratique pour le rendre linéaire.
- Rappels et manipulation de base des structures de données: 0,5 jour
Tableaux indicés
Tableaux associatifs/dictionnaires
Files et piles
Skip list
Listes chaînées
Arbres et graphes
Travaux pratiques :
Création, modification, recherche, insertion, suppression d'éléments avec chaque structure et mesure de leurs complexités respectives.
- Récursivité: 0,5 jour
Prise en mains et cas d'utilisations: suites numériques, analyseurs syntaxiques, parcours d'arbres, ...
Bien comprendre la récursivité
Mise en oeuvre top down et bottom up
Limites
Travaux pratiques :
Implémentation et explication de nombreux cas pratiques: suite numérique, tour de Hanoï, création d'un analyseur syntaxique, trouver toutes les solutions du jeu le compte est bon
- Les graphes: 1,5 jour
Définition d'un graphe, noeuds, arrêtes, directionnels, ...
Pourquoi utiliser un graphe
Exemples d'algorithmes : recherche de relations, du plus court/long chemin, problème du voyageur de commerce, ...
Matrice d'adjacence
Visualiser un graphe
Parcourir un graphe
Recherche dans un graphe
Graphes pondérés
Présentation et mise en oeuvre d'algorithmes: Djikstra, chemins hamiltoniens, 2-opt, ...
Travaux pratiques:
Implémentation de la recherche du plus court chemin (et son tracé) dans un graphe de dimension réelle de toutes les rues de Paris. Recherche et parcours d'informations.
- Les arbres: 1 jour
Définition d'un arbre
Présentation des arbres binaires: parcours en ordre, préfixé et postfixé
Recherche dans un arbre binaire
Insertion et suppression
Utilisation d'arbres Trie/m-aire
Travaux pratiques :
Création, manipulation et recherche dans des arbres.
- Application à des problèmes réels : 1 jour
Mise en oeuvre de différents algorithmes de tri et de recherche
Création d'un analyseur syntaxique et d'un interpréteur
Résolution d'anagrammes
Jeu du labyrinthe : génération et résolution
Travaux pratiques :
De nombreux autres exercices et jeux : astéroïdes, somme maximale dans une pyramide, recherche d'un point d'équilibre, programmation sans branche, somme de pièces, mémoïsation, la mine d'or,...

Validation et sanction

Attestation de formation

Type de formation

Non certifiante

Sortie

Sans niveau spécifique