Algorithmique TD 2

Licence M/I

Date: 3 octobre 2005

Exercice 1: Soit t un tableau d'entiers relatifs de taille n; on considère les sommes de cases successives et on veut calculer le maximum parmi ces sommes. Proposer un algorithme et évaluer sa complexité.

Exercice 2: Problème de sac à dos. Un sac à dos a une certaine capacité C On dispose de n objets de volumes v[1],v[2],...,v[n]. On veut remplir le plus possible le sac à dos, c'est-à-dire trouver un sous-ensemble d'objets dont la somme des volumes soit inférieure à C et maximale.

1. Résoudre le problème du sac à dos pour C=150 et v={16,22,54,56,71}.

2. On note m(C,v[1..k]) la solution au problème de sac à dos pour un sac de capacité avec les objets 1,2,...,k. Trouver une relation entre m(C,v[1..k]), m(C,v[1..(k-1)]) et m(C-v[k],v[1..(k-1)]). En déduire un algorithme de calcul de m(C,v[1..n]). Quel est sa complexité en temps et en espace ?

3. On veut remplir un tableau M de taille nXn de telle sorte que M[i,k]=m(C-(v[i+1]+..+v[n]),v[1..k]). Donner un algorithme quadratique pour remplir ce tableau. En déduire un algorithme quadratique en temps et en espace pour calculer m(C,v[1..n]).

Exercice 3: Plus grande sous-séquence commune. Un mot w de longueur n est une suite de n lettres: w=w[1]w[2]...w[n]. Un sous-mot de w est une sous-suite: w[s(1)]w[s(2)]...w[s(k)], avec s fonction strictement croissante. On cherche un algorithme pour calculer la longueur maximale d'un sous-mot commun à deux mots donnés u et v.

1. Trouver le(s) plus long(s) sous-mot(s) commun(s) à abracadabra et barbapapa.

2. On note l(u,v) la longueur maximale d'un sous-mot commun à u et à v. Si u=u[1]...u[n] et v=v[1]...v[m], on note u'=u[1]...u[n-1] et v'=v[1]...v[m-1]. Trouver une relation entre l(u,v), l(u',v), l(u,v') et l(u',v'). dépendant du fait que les dernières lettres de u et v sont égales ou non.

3. Trouver un algorithme quadratique pour le calcul du plus long sous mot commun.