Date : 1997
Editeur / Publisher : [S.l.] : [s.n.] , 1997
Format : 211 P.
Type : Livre / Book
Type : Thèse / ThesisLangue / Language : français / French
Résumé / Abstract : CETTE THESE PRESENTE PLUSIEURS VARIATIONS SYSTOLIQUES, C'EST-A-DIRE PLUSIEURS SOLUTIONS MATERIELLES, POUR UNE CLASSE DE PROBLEMES RELATIFS AU PROBLEME DU PLUS LONG SOUS-MOT COMMUN. UNE MOTIVATION MAJEURE A L'ETUDE APPROFONDIE DE CE PROBLEME EST L'IMPORTANCE DE CES APPLICATIONS (PROBLEMATIQUE DE L'HOMOLOGIE DE SEQUENCES EN BIOLOGIE MOLECULAIRE, COMPRESSION DE DONNEES, CORRECTION DE SIGNAUX ...). LE MODELE SYSTOLIQUE COMME LE DEFINIT H.T. KUNG PERMET DE REALISER A L'AIDE DE TECHNOLOGIES VLSI (VERY LARGE SCALE INTEGRATION) DES ARCHITECTURES SYNCHRONES ET REGULIERES MASSIVEMENT PARALLELES SOUS FORME DE PROCESSEURS SPECIALISES. LE GAIN DE TEMPS QUE PEUT APPORTER L'INTRODUCTION D'UN TEL PARALLELISME A CES PROBLEME EST TRES APPRECIABLE. PAR EXEMPLE, L'INTRINSEQUE COMPLEXITE EN TEMPS QUADRATIQUE (L'ALGORITHME SEQUENTIEL DE PROGRAMMATION DYNAMIQUE S'EXECUTE EN TEMPS O(NM)) DU PROBLEME DE LA DETERMINATION DE LA LONGUEUR D'UN PLUS LONG SOUS-MOT COMMUN A DEUX MOTS DE LONGUEURS N ET M PEUT ETRE REDUITE A O(N + M) SUR UN RESEAU SYSTOLIQUE LINEAIRE DE M PROCESSEURS ELEMENTAIRES. NOUS AVONS PROPOSE PLUSIEURS ALGORITHMES SYSTOLIQUES PERFORMANTS SUR DIFFERENTS RESEAUX (MEME MULTIDIMENSIONNELS) POUR DETERMINER UN PLUS LONG SOUS-MOT COMMUN A DEUX, TROIS OU QUATRE MOTS, QUI ONT ETE SIMULES SUR UN RESEAU DE TRANSPUTERS T9000.