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

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 schools

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

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

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.


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.

- 209 p.
ISBN 978-0-8218-6597-2

DIMACS series in discrete mathematics and theoretical computer science , 0013

Localisation : Collection 1er étage

algorithme pour jeu stochastique simple # application de technique de théorie des jeux à la cryptograp # approximation diophantienne # complexité d'adaptation parallèle du théorème de Ramsey # composition de relation universelle # comptage approché avec circuit de profondeur constante unifo # factorisation d'entier et calcul de logarithme discret # jeu loyal contre adversaire tout-puissant # problème de E-isomorphisme # programme de branchement lu- seulement une fois # réduction aléatoire localement en théorie de la compléxité i # sécurité cryptographique parfaite partique # séparation forte de AC puissance 0 # théorème de la borne inférieure # thérorie de la complexité informatique algorithme pour jeu stochastique simple # application de technique de théorie des jeux à la cryptograp # approximation diophantienne # complexité d'adaptation parallèle du théorème de Ramsey # composition de relation universelle # comptage approché avec circuit de profondeur constante unifo # factorisation d'entier et calcul de logarithme discret # jeu loyal contre adversaire tout-puissant # problème de E-isomorphisme # programme de branchement ...

68P25 ; 68Q15 ; 68Q25 ; 68R05 ; 68R10

... Lire [+]

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

- 278 p.
ISBN 978-3-540-50667-6

Lecture notes in computer science , 0343

Localisation : Collection 1er étage

algèbre # grammaire # langage de programmation # logique mathématique # programmation logique # reécriture des systèmes # technique de programmation

68N17 ; 68Q25

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

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

Lecture notes in computer science , 0877

Localisation : Collection 1er étage

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

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

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

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

- 403 p.
ISBN 978-3-540-61581-1

Lecture notes in computer science , 1122

Localisation : Collection 1er étage

algorithme non numérique # algorithmique # algèbre # algèbre de l'informatique # analyse d'algorithme # arithmétique # corps des nombres finis # cryptage des données # cryptographie # encryptage de données # grammaire # informatique théorique # mathématique de l'informatique # mathématique discrète # polynôme # problème de complexité # théorie algorithmique des nombres # théorie des nombres # traitement des données informatiques

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

... Lire [+]

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

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

Lecture notes in computer science , 1203

Localisation : Collection 1er étage

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

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

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

Localisation : Colloque 1er étage (PITT)

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

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

... Lire [+]

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

- 688 p.
ISBN 978-3-540-58325-7

Lecture notes in computer science , 0834

Localisation : Collection 1er étage

VLSI et routage # algorithme algébrique # algorithme combinatoire # algorithme distribué et aléatorisé # algorithme et calcul # algorithme géométrique # algorithme parallèle # approximation et optimisation # complexité # complexité informatique # géométrie informatique # structure de données

68Q25 ; 68Q35 ; 68Qxx ; 68U05

... Lire [+]

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

- 510 p.
ISBN 978-3-540-56279-5

Lecture notes in computer science , 650

Localisation : Collection 1er étage

algorithme # algorithme combinatoire # algorithme des couleurs # algorithme des graphes # algorithme parallèle # algorithmique # calcul # complexité # graphe # géométrie de l'informatique # stucture des données # théorie de la complexité

68P05 ; 68Q25 ; 68Q30 ; 68Qxx ; 68R05

... Lire [+]

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

- 495 p.
ISBN 978-3-540-54343-5

Lecture notes in computer science , 0519

Localisation : Collection 1er étage

algorithme # algorithmique # énumération # graphe # structure des données

68P05 ; 68Q20 ; 68Q22 ; 68Q25 ; 68Q30

... Lire [+]

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


ISBN 978-0-7923-0007-6

Nato a.s.i. series

Localisation : Colloque 1er étage (OTTA)

algorithme # algorithmiqu e # combinatoire # complexite # donnee graphique # ensemble ordonne # informatique graphique # logique # ordre # structure de donnee graphique # structure ordonnee

68Q25 ; 68Q30

... Lire [+]

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

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

the IMA volumes in mathematics and its applications , 0146

Localisation : Colloque 1er étage (MINN)

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

Z