Licence Info
Algorithmique Avancée
TD 12 : 4-5/5/04

  1. Ramassage
    Supposons qu'un programme C utilise des structures composées de noeuds où chaque noeud contient deux pointeurs Gauche et Droite. (Les structures ne sont pas forcément des arbres; elles peuvent avoir des sous-structures partagées et/ou des cycles.)
    Ecrire une fonction avec un paramètre de type pointeur vers un noeud qui parcourt toute la structure accessible à partir de ce noeud et applique free() à chaque noeud une seule fois. Il est interdit d'examiner un noeud déjà libéré.
    Vous pourriez construire une liste de pointeurs qui contient exactement un pointeur vers chaque noeud de la structure de départ. Si vous faites ça, il faudra bien sûr libérer aussi les noeuds utilisés pour votre liste.  corrigé

  2. Analyse
    On veut trier un tableau T qui contient n entiers de l'intervalle [1..m2] où m n'est pas très grand; on peut utiliser des tableaux de taille m.

    1. Donner un algorithme qui trie le tableau selon les valeurs de T[i]/m (arrondies vers le bas), en temps linéaire (O(n+m));

    2. Donner un algorithme qui trie le tableau selon les valeurs de T[i] mod m, en temps linéaire (O(n+m));

    3. En utilisant les deux algorithmes précédents donner un algorithme qui trie le tableau en temps linéaire;

    4. Comparer cet algorithme avec un algorithme qui trie le tableau en utilisant O(nlogn) comparaisons;

    5. Généraliser l'algorithme et l'analyse au tri de tableaux d'entiers positifs où le majorant est supérieur à m2.
corrigé

File translated from TEX by TTH, version 3.05.
On 3 May 2004, 15:50.