F Nous contacter


0

Computer Science  | enregistrements trouvés : 113

O

-A +A

Sélection courante (0) : Tout sélectionner / Tout déselectionner

P Q

I will describe a recent framework for robust shape reconstruction based on optimal transportation between measures, where the input measurements are seen as distribution of masses. In addition to robustness to defect-laden point sets (hampered with noise and outliers), this approach can reconstruct smooth closed shapes as well as piecewise smooth shapes with boundaries.

68Rxx ; 65D17 ; 65D18

La décomposition par substitution des permutations permet de voir ces objets combinatoires comme des arbres. Je présenterai d'abord cette décomposition par substitution, et les arbres sous-jacents, appelés arbres de décomposition. Puis j'exposerai une méthode, complètement algorithmique et reposant sur les arbres de décomposition, qui permet de calculer des spécifications combinatoires de classes de permutations à motifs interdits. La connaissance de telles spécifications combinatoires ouvre de nouvelles perspectives pour l'étude des classes de permutations, que je présenterai en conclusion. La décomposition par substitution des permutations permet de voir ces objets combinatoires comme des arbres. Je présenterai d'abord cette décomposition par substitution, et les arbres sous-jacents, appelés arbres de décomposition. Puis j'exposerai une méthode, complètement algorithmique et reposant sur les arbres de décomposition, qui permet de calculer des spécifications combinatoires de classes de permutations à motifs interdits. La c...

68-06 ; 05A05

Tous les fournisseurs d'applications mettent actuellement en place des infrastructures "cloud". Cette nouvelle approche de l'utilisation des logiciels va complètement changer notre comportement en tant qu'utilisateurs, mais aussi en tant qu'enseignants et en tant que chercheurs.
L'objectif de cet exposé est de dégager les grands concepts scientifiques de cette évolution technologique et commerciale.
* Pourquoi le cloud aujourd'hui?
* Qu'est-ce qui a permis son émergence si rapide maintenant?
* Qu'est-ce que ça change pour l'enseignement?
* Quels sont les nouveaux défis de recherche qui sont posés?
Tous les fournisseurs d'applications mettent actuellement en place des infrastructures "cloud". Cette nouvelle approche de l'utilisation des logiciels va complètement changer notre comportement en tant qu'utilisateurs, mais aussi en tant qu'enseignants et en tant que chercheurs.
L'objectif de cet exposé est de dégager les grands concepts scientifiques de cette évolution technologique et commerciale.
* Pourquoi le cloud aujourd'hui?
* Qu'est-ce ...

68Qxx

We show that two-player stochastic games with perfect-information and shift-invariant submixing payoff functions are half-positional, i.e. in these games the maximizer has a positional optimal strategy. This extension of our previous result for one-player games relies on an interesting existence result about the existence of epsilon-subgame-perfect strategies.

68Q60 ; 91AXX

We present two related contributions of independent interest: high-probability finite sample rates for $k$-NN density estimation, and practical mode estimators ­ based on $k$-NN ­ which attain minimax-optimal rates under surprisingly general distributional conditions.

$k$-nearest neighbor ($k$-NN) - $k$-NN density rates - mode estimation

62G07

Post-edited  Une deuxième révolution galiléenne ?
Dowek, Gilles (Auteur de la Conférence) | CIRM (Editeur )

L'introduction d'un nouveau concept scientifique permet souvent de donner de nouvelles réponses à des questions anciennes qui n'avaient jusqu'alors reçu que des réponses imparfaites. Cet exposé présente quelques questions qui ont trouvé de nouvelles réponses depuis que nous comprenons mieux la notion d'algorithme : qu'est-ce qu'un aéroport ?, qu'est-ce qu'une cellule, qu'est-ce qu'une loi physique ?, ... La prise de conscience du caractère algorithmique de ces objets scientifiques nous amène à considérer de nouveaux langages pour les décrire. Cette révolution, dans le langage dans lequel la science s'écrit, peut-être comparée à la révolution qui s'est produite, au début du XVIIe siècle, quand le langage mathématique a commencé à être utilisé pour décrire des phénomènes physiques. L'introduction d'un nouveau concept scientifique permet souvent de donner de nouvelles réponses à des questions anciennes qui n'avaient jusqu'alors reçu que des réponses imparfaites. Cet exposé présente quelques questions qui ont trouvé de nouvelles réponses depuis que nous comprenons mieux la notion d'algorithme : qu'est-ce qu'un aéroport ?, qu'est-ce qu'une cellule, qu'est-ce qu'une loi physique ?, ... La prise de conscience du caractère ...

00A30 ; 03B35 ; 68T15

A non-backtracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The non-backtracking matrix of a graph is indexed by its directed edges and can be used to count non-backtracking walks of a given length. It has been used recently in the context of community detection and has appeared previously in connection with the Ihara zeta function and in some generalizations of Ramanujan graphs. In this work, we study the largest eigenvalues of the non-backtracking matrix of the Erdos-Renyi random graph and of the Stochastic Block Model in the regime where the number of edges is proportional to the number of vertices. Our results confirm the "spectral redemption" conjecture that community detection can be made on the basis of the leading eigenvectors above the feasibility threshold. A non-backtracking walk on a graph is a directed path such that no edge is the inverse of its preceding edge. The non-backtracking matrix of a graph is indexed by its directed edges and can be used to count non-backtracking walks of a given length. It has been used recently in the context of community detection and has appeared previously in connection with the Ihara zeta function and in some generalizations of Ramanujan graphs. In this work, we ...

05C50 ; 05C80 ; 68T05 ; 91D30

Post-edited  Wrapping in exact real arithmetic
Müller, Norbert (Auteur de la Conférence) | CIRM (Editeur )

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

We will consider (sub)shifts with complexity such that the difference from $n$ to $n+1$ is constant for all large $n$. The shifts that arise naturally from interval exchange transformations belong to this class. An interval exchange transformation on d intervals has at most $d/2$ ergodic probability measures. We look to establish the correct bound for shifts with constant complexity growth. To this end, we give our current bound and discuss further improvements when more assumptions are allowed. This is ongoing work with Michael Damron. We will consider (sub)shifts with complexity such that the difference from $n$ to $n+1$ is constant for all large $n$. The shifts that arise naturally from interval exchange transformations belong to this class. An interval exchange transformation on d intervals has at most $d/2$ ergodic probability measures. We look to establish the correct bound for shifts with constant complexity growth. To this end, we give our current bound and discuss ...

37B10 ; 37A25 ; 68R15

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

Post-edited  Coloring graphs on surfaces
Esperet, Louis (Auteur de la Conférence) | CIRM (Editeur )

The alternating direction method of multipliers (ADMM) is an optimization tool of choice for several imaging inverse problems, namely due its flexibility, modularity, and efficiency. In this talk, I will begin by reviewing our earlier work on using ADMM to deal with classical problems such as deconvolution, inpainting, compressive imaging, and how we have exploited its flexibility to deal with different noise models, including Gaussian, Poissonian, and multiplicative, and with several types of regularizers (TV, frame-based analysis, synthesis, or combinations thereof). I will then describe more recent work on using ADMM for other problems, namely blind deconvolution and image segmentation, as well as very recent work where ADMM is used with plug-in learned denoisers to achieve state-of-the-art results in class-specific image deconvolution. Finally, on the theoretical front, I will describe very recent work on tackling the infamous problem of how to adjust the penalty parameter of ADMM. The alternating direction method of multipliers (ADMM) is an optimization tool of choice for several imaging inverse problems, namely due its flexibility, modularity, and efficiency. In this talk, I will begin by reviewing our earlier work on using ADMM to deal with classical problems such as deconvolution, inpainting, compressive imaging, and how we have exploited its flexibility to deal with different noise models, including Gaussian, ...

65J22 ; 65K10 ; 65T60 ; 94A08

We will cover some of the more important results from commutative and noncommutative algebra as far as applications to automatic sequences, pattern avoidance, and related areas. Well give an overview of some applications of these areas to the study of automatic and regular sequences and combinatorics on words.

11B85 ; 68Q45 ; 68R15

The performance of numerical algorithms, both regarding stability and complexity, can be understood in a unified way in terms of condition numbers. This requires to identify the appropriate geometric settings and to characterize condition in geometric ways.
A probabilistic analysis of numerical algorithms can be reduced to a corresponding analysis of condition numbers, which leads to fascinating problems of geometric probability and integral geometry. The most well known example is Smale's 17th problem, which asks to find a solution of a given system of n complex homogeneous polynomial equations in $n$ + 1 unknowns. This problem can be solved in average (and even smoothed) polynomial time.
In the course we will explain the concepts necessary to state and solve Smale's 17th problem. We also show how these ideas lead to new numerical algorithms for computing eigenpairs of matrices that provably run in average polynomial time. Making these algorithms more efficient or adapting them to structured settings are challenging and rewarding research problems. We intend to address some of these issues at the end of the course.
The performance of numerical algorithms, both regarding stability and complexity, can be understood in a unified way in terms of condition numbers. This requires to identify the appropriate geometric settings and to characterize condition in geometric ways.
A probabilistic analysis of numerical algorithms can be reduced to a corresponding analysis of condition numbers, which leads to fascinating problems of geometric probability and integral ...

65F35 ; 65K05 ; 68Q15 ; 15A12 ; 65F10 ; 90C51 ; 65H10

Post-edited  Le problème Graph Motif - Partie 1
Fertin, Guillaume (Auteur de la Conférence) | CIRM (Editeur )

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

Post-edited  Detection theory and novelty filters
Morel, Jean-Michel (Auteur de la Conférence) | CIRM (Editeur )

In this presentation based on on-line demonstrations of algorithms and on the examination of several practical examples, I will reflect on the problem of modeling a detection task in images. I will place myself in the (very frequent) case where the detection task can not be formulated in a Bayesian framework or, rather equivalently that can not be solved by simultaneous learning of the model of the object and that of the background. (In the case where there are plenty of examples of the background and of the object to be detected, the neural networks provide a practical answer, but without explanatory power). Nevertheless for the detection without "learning", I will show that we can not avoid building a background model, or possibly learn it. But this will not require many examples.

Joint works with Axel Davy, Tristan Dagobert, Agnes Desolneux, Thibaud Ehret.
In this presentation based on on-line demonstrations of algorithms and on the examination of several practical examples, I will reflect on the problem of modeling a detection task in images. I will place myself in the (very frequent) case where the detection task can not be formulated in a Bayesian framework or, rather equivalently that can not be solved by simultaneous learning of the model of the object and that of the background. (In the case ...

65D18 ; 68U10 ; 68T05

Recently, an important research activity on mean field games (MFGs for short) has been initiated by the pioneering works of Lasry and Lions: it aims at studying the asymptotic behavior of stochastic differential games (Nash equilibria) as the number $n$ of agents tends to infinity. The field is now rapidly growing in several directions, including stochastic optimal control, analysis of PDEs, calculus of variations, numerical analysis and computing, and the potential applications to economics and social sciences are numerous.
In the limit when $n \to +\infty$, a given agent feels the presence of the others through the statistical distribution of the states. Assuming that the perturbations of a single agent's strategy does not influence the statistical states distribution, the latter acts as a parameter in the control problem to be solved by each agent. When the dynamics of the agents are independent stochastic processes, MFGs naturally lead to a coupled system of two partial differential equations (PDEs for short), a forward Fokker-Planck equation and a backward Hamilton-Jacobi-Bellman equation.
The latter system of PDEs has closed form solutions in very few cases only. Therefore, numerical simulation are crucial in order to address applications. The present mini-course will be devoted to numerical methods that can be used to approximate the systems of PDEs.
The numerical schemes that will be presented rely basically on monotone approximations of the Hamiltonian and on a suitable weak formulation of the Fokker-Planck equation.
These schemes have several important features:

- The discrete problem has the same structure as the continous one, so existence, energy estimates, and possibly uniqueness can be obtained with the same kind of arguments

- Monotonicity guarantees the stability of the scheme: it is robust in the deterministic limit

- convergence to classical or weak solutions can be proved

Finally, there are particular cases named variational MFGS in which the system of PDEs can be seen as the optimality conditions of some optimal control problem driven by a PDE. In such cases, augmented Lagrangian methods can be used for solving the discrete nonlinear system. The mini-course will be orgamized as follows

1. Introduction to the system of PDEs and its interpretation. Uniqueness of classical solutions.

2. Monotone finite difference schemes

3. Examples of applications

4. Variational MFG and related algorithms for solving the discrete system of nonlinear equations
Recently, an important research activity on mean field games (MFGs for short) has been initiated by the pioneering works of Lasry and Lions: it aims at studying the asymptotic behavior of stochastic differential games (Nash equilibria) as the number $n$ of agents tends to infinity. The field is now rapidly growing in several directions, including stochastic optimal control, analysis of PDEs, calculus of variations, numerical analysis and ...

49K20 ; 49N70 ; 35K40 ; 35K55 ; 35Q84 ; 65K10 ; 65M06 ; 65M12 ; 91A23 ; 91A15

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

Quel rapport entre la forme d'un chou-fleur des côtes de Bretagne, des vaisseaux sanguins et les structures fractales ?
Quel rapport entre une maladie génétique et un fichier de musique mp3 ?
Quel rapport entre des dessins faits par Léonard de Vinci et les lois mathématiques gouvernant la forme des plantes ou la reproduction des lapins ?
Quel rapport entre la forme de la terre, le GPS de ma voiture et un vieux puits d'Egypte ?
Pourquoi les météorologues sont capables de prédire une hausse du niveau des océans dans 100 ans mais incapables de prévoir s'il va pleuvoir dans 15 jours ?
Quel rapport entre le cerveau humain et le cerveau d'un ordinateur ?
Nous répondrons à toutes ces questions via des mathématiques simples et élégantes, accessibles à tous.
Quel rapport entre la forme d'un chou-fleur des côtes de Bretagne, des vaisseaux sanguins et les structures fractales ?
Quel rapport entre une maladie génétique et un fichier de musique mp3 ?
Quel rapport entre des dessins faits par Léonard de Vinci et les lois mathématiques gouvernant la forme des plantes ou la reproduction des lapins ?
Quel rapport entre la forme de la terre, le GPS de ma voiture et un vieux puits d'Egypte ?
Pourquoi les ...

00A06 ; 00A08 ; 68-XX ; 92-XX

Z