Algorithmie : Maîtrisez la Logique pour Optimiser vos Codes

Le contenu de la formation - Tous les programmes sont sur mesure et à adapter selon vos besoins

Rappels

• Rappel sur les différentes structures de données
  • Les files et les piles (FIFO/LIFO)
  • Les listes linéaires chaînées
  • Les arbres et graphes
  • Les tableaux indicés
  • Les tableaux associatifs
• Calculer la complexité d’un algorithme
  • Qu’est-ce que la complexité d’un algorithme ?
  • Complexité temporelle et spatiale
  • Notations
  • Exemples de calculs de complexité

La récursivité

• Comprendre le concept des fonctions récursives
  • Qu’est-ce qu’une fonction récursive
  • Premier exemple : compte à rebours
  • Avantages et inconvénients des fonctions récursives
  • Exemples d’applications : les suites numériques incontournables (factorielle et Fibonacci), le parcours d’arbres, les analyseurs syntaxiques, la recherche de solutions, les fractales
  • Mesurer le coût d’une fonction récursive
  • Utiliser le cache pour diminuer la récursivité et améliorer les performances
• Mise en pratique
  • La tour de Hanoi
  • Créer un analyseur syntaxique
  • Dessiner une fractale
  • Calculer une suite numérique
  • Résoudre le problème du jeu «le compte est bon»
  • Parcours d’arbre
  • Parcourir un labyrinthe

Tris et recherche

• Algorithmes de tris et de recherche
  • Recherche séquentielle
  • Recherche binaire
  • Recherches avec une table de hachage
  • Les principaux algorithmes de tris : Tri à bulles, tri sélectif, tri par insertion, tri de shell, tri par fusion, tri rapide (quick sort)…
  • Etude de la complexité en temps et mémoire des différentes solutions
• Mise en pratique
  • Recherche de valeurs dans une liste
  • Recherche de valeurs dans une liste triée
  • Intersection de listes avec les tables de hachage
  • Implémentation et mesure des différents algorithmes de tris

Les arbres

• Les arbres
  • Qu’est-ce qu’un arbre ?
  • Terminologie associée aux arbres
  • Les arbres binaires
  • Comment représenter un arbre ?
  • Comment parcourir un arbre ? Parcours infixé, préfixé, postfixé
  • Recherche dans un arbre
• Exercices pratiques
  • Parcours en largeur et profondeur d’un arbre généalogique
  • Créer un arbre de décision
  • Implémenter une recherche binaire
  • Insertion et suppression d’éléments dans un arbre
  • Réaliser un interpréteur

Les graphes

• Les graphes
  • Qu’est-ce qu’un graphe ?
  • Terminologie associée aux graphes
  • Comment représenter un graphe ?
  • Recherche dans un graphe
  • Parcours de graphes
  • Modifier un graphe
  • Principaux problèmes traités avec les graphes : existe-t-il un chemin, plus court/long chemin, l’algorithme du voyageur de commerce, coloration d’un graphe...
• Exercices pratiques
  • Recherche du plus court chemin avec l’algorithme de Dijkstra
  • Algorithme du voyageur de commerce
  • Parcours en largeur et profondeur (BFS/DFS)
  • Jeux algorithmiques utilisant des graphes (NIM, Col, Gendarme et voleur...)