En poursuivant votre navigation sur ce site, vous acceptez l'utilisation d'un simple cookie d'identification. Aucune autre exploitation n'est faite de ce cookie. OK

Documents 4 résultats

Filtrer
Sélectionner : Tous / Aucun
P Q
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y
Pendant cet exposé je donnerai un aperçu des méthodes galoisiennes appliquées aux équations fonctionnelles, afin de présenter des résultats sur la nature de certaines séries génératrices issues de la combinatoire, et en particulier de la combinatoire énumérative, récemment obtenus par plusieurs auteurs. L'objectif est de donner l'intuition du principe commun de ces preuves.

30D05 ; 34M15 ; 39B12

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y
Si l'hypothèse P $\neq$ NP a pour conséquence que les problèmes NP-difficiles ne sont pas résolubles en temps polynomial, l'obtention de résultats négatifs plus précis nécessite le recours à des hypothèses plus fortes. Dans cet exposé, nous présenterons certains résultats négatifs (bornes inférieures de complexité) obtenus à partir des hypothèses ETH (exponential time hypothesis) et SETH (strong exponential time hypothesis). Il y sera question de SAT, de graphes, de complexité (classique et parfois paramétrée), de problèmes difficiles mais aussi de problèmes polynomiaux.[-]
Si l'hypothèse P $\neq$ NP a pour conséquence que les problèmes NP-difficiles ne sont pas résolubles en temps polynomial, l'obtention de résultats négatifs plus précis nécessite le recours à des hypothèses plus fortes. Dans cet exposé, nous présenterons certains résultats négatifs (bornes inférieures de complexité) obtenus à partir des hypothèses ETH (exponential time hypothesis) et SETH (strong exponential time hypothesis). Il y sera question ...[+]

68Q17 ; 68Q25 ; 05C85

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y
La génération aléatoire est un outil de choix pour étudier les structures combinatoires et notamment leurs propriétés asymptotiques. Bien qu'il soit parfois possible de concevoir des générateurs ad hoc efficaces pour certaines classes d'objets combinatoires, nous nous intéresserons plutôt aux méthodes de générations dites 'automatiques' : la méthode récursive et la méthode de Boltzmann en particulier. Dans les deux cas, il est possible de traduire directement les spécifications combinatoires issues de la méthode symbolique de Flajolet et Sedgewick en algorithmes de génération aléatoire uniforme (tous les objets de même taille ont la même probabilité d'être tirés). Ces deux techniques s'appuient fortement sur l'utilisation des séries génératrices afin de garantir l'uniformité des tirages. Dans le cas de la méthode récursive, on exploitera les coefficients des séries formelles alors que la méthode de Boltzmann s'appuie sur l'évaluation numérique de ces mêmes séries. Durant la séance d'exercices vous pourrez programmer vos propres générateurs suivant l'une ou l'autre de ces méthodes.[-]
La génération aléatoire est un outil de choix pour étudier les structures combinatoires et notamment leurs propriétés asymptotiques. Bien qu'il soit parfois possible de concevoir des générateurs ad hoc efficaces pour certaines classes d'objets combinatoires, nous nous intéresserons plutôt aux méthodes de générations dites 'automatiques' : la méthode récursive et la méthode de Boltzmann en particulier. Dans les deux cas, il est possible de ...[+]

05A15 ; 05A16 ; 60C05 ; 68W20

Sélection Signaler une erreur
Déposez votre fichier ici pour le déplacer vers cet enregistrement.
y
La génération aléatoire est un outil de choix pour étudier les structures combinatoires et notamment leurs propriétés asymptotiques. Bien qu'il soit parfois possible de concevoir des générateurs ad hoc efficaces pour certaines classes d'objets combinatoires, nous nous intéresserons plutôt aux méthodes de générations dites 'automatiques' : la méthode récursive et la méthode de Boltzmann en particulier. Dans les deux cas, il est possible de traduire directement les spécifications combinatoires issues de la méthode symbolique de Flajolet et Sedgewick en algorithmes de génération aléatoire uniforme (tous les objets de même taille ont la même probabilité d'être tirés). Ces deux techniques s'appuient fortement sur l'utilisation des séries génératrices afin de garantir l'uniformité des tirages. Dans le cas de la méthode récursive, on exploitera les coefficients des séries formelles alors que la méthode de Boltzmann s'appuie sur l'évaluation numérique de ces mêmes séries. Durant la séance d'exercices vous pourrez programmer vos propres générateurs suivant l'une ou l'autre de ces méthodes.[-]
La génération aléatoire est un outil de choix pour étudier les structures combinatoires et notamment leurs propriétés asymptotiques. Bien qu'il soit parfois possible de concevoir des générateurs ad hoc efficaces pour certaines classes d'objets combinatoires, nous nous intéresserons plutôt aux méthodes de générations dites 'automatiques' : la méthode récursive et la méthode de Boltzmann en particulier. Dans les deux cas, il est possible de ...[+]

05A15 ; 05A16 ; 60C05 ; 68W20

Sélection Signaler une erreur