Exercice 2: 4 pts

Université AbouBekr Belkaid Tlemcen
Tlemcen le 11/01/2016 Faculté des Sciences Département d'informatique Master 1 RSD-GL Algorithmique Avancée et Complexité Corrigé - Examen Final Exercice 1: 4 pts Supposons qu'on veut insérer des éléments dans une table de hachage de
taille 40, les codes de ces éléments sont formés par 3 caractères, le
premier et le deuxième caractère contiennent des lettres de l'alphabet de A
à D, le 3eme contient des nombres de 0-9. Exemple: AA0, AB8, AC7, BB5 . 1. Quelle est le nombre des codes possibles. 2. Proposer une fonction de hachage pour avoir au plus trois collisions par
code. Sol : 1-160 codes possibles. 1pt 2- Parmi les solutions possibles:
3pts H(element)=(position(element,2)-1)*10+valeur_car(element,2). Exercice 2 : 4pts
1. Ecrire un algorithme qui permet d'inverser une liste chainée, de taille
N.
(Vous n'avez pas le droit d'utiliser d'autre structure de données).
2. Calculer la complexité de cet algorithme. Sol
1-
3pts
list* Inverse( list* entree)
Debut
list* travail=NULL; list* retour=NULL; Tant que(entree!=NULL)
Debut
travail=entree;
entree=travail->suiv;
travail->suiv=retour;
Fin
return retour;
Fin 2-Complexité = ?(N) 1pt Exercice 3: 8pts 1.Ecrire un algorithme glouton pour résoudre le problème suivant du sac à
dos sachant que La capacité totale du sac est 9.
|Article |Poids |valeur |
|1 |6 |90 |
|2 |5 |63 |
|3 |4 |56 |
|4 |2 |12 | 2. Appliquer la méthode de la programmation dynamique au problème précédent
du sac à dos ? 3-Que peut-on conclure des résultats ? 4-Donner l'algorithme complet de résolution du problème sac à dos. 5-Calculer la complexité de cet algorithme. Sol : Exemple méthode maximisant le bénéfice.
2pts 1- Algorithme glouton Debut N : Nombre d'objets P : Tableau qui contient les poids. V : Tableau qui contient les valeurs. Res : Tableau des résultats initialisé a 0 ; Cap : capacité du sac Ben : Bénéfice max ; Poid : poids des objets dans le sac. Poid=0 ; Ben=0 ; Pour i allant de 1 à N faire Debut Si Cap>P[i] alors Debut Poid= Poid+ P[i] ;
Cap=Cap- P[i] ; Ben=Ben+V[i]; Res[i]=1; Fin Fin Retourner(Res,Poids,Ben) Fin 2-
3pts Objet 2 et 3 , Poids Tot =9, Benifice Max= 119 3-
1pt Le résultat obtenu par l'algorithme glouton est : Objet 1et 4 , Poids Tot =9, Benifice Max= 102. L'algothme de programmation dynamique donne une sol optimale 4 et 5
2pts Les deux Algorithmes de cours. Exercice: 4 pts 1-Ecrire une fonction Compare() qui compare deux arbres binaires(la
fonction renvoie vrai si les deux arbres sont identiques) 2-Calculer la complexité au meilleur et au pire de cette fonction. Sol 1-Fonction Compare(arbre : A,arbre :B)
3pts Debut Si(valeur(A)=Valeur(B)) alors Si (Valeur(A)=Null) alors retourner vrai ; Sinon retourner Compare(Gauche(A), Gauche(B))et Compare(Droit(A),
Droit(B)) Fsi Sinon retourner Faux ; Finsi Fin 2 1pt - La complexité au meilleur = ?(1) -La complexité au pire = ?(N)