jeudi 25 septembre 2014

Mise à niveau informatique : cours 4

Après les listes chaînées, les arbres...

Préambules : complexité & récursivité

Complexité

Nous allons d'abord voir un concept très important : la notion de complexité algorithmique.
Cela est expliqué dans le support de cours de 2A, pages 25 à 31.

Après avoir constaté l'intérêt des listes, on va aussi constater certaines de leur faiblesses, en particulier la complexité algorithmique d'accès aux éléments...

Récursivité

Il nous faudra aussi comprendre le principe de la programmation récursive car les structures de données d'arbres y font constamment référence. Cela est expliqué dans le support de cours de 2A, pages 32 à 33.

Les Arbres

Nous allons voir un type d'arbre (il y en a des tas d'autres) qui permet de contourner le problème de complexité d'accès au élément d'un liste tout en ayant les même propriété de souplesse.
Il s'agit des Arbre Binaire de Recherche (ou ABR) cela est expliqué dans le support de cours de 2A, pages 45 à 49.

Comme pour les listes, pour des raison de manque de temps, nous allons faire le strict minimum :
  • Définir un type permettant de stocker un noeud d'arbre binaire de recherche
  • Écrire la fonction d'insertion (en suivant la logique ABR), et l'utiliser dans le main.
  • Écrire la fonction de recherche d'un élément. La tester en l'appelant dans le main.
  • Écrire la fonction qui permet d'afficher tous les éléments de l'ABR. Réflechissez aux 3 versions différentes de parcours qu'on peut écrire, testez les pour voir leur différence.
  • Écrire la fonction de désallocation. Pour cela identifiez qu'un des ordres de parcours vu à la question précédente offre précisément l'ordre idéal. Rappel : dans les structures chaînées il faut absolument éviter de supprimer un élément dont on a besoin pour supprimer les éléments suivants.

Travail personnel

Il me parait peu vraisemblable qu'on arrive à faire tout cela en une séance. Vous finirez donc chez vous, je répondrai à vos questions la semaine suivante.