A partir de cette page vous pouvez :
| Retourner au premier écran avec les dernières notices... |
Résultat de la recherche
4 résultat(s) recherche sur le tag 'complexite'
Affiner la recherche Interroger des sources externesInvitation to Fixed-Parameter Algorithms / R. NIEDERMEIER
Titre : Invitation to Fixed-Parameter Algorithms Type de document : texte imprimé Auteurs : R. NIEDERMEIER, Auteur Editeur : Oxford University Press Année de publication : 2006 Importance : 300 p. ISBN/ISSN/EAN : 0-19-856607-7 Langues : Inconnue (und) Tags : COMPLEXITE ALGORITHMIQUE Index. décimale : G1 G1 - Mathématiques Invitation to Fixed-Parameter Algorithms [texte imprimé] / R. NIEDERMEIER, Auteur . - [S.l.] : Oxford University Press, 2006 . - 300 p.
ISBN : 0-19-856607-7
Langues : Inconnue (und)
Tags : COMPLEXITE ALGORITHMIQUE Index. décimale : G1 G1 - Mathématiques Réservation
Réserver ce document
Exemplaires
Cote Support Localisation Section Notes Disponibilité G1 / 12995 Papier OUVRAGES GENERALITES Disponible
Titre : Computational Complexity Type de document : texte imprimé Auteurs : C. PAPADIMITRIOU, Auteur Editeur : Addison Wesley Année de publication : 1994 Langues : Inconnue (und) Tags : informatique theorique complexite Index. décimale : I1 I1 - Informatique Théorique Computational Complexity [texte imprimé] / C. PAPADIMITRIOU, Auteur . - [S.l.] : Addison Wesley, 1994.
Langues : Inconnue (und)
Tags : informatique theorique complexite Index. décimale : I1 I1 - Informatique Théorique Réservation
Réserver ce document
Exemplaires
Cote Support Localisation Section Notes Disponibilité I1 / 5085 Papier OUVRAGES INFORMATIQUE Disponible I1 / 5085-2 Papier OUVRAGES INFORMATIQUE Emprunté par: Michel Habib
Sorti jusqu'au 15/09/2011I1 / 5085-3 Papier OUVRAGES INFORMATIQUE Disponible
Titre : Impact de la Contrainte d'Incompatibilité sur la Complexité et l'Approximation des Problèmes d'Ordonnancement en Présence de Tâches-Couplées Type de document : texte imprimé Auteurs : Gilles SIMONIN, Auteur Année de publication : 2009 Langues : Français (fre) Tags : ORDONNANCEMENT TACHES-COUPLEES COMPLEXITE APPROXIMATION GRAPHE COMPATIBILITE Index. décimale : THE Thèses de doctorat Résumé : Les travaux présentés dans cette thèse portent sur l'étude de la complexité et de l'approximation des problèmes d'ordonnancement en présence de tâches-couplées sur un mono-processeur. Ces problèmes sont motivés par la modélisation d'un problème de robotique portant sur une torpille sous-marine d'exploration. Cette torpille a pour objectif d'exécuter deux types de tâches : celles d'acquisition et celles de traitement. Les tâches d'acquisition sont semblables à des tâches-couplées, et les tâches de traitement sont des tâches classiques. La torpille utilise différents capteurs pour réaliser les acquisitions, certains capteurs ne peuvent pas être utilisés en même temps pour cause d'interférences. Nous introduisons donc un graphe de compatibilité permettant de représenter les tâches d'acquisition pouvant avoir leurs exécutions qui se chevauchent. La torpille possède un monoprocesseur embarqué permettant d'exécuter toutes la tâches. La première partie de nos travaux s'intéresse à la modélisation du problème, aux différentes tâches utilisées et aux contraintes qui leur sont appliquées. Nous mettons en avant l'impact de la contrainte de compatibilité, nous forçant à utiliser la théorie des graphes pour analyser nos problèmes. Enfin, nous finissons cette partie avec un état de l'art sur les différents résultats portant sur l'ordonnancement de tâches-couplées sur mono-processeur, et sur des problèmes de recouvrement de sommets dans des graphes. Dans une seconde partie, nous donnons la classification des problèmes possibles en faisant varier les paramètres des tâches-couplées. Nous donnons des preuves de complexité pour certains problèmes se trouvant à la limite entre la polynomialité et la $\mathcal{NP}$-complétude selon les valeurs des paramètres. Pour chaque problème $\mathcal{NP}$-complet, nous proposons des algorithmes d'approximation en temps polynomial et analysons les bornes obtenues selon les paramètres ou les topologies du graphe de compatibilité. L'ensemble des résultats est décomposé en trois chapitres prenant chacun en compte l'introduction d'une contrainte (d'incompatibilité et/ou de précédence). Tout au long de cette partie nous cherchons à montrer l'impact de l'introduction de la contrainte d'incompatibilité sur la complexité des problèmes d'ordonnancement avec tâches-couplées, à travers les preuves de NP-complétude et les techniques employées pour résoudre ou approximer un problème. Directeur(s) de thèse : KONIG J.C. Co-directeur(s) de thèse : GIROUDEAU R. Rapporteur(s) : BAMPIS E.;BRAUNER VETTIER N. Examinateur(s) : HANEN C.;PAUL C. Date de soutenance : 01/12/2009 Impact de la Contrainte d'Incompatibilité sur la Complexité et l'Approximation des Problèmes d'Ordonnancement en Présence de Tâches-Couplées [texte imprimé] / Gilles SIMONIN, Auteur . - 2009.
Langues : Français (fre)
Tags : ORDONNANCEMENT TACHES-COUPLEES COMPLEXITE APPROXIMATION GRAPHE COMPATIBILITE Index. décimale : THE Thèses de doctorat Résumé : Les travaux présentés dans cette thèse portent sur l'étude de la complexité et de l'approximation des problèmes d'ordonnancement en présence de tâches-couplées sur un mono-processeur. Ces problèmes sont motivés par la modélisation d'un problème de robotique portant sur une torpille sous-marine d'exploration. Cette torpille a pour objectif d'exécuter deux types de tâches : celles d'acquisition et celles de traitement. Les tâches d'acquisition sont semblables à des tâches-couplées, et les tâches de traitement sont des tâches classiques. La torpille utilise différents capteurs pour réaliser les acquisitions, certains capteurs ne peuvent pas être utilisés en même temps pour cause d'interférences. Nous introduisons donc un graphe de compatibilité permettant de représenter les tâches d'acquisition pouvant avoir leurs exécutions qui se chevauchent. La torpille possède un monoprocesseur embarqué permettant d'exécuter toutes la tâches. La première partie de nos travaux s'intéresse à la modélisation du problème, aux différentes tâches utilisées et aux contraintes qui leur sont appliquées. Nous mettons en avant l'impact de la contrainte de compatibilité, nous forçant à utiliser la théorie des graphes pour analyser nos problèmes. Enfin, nous finissons cette partie avec un état de l'art sur les différents résultats portant sur l'ordonnancement de tâches-couplées sur mono-processeur, et sur des problèmes de recouvrement de sommets dans des graphes. Dans une seconde partie, nous donnons la classification des problèmes possibles en faisant varier les paramètres des tâches-couplées. Nous donnons des preuves de complexité pour certains problèmes se trouvant à la limite entre la polynomialité et la $\mathcal{NP}$-complétude selon les valeurs des paramètres. Pour chaque problème $\mathcal{NP}$-complet, nous proposons des algorithmes d'approximation en temps polynomial et analysons les bornes obtenues selon les paramètres ou les topologies du graphe de compatibilité. L'ensemble des résultats est décomposé en trois chapitres prenant chacun en compte l'introduction d'une contrainte (d'incompatibilité et/ou de précédence). Tout au long de cette partie nous cherchons à montrer l'impact de l'introduction de la contrainte d'incompatibilité sur la complexité des problèmes d'ordonnancement avec tâches-couplées, à travers les preuves de NP-complétude et les techniques employées pour résoudre ou approximer un problème. Directeur(s) de thèse : KONIG J.C. Co-directeur(s) de thèse : GIROUDEAU R. Rapporteur(s) : BAMPIS E.;BRAUNER VETTIER N. Examinateur(s) : HANEN C.;PAUL C. Date de soutenance : 01/12/2009 Réservation
Réserver ce document
Exemplaires
Cote Support Localisation Section Notes Disponibilité THE-09 / 13781 Non renseigné THESES INFORMATIQUE Disponible 
Titre : Problèmes Algorithmiques dans les Réseaux Tout-Optique Type de document : texte imprimé Auteurs : J. PALAYSI, Auteur Année de publication : 2002 Langues : Français (fre) Tags : RESEAUX WDM MINIMISATION DE CHARGE RESEAUX WDM MINIMISATION DE CHARGE COLORATION DE CHAINES ROUTAGE TOUT-OPTIQUE COLORATION SUR LISTES GRAPHES ALGORITHMES COMPLEXITE NETWORKS WDM LOAD MINIMIZATION PATH COLORING ALL-OPTICAL ROUTING LIST COLORING GRAPHS AGORITHMS COMPLEXITY Index. décimale : THE Thèses de doctorat Résumé : L'avènement des réseaux tout-optique fait apparaître ou reapparaîre des problèmes algorithmiques théoriques parmi lesquels : la Minimisation de Charge, la Coloration de Chaînes, le Routage Tout-Optique et la Coloration sur Listes. Les trois premiers problèmes sont NP difficiles en général. Nous montrons plus precisément que la Coloration de Chaînes dans les grilles et les tores est No-APX. Nous montrons également qu'il existe des algorithmes approchants pour ces trois problèmes lorsque les instances sont réduites à des réseaux en forme de grille ou de tore et que les routes recherchées doivent être de type ligne-colonne. La Coloration sur Listes est un problème NP-complet en général. Il s'agit d'une généralisation du problème bien connu de coloration des sommets d'un graphe. Nous étudions d'abord l'intérêt de connaître une coloration classique d'un graphe dans la résolution d'une instance de Coloration sur Listes. Nous nous intéressons ensuite à la liste-colorabilité des graphes bipartis.
The raising of all-optical networks makes several theoretical algorithmic problems appear or reappear among which we can find : Load Minimization, Path Coloring, All-Optical Routing and List Coloring. The first three problems are NP-hard in general. We show more precisely that Path Coloring in meshes and toroidal meshes is No-APX. We also show that these problems can be solved by approximation algorithms if instances are reduced to mesh networks or toroidal mesh networks and if the paths we are looking for have row-column type. The List Coloring is a NP-complete problem in general. This is a variation and a generalization of the well-known vertex coloring problem. First, we study if knowing a classic coloring of a graph helps to solve an instance of List Coloring. Then we focus on bipartite graph choosability.Directeur(s) de thèse : KONIG J.C. Co-directeur(s) de thèse : COGIS O. Président du jury : CHEIN M. Rapporteur(s) : GERMA A.;BARTH D. Date de soutenance : 19/12/2002 Problèmes Algorithmiques dans les Réseaux Tout-Optique [texte imprimé] / J. PALAYSI, Auteur . - 2002.
Langues : Français (fre)
Tags : RESEAUX WDM MINIMISATION DE CHARGE RESEAUX WDM MINIMISATION DE CHARGE COLORATION DE CHAINES ROUTAGE TOUT-OPTIQUE COLORATION SUR LISTES GRAPHES ALGORITHMES COMPLEXITE NETWORKS WDM LOAD MINIMIZATION PATH COLORING ALL-OPTICAL ROUTING LIST COLORING GRAPHS AGORITHMS COMPLEXITY Index. décimale : THE Thèses de doctorat Résumé : L'avènement des réseaux tout-optique fait apparaître ou reapparaîre des problèmes algorithmiques théoriques parmi lesquels : la Minimisation de Charge, la Coloration de Chaînes, le Routage Tout-Optique et la Coloration sur Listes. Les trois premiers problèmes sont NP difficiles en général. Nous montrons plus precisément que la Coloration de Chaînes dans les grilles et les tores est No-APX. Nous montrons également qu'il existe des algorithmes approchants pour ces trois problèmes lorsque les instances sont réduites à des réseaux en forme de grille ou de tore et que les routes recherchées doivent être de type ligne-colonne. La Coloration sur Listes est un problème NP-complet en général. Il s'agit d'une généralisation du problème bien connu de coloration des sommets d'un graphe. Nous étudions d'abord l'intérêt de connaître une coloration classique d'un graphe dans la résolution d'une instance de Coloration sur Listes. Nous nous intéressons ensuite à la liste-colorabilité des graphes bipartis.
The raising of all-optical networks makes several theoretical algorithmic problems appear or reappear among which we can find : Load Minimization, Path Coloring, All-Optical Routing and List Coloring. The first three problems are NP-hard in general. We show more precisely that Path Coloring in meshes and toroidal meshes is No-APX. We also show that these problems can be solved by approximation algorithms if instances are reduced to mesh networks or toroidal mesh networks and if the paths we are looking for have row-column type. The List Coloring is a NP-complete problem in general. This is a variation and a generalization of the well-known vertex coloring problem. First, we study if knowing a classic coloring of a graph helps to solve an instance of List Coloring. Then we focus on bipartite graph choosability.Directeur(s) de thèse : KONIG J.C. Co-directeur(s) de thèse : COGIS O. Président du jury : CHEIN M. Rapporteur(s) : GERMA A.;BARTH D. Date de soutenance : 19/12/2002 Réservation
Réserver ce document
Exemplaires
Cote Support Localisation Section Notes Disponibilité THE-02 / 7478 Papier THESES INFORMATIQUE Disponible Documents numériques
Fichier (PDF)URL
