Rappels des actions élémentaires, variables et types élémentaires
- Actions élémentaires, variables, types élémentaires.
- Boucles, procédures et fonctions.
- L’héritage et les exceptions. Comment la POO simplifie l’écriture et la lecture des programmes/algorithmes.
- La récursivité.
Travaux pratiques
Conception d’algorithmes avec des boucles imbriquées. Décomposition de programmes en procédures et fonctions. Conception d’algorithmes récursifs.
Algorithmes sur les tableaux
- Conventions syntaxiques.
- Parcours d’un tableau de dimension 1. Calcul de somme, de moyenne.
- Recherche d’une valeur dans un tableau de dimension 1. Valeur maximale, valeur minimale.
- Parcours d’un tableau de dimension 2.
- Recherche d’une valeur dans un tableau de dimension 2.
Travaux pratiques
Calcul de la transposée d’une matrice nxn.
Algorithmes de tri
- Le tri à bulle.
- Le tri par sélection.
- Le tri par insertion.
- Le heap sort (tri par tas).
- Le tri par fusion.
- Le quicksort.
Travaux pratiques
Comparaison du nombre maximum de swaps entre deux algorithmes.
Les principales structures de données
- Les files d’attente ; structure FIFO.
- Exemple d’algorithme utilisant une structure FIFO.
- Les piles ; structure LIFO.
- Exemple d’algorithme utilisant une structure de pile.
Algorithmes sur les graphes
- Représentation des graphes.
- Parcours de graphe en largeur.
- Recherche d’un arbre minimal de recouvrement du graphe.
- Algorithme de recherche des plus courts chemins entre toutes les paires de points.
Travaux pratiques
Écriture d’un algorithme de recherche du minimum spanning tree.
Algorithmes de parcours d'arbres
- Représentation des graphes.
- Parcours en largeur d’abord. Calcul d’une somme.
- Parcours en profondeur d’abord.
- Abandon de l’exploration d’une branche (notion de back-track).
Travaux pratiques
Écriture d’un algorithme nécessitant l’exploration en profondeur d’un arbre d’abord.
4j
- 28h00 
