m

F Nous contacter

0

Documents  68Q17 | enregistrements trouvés : 27

O

-A +A

P Q

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.

- 224 p.
ISBN 978-0-8218-3483-1

Contemporary mathematics , 0349

Localisation : Collection 1er étage

théorie des groupes # groupe de permutation # groupe non-abélien # théorie quantique # informatique # algorithme # groupe d'automorphisme # calcul quantique

20B40 ; 20E05 ; 20F28 ; 81P68 ; 68Q05 ; 68Q17 ; 68Q42 ; 68Q45 ; 68T05

... Lire [+]

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

- x, 226 p.

Localisation : Séminaire 1er étage

théorie ergodique # géométrie # dynamique symbolique # combinatoire de mots # billard # transport de mesures # courbure de Ricci # flot quasi-conforme # variété Hadamard # isométrie # opérateur Lamé

37A35 ; 37C35 ; 11N37 ; 32G15 ; 32M15 ; 32Q45 ; 58J50 ; 35R30 ; 22E40 ; 20F65 ; 68Q17 ; 46Bxx ; 53DXX ; 53Cxx

... Lire [+]

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

- viii; 97 p.
ISBN 978-3-03719-069-2

Localisation : Colloque 1er étage (JENA)

informatique # optimisation

65-02 ; 65-03 ; 00B10 ; 01A70 ; 68-06 ; 90-06 ; 68Q17 ; 00B25

... Lire [+]

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

- xi; 556 p.
ISBN 978-2-85629-371-3

Astérisque , 0352

Localisation : Périodique 1er étage

Algorithme d'approximation # carte brownienne # cartes planaires # champ libre gaussien # champ moyen # choix social # concentration-compacité # condition nulle # configuration polynomiale # courbe elliptique # D-module holonome # difficulté d'approximation # équation aux dérivées partielles # équations d'Einstein # équations différentielles partielles # équations non-linéaires dispersives # espaces adiques # espaces de Berkovich # espaces homogènes # espaces métriques # espaces normés # espaces perfectoïdes # existence globale # fibré de Higgs # fibré holomorphe plat # forme quartique binaire # formule de KPZ # gravité quantique # groupe de Galois motivique # groupe de Selmer # groupes de Lie # groupes quasi-fuchsiens # hamiltonien # marches aléatoires # mélange exponentiel du fibré des repères # mesures de Liouville # mesures stationnaires # métrique harmonique # modération topologique # monodromie-poids # motifs de Tate mixtes # multizêtas # nonlinéaire # norme d'uniformité # orbites coadjointes # plongement métrique # principe de transfert # programmation semi-définie # Programme de Ribe # progression arithmétique # pureté # rang # réarrangement # Relativité générale # représentations des groupes algébriques réductifs # représentations des groupes de Lie compacts # résonances en espace temps # rigidité # singularités irrégulières # stabilité orbitale # surfaces enfermées # système stellaire auto-gravitant # théorème de Lefschetz difficile # théorie de Hodge # théorie géométrique des invariants # topologie étale # trous noirs # types stablement dominés # variétés de drapeaux # variétés hyperboliques de dimension 3 # Vlasov-Poisson Algorithme d'approximation # carte brownienne # cartes planaires # champ libre gaussien # champ moyen # choix social # concentration-compacité # condition nulle # configuration polynomiale # courbe elliptique # D-module holonome # difficulté d'approximation # équation aux dérivées partielles # équations d'Einstein # équations différentielles partielles # équations non-linéaires dispersives # espaces adiques # espaces de Berkovich # espaces ...

14L24 ; 14M15 ; 20G05 ; 22E46 ; 35-XX ; 35Qxx ; 37-XX ; 37NXX ; 37N20 ; 82-XX ; 82Cxx ; 85-XX ; 85AXX ; 05C12 ; 05C85 ; 46N10 ; 68Q17 ; 68R10 ; 68W25 ; 90C22 ; 91B14 ; 11G99 ; 11G05 ; 11E76 ; 14J60 ; 32C38 ; 53C07 ; 83C57 ; 83C75 ; 83C05 ; 35L67 ; 60C05 ; 60F17 ; 60-02 ; 05C10 ; 05C80 ; 82B20 ; 82B05 ; 82B27 ; 35B34 ; 35E20 ; 35B60 ; 35Q60 ; 35Q35 ; 11N13 ; 11B25 ; 30F99 ; 03C64 ; 03C65 ; 03C99 ; 14G22 ; 11G25 ; 14F20 ; 14G20 ; 22E40 ; 37D40 ; 60B99

... Lire [+]

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

Research talks;Computer Science

Approximation methods and probabilistic algorithms are two important ways to obtain efficient algorithms giving approximate solutions to hard problems. We give some examples from optimization, counting and verification problems. Property testing is also a very efficient method to approximate verification problems.
complexity - difficult problem - approximation - probabilistic approximation schemes - optimization - counting
verification - property testing
Approximation methods and probabilistic algorithms are two important ways to obtain efficient algorithms giving approximate solutions to hard problems. We give some examples from optimization, counting and verification problems. Property testing is also a very efficient method to approximate verification problems.
complexity - difficult problem - approximation - probabilistic approximation schemes - optimization - counting
verification - ...

68Q15 ; 68Q17 ; 68Q19 ; 68W20 ; 68W25

... Lire [+]

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

Research schools;Combinatorics;Computer Science;Topology

68Q17 ; 57Q35

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

- 411 p.
ISBN 978-3-7643-6654-4

Progress in computer science and applied logic , 0022

Localisation : Ouvrage RdC (SHPA)

théorie de la complexité # problème du logarithme discret # problème de Diffie-Hellman # protocole RSA et ElGamal # sécurité du système NTRU # fonction booléenne # générateur de nombre pseudo-aléatoire # complexité des problèmes de théorie des nombres appliqués à la cryptographie # générateur BBS et RSA

03D15 ; 11T71 ; 11Yxx ; 68Q15 ; 68Q17 ; 68Q25 ; 94A60

... Lire [+]

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

- 300 p.
ISBN 978-0-19-856607-6

Oxford lecture series in mathematics and its applications , 0031

Localisation : Ouvrage RdC (NIED)

algorithme à paramètre fixe # statistiques # informatique # paramétrisation # arbre de recherche # programmation dynamique # décomposition de graphe # complexité # algorithme d'approximation

68Q25 ; 68Q17 ; 92-99 ; 68-99 ; 62-99

... Lire [+]

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

- 389 p.
ISBN 978-0-8218-2872-4

IAS/Park City mathematics series , 0010

Localisation : Collection 1er étage

informatique # théorie de la complexité # classe de complexité # preuve de complexité # difficulté calculatoire d'un problème # calcul quantique # pseudoaléatoire

68-06 ; 68Qxx ; 03D15 ; 68Q15 ; 03F20 ; 68-02 ; 68Q17 ; 81P68

... Lire [+]

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

- xi, 384 p.
ISBN 978-3-03719-026-5

Tracts in Mathematics , 0006

Localisation : Ouvrage RdC (NOVA)

loi n variables # tractabilité # méthode cas pire # algorithme randomisé # norme pondérée # produit pondéré # méthode cas moyen

65-02 ; 68Q17 ; 68Q25 ; 41A63 ; 46E22 ; 28C20 ; 46E30

... Lire [+]

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

- xiii; 151 p.
ISBN 978-3-540-68546-3

Algorithms and computation in mathematics , 0023

Localisation : Ouvrage RdC (BRAV)

logique # calcul complexe # théorie de la récursion # ensemble de Julia # modèles de calcul

03D15 ; 03D80 ; 37F10 ; 37F50 ; 65Y20 ; 68Q05 ; 68Q17 ; 03-99

... Lire [+]

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

- xxiv; 606 p.
ISBN 978-0-521-88473-0

Localisation : Ouvrage RdC (GOLD)

complexité # difficultés calculatoires # analyse d'algorithmes # cryptographie # classe de complexité # algorithme déterministe # algorithme probabiliste

68Q15 ; 68Q17 ; 68Q25 ; 68W40 ; 68-01 ; 68-02 ; 94A60 ; 94A62

... Lire [+]

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

- viii, 182 p.
ISBN 978-3-642-12247-7

Lecture notes in mathematics

Localisation : Collection 1er étage

électromagnétique # EDP # opérateur de Schrödinger # fonction d'onde électronique # 3N variable # mécanique quantique

35J10 ; 35B65 ; 41A25 ; 41A63 ; 68Q17

... Lire [+]

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

- x; 114 p.
ISBN 978-0-8218-5192-0

University lecture series , 0055

Localisation : Collection 1er étage

complexité de calcul # générateur de nombres aléatoires # théorie de l'information algorithmique # algorithme randomisé # pseudo-aléatoire

68-01 ; 68-02 ; 68R01 ; 68Q15 ; 68Q17 ; 68W20 ; 68Q30

... Lire [+]

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

- ix; 296 p.
ISBN 978-3-03719-085-2

Tracts in mathematics , 0011

Localisation : Ouvrage RdC (TRIE)

espace fonctionnel # bases # espace de Sobolev # système de faber # echantillonage # approximation multidimensionel # intégration numérique # discrépance

46-02 ; 46E35 ; 42C40 ; 42B35 ; 68Q17 ; 41A55 ; 46B15 ; 42C15 ; 41A63 ; 41A30 ; 65D30

... Lire [+]

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

- xviii; 657 p.
ISBN 978-3-03719-084-5

Tracts in mathematics , 0012

Localisation : Ouvrage RdC (NOVA)

analyse multivariée # algorithme

65Y20 ; 68Q17 ; 68Q25 ; 41A63 ; 65-02 ; 46E22 ; 28C20 ; 46E30 ; 11K38 ; 65D32

... Lire [+]

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

- xvi; 247 p.
ISBN 978-0-521-15433-8

London mathematical society lecture note series , 0382

Localisation : Collection 1er étage

complexité # variable aléatoire # analyse mathématique # limite arithmétique # mesure de Loeb # arbre de décision

03F20 ; 03-02 ; 03C62 ; 03F30 ; 68Q17

... Lire [+]

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

- xx; 439 p.
ISBN 978-0-8218-6907-9

Graduate studies in mathematics , 0128

Localisation : Collection 1er étage

algèbre multilinéaire # produit tenseur # matrice # théorie du signal # phylogénétique # statistiques algébriques # G-variétés # théorème d'Alexander-Hirschowitz # méthode de Weyman-Kempf

15-01 ; 15A69 ; 68Q17 ; 14M17 ; 94A12 ; 94A13 ; 20G05 ; 62E10 ; 14N05 ; 14M12 ; 14M15 ; 15A72 ; 15A75

... Lire [+]

Z