m

F Nous contacter

0

Documents  68Q25 | enregistrements trouvés : 206

O

-A +A

P Q

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Computer Science;Logic and Foundations

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

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Combinatorics;Computer Science;Control Theory and Optimization

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

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research School;Combinatorics;Computer Science;Mathematics in Science and Technology

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

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research schools

68Q25 ; 68Q42 ; 90C39 ; 92D20 ; 92E10

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Computer Science

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

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Research talks;Combinatorics;Computer Science;Mathematics in Science and Technology

Déléguer à une machine l'affectation des bacheliers dans le supérieur pose un certain nombre de questions : quels règles souhaite-t-on pour l'accès au supérieur ? Quels sont alors les objectifs assignés à la machine ? Quel algorithme permet de les atteindre ? Comment permettre à tous les citoyens de vérifier une exécution de l'algorithme ? On verra rapidement quels faux et vrais problèmes posait APB et pose Parcoursup. Je présenterai l'algorithme de Gale-Shapley et je montrerai comment on peut vérifier a posteriori que cet algorithme a été exécuté correctement, de façon plus ou moins complète selon le degré d'anonymat des candidatures et des classements.

In France, matching students who have passed the baccalaureat to higher education is a computer-based process. A new process is being used this year. Some questions arise: what are the rules that determine access to higher education? What goal is the computer-based process supposed to be aimed at? By what means? How are citizens allowed to check that the process runs smoothly and gives equitable results? This talk reviews some of the issues raised by both the former and the new processes, introduces the Gale-Shapley algorithm and explains how a run of the process can be independently verified.
Déléguer à une machine l'affectation des bacheliers dans le supérieur pose un certain nombre de questions : quels règles souhaite-t-on pour l'accès au supérieur ? Quels sont alors les objectifs assignés à la machine ? Quel algorithme permet de les atteindre ? Comment permettre à tous les citoyens de vérifier une exécution de l'algorithme ? On verra rapidement quels faux et vrais problèmes posait APB et pose Parcoursup. Je présenterai l'...

68Q25 ; 91B68 ; 05D15

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 120 p.

Localisation : Salle de manutention

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

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

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Publications du departement de mathematiquess

Localisation : Colloque 1er étage (AVIG)

algorithme # automate # complexite des algorithmes # langage

68Q25

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 761 p.
ISBN 978-3-540-56610-6

Lecture notes in computer science , 0668

Localisation : Collection 1er étage

analyse des algorithmes # calcul informatique # calcul parallèle # informatique théorique # langage de programmation # logique et arborescence # logique et spécification des programmes # programmation concurrente # spécification # système # système concurrent

68Q10 ; 68Q25 ; 68Q60

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 618 p.
ISBN 978-3-540-55210-9

Lecture notes in computer science , 0577

Localisation : Collection 1er étage

acquisition # algorithme géométrique # algorithme parallèle # algèbre # analyse numérique # apprentissage # calcul informatique # calcul numérique # complexité des structures # complexité et communication # cryptographie # géométrie de l'informatique # hiérarchie # informatique graphique # informatique théorique # langage de spécification PLUSS # logique # mathématique discrète # moto # méthodologie du calcul informatique # réseau # réécriture # système distribué # système informatique # sémantique # transformation géométrique acquisition # algorithme géométrique # algorithme parallèle # algèbre # analyse numérique # apprentissage # calcul informatique # calcul numérique # complexité des structures # complexité et communication # cryptographie # géométrie de l'informatique # hiérarchie # informatique graphique # informatique théorique # langage de spécification PLUSS # logique # mathématique discrète # moto # méthodologie du calcul informatique # réseau # réécriture # ...

68M10 ; 68Mxx ; 68Q25 ; 68Qxx ; 68Rxx

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 548 p.
ISBN 978-3-540-53709-0

Lecture notes in computer science , 0480

Localisation : Collection 1er étage

algorithme # calcul parallèle # complexité # démonstration # informatique théorique # logique # sémantique # syntaxe

68N15 ; 68Pxx ; 68Q25 ; 68Q50 ; 68Qxx

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

- 311 p.
ISBN 978-3-540-52282-9

Lecture notes in computer science , 0415

Localisation : Collection 1er étage

algèbre de l

68Q15 ; 68Q25 ; 68Qxx ; 68Rxx ; 68U05

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Publications mathématiques de l'université Paris VII , 0019

Localisation : Publication 1er étage

codage des ordres dénombrables # complexité algorithmique # corps # espace polonais # géométrie des espaces de Banach # logique du premier ordre # logique stationnaire # méthode de priorité # théorie de la classification # théorie des modules # échelle des grands cardinaux

03-02 ; 03-06 ; 03Cxx ; 03D15 ; 68Q25

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

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

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

Publications du departement de mathematiquess

Localisation : Colloque 1er étage (AVIG)

algorithme # automate # complexite des algorithmes # langage

68Q25

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.


ISBN 978-0-8218-5500-3

Proceedings of symposia in applied mathematics , 0044

Localisation : Collection 1er étage

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

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

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

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

Localisation : Colloque 1er étage (MONT)

parallélisme # complexité

05-06 ; 68Q22 ; 68Q25

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.


ISBN 978-0-387-98664-7

The ima volumes in mathematics and its applications , 0106

Localisation : Colloque 1er étage (MINN)

analyse d

68Q10 ; 68Q25 ; 90C05 ; 90C06 ; 90C27

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.


ISBN 978-0-444-87528-0

Localisation : Colloque 1er étage (BERL)

65-XX ; 68-06 ; 68Q20 ; 68Q25 ; 68Qxx

... Lire [+]

Déposez votre fichier ici pour le déplacer vers cet enregistrement.

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

Z