Scribd
Importer
19 vues2 pages

Examen de Complexité Appliquée RO 2022

Le document est un examen de rattrapage pour le module de Complexité appliquée à la RO, comprenant trois exercices. Le premier exercice demande d'analyser la complexité de trois fonctions, le deuxième porte sur la somme d'un tableau avec un algorithme diviser-pour-régner, et le troisième concerne une fonction récursive avec des questions sur sa trace d'exécution et sa complexité. L'examen se déroule sur deux pages, sans documents autorisés, et dure 1h30.

Transféré par

Aziz Zarkaoui
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
19 vues2 pages

Examen de Complexité Appliquée RO 2022

Le document est un examen de rattrapage pour le module de Complexité appliquée à la RO, comprenant trois exercices. Le premier exercice demande d'analyser la complexité de trois fonctions, le deuxième porte sur la somme d'un tableau avec un algorithme diviser-pour-régner, et le troisième concerne une fonction récursive avec des questions sur sa trace d'exécution et sa complexité. L'examen se déroule sur deux pages, sans documents autorisés, et dure 1h30.

Transféré par

Aziz Zarkaoui
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Examen

Session : Rattrapage

Module : Complexité appliquée à la RO


Enseignant(s): Équipe Complexité appliquée à la RO
Documents autorisés : NON ; Nombre de pages : 2 ; Internet autorisée : NON
Calculatrice autorisée : OUI
Date : 22/06/2022 à 10H 30 Durée : 1H30

Exercice 1 (6 points):
On considère les fonctions A, B et C définies ci-dessous, déterminer la complexité en nombre
d’ « operation » en justifiant votre réponse.

A (int n){ B (int n) { C (int n) {


while (1 < n) { int i ; int i ;
operation ; for (i=0 ; i<n*n ; i++) { for (i=0 ; i<n ; i++) {
n = n / 2; operation ; A(n) ;
} } }
} } B(n) ;
}

Exercice 2 : (6 points)

On cherche la somme d’un tableau T de n éléments entiers.

1. Écrivez un algorithme de type diviser-pour-régner qui résout ce problème.


2. Analysez sa complexité.
 Donner l’équation récurrente estimant la complexité
 Déduire l’ordre de complexité
3. Comparez la complexité de l'algorithme proposé avec sa version itérative.

1
Exercice 3: (8 points)
Soit la fonction récursive « Traiter » :

int Traiter (int n)


{
if (n = = 0){
Return 1; }

if (n = = 1){
Return 0; }

else
Return Traiter (n-1) + 2 * Traiter (n-2);

1. Donner la trace d'exécution de la fonction « Traiter » lorsqu'on lui fournit comme entrée
n = 4.
2. Quel-est le type de cette récursivité ?
3. Donner l’équation de récurrence de la fonction « Traiter ».
4. Quel-est le polynôme caractéristique de cette fonction ?
5. Calculer la complexité de « Traiter » tout en détaillant les étapes de calcul.
6. Déduire la classe de complexité de « Traiter ».

Vous aimerez peut-être aussi