EXERCICE 1 : nbPlusPetit = nbPlusPetit + milieu - 1

Fonction trouverMedian(base1, base2, n) sinon

// base1 et base2 sont les bases de données pour i allant de 1 a milieu -1 faire
// n est le nombre d'éléments dans chaque base si [Link](i) <= medianBase1 alors
nbPlusPetit = nbPlusPetit + 1
debut = 1 fin si
fin = n fin pour
fin si
tant que debut <= fin faire
milieu = (debut + fin) / 2 // Division entière
pour i allant de 1 a milieu faire
// Obtenir les éléments de base1 et base2 au milieu si [Link](i) <= medianBase2 alors
medianBase1 = [Link](milieu) nbPlusPetit = nbPlusPetit + 1
medianBase2 = [Link](milieu) fin si
fin pour
// Obtenir les éléments de base1 au milieu-1 et milieu+1 (si
possible) si nbPlusPetit = n alors
si milieu > 1 alors retourner medianBase2
medianBase1_moins1 = [Link](milieu -1) sinon si nbPlusPetit > n alors
sinon debut = milieu + 1
medianBase1_moins1 = -INFINI sinon
fin si fin = milieu -1
fin si
si milieu < n alors fin si
medianBase1_plus1 = [Link](milieu+1) fin tant que
sinon
medianBase1_plus1 = INFINI retourner -1 // Erreur : le médian n'a pas été trouvé (impossible
fin si normalement)
Fin Fonction
//Obtenir les éléments de base2 au milieu-1 et milieu+1 (si EXERCICE 2 :
possible) Fonction estAntiPalindrome(tableau, debut, fin)
si milieu > 1 alors // tableau est le tableau de caractères
medianBase2_moins1 = [Link](milieu-1) // debut et fin sont les indices pour la sous-partie à vérifier
sinon
medianBase2_moins1 = -INFINI si debut >= fin alors
fin si retourner VRAI // Cas de base : soit un seul élément, soit on a
traversé tout le tableau
si milieu < n alors fin si
medianBase2_plus1 = [Link](milieu+1)
sinon si tableau[debut] == tableau[fin] alors
medianBase2_plus1 = INFINI retourner FAUX // Ce n'est pas un anti-palindrome
fin si sinon
retourner estAntiPalindrome(tableau, debut + 1, fin - 1)
fin si
//Cas 1 : medianBase1 <= medianBase2 Fin Fonction
si medianBase1 <= medianBase2 alors
Fonction verifierAntiPalindrome(tableau)
//Verifie le nombre de nombre plus petits ou egale n = taille(tableau)
nbPlusPetit = 0 retourner estAntiPalindrome(tableau, 1, n)
Fin Fonction
si medianBase1_moins1 >= medianBase2 alors 2. Calcul de la représentation binaire
nbPlusPetit = nbPlusPetit + milieu - 1 Fonction representationBinaire(n, resultat)
sinon // n est l'entier positif à convertir
pour i allant de 1 a milieu-1 faire // resultat est une chaîne de caractères construite récursivement
si [Link](i) <= medianBase2 alors (par référence)
nbPlusPetit = nbPlusPetit + 1
fin si si n == 0 alors
fin pour si resultat est vide alors
fin si resultat = "0"
fin si
pour i allant de 1 a milieu faire retourner resultat
si [Link](i) <= medianBase1 alors fin si
nbPlusPetit = nbPlusPetit + 1
fin si representationBinaire(n / 2, resultat) // appel récursif avec
fin pour division entière
resultat = resultat + (n % 2).toString() // ajout du bit actuel à la
chaîne
si nbPlusPetit = n alors retourner resultat
retourner medianBase1 Fin Fonction
sinon si nbPlusPetit > n alors
fin = milieu - 1 Fonction calculerRepresentationBinaire(n)
sinon chaineResultat = ""
debut = milieu + 1 retourner representationBinaire(n, chaineResultat)
fin si Fin Fonction
sinon // Cas 2 : medianBase1 > medianBase2 Fonction trouverPlusProche(tableau, x, debut, fin)
//Verifie le nombre de nombre plus petits ou egale // tableau est le tableau d'entiers
nbPlusPetit = 0 // x est la valeur de référence
// debut et fin sont les indices pour la sous-partie à considérer
si medianBase2_moins1 >= medianBase1 alors
 si debut == fin alors × (12, 15) : 15 % 12 = 3, 12 % 3 = 0, PGCD est 3.
retourner tableau[debut] // Cas de base : un seul élément, × (20, 75) : 75 % 20 = 15, 20 % 15 = 5, 15 % 5 = 0, PGCD est 5.
il est le plus proche × (18, 16) : 18 % 16 = 2, 16 % 2 = 0, PGCD est 2.
fin si × (6, 4) : 6 % 4 = 2, 4 % 2 = 0, PGCD est 2.
• DPR (Division and Conquer): (Implémentation à voir dans la
milieu = (debut + fin) / 2 question 3)

si x <= tableau[milieu] alors 2. Paradigme approprié pour le PGCD et justification

// x est dans la première moitié ou égal
si milieu = debut alors L'approche itérative avec l'algorithme d'Euclide est le paradigme le
retourner tableau[debut] plus approprié pour calculer le PGCD. Voici pourquoi:
sinon
valeurProche = trouverPlusProche(tableau, x, debut, • Efficacité: L'algorithme d'Euclide a une complexité logarithmique
milieu) O(log(min(a, b))), ce qui le rend très efficace même pour les
si abs(valeurProche -x) <= abs(tableau[milieu] - x) alors grands nombres.
retourner valeurProche • Simplicité: Il est facile à comprendre et à implémenter.
sinon • Pas d'exploration inutile: Contrairement à la force brute, il ne teste
retourner tableau[milieu] pas tous les diviseurs. Il se base sur la propriété mathématique du
fin si PGCD.
fin si • La programmation dynamique est ici inutile car le calcul du PGCD
sinon ne présente pas de sous-problèmes qui se chevauchent, ni une
// x est dans la deuxième moitié structure de sous-problèmes optimale.
si milieu = fin alors
retourner tableau[fin] 3. Simulation du DPR pour le PGCD
sinon
valeurProche = trouverPlusProche(tableau, x, milieu + Bien que la DPR ne soit pas la méthode la plus efficace pour le
1, fin) PGCD, on peut l'implémenter de la façon suivante, pour illustrer le
si abs(valeurProche -x) <= abs(tableau[milieu+1] - x) paradigme:
alors
retourner valeurProche ```
sinon Fonction pgcd_dpr(a, b)
retourner tableau[milieu+1] Si b == 0 alors
fin si retourner a
fin si Sinon
Fin Fonction retourner pgcd_dpr(b, a % b)
Fin si
Fonction calculerPlusProche(tableau, x) Fin fonction
n = taille(tableau) ```
si n = 0 alors
retourner -1 //tableau vide Simulation avec (12, 15) :
fin si
1. pgcd_dpr(12, 15)
retourner trouverPlusProche(tableau, x, 1, n) 2. pgcd_dpr(15, 12)
Fin Fonction 3. pgcd_dpr(12, 3)
4. pgcd_dpr(3, 0)
PARTIE 2 : PARAGDIGMES 5. Retourne 3.
1. Il n'y a pas un paradigme universellement "meilleur". Le choix
optimal dépend des caractéristiques spécifiques du problème, des Explication:
contraintes de temps, et de la mémoire.
2. Cette implémentation du PGCD en utilisant le paradigme Diviser
pour Régner (DPR) est une variante récursive de l'algorithme
d'Euclide, qui consiste à diviser le problème de la recherche du
PGCD de deux nombres en deux sous-problèmes, un de taille b et
l'autre de taille a mod b, jusqu'à ce que le second nombre soit nul,
et dans ce cas, le résultat est le premier nombre.

Exercice : Définition du problème: Étant donné deux polynômes P(x)

et Q(x), on veut calculer leur produit R(x) = P(x) × Q(x). Un polynôme
est représenté par un tableau de coefficients.

EXERCICE 2 : 1. Algorithme Force Brute

Exercice 2: Le Plus Grand Commun Diviseur (PGCD) Fonction multiplierPolynomesForceBrute(P, Q)
// P et Q sont des tableaux de coefficients
1. Simulation de l'évaluation du PGCD avec différents n = taille(P) - 1 // Degré du polynôme P
paradigmes m = taille(Q) - 1 // Degré du polynôme Q
R = tableau de taille (n + m + 1) initialisé à 0
Voici des simulations pour le PGCD de l'ensemble (12, 15),
(20, 75), (18, 16), (6,4). pour i allant de 0 à n faire
• Force Brute: pour j allant de 0 à m faire
• (12, 15) : On teste tous les diviseurs de 1 jusqu'au plus petit R[i + j] = R[i + j] + P[i] * Q[j]
nombre, le PGCD est 3. fin pour
• (20, 75) : On teste tous les diviseurs de 1 jusqu'au plus petit fin pour
nombre, le PGCD est 5.
• (18, 16) : On teste tous les diviseurs de 1 jusqu'au plus petit retourner R
nombre, le PGCD est 2. Fin Fonction
• (6, 4) : On teste tous les diviseurs de 1 jusqu'au plus petit Complexité: L'algorithme effectue deux boucles imbriquées, de taille n
nombre, le PGCD est 2. et m respectivement. La complexité est donc O(n×m). Si n=m alors, la
• Approche Itérative (Algorithme d'Euclide): complexité est en O(n^2).
 pour i allant de 0 a tailleMax-1 faire
2. Algorithme de Karatsuba si i < tailleA alors
Fonction multiplierPolynomesKaratsuba(P, Q) res[i] = A[i]
n = taille(P) -1 fin si
m = taille(Q) - 1 si i < tailleB alors
res[i] = res[i] - B[i]
si n < 1 ou m < 1 alors fin si
retourner multiplierPolynomesForceBrute(P,Q) fin pour
fin si
retourner res
si n > m alors Fin Fonction
tmp = P
P= Q Fonction concatener(A,B,C, milieu)
Q = tmp tailleA = taille(A)
n = taille(P)-1 tailleB = taille(B)
m = taille(Q)-1 tailleC = taille(C)
fin si res = tableau de taille (tailleA+tailleB+tailleC + milieu*2) initialise
a0
si n == 0 alors
R = tableau de taille (m+1) initialisé a 0 pour i allant de 0 a tailleA-1 faire
pour i allant de 0 a m faire res[i+ milieu*2] = A[i]
R[i] = P[0] * Q[i] fin pour
fin pour
retourner R pour i allant de 0 a tailleB-1 faire
fin si res[i+ milieu] = res[i+ milieu] + B[i]
fin pour
milieu = n / 2 // Division entière
pour i allant de 0 a tailleC-1 faire
// Diviser les polynomes res[i] = res[i] + C[i]
A_H = P[milieu : n] fin pour
A_L = P[0 : milieu-1] retourner res
B_H = Q[milieu : min(n,m)] Fin Fonction
B_L = Q[0 : milieu-1]
Exercice 5: Trouver le Champion dans un Tableau
// Calculer les quatre produits récursivement
A_H_B_H = multiplierPolynomesKaratsuba(A_H, B_H) 1. Algorithme Force Brute
A_L_B_L = multiplierPolynomesKaratsuba(A_L, B_L) Fonction trouverChampionForceBrute(tableau)
n = taille(tableau)
// Calculer (A_H + A_L)*(B_H + B_L)
A_sum = somme(A_H,A_L) pour i allant de 1 à n faire
B_sum = somme(B_H,B_L) compteur = 0
A_B_sum = multiplierPolynomesKaratsuba(A_sum, B_sum) pour j allant de 1 à n faire
si tableau[i] == tableau[j] alors
A_L_B_H_A_H_B_L = soustraction(A_B_sum , A_L_B_L) compteur = compteur + 1
A_L_B_H_A_H_B_L = soustraction(A_L_B_H_A_H_B_L , fin si
A_H_B_H) fin pour
si compteur > n / 2 alors
//Construire le resultat final retourner tableau[i]
R = concatener( A_H_B_H, A_L_B_H_A_H_B_L, A_L_B_L, fin si
milieu) fin pour

retourner R retourner null // Pas de champion

Fin Fonction
Fin Fonction 2. Algorithme DPR (Diviser pour régner)
Fonction trouverChampionDPR(tableau, debut, fin)
Fonction somme(A,B) n = fin - debut +1
//A et B sont des tableaux de coefficients si debut == fin alors
tailleA = taille(A) retourner tableau[debut] // Cas de base : 1 seul élément
tailleB = taille(B) fin si
tailleMax = max(tailleA,tailleB)
res = tableau de taille tailleMax initialise a 0 milieu = (debut + fin) / 2
pour i allant de 0 a tailleMax-1 faire
si i < tailleA alors championGauche = trouverChampionDPR(tableau, debut, milieu)
res[i] = res[i] + A[i] championDroit = trouverChampionDPR(tableau, milieu + 1, fin)
fin si
si i < tailleB alors si championGauche == null et championDroit == null alors
res[i] = res[i] + B[i] retourner null
fin si fin si
fin pour si championGauche == championDroit alors
retourner championGauche
retourner res fin si
Fin Fonction
// Compter l'occurence des champions gauche et droit dans le
Fonction soustraction(A,B) tableau
//A et B sont des tableaux de coefficients compteurGauche = 0
tailleA = taille(A) compteurDroit = 0
tailleB = taille(B) pour i allant de debut a fin faire
tailleMax = max(tailleA,tailleB) si tableau[i] == championGauche alors
res = tableau de taille tailleMax initialise a 0 compteurGauche = compteurGauche + 1
 fin si retourner null
si tableau[i] == championDroit then fin si
compteurDroit = compteurDroit + 1 retourner selectionRecursif(tableau,k,1,n)
fin si Fin fonction
fin pour Complexité: Dans le pire des cas, l'algorithme pourrait avoir une
complexité O(n^2), mais dans le cas moyen, si on choisit le pivot de
si compteurGauche > n / 2 alors façon aleatoire, on a une complexité O(n). La complexité en espace est
retourner championGauche de O(log n) car on a des appels récursifs.
fin si
si compteurDroit > n / 2 alors Exercice 7: Vecteur Unimodal
retourner championDroit
fin si 1. Algorithme O(log n)
Fonction trouverMaxUnimodal(V, debut, fin)
retourner null // V est le vecteur, debut et fin sont les indices de la sous-partie à
traiter
Fin Fonction
si debut == fin alors
Fonction calculerChampion(tableau) retourner V[debut] // Cas de base : un seul élément
n= taille(tableau) fin si
retourner trouverChampionDPR(tableau, 1, n)
Fin fonction si debut +1 == fin alors
Complexité: L'algorithme suit le schéma diviser pour régner avec retourner max(V[debut],V[fin]) // Cas de base : deux éléments
deux appels récursifs sur des moitiés du tableau, et un parcours du fin si
tableau. Le coût du parcours étant O(n) et la division O(log n), la
complexité est O(n log n). milieu = (debut + fin) / 2

Exercice 6: Le Problème de la Sélection si V[milieu] < V[milieu+1] alors

// Le max est à droite
Fonction selectionRecursif(A, k, debut, fin) retourner trouverMaxUnimodal(V, milieu + 1, fin)
// A est le tableau, k est le nombre maximal d'éléments sinon si V[milieu] > V[milieu + 1] then
inférieurs ou égaux // le max est a gauche ou est lui-même
// debut et fin sont les indices de la partie à traiter retourner trouverMaxUnimodal(V, debut, milieu)
fin si
si debut > fin alors
retourner null //Cas impossible retourner -INFINI // Ne devrait pas arriver normalement
fin si Fin Fonction

si debut == fin alors Fonction calculerMaxUnimodal(V)

retourner A[debut] //Cas de base n = taille(V)
fin si si n <= 0 alors
retourner -INFINI
//Choisir un pivot de façon aleatoire fin si
indicePivot = genererAleatoire(debut, fin) // retourne un retourner trouverMaxUnimodal(V,1,n)
nombre aleatoire dans l'intervalle [debut, fin] Fin Fonction
2. Justification de la complexité
pivot = A[indicePivot]
A_moins_pivot = nouveauTableau() • L'algorithme utilise une recherche dichotomique, en divisant l'intervalle
A_plus_pivot = nouveauTableau() de recherche par deux à chaque étape.
A_egal_pivot = nouveauTableau() • Le nombre d'appels récursifs est au plus log2(n)
• La complexité de l'algorithme est donc bien O(log n).
pour i allant de debut a fin faire
si A[i] < pivot alors
A_moins_pivot = ajouterElement(A_moins_pivot,A[i]) Exercice 8: Tri Fusion et Plus
sinon si A[i] > pivot alors
A_plus_pivot = ajouterElement(A_plus_pivot,A[i]) 1. Tri Fusion
sinon
A_egal_pivot = ajouterElement(A_egal_pivot,A[i]) Principe: Le tri fusion est un algorithme de tri basé sur le paradigme
fin si "diviser pour régner". Il divise récursivement le tableau en deux moitiés,
fin pour les trie séparément, puis fusionne les deux moitiés triées.

nombreElementsInferieur = taille(A_moins_pivot) Complexité: Le tri fusion a une complexité temporelle de O(n log
n) dans le meilleur, le pire, et le cas moyen. La fusion a une complexité
si k = nombreElementsInferieur alors en O(n).
retourner max(A_moins_pivot)
sinon si k < nombreElementsInferieur alors Si le vecteur est divisé en 3 parties, et que les sous-vecteurs sont
// le k-ieme plus grand est dans la partie gauche fusionnés en deux temps :
retourner selectionRecursif(A_moins_pivot, k, 1, La complexité reste toujours de O(n log n).
taille(A_moins_pivot)) • La division en 3 parties à chaque fois donne un arbre de profondeur
sinon O(log3 n), c'est-à-dire O(log n)
// le k-ieme plus grand est dans la partie droite • À chaque niveau, la fusion de tous les sous-tableaux prend O(n).
retourner selectionRecursif(A_plus_pivot, k- • Le coût est donc O(n log n).
nombreElementsInferieur-taille(A_egal_pivot) , 1,
taille(A_plus_pivot)) 2. Minimum et Maximum en O(3n/2)
fin si Fonction minMaxDPR(V, debut, fin)
Fin fonction // V est le vecteur, debut et fin sont les indices de la sous-partie à
traiter
Fonction selection(tableau, k)
n = taille(tableau) si debut == fin alors
si n <= 0 alors retourner (V[debut], V[debut]) // Cas de base : un seul élément
 fin si en O(n log n).

si debut + 1 == fin alors

retourner (min(V[debut],V[fin]), max(V[debut],V[fin]))
fin si

milieu = (debut + fin) / 2

(minGauche, maxGauche) = minMaxDPR(V, debut, milieu)

(minDroit, maxDroit) = minMaxDPR(V, milieu + 1, fin)

retourner (min(minGauche, minDroit), max(maxGauche,

maxDroit))
Fin Fonction

Fonction calculerMinMax(V)
n= taille(V)
si n<=0 alors
retourner (null, null)
fin si
retourner minMaxDPR(V,1,n)
Fin Fonction
Complexité: À chaque niveau de récursion, on fait 2 appels
récursifs avec des tailles moitié et on effectue 2 comparaisons (min
et max) pour chaque couple (gauche et droite). On a T(n) = 2T(n/2)
+ 2 avec T(1) = 0, et T(2) = 1, ce qui donne environ
O(3n/2) comparaisons et O(n) pour la complexité temporelle.

3. Élément Majoritaire en DPR

Fonction trouverMajoritaireDPR(V, debut, fin)
n = fin - debut +1
si debut == fin alors
retourner V[debut] // Cas de base : 1 seul élément
fin si

milieu = (debut + fin) / 2

majoritaireGauche = trouverMajoritaireDPR(V, debut,

milieu)
majoritaireDroit = trouverMajoritaireDPR(V, milieu + 1, fin)

si majoritaireGauche == null et majoritaireDroit == null alors

retourner null
fin si
si majoritaireGauche == majoritaireDroit alors
retourner majoritaireGauche
fin si

// Compter l'occurence des majoritaires gauche et droit dans

le tableau
compteurGauche = 0
compteurDroit = 0
pour i allant de debut a fin faire
si V[i] == majoritaireGauche alors
compteurGauche = compteurGauche + 1
fin si
si V[i] == majoritaireDroit then
compteurDroit = compteurDroit + 1
fin si
fin pour

si compteurGauche > n / 2 alors

retourner majoritaireGauche
fin si
si compteurDroit > n / 2 alors
retourner majoritaireDroit
fin si

retourner null

Fin Fonction

Fonction calculerMajoritaire(V)
n= taille(V)
retourner trouverMajoritaireDPR(V, 1, n)
Fin Fonction
Complexité: On a deux appels récursifs sur la moitié du tableau et
à chaque appel récursif, on parcourt le tableau. La complexité est