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 schools

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

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

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

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.

I.S.N.M. , 0006

Localisation : Colloque 1er étage (HANN)

68-06 ; 68C05 ; 68Q25 ; 68Txx

... Lire [+]

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

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

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

Localisation : Colloque 1er étage (UDIN)

68Q20 ; 68Q25

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


ISBN 978-3-540-13920-1

Nato a.s.i. series

Localisation : Colloque 1er étage (ILKL)

informatique graphique

68Q25 ; 68U05 ; 68Uxx

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

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.

- 486 p.
ISBN 978-0-12-386870-1

Perspectives in computing , 0015

Localisation : Colloque 1er étage (KYOT)

algorithme # co dage # code # complexite des algorithmes # cryptographie # mathematiques discretes # theorie de l' information

68Q25 ; 68Q30 ; 68R10 ; 94A60 ; 94Axx

... Lire [+]

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

- 551 p.
ISBN 978-3-540-08921-6

Lecture notes in computer science , 0064

Localisation : Collection 1er étage

automate # complexité informatique # information théorique # intelligence artificielle # langage formel # recherche d'information # théorie des automates

03C80 ; 03C99 ; 68Wxx ; 68Q25 ; 68Q45

... Lire [+]

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


ISBN 978-0-8186-0644-1

Localisation : Colloque 1er étage (PONT)

algorithme # automatique # informatique # ordinateur

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

... Lire [+]

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

- 301 p.
ISBN 978-3-540-11607-3

Lecture notes in computer science , 0144

Localisation : Collection 1er étage

calcul symbolique algébrique # complexité de calcul

68Q25 ; 68Q40

... Lire [+]

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

- 519 p.
ISBN 978-3-540-15650-5

Lecture notes in computer science , 0194

Localisation : Collection 1er étage

algorithme # algorithmes distribués # combinatoire # complexité # informatique théorique # langage # langage de programmation # logique # mathématique discrètes # processeurs # sémantique # vérification des algorithmes

68Q25 ; 68Q45 ; 68Q55 ; 68Qxx ; 68Rxx

... Lire [+]

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

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

Lecture notes in computer science , 0215

Localisation : Collection 1er étage

algorithme # algorithmique # informatique théorique

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

... Lire [+]

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

- 474 p.
ISBN 978-3-540-16761-7

Lecture notes in computer science , 0226

Localisation : Collection 1er étage

algèbre linéaire numérique # analyse des algorithmes et complexité des problèmes # approximation # calcul par des appareils abstraits # logique et signification des programmes # logique mathématique et langage formels # théorie des graphes

68Q05 ; 68Q25 ; 68Q45 ; 68R10

... Lire [+]

Z