Lamiae
Sommaire: Systèmes bio-inspires pour le traitement de l’informatique, application du DNA computing à la résolution de problèmes NP-complets
Résumé
Table des matières
Liste des figures
Liste des tableaux
Introduction générale
Chapitre1 : Les systèmes bio-inspirés
1.1 Introduction
1.2 Intelligence artificielle
1.3 Vie artificielle
1.3.1 Les critères de la vie artificielle
1.3.2 Les domaines de la vie artificielle
1.4 Les systèmes bio-inspirés
1.4.1 Pourquoi étudier les systèmes biologiques
1.4.2 Les types principaux des systèmes bio-inspirés
1.4.2.1 L’intelligence d’essaim ‘Swarm Intelligence
1.4.2.1.1 L’optimisation par Colonies de fourmis
1.4.2.1.2 La communication et l’auto-organisation chez les colonies d’abeilles
1.4.2.2 Les boids de Reynolds
1.4.2.3 Les essaims de particule (Particle Swarm)
1.4.2.4 Le calcul à l’ADN (DNA computing)
1.4.2.5 Les réseaux de neurones artificiels (Artificial Neural Network)
1.4.2.6 Algorithmes évolutionnaires (EA : Evolutionary Algorithms)
1.4.2.7 Système Immunitaire Artificielle (AIS : Artificial Immune System)
1.4.2.8 Les automates cellulaires
1.4.2.9 L-système
1.5 Conclusion
Chapitre2 : L’étude biologique de l’ADN
2.1 Introduction
2.2 L’ADN, le miracle
2.3 Où trouve-t-on l’ADN dans les organismes?
2.4 La structure de l’ADN
2.5 Les outils de la biologie moléculaire
2.5.1 Les enzymes
2.5.1.1 Les polymérases
2.5.1.2 Ligase
2.5.1.3 Enzymes de restrictions
2.5.2 Electrophorèse
2.5.3 PCR
2.5.4 L’ADN recombinant
2.5.5 Séquençage d’ADN
2.5.6 Synthèse d’ADN
2.6 Conclusion
Chapitre3 : L’expérience d’Adleman & les ordinateurs à l’ADN
3.1 Introduction
3.2 Le langage
3.3 Les machines de Turing et les systèmes d’insertion délétion
3.4 Les machines à l’ADN concrètes
3.4.1 L’expérience d’Adleman
3.4.1.1 Le problème du chemin hamiltonien (Hamiltonian path problem (HPP))
3.4.1.2 Algorithme d’Adleman
3.4.1.3 Exemple d’application de l’algorithme d’Adleman
3.4.2 Les travaux qui suivent le travail d’Adleman
3.4.3 Les limites actuelles des ordinateurs à l’ADN
3.5 Conclusion
Chapitre4 : Résolution des problèmes NP-complets par le calcul d’ADN
4.1 Introduction
4.2 Généralités sur la complexité des problèmes
4.2.1 Notion de complexité : Définition
4.2.2 Problèmes de décision et d’optimisation
4.2.3 Classement des problèmes
4.2.3.1 Problèmes « faciles », problèmes « difficiles »
4.2.3.2 Les classes P et NP
4.2.3.3 Classe NP-complet
4.2.3.4 Relation entre les classes
4.3 Les problèmes NP-complet les plus célèbres
4.3.1 Problème de satisfiabilité : SAT
4.3.2 Problème du voyageur de commerce
4.3.3 Problème de sac à dos (Knapsack problem)
4.3.4 Problèmes de 8 reines
4.4 Résolution de quelques problèmes NP-complet en utilisant le calcul d’ADN
4.4.1 Le problème de la satisfaisabilité
4.4.2 Le problème de voyageur de commerce (TSP : Traveling Salesman Problem)
4.5 Deux algorithmes proposés pour la résolution de TSP et SAT par le calcul d’ADN
4.5.1 Nouvel algorithme proposé pour la résolution du TSP
4.5.1.1 Etapes de l’algorithme
4.5.1.2 Exemple d’application
4.5.1.3 Discussion
4.5.2 Nouveaux algorithmes proposés pour la résolution de K-SAT
4.5.2.1 Algorithme1
4.5.2.1.1 Les étapes de l’algorithme1
4.5.2.1.3 Discussion
4.5.2.2 Algorithme2
4.5.2.2.1 Les étapes de l’algorithme2
4.5.2.2.2 Exemple d’application
4.5.2.3 Discussion
4.6 Conclusion
Conclusion générale
Bibliographie
Extrait du mémoire systèmes bio-inspires pour le traitement de l’informatique, application du DNA computing à la résolution de problèmes NP-complets
Chapitre 1 : Les systèmes bio-inspirés
1.1 Introduction
Des avancées récentes dans les techniques d’IA ont été réalisées en s’inspirant de phénomènes physiques (recuit simulé), ou biologiques (réseaux de neurones, algorithmes génétiques, sociétés d’insectes, [9]). Plus récemment, des tentatives sont menées pour utiliser les capacités de calcul massivement parallèle d’entités biologiques pour résoudre des problèmes NPComplets [84].
Ces différentes approches procèdent de la démarche suivante.
Application du DNA computing
Certains phénomènes naturels sont capables de mettre en oeuvre des heuristiques originales susceptibles de résoudre des problèmes pour lesquels il est difficile de trouver des solutions de manière déterministe par des algorithmes classiques.
De plus, ces heuristiques sont robustes, une défaillance d’un élément constitutif de l’heuristique ne mettant pas en péril l’heuristique dans son ensemble.
Ce premier chapitre est consacré pour l’inspiration biologique. On va parler un petit peu de l’intelligence artificielle et de la vie artificielle et d’une façon générale de systèmes bio-inspirés dans lesquels on va voir quelques système biologiques très intéressant tel que l’intelligence d’essaim, le système immunitaire, les réseaux de neurones …et comment utiliser les principes de ces systèmes pour trouver des nouvelles idées qui seront utilisées par la suite pour trouver de nouvelles techniques et résoudre différents problèmes.
Application du DNA computing
1.2 Intelligence artificielle
L’intelligence artificielle ou l’IA (Artificial Intelligence ou AI) peut être définie comme:
1 – Quatre vues:
– Penser comme un humain.
– Agir comme un humain.
– Penser raisonnablement.
– Agir raisonnablement.
Application du DNA computing
2 – Agir raisonnablement: Faire la bonne chose.
3 -Etudier des agents intelligents
L’intelligence artificielle apparaît dans les années cinquante, lorsque le développement des premiers ordinateurs donne à penser qu’ils seront rapidement capables de simuler la pensée. Le mathématicien britannique Alan Mathison Turing propose ainsi, en 1950, un test (appelé test de Turing) permettant d’évaluer l’intelligence d’une machine : un ordinateur est qualifié d’intelligent si, en communiquant avec lui à distance et par écrit, un utilisateur ne peut deviner s’il s’agit ou non d’un être humain [4]. Turing et d’autres chercheurs, comme Donald Michie, pensent qu’un tel ordinateur peut voir le jour avant la fin du XXe siècle. Mais les résultats ne sont pas à la hauteur des attentes, car les difficultés pour reproduire les mécanismes de l’intelligence humaine se révèlent considérables [4]. Toutefois, les recherches menées en intelligence artificielle permettent de concevoir des ordinateurs capables d’effectuer des déductions, d’apprendre à partir d’une expérience passée, ou de reconnaître des formes complexes. Aujourd’hui, les travaux réalisés sur la modélisation des connaissances et du raisonnement expert sont effectués dans le but de développer des systèmes experts et plus généralement des systèmes à bases de connaissances.
L’IA a connu de nombreux succès dans des applications extrêmement variées et particulièrement dans la conception de systèmes experts. Cependant au fil du temps, si elle a acquis le statut d’une science à part entière, elle s’est éloignée de son objet premier : créer des systèmes artificiels capables de reproduire les comportements intelligents de systèmes biologiques.
……….
Si le lien ne fonctionne pas correctement, veuillez nous contacter (mentionner le lien dans votre message)
Mémoire Online: Systèmes bio-inspires pour le traitement de l’informatique, application du DNA computing à la résolution de problèmes NP-complets (3.1 MO) (Cours PDF)
