Mémoires de Fin d’Etudes
Etablissement
Université de Batna 2 - Mustafa Ben Boulaid
Affiliation
Département de l’Informatique
Auteur
AKSA, Karima
Directeur de thèse
Batouche M. C. (Professeur)
Filière
Informatique Industriel
Diplôme
Magister
Titre
Systèmes bio-inspirés pour le traitement de l’information : Application du DNA computing à la résolution de problèmes NP-complets
Mots clés
Calcul moléculaire; Calcul de l’ADN; Ordinateur à l’ADN; Bio-calcul; Problèmes NP-complets; Bio-informatique; Systèmes bio-inspirés; Biologie moléculaire; ADN
Résumé
La solution d’un problème combinatoire, quand elle existe, peut être déterminée par l’énumération d’un ensemble fini E de possibilités. S’il y a un algorithme simple pour tester si un élément de cet ensemble est une solution, on dispose d’un algorithme pour trouver une solution au problème en testant toutes les possibilités. Mais le cardinal de E est souvent exponentiel par rapport à la taille des données, ce qui rend l’énumération impossible dans un temps raisonnable. Il existe de très nombreux problèmes d’un grand intérêt pratique pour lesquels on ne connaît pas d’algorithme plus efficace qu’un test portant sur tous les sous ensembles d’un ensemble, ce qui implique un temps de calcul exponentiel par rapport à la taille de l’ensemble. De nos jours, certains problèmes nécessitent, pour être résolue une capacité de calcul phénoménale. L’ordinateur actuel étant limité dans sa puissance de calcul constitue une barrière dans la résolution de tels problèmes. C’est dans cette optique que de nouveaux concepts d’ordinateurs sont développés. Ainsi on tente de mettre sur pied des ordinateurs quantiques et des ordinateurs moléculaires. Ces derniers représentent certainement l’alternative de demain aux ordinateurs actuels. En utilisant l’ADN, contrairement aux ordinateurs actuels, cela permet de réaliser des opérations en parallèles (multitask) avec des vitesses de calculs phénoménales. De plus, l’ADN constitue un excellent moyen de stockage de données et ne demande qu’un apport infime en énergie. L’expérience qui a éveillé le monde des ordinateurs à ADN est celle d’Adleman. En 1994, Adleman, qui est un mathématicien de l’université de Californie du sud et qui possède également des connaissances en biologie, à résolut grâce à un ordinateur moléculaire le problème de chemin haméltonien (HPP : Hamiltonian Path Problem)
Date de soutenance
2006
Cote
TH1.5152
Pagination
103 p.
Illusatration
ill.
Format
30 cm.
Statut
Soutenue