F Nous contacter


0

Computer Science  | enregistrements trouvés : 98

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

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

Microparasites (virus, bactéries, protozoaires ...) et macroparasites (métazoaires : helminthes, arthropodes...) sont omniprésents dans les écosystèmes terrestres et marins. Le nombre total d'espèces parasites sur la planète est supérieur à celui des espèces libres qu'ils colonisent, temporairement ou non, au point que ces organismes interfèrent à toutes les échelles d'organisation du vivant. Les pathologies qu'ils peuvent parfois engendrer sont dépendantes de conditions particulières, soit liées à leur propre virulence, soit à un ensemble de facteurs environnementaux. Dans ce contexte, les modèles mathématiques constituent des outils précieux en épidémiologie, permettant de mieux comprendre les modalités de leur propagation dans les populations d'hôtes. Aborder les stratégies démographiques des micro ou des macroparasites implique des approches mathématiques différentes. Le développement de ces modèles ouvre des perspectives intéressantes pour décrire, analyser et même prévoir les comportements démographiques de ces systèmes couplés. En milieu marin, les macroparasites peuvent aussi poser des problèmes de santé à leurs hôtes quand les équilibres de différentes natures sont déplacés, avec ou sans l'intervention de l'homme (espace protégé, pêche, aquaculture...). En prenant l'exemple de parasites de Poissons téléostéens, l'accent sera mis sur la complexité des processus biologiques en cause, et son intégration dans des modèles mathématiques.

Microparasites (virus, bactéries, protozoaires ...) et macroparasites (métazoaires : helminthes, arthropodes...) sont omniprésents dans les écosystèmes terrestres et marins. Le nombre total d'espèces parasites sur la planète est supérieur à celui des espèces libres qu'ils colonisent, temporairement ou non, au point que ces organismes interfèrent à toutes les échelles d'organisation du vivant. Les pathologies qu'ils peuvent parfois engendrer sont ...

00A06 ; 00A08 ; 92-XX

The persistent homology with coefficients in a field F coincides with the same for cohomology because of duality. We propose an implementation of a recently introduced algorithm for persistent cohomology that attaches annotation vectors with the simplices. We separate the representation of the simplicial complex from the representation of the cohomology groups, and introduce a new data structure for maintaining the annotation matrix, which is more compact and reduces substancially the amount of matrix operations. In addition, we propose heuristics to simplify further the representation of the cohomology groups and improve both time and space complexities. The paper provides a theoretical analysis, as well as a detailed experimental study of our implementation and comparison with state-of-the-art software for persistent homology and cohomology.
persistent cohomology - implementation - matrix reduction - data structure - annotation - simplex tree
The persistent homology with coefficients in a field F coincides with the same for cohomology because of duality. We propose an implementation of a recently introduced algorithm for persistent cohomology that attaches annotation vectors with the simplices. We separate the representation of the simplicial complex from the representation of the cohomology groups, and introduce a new data structure for maintaining the annotation matrix, which is ...

68Wxx

Z