TD 15-16 - Annales d’examens

1 Examen 2023

1.1 Questions de cours (4 points)

  1. Qu’est-ce qu’une instance d’un problème algorithmique ?

  2. Pour chacune des complexités suivantes donner un exemple d’algorithme vu en cours : \(O(n)\), \(O(\log n)\), \(O(n^2)\), \(\Theta(n^2)\).

  3. Quelle est la complexité d’un tri comparatif optimal ?

  4. Pour rechercher un élément donné dans un tableau, est-il plus efficace de trier le tableau puis de faire une recherche par dichotomie ou d’effectuer directement une recherche séquentielle ? Justifier.

  5. Calculer \(1 + 2 + 3 + \cdots + 2000\) (on détaillera le calcul).

  1. Instance : Un cas particulier d’un problème avec des données concrètes. Exemple : pour le tri, une instance est un tableau spécifique comme [5, 2, 8, 1].

  2. Exemples :

    • \(O(n)\) : recherche séquentielle, parcours de tableau
    • \(O(\log n)\) : recherche dichotomique
    • \(O(n^2)\) : tri à bulles, tri sélection
    • \(\Theta(n^2)\) : tri sélection (tous les cas)

  3. Tri comparatif optimal : \(O(n \log n)\) (exemple : tri fusion, tri rapide en moyenne)

  4. Comparaison :

    • Tri + dichotomie : \(O(n \log n) + O(\log n) = O(n \log n)\)
    • Recherche séquentielle : \(O(n)\)
    • Conclusion : recherche séquentielle plus efficace pour une seule recherche

  5. Calcul : [1 + 2 + + 2000 = = 1000 = 2,001,000]

1.2 Inversion dans un tableau (2 points)

Soit \(T\) un tableau d’entiers tous distincts de taille \(n\).

Soient deux entiers \(1 \leq i < j \leq n\), on dit que la paire d’indices \((i, j)\) est en inversion pour \(T\) si \(T[i] > T[j]\).

  1. Écrire un algorithme NbInversion(T) qui renvoie le nombre de paires d’indices en inversion pour \(T\).
NoteExemples
  • Tableau \([1, 2, 3, 4]\) : 0 inversion (trié)
  • Tableau \([4, 3, 2, 1]\) : 6 inversions (toutes les paires)
  • Tableau \([2, 1, 3]\) : 1 inversion (indices 1 et 2)

1.3 Vecteurs de dimension n (8 points)

Dans la suite de l’exercice, un vecteur de dimension \(n\) \(\vec{u} = (u_1, u_2, \ldots, u_n)\) est représenté par un tableau de flottants \(U\) de taille \(n\).

Étant donné deux vecteurs \(\vec{u}\) et \(\vec{v}\), on appelle produit scalaire (noté \(\langle \vec{u}, \vec{v} \rangle\)) la quantité

[, = u_1 v_1 + u_2 v_2 + + u_n v_n.]

On définit la norme d’un vecteur \(\vec{u}\) par \(\|\vec{u}\| = \sqrt{\langle \vec{u}, \vec{u} \rangle}\) et on dit que deux vecteurs sont orthogonaux si leur produit scalaire vaut 0.

  1. Écrire un algorithme ProdScal(U,V) qui renvoie le produit scalaire de \(U\) et \(V\).

  2. En déduire deux algorithmes Norme(U) et Orthogonaux(U,V) qui renvoient respectivement la norme de \(U\) et VRAI ou FAUX selon que \(U\) et \(V\) sont orthogonaux ou pas.

  3. On considère maintenant un tableau de \(m\) vecteurs de dimension \(n\) ainsi qu’un vecteur \(X\) de dimension \(n\). Écrire un algorithme RangeOrtho(T,X,i,j) qui range les vecteurs du sous-tableau \(T[i:j]\) orthogonaux avec \(X\) au début du sous-tableau (à partir de l’indice \(i\)). On ne pourra parcourir le sous-tableau qu’une seule fois.

  4. En déduire un algorithme RangeVecteurs(T,X) qui range les vecteurs en fonction de leur norme puis de leur orthogonalité avec \(X\). Les vecteurs de norme strictement inférieure à 1 au début, ceux de norme 1 au milieu et les autres à la fin. Dans chaque cas les vecteurs orthogonaux avec \(X\) seront avant les autres. On ne pourra parcourir le tableau que deux fois.

  5. On considère que le tableau \(T\) a été rangé à l’aide de l’algorithme précédent. Écrire un algorithme NBOrthoNorme1(T,X) de complexité \(O(\log m)\) qui renvoie le nombre de vecteurs orthogonaux à \(X\) de norme 1.

AstuceIndices
  • Question 3 : Algorithme de partition (comme quicksort)
  • Question 4 : D’abord ranger par norme (3 catégories), puis dans chaque catégorie appliquer RangeOrtho
  • Question 5 : Recherche dichotomique du début et de la fin de la zone de norme 1 orthogonaux

1.4 Tri et Piles (6 points)

On considère dans la suite des piles contenant des nombres entiers. On rappelle les procédures standards de manipulation des piles : Vide(P), Lire(P), Empiler(P,x), Depiler(P).

  1. On considère une pile \(P\) triée dans l’ordre croissant (le plus grand élément au sommet). Écrire un algorithme InserePile(P,x) qui insère l’entier \(x\) à sa place dans la pile. L’algorithme ne pourra utiliser qu’une seule autre pile en variable auxiliaire.

  2. En déduire un algorithme TriPile(P1,P2), basé sur l’algorithme du tri insertion, qui range les éléments de la pile \(P1\) dans la pile \(P2\) dans l’ordre croissant. On peut faire appel à la fonction InserePile.

  3. En vous inspirant de l’algorithme précédent, écrire un algorithme TriPile2(P1,P2), qui range les éléments de la pile \(P1\) dans la pile \(P2\) dans l’ordre croissant, sans utiliser de pile auxiliaire ni la fonction InserePile.

2 Examen 2024

2.1 Questions de cours (6 points)

  1. Qu’est-ce que la complexité en pire cas ? Donner un exemple à l’aide d’un algorithme du cours.

  2. La complexité d’un tri comparatif optimal est en \(O(n\log n)\). Comment expliquer que le tri comptage vu en cours est de complexité \(\Theta(n)\) ?

  3. Un algorithme de complexité \(\Theta(n\sqrt{n})\) met 1 000 secondes pour traiter une instance de taille 1 000. Combien de temps lui faudra-t-il pour une instance de taille 100 000 ? Même question pour \(\Theta((\log_{10} n)^2)\).

  4. Calculer \(4 + 8 + 12 + 16 +\cdots +1996 +2000\) (on détaillera le calcul).

  5. Monsieur M. veut rendre les copies d’examen à ses étudiants après un contrôle en les mettant en ligne par ordre alphabétique. Il distribue les copies au hasard, et les étudiants ne peuvent échanger leurs copies et communiquer qu’avec leurs voisins directs. Proposez un algorithme pour que chaque étudiant obtienne sa propre copie sans se déplacer. Quelle est sa complexité (justifier brièvement) ?

  1. Complexité en pire cas : Le temps d’exécution maximal sur toutes les instances de taille \(n\). Exemple : recherche séquentielle en \(O(n)\) quand l’élément est absent ou en dernière position.

  2. Tri comptage : C’est un tri non comparatif. Il compte les occurrences (possible car valeurs bornées). La borne \(\Omega(n \log n)\) ne s’applique qu’aux tris comparatifs.

  3. Calcul de temps :

    • Pour \(\Theta(n\sqrt{n})\) : \(\frac{100000\sqrt{100000}}{1000\sqrt{1000}} = \frac{100000 \times 316.2}{1000 \times 31.62} \approx 1000\) secondes
    • Pour \(\Theta((\log_{10} n)^2)\) : \(\frac{(\log_{10} 100000)^2}{(\log_{10} 1000)^2} = \frac{5^2}{3^2} = \frac{25}{9} \approx 2.78\) fois plus, soit environ 2780 secondes

  4. Calcul : [4 + 8 + + 2000 = 4(1 + 2 + + 500) = 4 = 2 = 501,000]

  5. Algorithme : Tri à bulles (chaque étudiant échange avec son voisin si nécessaire). Complexité : \(O(n^2)\) dans le pire cas.

2.2 Matrice circulante (3 points)

On rappelle qu’une matrice \(M\) est un tableau de tableaux. L’élément \(M[i][j]\) est sur la ligne d’indice \(i\) et la colonne \(j\). On appelle permutation circulaire (à droite) d’un tableau, le décalage de chaque valeur du tableau d’un indice sur la droite, avec retour de la dernière valeur à l’indice 1.

  1. Écrire un algorithme EstPermutation(T1,T2) qui retourne VRAI si le tableau \(T2\) est la permutation circulaire de \(T1\), FAUX sinon.

  2. On dit qu’une matrice carrée est circulante si chaque ligne est une permutation circulaire de la ligne du dessus. Écrire un algorithme EstCirculante(M) qui retourne VRAI si la matrice \(n\times n\) est circulante, FAUX sinon (l’algorithme doit s’arrêter dès que possible).

  3. Donner la complexité de l’algorithme précédent en justifiant brièvement.

NoteExemple de matrice circulante

\[\begin{pmatrix} 1 & 2 & 3 & 4 \\ 4 & 1 & 2 & 3 \\ 3 & 4 & 1 & 2 \\ 2 & 3 & 4 & 1 \end{pmatrix}\]

Chaque ligne est obtenue en décalant la précédente d’une position à droite.

2.3 Rangement de points (6 points)

Dans la suite de l’exercice un point \(P = (x, y)\) du plan est représenté par un tableau de dimension 2 \(P = [x, y]\).

  1. Écrire un algorithme RangePointsX(T,P) de complexité \(\Theta(n)\) qui range les points de \(T\) dont la coordonnée \(x\) est inférieure à celle de \(P\) en début de tableau et les autres à la fin. L’algorithme renverra le plus petit indice d’un point dont la coordonnée \(x\) est supérieure à celle de \(P\) après rangement.

  2. Soit \(Q=(x',y')\), on lui associe une zone du plan en fonction de sa position par rapport à \(P = (x, y)\) :

    • si \(x' < x\) et \(y' < y\) : Zone 1 (Sud-Ouest)
    • si \(x' \geq x\) et \(y' < y\) : Zone 2 (Sud-Est)
    • si \(x' < x\) et \(y' \geq y\) : Zone 3 (Nord-Ouest)
    • si \(x' \geq x\) et \(y' \geq y\) : Zone 4 (Nord-Est)

    Proposer un algorithme qui range les points selon leur zone (Zone 1, puis 2, puis 3, puis 4).

AstuceIndice

Utiliser l’algorithme de rangement (partition) similaire au drapeau hollandais, mais avec 4 catégories au lieu de 3.

2.4 Conseils de révision

ImportantPoints clés à maîtriser
  1. Complexité : Savoir calculer et comparer les complexités
  2. Tris : Connaître les algorithmes classiques et leurs complexités
  3. Recherche : Séquentielle vs dichotomique
  4. Structures de données : Piles, files, matrices
  5. Algorithmes de rangement : Partition, drapeau hollandais
  6. Calculs mathématiques : Sommes arithmétiques, manipulations algébriques
NoteMéthodologie
  • Lire attentivement l’énoncé
  • Identifier les contraintes (complexité, nombre de parcours, etc.)
  • Proposer d’abord un algorithme simple, puis optimiser
  • Vérifier sur des exemples simples
  • Analyser la complexité systématiquement