TD 05 - Parcours de tableau 2

1 Comptages

1.1 Exercice 1

On considère un tableau \(T\) de \(n\) entiers et un entier \(k \geq 1\).

On souhaite déterminer combien d’éléments distincts du tableau apparaissent strictement plus de \(k\) fois dans ce tableau.

  1. Écrire un algorithme en pseudo-code qui résout ce problème en utilisant deux boucles imbriquées.
  2. Donner la complexité de l’algorithme proposé.
  3. 🏠 À faire à la maison : Si les nombres du tableau sont tous compris entre 1 et \(N\), proposer une adaptation utilisant une liste dont les indices sont les éléments concernés. Puis donner la complexité de votre algorithme.

1.2 Exercice 2 🏠

On considère un tableau \(T\) de \(n\) entiers (éventuellement avec des répétitions).

  1. Écrire un algorithme qui construit un nouveau tableau \(S\) contenant, dans l’ordre d’apparition, tous les éléments distincts de \(T\) (chaque valeur de \(T\) n’apparaît ainsi qu’une seule fois dans \(S\)).

    On pourra se servir de l’instruction Taille(M) qui renvoie le nombre d’éléments du tableau M.

  2. Tester votre algorithme sur l’exemple suivant : \(T = [2, 7, 5, 2, 7, 8, 5, 9]\)

    Quel tableau \(S\) obtient-on en sortie ?

  3. Que se passe-t-il si tous les éléments de \(T\) sont distincts ? Si tous les éléments de \(T\) sont identiques ?

  4. Donner la complexité de votre algorithme.

2 Filtrage

2.1 Exercice 3

Écrire un algorithme qui renvoie VRAI si la somme des nombres pairs d’un tableau de \(n\) entiers est supérieure à la somme de ses nombres impairs.

3 Parcours double 1

3.1 Exercice 4

Écrire un algorithme traitant 2 chaînes de caractères et qui retourne VRAI si la première chaîne est un préfixe de la seconde et FAUX sinon.

Par exemple, 'algo' est un préfixe de 'algorithme' par contre 'ramer' n’est pas un préfixe de 'rame'.

Faire une analyse en pire et en meilleur cas. Quelle est la complexité générale de l’algorithme ?

3.2 Exercice 5 🏠

Écrire un algorithme traitant 2 chaînes de caractères et qui retourne VRAI si la première chaîne est un suffixe de la seconde et FAUX sinon.

Par exemple, 'rithme' est un suffixe de 'algorithme' par contre 'rme' n’est pas un suffixe de 'rame'.

Faire une analyse en pire et en meilleur cas. Quelle est la complexité générale de l’algorithme ?

3.3 Exercice 6 🏠

Écrire un algorithme qui prend en entrée deux chaînes de caractères, \(C_1\) (le motif recherché) et \(C_2\) (la chaîne principale), et qui retourne VRAI si \(C_1\) apparaît quelque part dans \(C_2\) et FAUX sinon.

Par exemple, 'gori' apparaît dans 'algorithme' alors que 'rme' n’apparaît pas dans 'algorithme'.

Faire une analyse en pire et en meilleur cas. Quelle est la complexité générale de l’algorithme proposé ?

4 Parcours double 2

4.1 Exercice 7

On représente un entier positif en base 2 par un tableau de 0 et de 1. Pour se simplifier l’écriture des algorithmes on décide de placer le chiffre des unités à la première case du tableau.

Adapter l’algorithme de multiplication classique à deux entiers binaires de \(n\) bits.

4.2 Exercice 8 🏠

On représente un entier positif par un tableau de nombres compris entre 0 et 9. Pour se simplifier l’écriture des algorithmes on décide de placer le chiffre des unités à la première case du tableau, suivi de celui des dizaines etc.

Par exemple, le nombre 31415 sera représenté par le tableau [5,1,4,1,3].

  1. Soit \(A = \displaystyle\sum_{i=1}^n a_i10^{i-1}=a_1+a_210+a_310^2+\dots+a_n10^{n-1}\) un nombre entier. Montrer que [A^2 = {i=1}^n a_i210{2(i-1)} + 2{i=1}^n_{j=i+1}^n a_ia_j10^{i+j-2}.]

  2. En déduire un algorithme de calcul du carré d’un nombre dont la complexité est à peu près moitié moindre que celle de l’algorithme de multiplication.

4.3 Exercice 9 🏠

On considère un tableau \(T\) de \(n\) entiers et un entier \(k\) tel que \(1 \leq k \leq n\).

  1. Écrire un algorithme qui calcule la somme des minima des sous-tableaux consécutifs de longueur \(k\) de \(T\).

    Autrement dit, pour chaque \(i\) allant de \(1\) à \(n - k + 1\), on considère le sous-tableau \(T[i], T[i+1], \ldots, T[i+k-1]\), on identifie son minimum, et l’on additionne tous ces minima.

  2. Tester votre algorithme sur l’exemple suivant pour \(k=3\) : \(T = [4, 2, 8, 7, 3, 9, 1, 5]\)

  3. Quelle est la complexité de l’algorithme ?

Pour \(T = [4, 2, 8, 7, 3, 9, 1, 5]\) et \(k=3\) :

  • Sous-tableau \([4,2,8]\) : min = 2
  • Sous-tableau \([2,8,7]\) : min = 2
  • Sous-tableau \([8,7,3]\) : min = 3
  • Sous-tableau \([7,3,9]\) : min = 3
  • Sous-tableau \([3,9,1]\) : min = 1
  • Sous-tableau \([9,1,5]\) : min = 1

Somme totale = 2 + 2 + 3 + 3 + 1 + 1 = 12