Download Free Contribution A Lalgorithmique Non Numerique Parallele Book in PDF and EPUB Free Download. You can read online Contribution A Lalgorithmique Non Numerique Parallele and write the review.

LE BUT DE CETTE THESE EST D'ETUDIER LA PARALLELISATION DES ALGORITHMES DES FAMILLES A* ET MINIMAX, ISSUES DE L'INTELLIGENCE ARTIFICIELLE, POUR LES PROBLEMES D'OPTIMISATION COMBINATOIRE. DANS LES DEUX PREMIERS CHAPITRES, NOUS MONTRONS QUE CES METHODES UTILISENT LE MEME PARADIGME D'EXPLORATION D'ESPACES DE RECHERCHE QUE LES ALGORITHMES BRANCH AND BOUND ET DEGAGEONS LES PARTIES SUSCEPTIBLES A ETRE PARALLELISEES. LE TROISIEME CHAPITRE FAIT LE POINT SUR L'EVOLUTION DES MACHINES PARALLELES, LES DIFFERENTS TYPES DE PARALLELISME POSSIBLES DANS UNE EXPLORATION D'ESPACE DE RECHERCHE ET LES TRAVAUX ANTERIEURES DES FAMILLES A* ET MINIMAX. NOUS PROPOSONS, AU CHAPITRE QUATRE, UNE NOUVELLE STRUCTURE DE DONNEES APPELEE CONCURRENT TREAP, A DOUBLE CRITERE (PRIORITE ET CLE) ET ACCES CONCURRENT POUR UNE IMPLANTATION PARALLELE EFFICACE DE A* (CAS). CETTE STRUCTURE PERMET D'EVITER LE PROBLEME D'INTERBLOCAGE DES STRUCTURES COMBINEES CLASSIQUES. LE CHAPITRE CINQ PRESENTE UN MODELE THEORIQUE POUR LA FAMILLE MINIMAX, PERMETTANT LE CALCUL DES BORNES D'ACCELERATION ET D'EFFICACITE POUR UN ARBRE UNIFORME DONNE. DEUX PARALLELISATIONS DE L'ALGORITHME ALPHA-BETA SONT PROPOSEES DANS LE DERNIER CHAPITRE. L'UNE (SABA), POUR MACHINES SIMD A PARALLELISME MASSIF, PERMET LA VALIDATION DU MODELE THEORIQUE. L'AUTRE (CABP), POUR MACHINES MIMD A MEMOIRE PARTAGEE, EST FONDEE SUR L'EXPLORATION D'UN ARBRE CRITIQUE ET L'INTRODUCTION D'UN DEGRE D'ELAGAGES CONCURRENT K. CE PARAMETRE AUTORISE UN CONTROLE DYNAMIQUE DU SURCOUT D'EXPLORATION EN COURS DE RECHERCHE
Combinatorial (or discrete) optimization is one of the most active fields in the interface of operations research, computer science, and applied math ematics. Combinatorial optimization problems arise in various applications, including communications network design, VLSI design, machine vision, air line crew scheduling, corporate planning, computer-aided design and man ufacturing, database query design, cellular telephone frequency assignment, constraint directed reasoning, and computational biology. Furthermore, combinatorial optimization problems occur in many diverse areas such as linear and integer programming, graph theory, artificial intelligence, and number theory. All these problems, when formulated mathematically as the minimization or maximization of a certain function defined on some domain, have a commonality of discreteness. Historically, combinatorial optimization starts with linear programming. Linear programming has an entire range of important applications including production planning and distribution, personnel assignment, finance, alloca tion of economic resources, circuit simulation, and control systems. Leonid Kantorovich and Tjalling Koopmans received the Nobel Prize (1975) for their work on the optimal allocation of resources. Two important discover ies, the ellipsoid method (1979) and interior point approaches (1984) both provide polynomial time algorithms for linear programming. These algo rithms have had a profound effect in combinatorial optimization. Many polynomial-time solvable combinatorial optimization problems are special cases of linear programming (e.g. matching and maximum flow). In addi tion, linear programming relaxations are often the basis for many approxi mation algorithms for solving NP-hard problems (e.g. dual heuristics).
Combinatorial (or discrete) optimization is one of the most active fields in the interface of operations research, computer science, and applied math ematics. Combinatorial optimization problems arise in various applications, including communications network design, VLSI design, machine vision, air line crew scheduling, corporate planning, computer-aided design and man ufacturing, database query design, cellular telephone frequency assignment, constraint directed reasoning, and computational biology. Furthermore, combinatorial optimization problems occur in many diverse areas such as linear and integer programming, graph theory, artificial intelligence, and number theory. All these problems, when formulated mathematically as the minimization or maximization of a certain function defined on some domain, have a commonality of discreteness. Historically, combinatorial optimization starts with linear programming. Linear programming has an entire range of important applications including production planning and distribution, personnel assignment, finance, alloca tion of economic resources, circuit simulation, and control systems. Leonid Kantorovich and Tjalling Koopmans received the Nobel Prize (1975) for their work on the optimal allocation of resources. Two important discover ies, the ellipsoid method (1979) and interior point approaches (1984) both provide polynomial time algorithms for linear programming. These algo rithms have had a profound effect in combinatorial optimization. Many polynomial-time solvable combinatorial optimization problems are special cases of linear programming (e.g. matching and maximum flow). In addi tion, linear programming relaxations are often the basis for many approxi mation algorithms for solving NP-hard problems (e.g. dual heuristics)."
LE BUT DE CETTE THESE EST D'ETUDIER LA PARALLELISATION DES METHODES DE RESOLUTION DES PROBLEMES D'OPTIMISATION COMBINATOIRE REPUTES NP-DIFFICILES: LES PROBLEMES DE RECHERCHE ARBORESCENTE PAR SEPARATION ET EVALUATION OU BRANCH AND BOUND. ELLE EST COMPOSEE DE TROIS PARTIES COMPLEMENTAIRES. DANS LA PREMIERE PARTIE, NOUS PRESENTONS LES DIFFERENTES DEFINITIONS ESSENTIELLES AU BRANCH AND BOUND. LE PARALLELISME INTRINSEQUE A CETTE METHODE EST DEGAGE ET UN MODELE D'EVALUATION DE PERFORMANCES DES BRANCH AND BOUND PARALLELES EST INTRODUIT, (CHAPITRE 1). LES DIFFERENTS PHENOMENES D'ANOMALIES D'ACCELERATION ET LA LIMITE DES SOLUTIONS CONNUES SONT PRESENTES DANS LE CHAPITRE 2. LE CHAPITRE 3 POSE LES PROBLEMES CLASSIQUES SOULEVES PAR L'IMPLEMENTATION PARALLELE. LA DEUXIEME PARTIE S'ATTACHE A PROPOSER DES SOLUTIONS A DES PROBLEMES PRIMORDIAUX: 1) LES ANOMALIES D'ACCELERATIONS, (CHAPITRE 5); DES BORNES SERREES AINSI QU'UNE PROPRIETE DE PREDISPOSITION AUX ANOMALIES SONT INTRODUITES ET PERMETTENT DES CHOIX PRECIS PARMI DIFFERENTES REGLES, 2) LA GRANULARITE DU TRAVAIL ALLOUE AUX PROCESSEURS, (CHAPITRE 6); LES GAINS ET SURCOUTS MIS EN EVIDENCE POUR UN PROCEDE DE SEPARATION POLYTOMIQUE PERMETTENT DE PROUVER SON INTERET, 3) L'ACCES AUX DONNEES PARTAGEES, (CHAPITRE 7); DES STRUCTURES DE DONNEES BIEN ADAPTEES AU BRANCH AND BOUND SONT ETUDIEES ET COMPAREES; POUR RESOUDRE LA CONTENTION D'ACCES A LA MEMOIRE, LES OPERATIONS DE BASES SUR CES STRUCTURES SONT RENDUES CONCURRENTES; LEURS PERFORMANCES SONT CONSERVEES ET LE SURCOUT D'IMPLEMENTATION REDUIT PAR UNE METHODE DE MARQUAGE, 4) L'EQUILIBRAGE DE CHARGE DES RESEAUX D'INTERCONNEXION DE PROCESSEURS, (CHAPITRE 8); UNE NOUVELLE FONCTION DE CHARGE ET UNE REGLE DE DECISION D'EQUILIBRAGE S'ADAPTANT D'ELLE-MEME A L'EVOLUTION DE LA RESOLUTION SONT DEVELOPPEES ET CONDUISENT A LA DESCRIPTION D'UN BRANCH AND BOUND DISTRIBUE. ENFIN, DANS LA TROISIEME PARTIE, NOUS TESTONS CES SOLUTIONS EN CONCEVANT DES BRANCH AND BOUND PARALLELES EFFICACES POUR DEUX PROBLEMES REPUTES DIFFICILES: 1) L'AFFECTATION QUADRATIQUE, CHAPITRE 9, OU LES PROBLEMES DE GRANULARITE ET D'ACCES AUX DONNEES SONT IMPORTANTS, 2) LE SAC-A-DOS MULTIDIMENSIONNEL, CHAPITRE 10, OU L'INTERET D'UNE SEPARATION POLYTOMIQUE POUR LA GRANULARITE SE CONFIRME
CETTE THESE SE SITUE DANS LE CADRE DE L'ALGORITHMIQUE PARALLELE NON NUMERIQUE. DEUX GRANDS POINTS SONT PRINCIPALEMENT ABORDES, LES STRUCTURES DE DONNEES SUR ARCHITECTURES A MEMOIRE DISTRIBUEE, A TRAVERS LA MACHINE DICTIONNAIRE, ET L'ALGORITHMIQUE PARALLELES POUR LES GRAPHES, AVEC LA FERMETURE TRANSITIVE ET LA RECONNAISSANCE DES ORDRES D'INTERVALLES