F Nous contacter

0

Documents  68Q25 | enregistrements trouvés : 197

O

-A +A

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

P Q

2 y

Research talks

The partially disjoint paths problem asks for paths $P_1, \ldots,P_k$ between given pairs of terminals, while certain pairs of paths $P_i$,$P_j$ are required to be disjoint. With the help of combinatorial group theory, we show that, for fixed $k$, this problem can be solved in polynomial time for planar directed graphs. We also discuss related problems. No specific foreknowledge is required.

05C10 ; 05C20 ; 05C25 ; 05C38 ; 68Q25 ; 90C27

... Lire [+]

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

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 [+]

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 [+]

V

- ix; 523 p.
ISBN 978-0-12-697540-6

Localisation : Colloque RdC

analyse numérique # algorithme # complexité de calcul # programmation

00Bxx ; 68-06 ; 68W99 ; 68Q25

... Lire [+]

V

- xv; 554 p.
ISBN 978-3-7643-7128-9

Trends in mathematics

Localisation : Colloque RdC

informatique # arbre # algorithme # combinatoire # générateur de nombres aléatoires # optimisation # évaluation de la performance

05-XX ; 60C05 ; 60Gxx ; 68P30 ; 68Q25 ; 68Rxx ; 68W20 ; 68W40 ; 90B15 ; 68-06 ; 68R10 ; 68R05 ; 00B25

... Lire [+]

V

- xiii; 557 p.
ISBN 978-3-7643-6933-0

Trends in mathematics

Localisation : Colloque RdC

informatique # arbre # algorithme # combinatoire # générateur de nombres aléatoires # optimisation # évaluation de la performance

68M20 ; 68Q25 ; 68P30 ; 68Rxx ; 68W20 ; 90B15 ; 00B25 ; 05-06 ; 68-06

... Lire [+]

y

- xi; 340 p.
ISBN 978-3-7643-6430-4

Trends in mathematics

Localisation : Colloque RdC

informatique # arbre # algorithme # combinatoire # générateur de nombres aléatoires # optimisation # évaluation de la performance

68W05 ; 00B25 ; 68-06 ; 68Rxx ; 68Q25

... Lire [+]

V

- xvi; 279 p.
ISBN 978-2-85629-363-8

Séminaires & congrès , 0026

Localisation : Collection 1er étage

Actions naturelles # algèbres de Hopf # algèbres de Lie tordues # algèbres pré-Lie # algèbre dendriforme # algorithme de Buchberger # bases de Gröbner # catégories d'arbres # catégories de Koszul # catégorification # cohomologie de Hochschild # complétion de Knuth-Bendix # confluence # co-opérade de Poisson # diagrammes de flux et de programmation # enchevêtrement # espaces de configurations # foncteur de Schur # forme canonique # Haskell # Homologie des E_n-algèbres # identités entre les relations # méthodes de renormalisation perturbatives # n-catégorie # opérade # opérade des petits disques # polygraphe # pro # prop # présentation par générateurs et relations # réécriture # réécriture de diagrammes # renormalisation # S-modules # théorèmes de PBW # théorèmes libres # théorie algébrique # treillis de Tamari # tresse # type de dérivation fini Actions naturelles # algèbres de Hopf # algèbres de Lie tordues # algèbres pré-Lie # algèbre dendriforme # algorithme de Buchberger # bases de Gröbner # catégories d'arbres # catégories de Koszul # catégorification # cohomologie de Hochschild # complétion de Knuth-Bendix # confluence # co-opérade de Poisson # diagrammes de flux et de programmation # enchevêtrement # espaces de configurations # foncteur de Schur # forme canonique # Haskell # ...

05C05 ; 06A11 ; 08B20 ; 16S15 ; 16G20 ; 17B35 ; 17D99 ; 18D05 ; 18C10 ; 18G15 ; 18D20 ; 18G55 ; 55P48 ; 55R80 ; 55U99 ; 57T30 ; 68Q05 ; 68Q12 ; 68N18 ; 68Q25 ; 68W30 ; 68Q42

... Lire [+]

V

- 144 p.
ISBN 978-2-89276-077-4

Publications du laboratoire de combinatoire et d'informatique mathématique , 0001

Localisation : Colloque RdC

parallélisme # complexité

05-06 ; 68Q22 ; 68Q25

... Lire [+]

V

- xi; 157 p.
ISBN 978-0-387-75154-2

the IMA volumes in mathematics and its applications , 0146

Localisation : Colloque RdC

géométrie algébrique # algorithme # analyse numérique # calcul formel

11T71 ; 13P05 ; 14G05 ; 14H50 ; 14J70 ; 14M17 ; 14M99 ; 14P05 ; 14P99 ; 14Q05 ; 14Q10 ; 14Q99 ; 47B35 ; 52A20 ; 65H10 ; 65H20 ; 68Q25 ; 68W30 ; 90C22 ; 14M15

... Lire [+]

V

- 85 p.

Journée annuelle de la SMF

Localisation : Colloque RdC

cryptographie # clé publique jacobienne # complexité algorithmique # groupe algébrique commutatif # courbe algébrique # corps fini # complexité # algorithme discret # problème de Diffie-Hellman # sécurité prouvée # chiffrement d'Elgamol # méthode de Fujisaki-Okamoto # chiffrement de Cramer-Shoup

94A60 ; 11Y60 ; 14Q05 ; 14Q15 ; 20G40 ; 14L10 ; 11T99 ; 11Y05 ; 11Y16 ; 12E20 ; 68Q25 ; 68P25 ; 11T71

... 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

- 433 p.
ISBN 978-0-8218-3177-9

Contemporary mathematics , 0323

Localisation : Collection 1er étage

matrice # transformation de Fourier # algorithme # interpolation rationnelle # décodage d'algorithme # algèbre de Lie # optimisation # résolution d'équation matricielle

68Q25 ; 65Y20 ; 65F05 ; 65F10 ; 65G50 ; 65M12 ; 15A57 ; 15A18 ; 47N70 ; 47N40

... Lire [+]

V


ISBN 978-0-8186-0742-4

Localisation : Colloque RdC

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

- 370 p.
ISBN 978-3-540-64824-6

Lecture notes in computer science , 1449

Localisation : Collection 1er étage

algorithme # analyse d"algorithme # combinatoire # complexité calculatoire # cryptographie # géométrie calculatoire # informatique # processus distribué # processus parallèle # reseau commuté # structure de données # théorie des graphes

05-06 ; 68-06 ; 68Q25 ; 68R10

... Lire [+]

V

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

DIMACS series in discrete mathematics and theoretical computer science , 0050

Localisation : Collection 1er étage

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

- 640 p.
ISBN 978-3-540-64657-0

Lecture notes in computer science , 1423

Localisation : Collection 1er étage

algorithmique # théorie des nombres # théorie des nombres calculatoires # traitement informatique

11T71 ; 11Yxx ; 12Y05 ; 68P25 ; 68Q20 ; 68Q25 ; 68Q40 ; 94A60

... 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


ISBN 978-0-8186-0742-4

Localisation : Colloque RdC

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 [+]

Nuage de mots clefs ici

Ressources Electroniques

Books & Print journals

Recherche avancée


0
Z