Exercices d'algo

[Anonyme]

Salut,
J'aurais besoin d'aide pour les 3 exercices suivants.
Merci d'avance à ceux qui m'aideront.


Exercice 1
Tri de suffixe
On considère une table de caractères,y,de dimension n.Le but de cet exercice est de calculer la table Pos de dimension n pour laquelle

y[Pos[0]..n-1]= g && Pos[d] >=pivot)
d=d-1;
if(g d)
return g;
}

[/CODE]


3)Ecrire un algorithme de classement des suffixes de y qui produit la table Pos en utilisant la fonction de partage du 2. Quelle table Pos obtient-on avec y = "abracadabra" ?

4)Donnez une majoration asymptotique des temps d'execution de
Partage(d,f,p) et de l'algorithme de classement. Quel peut etre son temps moyen d'éxécution en supposant que le temps moyen pour comparer 2 suffixes est O(logn)[/b]

[Anonyme]

Exercice 2

Arbres feuillus
Les arbres considérés dans cet exercice sont des arbres binaires feuillus (complets) dont les noeuds sont des entiers . À un tel arbre A on associe le mot


ou r est la racine de A, G son sous-srbre gauche et D son sous-abre droit.

1)Calculer Str((1,(2,(3),(4)),(5))) et Str((1,(2),(3,(4),(5))))
Dessinez les arbres qui correspondent aux mots 0001111 et 0101011

Str((1,(2,(3),(4)),(5)))
00111

Str((1,(2),(3,(4),(5))))
01011

2)Soit x = Str(A) et y = Str(B) pour 2 arbres A et B
Montrez que x = y si et seulement si A et B sont égaux à la numérotaion près de leurs noeuds (autrement dit, s'il existe une bijection entre les noeuds qui respecte la structure de l'arbre)
*si A = B on a Str(A) = Str(B) et donc x=y
*si x = y on a Str(a) = Str(B) et donc A = B


3)Indiquer comment mémoriser dans un fichier le code obtenu par la méthode de Huffman , en adaptant la fonction Str à appliquer à l'arbre de Huffman de codage

Pour mémoriser dans un fichier le code obtenu,il suffit d'indiquer que la valeur 0 correspond à un noeud et 1 à une feuille.
En parcourant la suite binaire on pourra reconstituer l'arbre.

4)Ecrire une fonction C qui produit sur la sortie standart x = Str(A) pour un arbre A

Code: Tout sélectionner

typedef struct noeud
{
  int val;
  struct noeud *g,d;
}Noeud ;

typedef Noeud *Arbre;


void Str(Arbre A)
{
  printf('0');
  while(A->g->g !=NULL)
    {
      printf('0');
      A = A->g;
    }
  printf('1');
  while(A->d->d !=NULL)
    {
      printf('0');
      A = A->d;
    }
  printf('1');
}

5)Ecrire une fonction C qui, à partir d'un mot binaire Str(A) sur l'entée standart ,reconstruit l'arbre A

[Anonyme]

Exercice 3

Sous-mots

Soient 2 mots x et y supposés déclarés en C par:

char x[100]; char y[100];

1)Écrire en C une fonction qui teste si x est un sous-mot de y

2)Ecrire en C une fonction qui calcule lsc(x,y),la longueur maximale des sous-mots communs à x et y

3)Calculer la table Tx,y relative aux mots x = agctga et y = cagatcagag et définie par :

Tx,y[i,j] = lsc(x[0]x[1]...x[i-1],y[0]y[1]...y[j-1])

ou i = 0,1...|x| et j= 0,1...|y|.(Pour i = 0 on convient x[0]x[1]...x[i-1] est le sous mot vide; meme convention avec y[0]y[1]...y[j-1] quand j = 0)

4)Quels sont les plus longs sous-mots communs à agctga et cagatcagag?.
Indiquer comment calculer un sous mot commun à x et y et de longeur lsc(x,y) à partir de la table Tx,y

[N_comme_Nul]

Salut !

Rien que ça ?

Je vais voir ce que je peux faire :hum:

[N_comme_Nul]

Pour l'implémentation de la fonction [FONT=Courier New]strcmp[/FONT], il en existe des tonnes. Je te file celle de Solaris , celle de FreeBSD est presque pareille :

Code: Tout sélectionner

/* Comparaison des chaines s et t comme suit :  s>t: >0  s==t: 0  s<t: <0 */
int strcmp(const char *s, const char *t) {
    if (s == t) return (0);
    while (*s == *t++)
        if (*s++ == '\0')
            return (0);
    return (*(unsigned char *)s - *(unsigned char *)--t);
}

[N_comme_Nul]

Ta notion de "suffixe", c'est en fait la notion de "sous-chaîne" ?

Dis-moi si je me trompe :
si l'on a

Code: Tout sélectionner

y[]="maison"

alors on devra trouver

Code: Tout sélectionner

pos[]={1,2,0,5,4}

ce qui correspond à
"aison" "ison" "maison" "n" "on" "son"

L'énoncé de l'exercice 1 est pénible ! Si je faisais de l'info avec ce genre d'écriture ça serait :mur: C'aurait été plus simple de tout faire soi-même et non de passer par cette fonction "Partage".

[Anonyme]

Ta notion de "suffixe", c'est en fait la notion de "sous-chaîne" ?

Dis-moi si je me trompe :
si l'on a

Code: Tout sélectionner

y[]="maison"

alors on devra trouver

Code: Tout sélectionner

pos[]={1,2,0,5,4}

ce qui correspond à
"aison" "ison" "maison" "n" "on" "son"

L'énoncé de l'exercice 1 est pénible ! Si je faisais de l'info avec ce genre d'écriture ça serait :mur: C'aurait été plus simple de tout faire soi-même et non de passer par cette fonction "Partage".

Ta notion de "suffixe", c'est en fait la notion de "sous-chaîne" ?

Oui,c'est bien cela

[Anonyme]

Il n' y a personne qui sache comment répondre aux questions des exos?

[N_comme_Nul]

Salut !

Cela fait ( au moins ) sur 3 fora que tu postes ces exercices.
Personne, apparemment, ne te répond (et pour l'implémentation du strcmp, franchement, un p'tit coup de google et on en parlait plus, c'est ce que j'ai fait d'ailleurs dans un précédent post). Je pense deviner pourquoi : tu mets des tartines d'énoncés sans rien montrer de ce que TOI tu as fait. Un peu de courage ! Ne laisse pas les autres faire tes exercices ... sinon à quoi bon, tu ne progresseras jamais.

Georg.

[Anonyme]

Salut !

Cela fait ( au moins ) sur 3 fora que tu postes ces exercices.
Personne, apparemment, ne te répond (et pour l'implémentation du strcmp, franchement, un p'tit coup de google et on en parlait plus, c'est ce que j'ai fait d'ailleurs dans un précédent post). Je pense deviner pourquoi : tu mets des tartines d'énoncés sans rien montrer de ce que TOI tu as fait. Un peu de courage ! Ne laisse pas les autres faire tes exercices ... sinon à quoi bon, tu ne progresseras jamais.

Georg.

Salut,
je viens de mettre mes réponses mais il faut remonter au sujet.
Si tu as un avis sur ce que j'ai fait n'hésite pas.