Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Universit´ e Paris Diderot L2 Informatique Ann´ ee 2015–2016 Examen d’algorithm

Universit´ e Paris Diderot L2 Informatique Ann´ ee 2015–2016 Examen d’algorithmique jeudi 14 janvier 2016 15h30–18h30 / Aucun document autoris´ e Mode d’emploi : Le bar` eme est donn´ e ` a titre indicatif. La qualit´ e de la r´ edaction des algorithmes et des explications sera fortement prise en compte pour la note. On peut toujours supposer une question r´ esolue et passer ` a la suite. Exercice 1 : D´ erouler des algorithmes (4 points) 1. On consid` ere l’algorithme P1 ci-dessous : Def P1(entier x) : Si x==0 Alors Retourner 0 Sinon : a=0 b=1 i=2 tant que i <= x faire: aux = b b = a+b a = aux i=i+1 Retourner b D´ ecrire ce que fait l’algorithme P1 appel´ e avec le param` etre 6. On d´ ecrira pr´ ecis´ ement l’´ etat des variables a et b au cours de l’algorithme. 2. On consid` ere l’algorithme P2 ci-dessous : Def P2(x) : Si x==0 ou x==1 Alors Retourner x Sinon Retourner P2(x-1)+P2(x-2) D´ ecrire ce que fait l’algorithme P2 appel´ e avec le param` etre 6. On d´ ecrira pr´ ecis´ ement tous les appels de fonctions. 3. Comparer ces deux algorithmes. Exercice 2 : Tri pour deux valeurs - 4 points On veut d´ eﬁnir un algorithme de tri pour des tableaux de taille n ne contenant que deux valeurs distinctes. On cherche ` a trier dans l’ordre croissant. Par exemple pour le tableau suivant de taille 5 : [2,4,4,2,2], on veut obtenir [2,2,2,4,4] 1. Ecrire un algorithme de tri bas´ e sur une m´ ethode de comptage. 2. Ecrire un algorithme qui trie le tableau en ne faisant qu’un seul parcours du tableau. 1/4 Universit´ e Paris Diderot L2 Informatique Ann´ ee 2015–2016 Exercice 3 : Algorithmes sur les arbres - 6 points On consid` ere des arbre binaires contenant des valeurs enti` eres dans les noeuds, comme dans l’exemple ci-dessous : On suppose que ces arbres sont repr´ esent´ es par des structures chaˆ ın´ ees (comme en cours). Un noeud de l’arbre (type noeud) sera repr´ esent´ e par une structure ayant les champs de valeurs suivants : — un champ de nom val et de type entier contenant la valeur stock´ ee ; — un champ de nom fg et de type arbre contenant l’adresse du ﬁls gauche ; — un champ de nom fd et de type arbre contenant l’adresse du ﬁls droit. Et un arbre est un pointeur (adresse) vers un noeud (l’adresse 0 d´ esigne un arbre vide). Lorsqu’un noeud n’a pas de ﬁls gauche, son champ fg vaut 0 (et c’est pareil pour le ﬁls droit avec fd). Un noeud qui n’a ni ﬁls gauche, ni ﬁls droit est une feuille. Si a est un arbre non vide, a->val d´ esigne la valeur stock´ ee ` a sa racine (le premier noeud de l’arbre), a->fg d´ esigne l’adresse du ﬁls gauche (donc un arbre), et a->fg d´ esigne l’adresse du ﬁls droit, etc. 1. Dessiner la structure chaˆ ın´ ee repr´ esentant l’arbre test ci-dessous : 2. ´ Ecrire un algorithme Somme qui ´ etant donn´ e un arbre a retourne la somme de toutes les valeurs stock´ ees dans les noeuds de cet arbre (et 0 si l’arbre est vide). NB : Sur l’exemple, on doit renvoyer 36. Proﬁl sugg´ er´ e : entier Somme(arbre a) Appliquer votre algorithme sur l’arbre test (et d´ ecrire les ´ eventuels appels de fonction, ou it´ erations. . . ) . 2/4 Universit´ e Paris Diderot L2 Informatique Ann´ ee 2015–2016 3. ´ Ecrire un algorithme CptFeuille qui ´ etant donn´ e un arbre a retourne le nombre de feuilles de l’arbre a. NB : Sur l’exemple, on doit renvoyer 4. Proﬁl : entier CptFeuille(arbre a) Quelle valeur retourne votre algorithme sur l’arbre test ? 4. Ecrire un algorithme CptOcc qui ´ etant donn´ e un arbre a et un entier x retourne le nombre d’occurrences de x dans l’arbre de racine a. NB : Sur l’exemple et avec x = 4, on doit renvoyer 2. Proﬁl sugg´ er´ e : entier CptOcc(arbre a, entier x) Quelle valeur retourne votre algorithme sur l’arbre test avec x = 4 ? 5. Ecrire un algorithme Hauteur qui ´ etant donn´ e un arbre a retourne la hauteur de l’arbre (la longueur du plus long chemin direct entre la racine et une feuille, et par convention on prendra -1 comme hauteur pour l’arbre vide). NB : Sur l’exemple, on doit renvoyer 3. Proﬁl sugg´ er´ e : entier Hauteur(arbre a) Quelle valeur retourne votre algorithme sur l’arbre test ? Exercice 4 : Backtracking - 6 points On s’int´ eresse ici aux mots construits ` a partir d’un alphabet ⌃(un ensemble ﬁni de lettres). Par exemple, si ⌃= {a, b, c}, alors les mots aaab, abc, abbbbbaaaab sont des mots possibles. Le mot vide est not´ e " et il est aussi un mot possible (de longueur 0). Mais le mot abbdaab n’est pas possible car d n’appartient pas ` a ⌃. Dans cet exercice, on pourra utiliser toutes les fonctions classiques sur les chaˆ ınes de caract` eres : concat´ enation (+), acc` es au i-` eme caract` ere (w[i]), longueur (|w|), la r´ ep´ etition d’une lettre i fois (i*’a’). . . 1. Etant donn´ e un alphabet ⌃repr´ esent´ e par un tableau T de taille n (T[i] est la i-` eme lettre) et un entier k, ´ ecrire un algorithme qui aﬃche tous les mots de longueur k possibles avec ⌃. NB : Avec l’alphabet ⌃= {a, b, c} et k = 2, l’algorithme devra aﬃcher : aa, ab, ac, ba, bb, bc, ca, cb, cc. Appliquer votre algorithme ` a l’alphabet ⌃= {a, b} (donc T=[a,b] et k = 3. On d´ ecrira avec pr´ ecision le d´ eroul´ e de l’algorithme. Proﬁl sugg´ er´ e si algorithme r´ ecursif : void GenererMot(T,k,w) o` u w est le mot en cours de construction (mot vide au premier appel). Et proﬁl sugg´ er´ e pour version it´ erative : void GenererMot(T,k). 2. On reprend la question pr´ ec´ edente mais cette fois, on remplace l’argument k par un tableau de caract` eres m[-] de longueur k qui va imposer un motif particulier aux mots recherch´ es : soit m[i] est une lettre de ⌃et alors tous les mots aﬃch´ es par l’algorithme devront avoir cette lettre ` a la position i, soit m[i] est * et alors n’importe quelle lettre de ⌃peut se trouver ` a la position i. ´ Ecrire un algorithme pour r´ esoudre ce probl` eme. NB : Avec l’alphabet ⌃= {a, b, c} et m=[a,*], l’algorithme devra aﬃcher : aa, ab, 3/4 Universit´ e Paris Diderot L2 Informatique Ann´ ee 2015–2016 ac. Et si m=[*,*], on retrouve tous les mots g´ en´ er´ es par l’algorithme de la question pr´ ec´ edente pour k = 2. Donner le r´ esultat de l’application de votre algorithme pour l’alphabet ⌃= {a, b, c} et m=[*,a,a,*]. 3. On modiﬁe le probl` eme pr´ ec´ edent en donnant un tableau d’entiers Nb[-] ` a la place du motif m[-] : Nb va d´ ecrire la taille des s´ equences de lettres identiques. Par exemple, si Nb est de taille 3 et que Nb[0] = 3, Nb[1] = 2 et Nb[2] = 1, alors les mots recherch´ es commenceront par une lettre r´ ep´ et´ ee trois fois, puis une autre (pas la mˆ eme !) sera r´ ep´ et´ ee 2 fois, et le mot se terminera par un dernier changement de lettre (sans r´ ep´ etition). Donc avec ⌃= {a, b, c} et ce tableau Nb, on obtiendrait les mots suivants : aaabba, aaabbc, aaacca, aaaccb, bbbaab, bbbaac, bbbcca, bbbccb, cccaab, cccaac, cccbba, et cccbbc. Modiﬁer l’algorithme pr´ ec´ edent pour r´ esoudre ce probl` eme. Donner le r´ esultat de l’application de votre algorithme pour l’alphabet ⌃= {a, b} et Nb=[2,4,3]. 4/4 uploads/Litterature/ examen-1516-session1z.pdf