Python - algorithmique

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