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éri?cation par la mesure de la complexité de plusieurs algorithmes. Simpli?cation 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, modi?cation, 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é?nition d'un graphe, nœuds, 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 œuvre 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é?nition d'un arbre
• Présentation des arbres binaires: parcours en ordre, pré?xé et post?xé
• 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