F Nous contacter

0

Documents  68Q25 | enregistrements trouvés : 195

O

-A +A

Sélection courante (0) : Tout sélectionner / Tout déselectionner

P Q

2 y

Research School

Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des réseaux biologiques, comme par exemple des réseaux d'interaction de protéines ou des réseaux métaboliques. Graph Motif a fait depuis l'objet d'une attention particulière qui se traduit par un nombre relativement élevé de publications, essentiellement orientées autour de sa complexité algorithmique.
Je présenterai un certain nombre de résultats algorithmiques concernant le problème Graph Motif, en particulier des résultats de FPT (Fixed-Parameter Tractability), ainsi que des bornes inférieures de complexité algorithmique.
Ceci m'amènera à détailler diverses techniques de preuves dont certaines sont plutôt originales, et qui seront je l'espère d'intérêt pour le public.
Le problème Graph Motif est défini comme suit : étant donné un graphe sommet colorié G=(V,E) et un multi-ensemble M de couleurs, déterminer s'il existe une occurrence de M dans G, c'est-à-dire un sous ensemble V' de V tel que
(1) le multi-ensemble des couleurs de V' correspond à M,
(2) le sous-graphe G' induit par V' est connexe.
Ce problème a été introduit, il y a un peu plus de 10 ans, dans le but de rechercher des motifs fonctionnels dans des ...

05C15 ; 05C85 ; 05C90 ; 68Q17 ; 68Q25 ; 68R10 ; 92C42 ; 92D20

... Lire [+]

2 y

Research talks

A serious problem common to all interval algorithms is that they suffer from wrapping effects, i.e. unnecessary growth of approximations during a computation. This is essentially connected to functional dependencies inside vectors of data computed from the same inputs. Reducing these effects is an important issue in interval arithmetic, where the most successful approach uses Taylor models.
In TTE Taylor models have not been considered explicitly, as they use would not change the induced computability, already established using ordinary interval computations. However for the viewpoint of efficiency, they lead to significant improvements.
In the talk we report on recent improvements on the iRRAM software for exact real arithmetic (ERA) based on Taylor models. The techniques discussed should also easily be applicable to other software for exact real computations as long as they also are based on interval arithmetic.
As instructive examples we consider the one-dimensional logistic map and a few further discrete dynamical systems of higher dimensions
Joint work with Franz Brauße, Trier, and Margarita Korovina, Novosibirsk.
A serious problem common to all interval algorithms is that they suffer from wrapping effects, i.e. unnecessary growth of approximations during a computation. This is essentially connected to functional dependencies inside vectors of data computed from the same inputs. Reducing these effects is an important issue in interval arithmetic, where the most successful approach uses Taylor models.
In TTE Taylor models have not been considered ...

68Q25 ; 03D60 ; 65Y15

... Lire [+]

2 y

Research talks

De nombreux problèmes d'optimisation sont NP-complets. Nous ne connaissons pas de problème NP-complet qui admette un algorithme optimal de résolution s'exécutant en temps polynomial en la taille de l'instance (sinon P=NP serait établi), et l'intuition commune est que P =/= NP. Pour ces problèmes, la recherche de solutions optimales peut donc être prohibitive. Les algorithmes d'approximation offrent un compromis intéressant: par définition, ils s'exécutent en temps polynomial et fournissent des solutions dont la qualité est garantie. Nous introduirons la notion d'algorithme d'approximation et de schéma d'approximation en temps polynomial, et nous illustrerons ces notions sur de nombreux exemples. Nous montrerons également comment établir qu'un problème n'admet pas d'algorithme d'approximation (à moins que P=NP), ou comment établir une borne inférieure au facteur d'approximation de tout algorithme d'approximation (sauf si P=NP). De nombreux problèmes d'optimisation sont NP-complets. Nous ne connaissons pas de problème NP-complet qui admette un algorithme optimal de résolution s'exécutant en temps polynomial en la taille de l'instance (sinon P=NP serait établi), et l'intuition commune est que P =/= NP. Pour ces problèmes, la recherche de solutions optimales peut donc être prohibitive. Les algorithmes d'approximation offrent un compromis intéressant: par définition, ils ...

68W25 ; 68Q25 ; 68T20

... Lire [+]

y

Publications du departement de mathematiquess

Localisation : 1er étage/Congrès/AVIG

algorithme # automate # complexite des algorithmes # langage

68Q25

... Lire [+]

y

Publications du departement de mathematiquess

Localisation : 1er étage/Congrès/AVIG

algorithme # automate # complexite des algorithmes # langage

68Q25

... Lire [+]

V


ISBN 978-0-8186-0644-1

Localisation : 1er étage/Congrès/PONT

algorithme # automatique # informatique # ordinateur

68-06 ; 68Q25 ; 68Q30 ; 68Q70 ; 68R10

... Lire [+]

V


ISBN 978-2-7261-0638-9

Publications i.n.r.i.a.

Localisation : 1er étage/Congrès/SOPH

algorithm ique # algorithme dynamique # algorithme geometrique # algorithme probabiliste # combinatoire # geometrie algorithmique

68Q25 ; 68Qxx ; 68R05 ; 68Uxx

... Lire [+]

V


ISBN 978-0-8186-0742-4

Localisation : 1er étage/Congrès/PARI

algorithme # application biomédicale # architecture # automate # bord # classification des données # connaissance de base de reconnaissance de forme # inférence et apprentissage # limite # tomagraphie # traitement des images # traitement du signal # vision

68Q20 ; 68Q25 ; 68T05 ; 68T10 ; 68T30 ; 68Txx ; 68U05 ; 68U10 ; 68U30 ; 68Uxx

... Lire [+]

V

- 120 p.

Localisation : Salle de manutention

complexité des algorithmes # informatique théorique # mathématique discrète

68Q25 ; 68Q45 ; 68Q55 ; 68Qxx ; 94Axx ; 94Bxx

... Lire [+]

V

- 483 p.
ISBN

Astérisque , 0266

Localisation : Périodique 1er étage

équation d'onde # optique géométrique # champs de vecteur # problème de Goursat # focntion L # valeur spéciale # théorie d'Iwasawa # motif # fonction L p-adique # conjecture de Beilinson # lois de réciprocité # conjecture de Leopold # variété projective # fibré en droite # tenseur de courbure # fibré positif # fibré ample # fibré nef # faisceau d'idéau multiplicateur de Nadel # théorème d'annulation # système linéaire adjoint # conjecture de Fujita # mouvement Brownien dans un environnement aléatoire # mesure typique et moyennée # méthode de grossissement des obstacles # mécanique céleste # petit diviseur # théorie KAM # comportement chatique # arbre # fibré # groupe # hakénien # hyperbolique # kleinien # lamination # quasi-conforme # représentation # surface # Teichmüller # variété # résonance # quasi-mode # formule de trace # diffusion # conjecture de Langlands # forme automorphe # variété de Shimura # groupe unitaire # groupe formel # algèbre de Lie simple # réplique-symétrique # champs moyen # état pur # modèle de Hopfield # modèle de Sherrington-Kirkpatrick # perceptron binaire # 1-forme rationelle # fonction localement analytique # variété abélienne # période p-adique # opérateur de Frobenius # polylogarithme p-adique # holonomie # système extèrieur différentiel # calcul classique # calcul quantique # univers constructif # problème P/NP # factorisation rapide # algorithme de Shor # conjecture de Kapler # empilement de sphère # Lie # ordinateur # plongement # simple # toral # torsion équation d'onde # optique géométrique # champs de vecteur # problème de Goursat # focntion L # valeur spéciale # théorie d'Iwasawa # motif # fonction L p-adique # conjecture de Beilinson # lois de réciprocité # conjecture de Leopold # variété projective # fibré en droite # tenseur de courbure # fibré positif # fibré ample # fibré nef # faisceau d'idéau multiplicateur de Nadel # théorème d'annulation # système linéaire adjoint # conjecture de ...

35L40 ; 11Fxx ; 11Gxx ; 11Rxx ; 11Sxx ; 14Fxx ; 14Gxx ; 14C30 ; 14F17 ; 14J60 ; 60K40 ; 82D30 ; 70F10 ; 70F15 ; 70K55 ; 37J05 ; 57M07 ; 57M50 ; 20E08 ; 51M10 ; 35L05 ; 35P25 ; 11F70 ; 11G18 ; 11R39 ; 14L05 ; 17B20 ; 60G70 ; 60G15 ; 90C27 ; 14Hxx ; 14Kxx ; 14Lxx ; 30Fxx ; 30Gxx ; 32Jxx ; 53C10 ; 53B05 ; 58A15 ; 68Q05 ; 68P25 ; 68Q25 ; 81P99 ; 51M04 ; 51M16 ; 52C17 ; 20-XX ; 22-XX

... Lire [+]

V

- 306 p.
ISBN 978-0-8218-1184-9

DIMACS series in discrete mathematics and theoretical computer science , 0050

Localisation : Collection RdC

algorithme de calcul # algorithme numérique # algorithmique # algèbre numérique # calcul des algorithmes numériques # calcul parallèle # complexité des algorithmes # gestion de mémoire # infographie # informatique théorique # mathématique discrète # modèle de calcul # structure des données # traitement des données

65Fxx ; 65Y20 ; 68Pxx ; 68Q05 ; 68Q25 ; 68R01 ; 68R10 ; 68U05 ; 68W01 ; 68W40

... Lire [+]

V

- 782 p.
ISBN 978-3-540-58201-4

Lecture notes in computer science , 0775

Localisation : Collection RdC

algorithme # algorithme de communication # algorithme des graphes # automate asynchrone # automate cellulaire # chiffrement des données # complexité aléatoire # complexité du calcul informatique # concordance avec un modèle # concurence # configuration machine # connectivité # encryptage des donnés # graphe # géométrie de l'informatique # informatique graphique # informatique théorique # langage et programmation d'automate # langage formel # logique # mathématique discrète # réseau d'interconnection # réécriture des systèmes # structure des données # sémantique # technique de programmation # vérification de programme algorithme # algorithme de communication # algorithme des graphes # automate asynchrone # automate cellulaire # chiffrement des données # complexité aléatoire # complexité du calcul informatique # concordance avec un modèle # concurence # configuration machine # connectivité # encryptage des donnés # graphe # géométrie de l'informatique # informatique graphique # informatique théorique # langage et programmation d'automate # langage formel # ...

68P05 ; 68Pxx ; 68Q25 ; 68Q68 ; 68Q80

... Lire [+]

V

- 322 p.
ISBN 978-3-540-58691-3

Lecture notes in computer science , 0877

Localisation : Collection RdC

CM-champ # algorithme # complexité # courbe elliptique rationnelle # courbe hyperelliptique # criblage de treillis # cycle d'isogénie # difficulté à trouver des témoins fiables # division d'essais # informatique # méthode symbolique en mathématique algorithmique # ordinateur quantique # réduction # théorie des nombres # théorie des nombres algorithmique # variété CM abelienne CM-champ # algorithme # complexité # courbe elliptique rationnelle # courbe hyperelliptique # criblage de treillis # cycle d'isogénie # difficulté à trouver des témoins fiables # division d'essais # informatique # méthode symbolique en mathématique algorithmique # ordinateur quantique # réduction # théorie des nombres # théorie des nombres algorithmique # variété CM abelienne

11T71 ; 11Yxx ; 68P25 ; 68Q25 ; 68Q40

... Lire [+]

V


ISBN 978-0-8186-0742-4

Localisation : Congès 1er étage (PARI/1986)

algorithme # application biomédicale # architecture # automate # bord # classification des données # connaissance de base de reconnaissance de forme # inférence et apprentissage # limite # tomographie # traitement des images # traitement du signal # vision

68Q20 ; 68Q25 ; 68T05 ; 68T10 ; 68T30 ; 68Txx ; 68U05 ; 68U10 ; 68U30 ; 68Uxx

... Lire [+]

V

- 444 p.
ISBN 978-3-540-17187-4

Lecture notes in computer science , 0243

Localisation : Collection RdC

algorithme # analyse des algorithmes # logique # programmation logique # structure des données # traitement de données

68P05 ; 68Pxx ; 68Q25 ; 68Q45

... Lire [+]

V

- 236 p.
ISBN 978-3-211-81816-9

C.I.S.M. courses and lectures , 0284

Localisation : Colloque 1er étage (Udin/1983)

68Q20 ; 68Q25

... Lire [+]

V

- 252 p.
ISBN 978-3-540-55121-8

Lecture notes in computer science , 0570

Localisation : Collection RdC

algorithme # algorithme parallèle # analyse des algorithmes # circuit # classe de complexité # complexité # géométrie de l'informatique # gestion des systèmes # grammaire # information des systèmes # informatique théorique # logique # logique mathématique # parallèle # reécriture des systèmes # structure de données # théorie des graphes # traitement de données algorithme # algorithme parallèle # analyse des algorithmes # circuit # classe de complexité # complexité # géométrie de l'informatique # gestion des systèmes # grammaire # information des systèmes # informatique théorique # logique # logique mathématique # parallèle # reécriture des systèmes # structure de données # théorie des graphes # traitement de données

03Dxx ; 68D05 ; 68P05 ; 68Q25 ; 94Cxx

... Lire [+]

V

- 245 p.
ISBN 978-3-540-16444-9

Lecture notes in computer science , 0215

Localisation : Collection RdC

algorithme # algorithmique # informatique théorique

68N05 ; 68Nxx ; 68Q20 ; 68Q25 ; 68Qxx

... Lire [+]

V


ISBN 978-0-8218-5500-3

Proceeding of symposia in applied mathematics , 0044

Localisation : Collection RdC

calcul du volume des corps convexes # chaîne de Markov se mélangeant rapidement # combinatoire probabiliste # graphe aléatoire # inégalité isopérimétrique discrète # méthode de Fourier finie

05C80 ; 52A20 ; 60C05 ; 60J15 ; 68Q25

... Lire [+]

V

- 310 p.
ISBN 978-3-540-62592-6

Lecture notes in computer science , 1203

Localisation : Collection RdC

algorithme # calcul informatique # complexité des algorithmes # géométrie de l'informatique # informatique graphique # mathématique discrète # mode de calcul # modèle de calcul # modélisation d'objet # méthodologie # structure des données

68P05 ; 68Q05 ; 68Q10 ; 68Q25 ; 68Qxx

... Lire [+]

Nuage de mots clefs ici

Ressources Electroniques

Books & Print journals

Recherche avancée


0
Z