Licence de Sciences et Technologies, option Licence de Sciences et Technologies, option Informatique
Algorithmique Avancée
TD 11 : décembre 2006

  1. Ramassage
    Supposons qu'un programme exalgo (ou 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 désallouer() (ou 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.

  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 û, 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.


File translated from TEX by TTH, version 3.05.
On 15 Dec 2006, 15:47.