LITA - Laboratoire d'Informatique Théorique et Appliquée - Université de Lorraine
Université de Lorraine - Laboratoire d'Informatique Théorique et Appliquée (LITA)
Université de Lorraine - Site de Metz - Île du Saulcy
57045 METZ CEDEX 1
Tel. : 02 87 31 54 44 - Fax : 04 87 31 53 09

Laboratoire d'Informatique Théorique et Appliquée (LITA)

Séminaires du LITA

16 Juin 2016 à 14h00
Salle de Réunion du LITA, E 215, Batiment UFR MIM, Campus Ile du Saulcy, Metz
"Difference-of-Convex Statistical Learning: Optimality Analysis and Computational Comparisons"
par
Professeur Jong-Shi Pang
University of Southern California

We study a fundamental bi-criteria optimization problem for variable selection in statistical learning;

the two criteria are a loss/residual function and a model control/regularization. The former function measures the fitness of the learning model to data and the latter function is employed as a control of the complexity of the model. We focus on the case where the loss function is convex and the model control function is a difference-of-convex (dc) sparsity measure.

From the perspective of optimality theory, we study the question of when a d(irectional)-stationary solution of the non-convex optimization problem has some kind of global optimality properties; from the perspective of computational performance, we compare the numerical results of sparse linear regression using several dc sparsity functions. The study is applicable to both exact and surrogate sparsity functions.

This is ongoing joint work with Miju Ahn (University of Southern California) and Jack Xin (University of California at Irvine).

* * *
10 Mars 2016 à 14h00
Salle de Réunion du LITA, UFR MIM
"On Temporal Graph Exploration".
par
Frank KAMMER
Universität Augsburg, Allemagne

A temporal graph is a graph in which the edge set can change from step to step. The temporal graph exploration problem TEMP is the problem of computing a foremost exploration schedule for a temporal graph, i.e., a temporal walk that starts at a given start node, visits all nodes of the graph, and has the smallest arrival time. We consider only temporal graphs that are connected at each step. For such temporal graphs with n nodes, we show that it is NP-hard to approximate TEMP with ratio O(n{1-epsilon}) for any epsilon>0. We also provide an explicit construction of temporal graphs that require Theta(n2) steps to be explored. We then consider TEMP under the assumption that the underlying graph (i.e. the graph that contains all edges that are present in the temporal graph in at least one step) belongs to a specific class of graphs. We show that temporal graphs can be explored in O(n.log3n) steps if the underlying graph is a (2 x n) grid.

* * *
8 Mars 2016 à 9h00
Salle de Réunion du LITA, UFR MIM
"Space-Efficient Basic Graph Algorithms".
par
Frank KAMMER
Universität Augsburg, Allemagne

We call an algorithm space-efficient if it matches the running times of standard algorithms or come close to it, but uses less space. The talk gives an overview of known space-efficient basic graph algorithms in a setting where an n-vertex input graph is read-only and the computation must take place in a working memory of O(n) bits or little more than that. We then shortly discuss the importance of graph representations in the context of space-efficient algorithms. We conclude the talk with the presentation of three algorithms for depth-first search that demonstrate some useful tricks to obtain further space-efficient algorithms.

* * *
13 Octobre 2015 à 14h15
Salle de Réunion du LITA, UFR MIM
"Reducing Complexity in Data via Mathematical Optimization".
par
Prof. Emilio Carrizo
Instituto de Matematicas de la Universidad de Sevilla, Spain.

Withthe aim of enhancing visualization of data sets, i.e., to make them easy to interpret, a powerful tool is to reduce the complexity of the data set by reducing its dimensionality in an interpretable manner, or to transform the data so that interpretability is enhanced. This is frequently done by solving a Mathematical Optimization problem, which may be far from trivial, but tractable.

In this talk we will present two examples of such complexity reduction strategy. First, we will address a Principal Component Analysis model with sparsity in their components, so that loadings have a clearer interpretation. Then we will address a classification model (Support Vector Machine) for data involving categorical variables, to be grouped in such a way that the weights in the score function are easier to interpret. Our numerical results will show that the use of Mathematical Optimization-based approaches may lead to results outperforming the state of the art.

* * *
02 Juillet 2015 à 14 heures
Salle de Réunion du LITA, UFR MIM
"Tiling rank matrices and its applications ".
par
LE Van Thanh
University of Leuven

In this talk, we will discuss two new data mining problems, namely, ranked tiling and rank matrix factorisation, which we introduce to mine a set of interesting patterns in rank matrices. In this type of matrix, each row defines a complete/partial ranking of the columns. Rank matrix occurs naturally in applications like sports or other competitions. It is also a useful abstraction when dealing with numeric data in which the rows are incomparable.

Ranked tiling studies the problem of finding areas called ranked tiles that have high average rank scores. Each ranked tile is defined by a set of rows and a set of columns. Mining such ranked tiles is useful as they reveal prominent local relations between sets of rows and columns. In contrast, rank matrix factorisation considers the problem of decomposing a rank matrix into a product of two smaller matrices, one of which contains k partial rankings of columns. That decomposition summaries the original matrix in a succinct way. In each case, I will show how we can formalise and solve the data mining problem using optimisation principles.

We will also discuss how to use the mined patterns to find biomarkers of patient subtypes, which is an important problem in the area of personalised medicine.

* * *
04 Juin 2015 à 14 heures
Salle de Réunion du LITA, UFR MIM
"Detection and Correction of Image Distortions from FIB-SEM Tomograms of Biological Samples".
par
Thai V. Hoang
Institut de Génétique et de Biologie Moléculare et Cellulaire (IGBMC), Strasbourg

FIB-SEM imaging combines scanning electron microscope (SEM) visualization with focused ion beam (FIB) milling and is becoming the method of choice to elucidate the 3D organization of the cellular architecture. However, this new technology has some inherent limitations due to the milling and scanning processes that may cause defects in the obtained image stacks. The first type of defects are curtaining effects which appear as vertical ripples from top to bottom of the SEM image. The second type appears in SEM images as horizontal irregular strips with inhomogeneous change in intensity values when compared to the preceding image in the stack. A third defect is revealed by an image deformation which results from specimen drifting during SEM image acquisition. In this talk, I will present our solutions to correct these defects by using Fourier analysis and correlation-based local deformation estimation to improve the visual quality of FIB-SEM data and to facilitate the segmentation of organelles and the subsequent extraction of quantitative information. The efficiency of the proposed correction solutions for FIB-SEM images of biological samples is demonstrated through a number of experiments.

* * *
26 Mars 2015 à 14 heures
Salle de Réunion du LITA, UFR MIM
"Subexponential algorithms for Intervalizing k-colored graphs".
par
Hans Bodlaender
Utrecht University / Eindhoven University of Technology (Pays bas)

In this talk, we consider exact algorithms for the following problem: determine for a graph G, given with a proper vertex color, whether it is a subgraph of a properly colored interval graph, i.e., we must turn G into an interval graph by adding edges between vertices with different colors. The problem is known to be NP-complete for the case of four colors. In this talk, we show that for any fixed number of colors the problem can be solved in 2^O(n/log n) time, and give a matching lower bound assuming the Exponential Time Hypothesis for any fixed number of colors >= 6.

* * *
18 Décembre 2014 à 14 heures
Amphi Hermite, UFR MIM
"Algorithmes Exacts et Exponentiels pour les Problèmes NP-difficiles sur les Graphes et Hypergraphes".
par
Manfred Cochefert
Université de Lorraine

* * *
13 Novembre 2013 à 14 heures
Salle de réunion du LITA, UFR MIM
Toward Large-scale Human Behavior Analysis
par
Minh Hoai Nguyen
Research Fellow - University of Oxford
www.robots.ox.ac.uk/~minhhoai/

Enabling computers to understand human behavior has the potential to revolutionize many areas that benefit society such as clinical diagnosis, human-computer interaction, and social robotics. Critical to the understanding of human behavior or any temporally-varying phenomenon in general is the ability to segment, classify, and cluster time series data.

In the first part of this talk, I will present Segment-based Support Vector Machines (Seg-SVMs), a framework for supervised, weakly-supervised, and unsupervised time series analysis. Seg-SVMs outperform state-of-the-art approaches by combining three powerful ideas: energy-based structure prediction, bag-of-words representation, and maximum-margin learning. I will provide an overview of Seg-SVMs and demonstrate their benefits for one particular problem: early event detection.

In the second part of this talk, I will describe an algorithm to harness the power of big data for large-scale human behavior analysis. In particular, I will present Instance Ranking SVM (IRSVM), a novel Multiple Instance Learning (MIL) formulation for learning from data with little annotation. IRSVM outperforms existing MIL algorithms by embracing the correlation of data instances and anticipating the deficiency of the instance classifier.

Bio.Minh Hoai is a research fellow at Oxford University. He obtained Ph.D from Carnegie Mellon University in 2012 and B.E. from The University of New South Wales in 2005. He is the recipient of the CVPR2012 Best Student Paper Award. He was a member of the mathematical Olympiad team representing Vietnam in the 41st International Mathematical Olympiad, where he won a Gold Medal

* * *
2 Octobre 2013 à 14 heures
Salle de réunion du LITA, UFR MIM
Une étude comparative entre l'Apprentissage par Renforcement Inverse (ARI) et l'Apprentissage par Imitation (AI)
par
Bilal Piot
SUPELEC

Cet exposé propose une étude comparative entre l'Apprentissage par Renforcement Inverse (ARI) et l'Apprentissage par Imitation (AI).

L'ARI et l'AI sont deux cadres de travail qui utilisent le concept de Processus Décisionnel de Markov (PDM) et dans lesquels nous cherchons à résoudre le problème d'Apprentissage par Démonstrations (AD). L'AD est un problème où un agent appelé apprenti cherche à apprendre à partir de l'observation des démonstrations d'un autre agent appelé expert.

Dans le cadre de travail de l'AI, l'apprenti essaie d'apprendre directement la politique de l'expert alors que dans le cadre de l'ARI, l'apprenti essaie d'apprendre la récompense qui explique la politique de l'expert. Cette récompense est ensuite optimisée pour imiter l'expert.

On peut donc légitimement se demander s'il y a un intérêt à estimer une récompense qui devra ensuite être optimisée ou si l'estimation d'une politique est suffisante. Cette question assez naturelle n'a pas encore été réellement traitée dans la littérature pour l'instant. Ici, des réponses partielles à la fois d'un point de vue théorique et pratique sont produites.

* * *

This talk provides a comparative study between Inverse Reinforcement Learning (IRL) and Apprenticeship Learning (AL).

IRL and AL are two frameworks, using Markov Decision Processes (MDP), which are used for the imitation learning problem where an agent tries to learn from demonstrations of an expert.

In the AL framework, the agent tries to learn the expert policy whereas in the IRL framework, the agent tries to learn a reward which can explain the behavior of the expert. This reward is then optimized to imitate the expert.

One can wonder if it is worth estimating such a reward, or if estimating a policy is sufficient. This quite natural question has not really been addressed in the literature right now. We provide partial answers, both from a theoretical and empirical point of view.

* * *
22 Septembre 2013 à 14 heures
Salle de réunion du LITA, UFR MIM
Visualizing Community Genomic Data
par
Nikos Vlassis
Luxembourg Centre for Systems Biomedicine
University of Luxembourg

Clustering and visualizing community genomic sequence data (aka metagenomic data) is a challenging problem in computational biology. We have recently developed an approach that is based on nonlinear dimension reduction of composition-based genomic features via a variant of Stochastic Neighbourhood Embedding. The latter casts the problem of data visualization as a non-convex optimization problem, and a challenging problem is the development of efficient solvers. In this talk I will give a general introduction to the problem and discuss possibilities to model it as a DC program.

* * *
22 Septembre 2013 à 10 heures
Salle de réunion du LITA, UFR MIM
An Unified Framework of Machine Learning via Mixed 0-1 Linear Programming and Applications
par
Dr. Hai Nguye
INRIA Lille-Nord

This research presents a significant improvement of machine learning algorithms by reformulating them as discrete optimization problems and by unifying them into a framework. In fact, we study (i) a class of feature (parameter) selection methods, e.g. correlation-based and mutual information-based feature (parameter) selection, (ii) supervised learning algorithms, e.g. Lp-norm support vector machines and (iii) un-supervised learning algorithms, e.g. K-means clustering algorithm. We prove that these algorithms can be casted into a mixed 0-1 linear programming problem (M01LP), in which the number of variables and constraints are linear in the number of input parameters. The obtained M01LP is solved by means of branch and bound algorithm. The new formulation of machine learning algorithms allows to (1) realize the same representation of many different algorithms, (2) easily combine these algorithm to study their reliability including their generalization and robustness, (3) optimize the parameter selection process and learning model selection process.

Our theoretical findings are supported by a number of experiments on real-world datasets from the field of information security and digital forensics. The experimental results show that our new proposed approaches (5) decreased the computational efforts due to optimal learning algorithms and optimal parameter selection, (6) increased the reliability including the generalization and robustness and (7) increased the efficiency and effectiveness of network-based intrusion detection systems, host-based intrusion detection systems, web attack detection systems, botnet malware detection systems and malicious PDF file detection.

* * *
27 Juin 2013 à 14 heures
Salle de réunion du LITA, UFR MIM
A general family of third order methods for finding multiple roots
par
Abdelhafid Serghini
University Mohammed I, ESTO, Laboratory MATSI,
Oujda, Morocco.

Newton's method is one of the fundamental tools in numerical analysis, operations research, optimization and control. It has numerous applications in management science, industrial and financial research, data mining. Newton's method is a method for finding successively better approximations to the roots (or zeroes) of a real or complex function. The Newton's method in one variable has a second order of convergence.

In recent years, some cubically convergent modified Newton's methods for multiple roots have been proposed and analyzed. These methods can be collected into two classes. The first one is based on the second derivative of the function f. The second one is based on the function f and its derivative f0.

In this work, we are interested in the second class. We describe a general family of iterative methods, which use exactly two values of f and one value of f0 at each iteration, for approximating a multiple root z with multiplicity m of a complex valued function. Almost all the families of methods existing in the literature are particular cases of this general method. We give some su±cient conditions that guarantee a third order of convergence and we discuss how to choose a small asymptotic error constant which may a®ect the convergence speed. Using Mathematica with its higher precision computation, we present some numerical examples to illustrate the theoretical results.

* * *
13 Juin 2013 à 14 heures
Salle de réunion du LITA, UFR MIM
On optimality and duality for robust multiobjective optimization problems
par
S. K. Mishra Yogendra Pandey
Department of Mathematics
Banaras Hindu University
Varanasi, India

We consider a multiobjective optimization problem with face of data uncertanity and its robust counterpart. We establish the sufficient optimality condition for a robust efficient solution and a weakly robust efficient solution of the uncertain multiobjective optimization problem under the assumption that the objective functions are convex and the inequality constraints are generalized convex.

We formulate Mond-Weir type dual for the uncertain multiobjective optimization problem and establish weak and strong duality theorems.

Keywords : Uncertain multiobjective optimization, Robust multiobjective optimization, Sufficient optimality condition, Robust duality

* * *
10 Avril 2013 à 14 heures
Salle de réunion du LITA, UFR MIM
Speeding up algorithms on tree decompositions with algebraic methods
par
Hans L. Bodlaender
Utrecht University

It is well known that many graph problems can be solved in linear time for graphs of bounded treewidth with help of dynamic programming on the tree decomposition.

The running time of such algorithms is typically at least exponential in the treewidth, but for many problems, only algorithms that are superexponential are known. In this talk, a new method is discussed to obtain faster algorithms on tree decompositions. Central ideas are "group dominance" to sparsify tables in a dynamic programming algorithm, a way to establish such group dominance by showing that certain matrices have small rank, and an explicit small size basis for these matrices.

The technique will be explained in an informal way at the hand of one central example: the Steiner Tree problem. Recent experimental work that shows that the technique gives significant speedups will also be discussed.

This is joint work with Marek Cygan, Stefan Fafiani, Stefan Kratsch, and Jesper Nederlof.

* * *
20 décembre 2012 à 14 heures
Salle de réunion du LITA, UFR MIM
Classifying Very-High-Dimensional Data with Random Forests of Oblique Decision Trees (RF-ODT) *
par
Thanh-Nghi Do
Institut Telecom; Telecom Bretagne
UMR CNRS 3192 Lab-STICC
Université européenne de Bretagne, France

L'algorithme des forêts aléatoires proposé par Breiman permet d'obtenir de bons résultats en fouille de données comparativement à de nombreuses approches. Cependant, en n'utilisant qu'un seul attribut parmi un sous-ensemble d'attributs tiré aléatoirement pour séparer les individus à chaque niveau de l'arbre, cet algorithme perd de l'information. Ceci est particulièrement pénalisant avec les ensembles de données en grandes dimensions où il peut exister de nombreuses dépendances entre attributs. Nous présentons un nouvel algorithme de forêts aléatoires d'arbres obliques obtenus par des séparateurs à vaste marge (SVM). La comparaison des performances de notre algorithme avec celles de l'algorithme de forêts aléatoires des arbres de décision C4.5 et de l'algorithme SVM montre un avantage significatif de notre proposition.

The random forests method is one of the most successful ensemble methods. However, random forests do not have high performance when dealing with very-high-dimensional data in presence of dependencies. In this case one can expect that there exist many combinations between the variables and unfortunately the usual random forests method does not effectively exploit this situation. We here investigate a new approach for supervised classification with a huge number of numerical attributes. We propose a random oblique decision trees method. It consists of randomly choosing a subset of predictive attributes and it uses SVM as a split function of these attributes. We compare, on 25 datasets, the effectiveness with classical measures (e.g. precision, recall, F1-measure and accuracy) of random forests of random oblique decision trees with SVMs and random forests of C4.5. Our proposal has significant better performance on very-high-dimensional datasets with slightly better results on lower dimensional datasets.

Keywords: High Dimensional Data, Random Forests, Oblique Decision Trees, Support Vector Machines.

* * *
24 Mai 2012 à 14 heures
Salle E203, UFR MIM
Linear Programming with Linear Complementarity Constraints
par
Prof Joaquim JUDICE
University of Coimbre, Portugal

Linear Programming with Linear Complementarity Constraints (LPLCC) is an area of active research in Optimization, due to its many applications, algorithms, and theoretical existence results. In this paper, a number of formulations for important nonconvex optimization problems are first reviewed. The most relevant algorithms for computing a complementary feasible solution, a stationary point, and a global minimum for the LPLCC are also surveyed, together with some comments about their efficiency and efficacy in practice.

* * *
10 Mai 2012 à 14 heures
Salle E203 - UFR MIM
Les métaheuristiques et leur adaptation pour l'optimisation continue
par
Patrick SIARRY
Université de Paris 12

La plupart des métaheuristiques ont été conçues, à l'origine, pour la résolution des problèmes d' « optimisation difficile » de nature discrète. Cependant, les ingénieurs sont souvent confrontés à des problèmes d'optimisation à variables continues : amélioration des performances d'un circuit électronique, identification des paramètres d'un modèle de gisement d'hydrocarbures, apprentissage d'un réseau de neurones ou d'une base de règles floues.

De tels problèmes peuvent être également « difficiles », dans un sens différent de celui consacré par la théorie de la complexité : fonction objectif non connue analytiquement ou bruitée, variables corrélées ou évoluant dans des gammes disparates, présence de non-linéarités, etc...

Les métaheuristiques offrent, dans ce cadre, un avantage précieux : elles n'exploitent pas les gradients de la fonction objectif. Ces techniques doivent cependant être adaptées au cas continu ; nous décrirons dans cet exposé quelques approches pour quatre métaheuristiques : le recuit simulé, la recherche tabou, les algorithmes génétiques et les algorithmes de colonies de fourmis. Nous esquisserons enfin le portrait d'un nouveau-né de la famille des métaheuristiques : la méthode des essaims particulaires, qui a été - quant à elle - conçue d'emblée dans le cas continu.

* * *
02 Février 2012 à 14 heures
Salle Ip1, UFR-MIM
Direct Multisearch For Multiobjective Optimization
par
Ismael F. Vaz
University of Minho, Portugal

In practical applications of optimization it is common to have several conflicting objective functions to optimize. Frequently, these functions are subject to noise or can be of black-box type, preventing the use of derivative-based techniques.

We propose a novel multiobjective derivative-free methodology, calling it direct multisearch (DMS), which does not aggregate any of the objective functions. Our framework is inspired by the search/poll paradigm of direct-search methods of directional type and uses the concept of Pareto dominance to maintain a list of nondominated points (from which the new iterates or poll centers are chosen).

The aim of our method is to generate as many points in the Pareto front as possible from the polling procedure itself, while keeping the whole framework general enough to accommodate other disseminating strategies, in particular when using the (here also) optional search step.

DMS generalizes to multiobjective optimization (MOO) all direct-search methods of directional type.

We prove under the common assumptions used in direct search for single objective optimization that at least one limit point of the sequence of iterates generated by DMS lies in (a stationary form of) the Pareto front. However, extensive computational experience has shown that our methodology has an impressive capability of generating the whole Pareto front, even without using a search step.

This is joint work with: A.L. Custódio, J.F.A. Madeira and Luis Nunes Vicente.

* * *
08 Décembre 2011 à 14 heures
E303, UFR-MIM
Sequential Coloring with Trichromatic Exchange
par
Hacène AIT HADDADENE
Operations Research Department, Mathematics Faculty, USTHB University
In this communication, we present a survey on the application of sequential colouring with trichromatic exchange technique, give some conjectures based on this technique and specify the results of some related concepts.
Mots-clés : Sequential coloring; Perfect Graph; Polynomial Algorithm; Maximum clique number; Conjectures.
* * *
10 novembre 2011 à 14 heures
E203, UFR-MIM
On the b-coloring problem
par
Flavia Bonomo
Université de Buenos Aires, Argentine
A b-coloring of a graph is a coloring such that every color class admits a vertex adjacent to at least one vertex receiving each of the colors not assigned to it. The b-chromatic number of a graph G is the maximum number t such that G admits a b-coloring with t colors.Several problems related to b-coloring of graphs have been introduced in the literature. Recently, the theory of b-colorings of graphs has been applied in to some clustering problems in data mining processes. In this talk, we will summarize the last algorithmic and theoretical results obtained on b-coloring and the related notions of b-perfection, b-continuity and b-monotonicity within some graph classes.
This is a mix of joint works with C. Betancur, G. Duran, I. Koch, F. Maffray, J. Marenco and M. Valencia-Pabon.
* * *
7 juillet 2011 à 14 heures 0
E203, UFM-MIM
On the Permuted Perceptron Problem - A New Formulation and Approach
par
Tiru S. Arthanari
University of Auckland Business School, Nouvelle-Zélande
The permuted perceptron problem (PPP) has received renewed interest due to its application in Cryptanalysis. Simulated annealing and other hybrid meta-heuristics are applied to attack this problem. Difference of convex functions approach is also combined with simulated annealing to solve problem instances of PPP.
In this talk after a brief review of the state of art of PPP approaches a new model for approaching the PPP will be introduced. This is a parametric minimum cost bipartite flow formulation with special cost structure. We have not worked on the computational efficiency of this approach, but highlight why this approach might yield better results.
* * *
23 juin 2011 à 11 heures 30
D206, UFM-MIM
Pre-invex and related Functions
par
Professor S. K. Mishra
Department of Mathematics, Banaras Hindu University Varanasi, India
In this talk, pre-invex functions and some of its generalizations are introduced. Some properties of pre-invex and related functions will be discussed as well.
* * *
23 juin 2011 à 10 heures 30
D206, UFM-MIM
DC Programming and DCA for solving DC Programs with DC constraints (joint work with Le Thi Hoai An and Huynh Van Ngai)
par
Professor Pham Dinh Tao
Laboratoire de Mathématiques, INSA de Rouen
DC (Difference of Convex functions) Programming and DCA(DC Algorithms) which constitue the backbone of Nonconvex Programming and Global Optimization were introduced by Pham Dinh Tao in their preliminary form in 1985 and extensively developed by Le Thi Hoai An and Pham Dinh Tao since 1994 to become now classic and increasingly popular (see for example http://lita.sciences.univ-metz.fr/~lethi/).DC programming is a natural and logical extension of Convex Programming, sufficiently large to cover almost all convex programs but not too in order to use the powerful arsenal of modern Convex Analysis and Convex Optimization.These theoretical and algorithmic tools have been successfully used by researchers to model and solve their nonconvex programs in different fields of Applied Sciences, in particular : Transport-Logistics, Telecommunication, Bioinformatics, Finance, Data Mining and Machine Learning, Cryptology, Mechanics, Image Processing, Robotics & Computer Vision, Petrochemistry, Optimal Control, Inverse Problems and Ill-Posed Problems, Multiobjective Programming, Variational Inequalty Problems (VIP), etc.In this talk, after a suitable outline of DC Programming and DCA, we present DC Programming and DCA for solving DC Programs with DC constraints.
* * *
23 juin 2011 à 9 heures
D206, UFM-MIM
Linear Multiobjective Optimization: Criteria and Dimension Reduction, and Optimization over Efficient Sets
par
Professor Nguyen Van Thoai
FB IV - Mathematik, Univ Trier, Germany
We discuss in this talk some methods for reducing the numbers of criteria and variables in a linear multiobjective optimization problem. Thereafter, a lift-and-project method for solving optimization problem over efficient sets is presented.
* * *
31 mars 2011 à 14 heures
E203, UFM-MIM
Apprentissage de fonctions définies par morceaux
par
Fabien Lauer
LORIA, Nancy
Les machines à vecteurs de support et autres méthodes à noyaux peuvent résoudre efficacement des problèmes de régression non linéaire, notamment grâce à la formulation d'un programme d'optimisation convexe.Cependant, ces approches se basent sur l'hypothèse d'une fonction recherchée continue et régulière. Le problème d'apprentissage de fonctions définies par morceaux impliquant des discontinuités de la fonction ou des dérivées à des points inconnus est bien plus difficile, car celui-ci mélange de manière intrinsèque des problématiques de classification et de régression.Ce séminaire introduira ce problème dans le cadre plus général de l'estimation de fonctions à commutations et formulera les programmes d'optimisation non convexe permettant de le résoudre. Quelques résultats numériques seront présentés pour permettre d'évaluer les avantages de ces formulations, notamment en termes d'efficacité pour traiter de grands jeux de données bruitées.
* * *
17 mars 2011 à 14 heures
E203, UFM-MIM
Programmation DC pour la détection de communautés
par
Conan-Guez Brieuc
LITA, Metz
Afin de détecter des communautés dans un réseau, un critère, nommé 'critère de modularité', a été proposé par Newman en 2004. Nous proposons dans ce travail, un nouveau schéma d'optimisation de ce critère basé sur la programmation DC.
* * *
22 octobre 2009 à 14 heures
Amphithéatre Hermite, UFM-MIM
Importance de la mise à jour dans les systèmes multi-agents. Une illustration sur le modèle 'multi-Turmite'.
par
Nazim Fatès
LORIA, Nancy
It is to date an open question to know how the updating methods affect the evolution of a multi-agent system.This question has been tackled for various complex systems such as cellular automata, Boolean networks, neural networks but little is known for multi-agent systems, especially for the models with a complex behaviour which emerges from simple local rules.Our talk focuses on the multi-Turmite model, also known as the multiple Langton's ants model.All the agents are updated simultaneously and the variation of the updating scheme consists only in choosing different strategies for solving the conflicts produced when two or more agents want to go on the same location.We show that for the same formulation of the agents' behaviour, and the same initial conditions, the use of different updating schemes may lead to qualitatively different evolutions of the system.As a positive spin-off of this study, we exhibit new phenomena of the multi-Turmite model such as deadlocks or gliders.
* * *
24 juin 2009 à 14 heures
Amphithéatre Hermite, UFM-MIM
Total Domination and the Caccetta-Häggkvist Conjecture.
par
Alain Hertz
Ecole Polytechnique de Montréal, Canada
A total dominating set in a digraph G is a subset W of its vertices such that every vertex of G has an immediate successor in W. The total domination number of G is the size of the smallest total dominating set.We consider several lower bounds on the total domination number and conjecture that these bounds are strictly larger than g(G)-1.where g(G) is the number of vertices of the smallest directed cycle contained in G.We prove that these new conjectures are equivalent to the Caccetta-Häggkvist conjecture which asserts that g(G)-10
* * *
1 avril 2010 à 14 heures
D216, UFR-MIM
Recent results for the Vehicle Routing Problem and its variants
par
Aristide Mingozzi
Université de Bologne, Italie
his paper presents an exact solution framework and a new state space relaxation method for solving some variants of the Vehicle Routing Problem (VRP) that can be modelled as Set Partitioning (SP) problems with additional constraints. The method consists in combining different dual ascent procedures to find a near optimal dual solution of the SP model. Then, a column-and-cut generation algorithm based on a new pricing strategy attempts to close the integrality gap left by the dual ascent procedures by adding valid inequalities to the SP formulation. The final dual solution is used to generate a reduced problem containing all optimal integer solutions that is solved by an integer programming solver. In this paper, we describe how this solution framework can be extended to solve different variants of the VRP by tailoring the different bounding procedures to deal with the constraints of the specific variant. We describe how this solution framework has been recently used to derive exact algorithms for a broad class of VRPs such as the Capacitated VRP (CVRP), the VRP with Time Windows (VRPTW), the Pickup and Delivery Problem with Time Windows (PDPTW), all types of Heterogeneous VRP (HVRP) including the Multi Depot VRP (MDVRP), and the Period VRP (PVRP).
The computational results show that the exact algorithm derived for each of these VRP variants outperforms all other exact methods published so far and can solve several test instances that were previously unsolved. Moreover, we show that the bounding method can be easily adapted to the Traveling Salesman Problem with Time Windows (TSPTW) and used into an exact dynamic programming algorithm. Our computational results indicates that the resulting exact algorithm outperforms all other exact methods published in the literature and is able of solving in few seconds all TSPTW instances previously unsolved by other methods.
* * *
4 mars 2010 à 14 heures
Amphithéatre Hermite, UFM-MIM
Apprentissage et Réseaux Sociaux.
par
Pr. Emmanuel Viennet
Laboratoire de Traitement et Transport de l'Information L2TI, Université de Paris 13
L'étude des réseaux sociaux a connu un essort remarquable ces dernières années, avec le développement de nouvelles méthodes d'analyse et de fouille de données. De nombreuses applications industrielles demandent l'analyse de données structurées en réseaux: sites Web 2.0, opérateurs de télécommunications. Les demandes sont variées et vont de la catégorisation de documents (messageries) à la détection de communautés d'utilisateurs, en passant par les systèmes de recommandation.
L'analyse des réseaux sociaux pose des problèmes difficiles, comme la modélisation des interactions 'sociales', la fouille de données structurées (graphes, textes, données hétérogènes) et la prise en compte de l'évolution temporelle des réseaux. De plus, les applications génèrent souvent des volumes de données très importants, avec des graphes comptants plusieurs dizaines des millions de noeuds, ce qui pose de sérieuses restrictions sur les algorithmes utilisables.
Dans ce séminaire, nous présenterons ce domaine de recherche et décrirons quelques problématiques et exemples issus de projets récents.
* * *
4 février 2010 à 14 heures
Amphithéatre Hermite, UFM-MIM
THE INFINITY COMPUTER AND NUMERICAL COMPUTATIONS WITH INFINITE AND INFINITESIMAL NUMBERS.
par
Yaroslav D. Sergeyev
Université de Calabria (Italie)
The lecture introduces a new methodology allowing one to execute numerical computations with finite, infinite, and infinitesimal numbers on a new type of a computer: the Infinity Computer (European Patent 1728149).The new approach is based on the principle 'The part is less than the whole' introduced by Ancient Greeks that is applied to all numbers (finite, infinite, and infinitesimal) and to all sets and processes (finite and infinite).It is shown that it becomes possible to write down finite, infinite, and infinitesimal numbers by a finite number of symbols as particular cases of a unique framework different from that of the non-standard analysis.
The new methodology evolves Cantor's ideas in a more applied way and introduces new infinite numbers that possess both cardinal and ordinal properties as usual finite numbers.It gives the possibility to execute computations of a new type and simplifies fields of mathematics where the usage of the infinity and/or infinitesimals is necessary (e.g., divergent series, limits, derivatives, integrals, measure theory, probability theory, fractals, etc.).Numerous examples and applications are given. A number of results related to the First Hilbert Problem are established.
The Infinity Calculator using the Infinity Computer technology is presented during the talk.
* * *
21 janvier 2010 à 14 heures
Amphithéatre Hermite, UFM-MIM
Projections non linéaires et modélisation topologique pour l'analyse exploratoire de données.
par
Michaël AUPETIT
Commissariat d'Energie Atomique
Dans de nombreux cas, les données que l'on veut comprendre peuvent se représenter comme un nuage de points dans un espace multidimensionnel. Lorsque ces données sont représentées dans le plan, la visualisation est un moyen efficace d'extraire des informations de nature statistique, géométrique et topologique. Lorsque les données ne se représentent pas naturellement dans le plan, il existe deux voies d'analyse possibles. D'une part, les méthodes de projection dans le plan et d'autre part, les méthodes d'analyse in situ dans l'espace multidimensionnel.Toutes deux posent le problème de l'intelligibilité de la représentation ainsi construite.Nous commencerons par présenter le paradigme de la visualisation multidimensionnelle in situ, qui définit un cadre dans lequel les projections planes de données multidimensionnelles sont interprétables. Nous montrerons que les méthodes de projection non-linéaires (type ISOMAP, MDS, Sammon, LLE, KPCA, SOM...) telles qu'elles sont habituellement employées ne sont en général pas utilisables pour inférer sans erreur des propriétés des données originelles. Nous montrerons comment replacer ces méthodes dans le cadre in situ pour leur donner tout l'intérêt qu'elles méritent. Nous présenterons ensuite une méthode d'extraction de caractéristiques topologiques du nuage de points multidimensionnel. Les caractéristiques topologiques (arc-connexité en particulier) sont habituellement extraites visuellement après projection des données dans le plan. Nous explorons la voie de l'extraction de ces caractéristiques directement dans l'espace d'origine par des modèles génératifs.
Nous montrerons sur des exemples la complémentarité de ces deux approches pour l'analyse exploratoire de données, et discuterons des problèmes ouverts dans ce domaine.
* * *
5 septembre 2008 à 14 heures
salle E203, UFM-MIM
Formal black box testing
par
Tudor BALANESCU
Université de Pitesti, Roumanie
Cet exposé sera séparé en deux parties : en premier lieu une présentation rapide de l'Université de Pitesti ainsi que du cadre d'un accord avec le département d'informatique de l'UFR-MIM concernant l'échange d'étudiants en master et d'enseignants, et en second lieu une présentation scientifique concernant les méthodologies de génération automatique de tests pour la validation des logiciels conçus à l'aide des X-machines.
* * *
2 juillet 2009 à 13 heures 30
Amphi Ampère, UFM-MIM
Approximation polynomiale pour la minimisation du flowtime pondéré sur une machine avec une contrainte d'indisponibilité
par
Imed Kacem
Université Paul Verlaine, Metz
We consider a single-machine scheduling problem with the aim of minimizing the weighted flowtime.We assume that the machine is unavailable during a fixed interval known in advance.The pre-emption of jobs is not allowed and one can perform only one job at a given time.The problem is NP-Hard and the elaboration of approximation algorithms is a challenging subject. Our contribution is related to the development of new approximation algorithms.In particular, we studied the WSPT rule worst-case performance and showed that its ratio is 3 under some conditions.Then, a new 2-approximation was proposed by improving such a rule.Finally, we designed an efficient fully polynomial time approximation scheme and showed that it is strongly polynomial.
* * *
27 mai 2009 à 14 heures
Salle Ampère, UFR MIM
Compact formulations for Difficult Combinatorial Problems - Pedigree Polytopes
par
Tiru Arthanari
University of Auckland, Auckland, New Zealand
This talk will be on some new polyhedral approaches that have exhibited some interesting properties and computational insights.Compact formulations are also studied by Carr and Lancia (2004), Carr et al (2007) for their performance.Multi stage insertion formulation for Symmetric Traveling Salesman Problem was given by Arthanari(1982) and subsequently Arthanari and Usha( 2001) brought out the interesting fact that the standard sub tour elimination polytope (SEP) due to Dantzig, Fulkerson and Johnson(1954) is equivalent to the projection space obtained from the MI formulation.That is it is tight compact formulation. New combinatorial objects called pedigrees which are in 1-1 correspondence with tours are defined and studied by Arthanari (2005, 2006, and 2008). The talk will highlight some of the interesting properties of the pedigree polytope, which have computational implications.
* * *
7 mai 2009 à 14 heures
salle Ampère, UFM-MIM
Incorporating Minimum Frobenius Norm Models in Direct Search
par
Luis Nunes Vicente
University of Coimbra, Portugal
The goal of this talk is to show that the use of minimum Frobenius norm quadratic models can improve the performance of direct-search methods.The approach taken here is to maintain the structure of directional direct-search methods,organized around a search and a poll step,and to use the set of previously evaluated points generated during a direct-search run to build the models.The minimization of the models within a trust region provides an enhanced search step.Our numerical results show that such a procedure can lead to a significant improvement of direct search for smooth,piecewise smooth, and stochastic and nonstochastic noisy problems.
* * *
2 avril 2009 à 14 heures
salle E203, UFM-MIM
Propriétés de la distribution statistique des pointeurs dans les gènes des ciliés.
par
Serghei VERLAN
Université Paris 12, France
Les gènes du macronoyau des ciliés sont composés des blocs séparés par des séquences non-codantes, l'ordre et l'orientation des blocs pouvant être différentes. Pendant la reproduction sexuelle tous les blocs sont assemblés dans le bon ordre et toutes les séquences non-codantes sont éliminées. Ce processus devient possible grâce à la structure spéciale des gènes du micronoyau: chaque bloc codant M se termine par une séquence de nucléotides, appelée pointeur, qui se répète en début du bloc qui succède M dans le gène assemblé. Le premier bloc commence par un marqueur du début et le dernier par le marqueur de la fin. Cependant, la longueur de certains pointeurs dans les gènes du micronoyau ne permet pas leur recognition sans ambiguïté. Plusieurs pointeurs possèdent des occurrences multiples sur les deux brins du gène,ce qui produit un grand nombre de division possibles en blocs codants et non-codants.
Nous avons étudié la distribution statistique des pointeurs pour tous les gènes séquencés à l'heure actuelle, afin d'identifier ce que différencie le gène réel parmi toutes les divisions codantes/non-codantes possibles. Cette étude nous a conduit à un critère qui différencie d'une manière stricte la division réelle. Les résultats obtenus utilisent une représentation du problème à l'aide de la théorie des langages formels.
* * *
29 novembre 2007 à 14 heures
salle FO6, IUT de Metz
Classification, Performance et Choix de fonds
par
Pascal Damel, Hery Razafitombo et Nadège Peltre
Université Paul Verlaine - Metz
Ce travail a pour principal objet la construction de méthodologie susceptible d’aider le gérant des fonds de fonds dans son activité de sélection. Les gérants de fonds de fonds se heurtent à une difficulté particulière lors dans la construction de portefeuille et la gestion de portefeuilles. Ils ne disposent pas de la relative lisibilité qu’ont les gérants de fonds traditionnels en matière de leviers de contrôle. Nous proposons dans cette étude une réflexion sur la méthodologie de choix de fonds dans le cadre d’un processus d’investissement et de construction d’un portefeuille de fonds de fonds. Plus particulièrement, nous proposons d’utiliser la méthode de classification hiérarchique pour constituer des groupes de fonds homogènes et sur lesquels le gérant peut faire correspondre ses objectifs d’investissements (anticipation, aversion pour le risque et horizon d’investissement). Il s’agit d’une méthodologie alternative à l’approche APT et à l’utilisation des classements des agences de notations en matière de gestion institutionnelle des fonds d’investissements. Elle a pour principal avantage de partir de l’ensemble d’informations directement à la disposition des gérants et surtout de proposer une approche multidimensionnelle pour tenir compte de la nature multicritère de la décision des gérants de fonds.
Mots-clés : performance des fonds d’investissement, sélection de fonds, méthode de classification.
* * *
22 novembre 2007 à 14 heures
salle FO6, IUT de Metz
Binary clustering and graphs
par
François Brucker
LITA, Université Paul Verlaine - Metz
In numerical taxonomy (data are described by a distance, or more generally by a dissimilarity), clusters classically are defined as the maximal cliques of some threshold graphs. However, according to this definition, a given dissimilarity may have an exponential number of clusters, which leads to the impossibility to compute them all in practice.
Analyzing a given dissimilarity is then, the most of time, only possible through approximating it by a dissimilarity whose clusters are polynomially computable (like ultrametrics whose cluster sets are hierarchies, Robinsonian dissimilarities whose cluster sets are pyramids and more generally or weak-ultrametrics whose cluster sets are weak hierarchies).
This talk shows that by using a slightly modified version of Melter’s boolean distances (called boolean dissimilarity) which are symmetric function from X×X to 2X (where X is the set of objects), one can associate to any dissimilarity an unique set of clusters which are polynomially computable.
The benefits of this approach are multiple. First of all, we do not need to approximate the data for producing clusters. Second, To each cluster is associated a pair of objects which represent it. Third, classical model of classification can be easily be interpreted as special boolean dissimilarities. At last, they are a polynomial instance of a NP hard representation problem.
References
  1. BARTHELEMY, J.-P., and BRUCKER, F. (2007), ”Binary Clustering”, Discrete Applied Mathematics, avaiable online.
  2. BRUCKER, F., and BARTHELEMY, J.-P. (2007), ”Éléments de Classification”, Hermes Publishing, London.
  3. BERTRAND, P. (2000), ”Set Systems and Dissimilarities”, European Journal of Combinatorics, 21, 727–743.
* * *
8 novembre 2007 à 14 heures
salle FO6, IUT de Metz
Algorithmique combinatoire et fouille de données
par
Alain Gély
LITA, Université Paul Verlaine - Metz
L'accroissement de l'utilisation de l'outil informatique a permis l'accès à de nombreuses données, à partir desquelles il faut extraire à posteriori des connaissances. La masse de données, en entrée (données brutes) comme en sortie (par exemple classes obtenues à partir des données) est telle qu'elle nécessite une algorithmique efficace.
Dans cet exposé, on s'intéressera plus particulièrement à un objet souvent utilisé dans le cadre de la fouille de données : Le treillis de Galois (Treillis des Concepts), ainsi qu'à une problématique algorithmique particulière : l'algorithmique d'énumération.
En effet, l'étude de la génération du treillis de Galois nous amènera à étudier des algorithmes d'énumération d'objets combinatoires : Cliques maximales d'un graphe et bicliques maximales d'un graphe biparti.
Dans un second temps, on s'intéressera au problème de la représentation d'un treillis (en fait, du système de fermeture pouvant lui être associé) par une famille d'implications. Après avoir rappelé l'intérêt d'une telle représentation en fouille de données (problème du panier de la ménagère), nous nous intéresserons aux problèmes algorithmiques posés par la génération des éléments d'une base d'implication minimale, la base de Guigues-Duquenne.
* * *
25 octobre 2007 à 14 heures
salle FO6, IUT de Metz
La convexité généralisée en économie mathématique
par
Jean Pierre Crouzeix
Université de Clermont Ferrand II
On montre, à travers la théorie du consommateur, comment la convexité est une notion tout à fait naturelle en économie.
* * *
18 octobre 2007 à 14 heures
salle FO6, IUT de Metz
Changing the Neighborhood of Cellular Automata
par
Hidenosuke Nishio
Université de Kyoto, Japon
We define the cellular automaton by (S, Q, fn, u), where S is a discrete space, Q is a state set, fn: Qn → Q is an n-variable local function and ν is an injection {1, …, n} → S called neighborhood function. A neighborhood function provides a connection between the variables of local function and the neighbors of every cell in S. Thus, Image(ν) ↔ (ν(1), …, ν(n)) becomes a neighborhood in the usual definition of CA.
When S and Q are fixed, say, S = ℤ and Q = {0, 1}, we focus on the pair (fn, ν) called local structure and investigate the global behavior of CA by changing local structures.
We first show basic properties of equivalence of local structures and then prove that a local structure induces countably many different global maps only by changing ν. Next we observe what properties depend on ν or not. Typically, we show some results and unsolved problems about reversibility and universality of 1-dimensional CA having 3 variable local function and 2 and 3 states. New Java Applet program and simulator will also be explained.
* * *
19 juin 2008 à 14 heures
salle F06, IUT de Metz
A Practical Solution for the Inventory Routing Problem with Stationary Demand Rates
par
El-Houssaine Aghezzaf
Ghent University, Belgium
Vendor-managed inventory (VMI) is a partnering strategy relating a supplier and his customers. Under the VMI policy, inventory monitoring and ordering responsibilities are entirely transferred to the supplier. As a consequence, the supplier decides both the quantities to deliver and the delivery times for his customers. The inventory routing problem (IRP) is an underlying optimization problem for VMI to cost-effectively coordinate and manage customer inventories and related replenishments logistics. The particular case where customer demand rates and travel times are stochastic but stationary will be discussed, and a version of the inventory routing optimization model that generates optimal robust distribution plans will be proposed. Results of a simplified real-life case implementing the proposed optimization-simulation approach will be discussed in detail.
* * *
29 mai 2008 à 14 heures
salle F06, IUT de Metz
Informatique de poche et entrée de texte
par
Mathieu RAYNAL
IRIT, Toulouse
La saisie de texte est une activité essentielle lors de l'utilisation d'un ordinateur. Pour les personnes ayant un fort handicap des membres supérieurs, cette activité a été rendue possible grâce aux claviers dits « logiciels » qui sont des représentations numériques de claviers physiques permettant de saisir des données. Le déplacement du pointeur pour pointer le caractère à saisir peut se faire à l'aide de tout type de dispositif de pointage : souris, trackball, touchpad, mais aussi des dispositifs plus « lourds » comme ceux de suivi du regard ou les mouvements de la tête.
Actuellement le clavier logiciel le plus fréquemment utilisé a une disposition de touches et de caractères qui est identique à celle des claviers physiques Azerty ou Qwerty (selon la culture). Si cette disposition présente l'avantage d'être utilisée depuis plus d'un siècle et donc d'être connue du plus grand nombre, elle a un inconvénient majeur qui réside dans l'éloignement des caractères les plus fréquemment utilisés. Ce problème ne se posait pas sur les claviers physiques avec l'utilisation de deux doigts différents pour saisir successivement deux caractères éloignés. Cependant, l'utilisation d'un seul pointeur pour sélectionner les caractères impose de déplacer ce dernier entre chaque caractère à saisir. L'éloignement des caractères les plus fréquemment utilisés entraîne une augmentation de la distance à parcourir avec le pointeur, ce qui engendre une diminution de la vitesse de saisie pour l'utilisateur, mais aussi des fatigues motrices voire oculaires.
Dans le but de diminuer au maximum les déplacements à effectuer avec le dispositif de pointage, de nombreuses techniques d'optimisation ont été testées. Après avoir présenté les différentes métriques utilisées pour évaluer les performances de l'utilisateur, nous dresserons un état de l'art des techniques d'optimisation déjà testées. Enfin, nous présenterons nos contributions à cette problématique avec :
  1. – l'application d'une méta-heuristique d'optimisation connue (les algorithmes génétiques) pour optimiser la disposition des caractères sur le clavier logiciel et ainsi minimiser les déplacements à effectuer lors de saisie de texte en français. Le clavier GAG (Généré par Algorithme Génétique) est le résultat de cette optimisation.
  2. – le système KeyGlass : celui-ci propose au fur et à mesure de la saisie des caractères supplémentaires à proximité du dernier caractère qui a été saisi. Ceci a pour but de diminuer les distances (avec le pointeur du dispositif de pointage) nécessaire à parcourir pour saisir du texte.
* * *
22 mai 2008 à 14 heures
salle F06, IUT de Metz
Informatique de poche et entrée de texte
par
Franck Poirier
Valoria - Université de Bretagne-Sud
&
LabSTICC - TELECOM Bretagne
La présentation portera sur l'essor de l'informatique de poche et de l'interaction nomade. L'exposé traitera de la problématique de la saisie de texte sur dispositifs mobiles en présentant un panorama des différentes approches de saisie. Les méthodes de saisie de la famille Glyph (Glyph2PPC, UniGlyph, HandiGlyph) seront plus particulièrement détaillées.
* * *
15 mai 2008 à 15 heures
salle FO6, IUT de Metz
Convexity-based clustering criteria and the k-tangent algorithm with applications to biclustering problems for a contingency table
par
Dr. Hans-Hermann Bock
Institute for Statistics, RWTH Aachen University
The well-known SSQ criterion in cluster analysis is typically minimized by using the k-means algorithm. This criterion can be generalized and leads to the maximization of a convex function of class means. Suitable transformations show that this new criterion can be maximized by a so called k-tangent or maximum-support-point algorithm. -- Such problems are met, e.g., when bi-clustering a contingency table. The paper presents the resulting iterative algorithm. Additionally, it discusses several principles for deriving bi-clustering criteria for data and for contingency tables.
* * *
15 mai 2008 à 14 heures
salle F06, IUT de Metz
The Eingenvalue Complementarity Problem
par
Joaquim Júdice
University of Coimbra and Institute of Telecommunications, Coimbra, Portugal
The Eigenvalue Complementarity Problem (EiCP) is discussed, which arises on a directional instability problem in systems with frictional contact. A few nonlinear programming formulations are introduced for the symmetric EiCP, that is, when the matrices of the problem are both symmetric, such that stationary points of the corresponding objective functions on appropriate convex sets lead to solutions of the problem. In the unsymmetric case, it is shown that the EiCP reduces to a Finite-Dimensional Variational Inequality and to a Mathematical Programming Problem with Linear Complementarity Constraints. Necessary and sufficient conditions for the existence of a solution to the EiCP are discussed. A spectral projected gradient method and an enumerative algorithm are introduced for finding a solution to the symmetric and unsymmetric EiCPs respectively. Computational experience is reported to illustrate the efficiency of the algorithms to deal with these two cases.
* * *
10 avril 2008 à 14 heures
salle FO6, IUT de Metz
Modélisation de la communication dirigée par la longueur dans le cadre du calcul moléculaire
par
Serghei Verlan
LACL, Université Paris 12
Dans cette présentation nous considérons la technique de séparation des molécules par la longueur, gel electrophoresis, qui est souvent utilisée en laboratoires biochimiques. Nous montrons une formalisation de cette technique dans le cadre du calcul moléculaire et nous démontrons que le modèle obtenu a la puissance d'une machine de Turing. Enfin, on discute quelques restrictions naturelles et des généralisations du modèle obtenu qui peuvent être utilisées pour la recherche des transformations efficaces des molécules d'ADN en laboratoire.
* * *
26 mars 2008 à 14 heures
salle FO6, IUT de Metz
Graphes structurés : étude algébrique et logique
par
Bruno Courcelle
LaBRI, Bordeaux
La construction des graphes de largeur arborescente ou de clique bornée permet d'étendre aux graphes les concepts de base de la théorie des langages : grammaires context-free, reconnaissabilité.
La logique du second ordre monadique permet de spécifier des propriétés de graphes et des transformations. La construction d'algorithmes FPT s'appuie sur ces notions.
* * *
13 mars 2008 à 14 heures
salle FO6, IUT de Metz
Upper bound analysis of branching algorithms
par
Magnus Wahlström
Institut Max Planck, Saarbruck, Allemagne
Branching algorithms are a common tool for solving NP-hard problems, both in theoretical work and in practice. A common focus in the theoretical work is to produce an algorithm with a strongest-possible upper bound on its worst-case running time (e.g. O(cn) for some constant c). This talk focuses on the analysis part of this process; that is, on how to show that a certain branching algorithm will have its time bounded by some O(cn) through the use of complexity measures.
One major step in this field is the work by Eppstein on multi-variate recurrences. For many branching algorithms, the best bound is due to modelling the execution of the algorithm as such a recurrence, and using Eppstein's method to automatically find a complexity measure which gives a bound O(cn) which is tight to within a polynomial factor for the model (if not for the actual execution of the algorithm). This model is presented, the assumptions and restrictions that surround the results are discussed, and some results and open questions on these are given.
In particular, Eppstein's model requires an assumption of uniformity of the algorithm. We finally show a way to relax this assumption, and give better bounds for essentially non-uniform algorithms, while still being able to automate the process, by using piecewise linear complexity measures. Here, #2SAT (the problem of counting solutions to a 2SAT formula) is used as an example.
* * *
6 mars 2008 à 14 heures
salle FO6, IUT de Metz
Changing the Neighborhood of Cellular Automata: Achieving universality and related questions
par
Thomas Worsch
Université de Karlsruhe
When investigating CA, usually a standard neighborhood is fixed and one looks at different local rules. We are interested in the opposite: Fix a local rule and have a look at what can happen when using it with different neighborhoods.
After some introductory examples and observations we will first show that one can achieve universality using a specific local CA function with neighborhoods of size 5. The second part of the talk will be concerned with some of the questions and problems related to the construction. In particular the presence/absence of certain propoerties of the notion of "simulation" used is worth a closer look.
* * *
28 février 2008 à 14 heures
salle FO6, IUT de Metz
Systèmes pédagogiques propositionnels
par
David Michel
LITA, Université Paul Verlaine - Metz
Il est fréquent dans l'enseignement des mathématiques d'illustrer les définitions d'objets à l'aide d'exemples les motivant dans le but de faciliter la compréhensions de notions parfois très abstraites. Certains théoriciens des sciences, comme Poincaré, préconisent de manière générale l'utilisation systématique de définitions accompagnées d'exemples. D'autres, comme Griss, avancent même que les définitions ne pouvant être motivées sont dénuées de sens.
Les systèmes pédagogiques sont des systèmes de déduction naturelle formalisant l'utilisation systématique de définitions motivées. Dans ce contexte, une définition est un ensemble de formules, les objets définis sont représentés par les variables libres de ces formules et les motivations sont des substitutions (i.e. des fonctions remplaçant des variables libres par des objets de même type dans une formule) rendant prouvables toutes les formules de l'ensemble.
Lors de cet exposé, nous présenterons différents systèmes pédagogiques propositionnels. Nous aborderons les conditions d'existence des motivations; puis nous détaillerons propriétés métamathématiques des systèmes pédagogiques, dont les principales sont la disparition de la négation et l'existence de traductions des systèmes intuitionnistes et classiques dans les systèmes pédagogiques.
* * *
7 février 2008 à 14 heures
salle FO6, IUT de Metz
Étude des courbes et surfaces discrètes
par
Isabelle Debled-Rennesson
LORIA
Les travaux qui seront présentés se situent dans le cadre de la géométrie discrète, dite analytique, initiée par Jean-Pierre Réveillès avec l'introduction de la définition arithmétique d'une droite discrète en 1991.
Dans la première partie de mon exposé, les algorithmes, issus de cette définition et permettant l'étude des courbes discrètes, seront exposés : estimateurs de paramètres géométriques, segmentation, polygonisation. Ces algorithmes perdent de leur efficacité sur des objets bruités et c'est pourquoi je présenterai, dans un second temps, un formalisme adapté aux objets discrets bruités qui tient compte du bruit inhérent aux outils et méthodes d'acquisition. Pour étudier les courbes et les surfaces discrètes bruitées, j'ai proposé les notions de segments flous arithmétiques et de morceaux de plans flous qui sont des généralisations des notions de segments de droites et de morceaux de plans discrets arithmétiques. L'étude des propriétés arithmétiques et géométriques de ces objets a permis d'obtenir des algorithmes de reconnaissance et d'extraire des paramètres géométriques (périmètre, courbure, normale, aire) sur les courbes et surfaces bruitées. Ces méthodes seront présentées ainsi que des applications en analyse d'image et en bioinformatique.
* * *
31 janvier 2008 à 14 heures
salle FO6, IUT de Metz
Sur la dissémination de l'information dans des classes de graphes réguliers et irréguliers
par
I. Todinca
LIFO, Université d'Orléans
Nous considérons un modèle très naturel de dissémination de l'information dans les graphes. Le processus démarre par le choix aléatoire des sommets actifs (contenant de l'information), chaque sommet étant choisi indépendamment avec probabilité p. Pendant le processus, un sommet inactif devient actif si la majorité absolue de ses voisins sont actifs ; les sommets actifs ne changent jamais d'état.
Nous donnons des familles de graphes pour lesquelles, même pour des valeurs de p relativement petites, l'information contamine presque sûrement la totalité du réseau. Ainsi, pour les « roues », formées d'un cycle plus un sommet universel, la contamination est presque certaine dès que p > 41%. Pour les graphes formés d'une grille torique plus un sommet universel, ce seuil baisse à 37%. Ceci contredit l'intuition naïve selon laquelle il faudrait une majorité de sommets initialement actifs afin de contaminer le graphe.
J'évoquerai brièvement quelques résultats sur les graphes cubiques, où il faut au moins 50% de sommets initialement actifs afin de contaminer le graphe.
* * *
17 janvier 2008 à 14 heures
salle FO6, IUT de Metz
Arbres m-aires de recherche et urnes de Pólya
par
Nicolas Pouyanne
Université de Versailles Saint-Quentin-en-Yvelines
Les arbres m-aires de recherche proviennent d'un algorithme de tri en informatique dans lesquels chaque nœud de l'arbre contient m clefs. Leur comportement aléatoire asymptotique présente une « transition de phase », selon que m≤26 ou m>26. Ces arbres entrent dans le modèle plus large des processus d'urnes de Pólya-Eggenberger, dans lesquelles des boules de plusieurs couleurs sont tirées aléatoirement une par une, avec une règle de remise dépendant de la couleur tirée. On fera l'analyse de ces algorithmes en décrivant l'asymptotique des processus aléatoires associés.
* * *
14 décembre 2006 à 14 heures
salle FO6, IUT de Metz
Exact algorithms for NP hard problems
par
Fedor Fomin
Université de Bergen, Norvège
It is a common belief that exponential time algorithms are unavoidable when we want to find an exact solution of an NP hard problem. The design of exact (moderately exponential) algorithms has a long history dating back to Held and Karp's paper on the travelling salesman problem in the early sixties. The last years have seen an emerging interest in constructing exact algorithms for combinatorial problems like Coloring, Max-Cut, 3-SAT, Minimum Dominating Set, Treewidth, and Maximum Independent Set. In this talk we overview some recent results and techniques in the area of exact algorithms and conclude with several open problems.
* * *
7 décembre 2006 à 14 heures
salle FO6, IUT de Metz
Un Algorithme exact exponentiel pour déterminer une clique dominante minimum
par
Mathieu Liedloff
LITA, Université Paul Verlaine - Metz
Une clique dominante d'un graphe G = (V, E) est un sous-ensemble des sommets qui est à la fois une clique et un ensemble dominant. On dit qu'un sous-ensemble C des sommets est une clique si et seulement si pour tout u, v dans C, l'arête {u, v} appartient au graphe. Un ensemble dominant est un sous-ensemble D des sommets tel que pour tout u n'appartenant pas à D, le sommet u a au moins un voisin dans D.
Décider si un graphe admet une clique dominante est un problème NP-complet. Par conséquent les problèmes d'optimisation Clique Dominante Minimum et Clique Dominante Maximum qui demandent respectivement de trouver une clique dominante de taille minimum et maximum sont également NP-difficiles.
Après avoir motivé l'étude des algorithmes exponentiels, nous présenterons un algorithme exact qui calcule une clique dominante minimum d'un graphe, si un tel ensemble existe. Nous montrerons que le temps d'exécution de notre algorithme est O(1,339n) grâce à une analyse utilisant la technique Mesurer pour Conquérir. En outre nous établirons comme borne inférieure Ω(1,2599n) sur le temps d'exécution au pire des cas. Nous compléterons l'exposé de quelques résultats connexes à l'étude de ce problème.
* * *
30 novembre 2006 à 14 heures
salle FO6, IUT de Metz
Optimisation et ré-optimisation en nombres entiers, application à la planification en transport
par
Anass Nagih
LITA, Université Paul Verlaine - Metz
Les travaux de recherche présentés dans cet exposé s'inscrivent dans le cadre de la résolution globale et efficace de problèmes d'optimisation de grande taille, issus de la gestion de ressources dans les réseaux de transport avec des volets théoriques, algorithmiques et applicatifs. Plus précisément, le travail de recherche présenté ici concerne les problèmes de (re)construction de rotations d'équipages en transport aérien suite à des perturbations majeures et leur résolution par des méthodes de décomposition. Il s'agit d'améliorer la qualité des solutions produites par le problème auxiliaire (par conséquent le nombre global d'itérations du schéma itératif) tout en réduisant le temps de résolution de chacune de ses instances. Les approches proposées sont basées :
  1. – d'une part sur des réductions de l'espace des états par agrégation des ressources ;
  2. – d'autre part sur l'utilisation de la ré-optimisation, en cas de faible modification des données, en exploitant l'historique des résolutions des différentes instances du processus.
Les principaux résultats théoriques et algorithmiques ont été validés expérimentalement sur des instances de la compagnie Air Canada issus de problèmes de planification opérationnelle.
* * *
9 novembre 2006 à 14 heures
salle FO6, IUT de Metz
Cellular Automata with a Fixed Local Function on Different Neighborhoods
par
Hidenosuke Nishio
Université de Kyoto
The neighborhood is a fundamental constituent of the cellular automaton. Usually a standard neighborhood like the von Neumann neighborhood is fixed and different local functions are investigated. In this talk, however, we go the reverse way; fix a local function and observe what happens if we change the neighborhood. We will show some instances where the global behavior is not affected by changing the neighborhood. On the other hand, injectivity and surjectivity are generally not preserved by changing the neighborhood.
* * *
31 mai 2007 à 15 heures
salle FO6, IUT de Metz
Quelques applications des fonctions splines variationnelles aux CAGD et aux sciences de la terre
par
Abdelouahed Kouibia
Université de Granada, Espagne
Dans ce travail, on considère un problème d'approximation des courbes et des surfaces paramétriques par des fonctions splines variationnelles, à partir d'un certain ensemble de donnée­s. Ce problème a des applications dans plusieurs champs, comme par exemple, CAGD, CAD, la Gé­ophysique et la Gé­ologie Structurelle, et autres Sciences de la Terre, etc...
Sous un sché­ma gé­né­rique, nous pré­sentons une mé­thode d'approximation sur des domaines borné­s, similaire à celle dé­veloppé­e par d'autres auteurs pour le cas des Dm-splines (voir [1] et [10]). Nous traiterons deux mé­thodes, l'une est d'interpolation et l'autre est d'ajustement, en minimisant certaines fonctionnelles dans un sous ensemble convexe d'un espace de Sobolev ou dans l'espace lui même. Ces fonctionnelles sont constitué­es d'une part, par une famille d'applications liné­aires et continues, qui ont pour but l'approximation d'un ensemble de donné­es bien dé­terminé­es, et d'autre part, par une autre famille de semiproduits scalaires continus, qui ont pour but la considé­ration de certaines restrictions, comme par exemple : la restriction « fair », la minimisation de la longueur, la minimisation de la courbure, la minimisation de l'air (voir [8]), etc...
Pour plusieurs applications dans les champs des Sciences de la terre et la CAGD, voir les réfé­rences [2]-[8].
On va terminer ce travail par une application au Dessin Gé­omé­trique Assisté­ par Ordinateur (CAGD) sur l'é­tude de blending curves, qui est un travail conjoint avec le Dé­partement de Mathématiques et d'Informatique de la Faculté­ des Sciences de l'Université­ Mohammed Premier, Oujda-Maroc, et le Laboratoire d'Informatique Thé­orique et Appliqué­e (LITA) de l'Université­ de Metz. Metz-France (voir [9]).
Bibliographie
  1. R. Arcangé­li, Dm-splines sur un domaine borné­ de ℝn. Publication UA 1204 CNRS N° 86/2 (1986).
  2. A. Kouibia, Aproximació­n de curvas y supercies paramé­tricas mediante splines variacionales, Thèse doctorale, Universidad de Granada, 28 de Mai 1999.
  3. A. Kouibia and M. Pasadas, Construction of Surfaces by discrete variational splines with Parallelism Conditions, J. Comput. Appl. Math. 164-165, 455-467, 2004.
  4. A. Kouibia and M. Pasadas, Approximation by Discrete Variational Splines, J. Comput. Appl. Math. 116, 145156, 2000.
  5. A. Kouibia and M. Pasadas, Variational bivariate interpolating splines with positivity constraints, Appl. Numer. Math. 44, 507-526, 2003.
  6. A. Kouibia, M. Pasadas and J. J. Torrens, Construction of Surfaces with Parallelism Conditions, Numerical Algorithms 33, 331-342, 2003.
  7. A. Kouibia and M. Pasadas, Construction of Surfaces by discrete variational splines with Parallelism Conditions, J. Comput. Appl. Math. 164-165, 455-467, 2004.
  8. A. Kouibia and M. Pasadas, Approximation of surfaces by fairness bicubic splines, Adv. Comput. Math. 20, 87-103, 2004.
  9. A. Kouibia, M. Pasadas, D. Sbibih, B. Bachir and A. Zidna, Linear interpolation Geometric continuity G2 of blended curves and surfaces, Preprint (2007).
  10. M. Pasadas, Aproximación de curvas y supercies paramé­tricas con condiciones de tangencia, Thèse doctorale, Universidad de Granada (1995).
* * *
31 mai 2007 à 14 heures
salle FO6, IUT de Metz
Optimization of Stochastic Systems and Worst-case Decisions
par
Nalan Gulpinar
Warwick Business School, Royaume-Uni
Stochastic decision-making involves uncertainty and consequently risk. An important tool to address the inherent error for forecasting uncertainty is worst-case analysis. The significance of robust strategies is increasingly recognized as attitudes towards risk evolve in diverse areas. In this talk I describe decision making methods for dynamic systems under uncertainty. Expected value optimization of stochastic systems and worst-case robust strategies are considered. Worst-case approach to financial portfolio management, mission planning and performance engineering is presented.
* * *
24 mai 2007 à 14 heures
salle FO6, IUT de Metz
Differential Evolution and its Applications in Optimization and Data Mining
par
Daniela Zaharie
Université de l'Ouest, Timisoara
Differential Evolution (DE) belongs to the class of stochastic optimization methods based on evolving a population of candidate solutions. Its main particularity with respect to other evolutionary methods consists in a particular type of recombination involving at least three parents. Since its invention, twelve years ago, DE attracted much interest due to its simplicity and good convergence behavior. A significant number of variants have been proposed and a lot of applications have been identified. Despite the large number of reported applications where DE was successfully applied, the theory of DE is still in its infancy. One of the problems in designing a DE, which may benefit from theoretical results, is to find the values of the control parameters which ensure a good balance between the exploration and the exploitation of the search space in order to avoid premature convergence or very slow convergence.
We will present some theoretical results concerning the exploration power of DE and a strategy to adapt the control parameters of the algorithm in order to avoid premature convergence. The influence of the process of adapting the control parameters on the algorithm behavior in the case of multi-objective, multi-modal and noisy optimization will be illustrated. Practical applications of DE in molecular structures optimization and in data clustering will be also presented.
* * *
10 mai 2007 à 14 heures
salle FO6, IUT de Metz
Modèles probabilistes de la connaissance pour les environnements d'apprentissage intelligents
par
Michel Desmarais
École Polytechnique de Montréal
Les environnements d'apprentissage intelligents, tels que les guides d'étude et les systèmes tutoriels, nécessitent souvent une évaluation détaillée des compétences acquises de l'apprenant. Les modèles probabilistes, comme les réseaux bayésiens, sont particulièrement adaptés pour l'évaluation des compétences acquises compte tenu de la nature incertaine de l'évaluation. En outre, les modèles basés sur l'apprentissage automatique à partir de données offrent des avantages attrayants par rapport aux modèles qui nécessitent l'intervention d'experts du domaine. Nous révisons les enjeux des modèles d'apprentissage automatique pour l'évaluation des compétences acquises. Nous rapportons les résultats de différentes études comparatives des modèles probabilistes bien connus et démontrons que des modèles simples en termes mathématiques et calculatoires, mais basés sur des fondements cognitifs reconnus, offrent les résultats les plus encourageants.
* * *
15 mars 2007 à 14 heures
salle FO6, IUT de Metz
Le parallélisme et équilibrage de charges dans les opérations de jointure sur une architecture distribuée
par
Mostafa Bamha
LIFO, université d'Orléans
La jointure est l'une des opérations les plus fréquentes et les plus coûteuses dans les systèmes de gestions de bases de données. Cette opération est très vulnérable au déséquilibre de l'attribut de jointure et au déséquilibre du résultat de jointure. Dans cet exposé, nous présenterons l'algorithme de jointure Osfa-join qui traite de manière efficace les problèmes du déséquilibre des données dans les opérations de jointures sur une architecture distribuée, tout en réduisant les coûts de communication au minimum. Une version pipelinée ainsi que d'autres extensions de l'algorithme sont également présentées. L'objectif du parallélisme pipeliné dans Osfa-join est de réduire le temps d'exécution des requêtes complexes tout en offrant une grande flexibilité dans l'allocation des ressources dans le parallélisme à grande échelle.
* * *
1 mars 2007 à 14 heures
salle FO6, IUT de Metz
Les données de biopuces et leur analyse
par
Doulaye Dembélé
Université de Strasbourg
La technologie de biopuces apparaît comme une technologie leader dans le domaine de la biologie moléculaire pour l'étude des gènes à l'échelle du genome. Nous nous intéresserons ici aux biopuces utilisées pour l'étude de l'expression génique. Une brève présentation de la technologie et de la production des données sera faite puis, les étapes d'analyse de ces données seront passées en revue. Nous nous intéresserons plus particulièrement aux méthodes de classification/clustering. Les problèmes liés au traitement de ces données qui sont de grandes dimensions seront évoqués ainsi que les solutions proposées. La présentation se terminera par les méthodes de fouille de données.
* * *
25 janvier 2007 à 14 heures
salle FO6, IUT de Metz
Self-organized symmetry in frame cellular automata
par
André Barbé
Katholieke Universiteit Leuven, Belgique
A frame is a finite set X of cells organized in a set of elementary frames. These are subsets Fj ⊂ X, j = 1,…,l such that lj=1 Fj = X. A frame forms the support of a so-called frame cellular automaton (FCA), which is obtained by attributing to each cell in the frame a state s from a finite set S, in some restricted way defined by a ("local") rule for the cell-states in each elementary frame. This rule is such that knowledge of all but one of the cell-states in an elementary frame determines the frame of the remaining cell. (I.e., if an elementary frame contains n cells, the configuration of the states in it is determined by an (n - 1)-ary quasigroup).
We discuss a series of experiments using FCA with geometrically symmetric support, where an essentially random feedback mechanism forces the state configuration pattern of the FCA into an attractor state with the same symmetry.
* * *
11 janvier 2007 à 14 heures
salle FO6, IUT de Metz
Épeler Fibonacci
par
Patrice Séébold
LIRMM, Université Montpellier II
Nous considérons les mots infinis, suites de lettres prises dans un alphabet donné. Ici nous nous intéressons à leur évolution sous l'action d'une transformation particulière, appelée par Conway « look and say », qui consiste à lire à haute voix les suites de lettres rencontrées en lisant un mot et à analyser le nouveau mot ainsi obtenu.
Nous nous focalisons plus particulièrement sur le mot de Fibonacci, mot infini engendré par le morphisme φ défini sur l'alphabet {1, 2} par φ(1) = 12, φ(2) = 1.
F = limn→∞ φn(1) = 1211212112112121121211211212112112…
Ce mot possède de nombreuses propriétés remarquables. En appliquant l'opération look and say au mot de Fibonacci qui commence par « un 1, un 2, deux 1, un 2,… », on obtient un nouveau mot (qui commence donc par 11122112) dont les propriétés sont intéressantes.
* * *
15 décembre 2005 à 14 heures
salle FO6, IUT de Metz
Extraction rapide d'information dans un corpus de documents textuelles. Application à Who is Who?
par
Abolfazl Fatholahzadeh
Supelec Metz
En extraction d'information (EI), on cherche à analyser le contenu des textes pour répondre à une besoin de recherche spécifique au sein d'un document. Dans cet exposé, la question de rapidité d'une telle recherche sera abordée par notre propre méthode combinant la théorie des automates et l'apprentissage symbolique. L'application de notre méthode pour déterminer des informations associées aux individus sera un prétexte pour aborder les problèmes suivants:
  1. P1. Le traitement des séquences des mots/clés inconnus vis-à-vis du (des) dictionnaire(s) d'EI ;
  2. P2. La richesse d'EI pour une classification pertinente.
Ensuite, nous montrons comment notre méthode traite efficacement P1 tout en aidant à résoudre le deuxième problème.
* * *
17 novembre 2005 à 14 heures
salle FO6, IUT de Metz
Modélisation neuronale et données fonctionnelles
par
Brieuc Conan-Guez
LITA, Université Paul Verlaine - Metz
L'Analyse de Données Fonctionnelles est une extension de l'analyse de données traditionnelles à des individus décrits par des fonctions. Le travail présenté ici s'inscrit pleinement dans ce courant, et tente de faire la jonction entre le domaine de la statistique fonctionnelle, et celui des techniques « neuronales » classiques.
L'extension du perceptron multi-couches (PMC) à des espaces fonctionnels apporte une réponse naturelle au traitement d'individus de type fonctions. Ce modèle possède deux propriétés théoriques importantes :
  1. – le modèle est un approximateur universel, i.e. que toute fonction continue définie sur un espace fonctionnel peut être approchée arbitrairement bien par un PMC fonctionnel ;
  2. – de plus, l'estimation des paramètres du modèle est consistante. L'originalité de ce résultat vient du fait que non seulement l'estimation s'effectue sur un nombre fini d'individus (les fonctions observées), mais que de plus chacune de ces fonctions n'est connue qu'en un nombre fini de points d'observation (discrétisation).
* * *
10 novembre 2005 à 14 heures
salle FO6, IUT de Metz
Résolution Parallèle du problème SAT : situation et perspectives
par
Daniel Singer
LITA, Université Paul Verlaine - Metz
Le problème SAT consiste à savoir si une formule du calcul propositionnel est satisfiable ou non. Ce problème est le prototype des problèmes NP-Complets et, du point de vue du parallélisme, un exemple d'application irrégulière.
De nombreux domaines ont récemment fait appel au formalisme propositionnel comme cadre de résolution ; citons les problèmes de planification et d'ordonnancement de tâches en optimisation combinatoire, la conception et la vérification de circuits logiques en électronique, le model checking borné dans les méthodes formelles et, très récemment, la cryptographie.
Plusieurs facteurs contribuent à ce regain d'intérêt pour SAT. Premièrement, de nouveaux algorithmes sont concus pour résoudre des problèmes de plus grande taille en un temps raisonnable (en 10 ans on est passé de 100 à 100 000 variables). Deuxièmement, des codages propositionnels plus sophistiqués sont proposés pour les problèmes réels et permettent, dans certains cas, de trouver une solution plus rapidement que dans leur codage d'origine. Cet intérêt crée une demande toujours croissante en puissance de calcul et notamment dans l'utilisation de machines parallèles ou distribuées pour la satisfaire. Mais, paradoxalement, il existe très peu de travaux fondamentaux ou de réalisations pratiques dans cette direction.
Après une présentation générale de la situation concernant la résolution séquentielle du problème SAT, nous donnons les diverses approches pour la résolution en parallèle. Nous aborderons aussi les perspectives de recherche dans ce domaine.
* * *
27 octobre 2005 à 14 heures
salle FO6, IUT de Metz
Au sujet des implémentations d'algorithmes primitifs récursifs
par
Pierre Valarcher
Université de Rouen
On s'intéresse à définir une classe d'algorithmes (assez large) en utilisant la notion de machine abstraite à états (ASM de Gurevich). Puis on montre comment un langage impératif simple permet d'implémenter de tels algorithmes. On discutera ensuite de la pertinence de cette classe d'algorithmes.
(Travail en commun avec Ph. Andary et B. Patrou - LIFAR).
* * *
13 octobre 2005 à 14 heures
salle FO6, IUT de Metz
From complex problems to efficient solutions: a structural and logical approach
par
Detlef Seese
Karlsruhe University
Many algorithmic problems of high complexity for graphs and networks can be solved efficiently (in polynomial or linear time) if their input structures are close related to trees (the similarity is measured by parameters as tree-width, branch-width, clique-width, ...). A uniform approach to such results is given by considering extensions of Monadic Second Order (MSO) logic and the logical tool of interpretability. The methods are used to investigate the borderline between decidable and undecidable monadic theories. A conjecture in this area states that each decidable MSO theory of countable structures can be reduced to the MSO theory of trees via interpretability. Recent results concerning this conjecture for graphs and matroids are discussed.
* * *
6 octobre 2005 à 14 heures
salle FO6, IUT de Metz
P-automata
par
Erzsébet Csuhaj-Varjú
Computer and Automaton Research Institute,
Hungarian Academie of Sciences
In this talk we characterize the classes of languages described by different variants of P automata, i.e. accepting P-systems with communication rules only.
Membrane systems, or P-systems, are biomolecular computing devices working in a distributed and parallel manner, inspired by the architecture and the functioning of the living cell. The main ingredient of a P-system are a hierarchically embedded structure of membranes and the sets of rules associated with them which describe the evolution and communication of the objects present in the regions embraced by the membranes.
P-automata have one more important ingredient: the environment. The environment is considered as an infinite supply of objects which may be requested by the application of one or more rules associated to the skin (the outmost) membrane, and these objects may traverse this membrane and enter when they are requested to do so. The objects in a P-automaton move through the membranes from region to region and they are not modified during the functioning of the systems. The languages determined by the P-automata are obtained as the set of accepted sequences of multisets containing the objects entering from the environment during the functioning of the system.
We present results on the computational power of these constructs, namely we show how we can obtain any recursively enumerable language by applying some appropriate mapping to the language of an appropriate P-automata. Motivated by properties of natural computing systems, computational complexity classes of the Turing machines with a certain restriction on the use of the available workspace in the course of computations have been related to the language classes described by P-automata. We show that if the rules of the P-system are applied sequentially, then the accepted language class is strictly included in the class of languages accepted by one-way Turing machines with a logarithmically bounded workspace, and if the rules are applied in the so-called maximal parallel manner, then the class of context-sensitive languages is obtained. We also discuss recent open problems in the area.
* * *
29 juin 2006 à 15 heures 30
amphitéâtre Pilâtre, UFR MIM
Sur l’orientation d’arêtes pour la détermination du nombre chromatique
par
Alain Hertz
École polytechnique de Montréal
Nous considérons le problème consistant à orienter les arêtes d’un graphe de telle sorte que la longueur d’un plus long chemin dans le graphe résultant soit minimum. Tel que démontré par Gallai, Roy et Vitaver, ce problème d’orientation d’arêtes est équivalent au problème de la détermination du nombre chromatique d’un graphe. Nous étudions diverses propriétés liées aux méthodes d’orientation d’arêtes dans le contexte de la recherche locale pour la coloration de graphes. Nous exploitons ensuite ces propriétés pour proposer quatre algorithmes de Recherche Tabou basés chacun sur des voisinages différents. Nous effectuons finalement quelques expériences numériques pour comparer ces quatre algorithmes, pour déterminer lesquels semblent les plus prometteurs et pour proposer des directions de recherche potentielles.
* * *
29 juin 2006 à 14 heures
amphitéâtre Pilâtre, UFR MIM
Vision-Simulated Imaging
par
Brian A. Barsky
Université de Californie
Vision-simulated imaging (VSI) is the computer generation of synthetic images to simulate a subject's vision, by incorporating the characteristics of a particular individual’s entire optical system. Using measured aberration data from a Shack-Hartmann wavefront aberrometry device, VSI modifies input images to simulate the appearance of the scene for the individual patient. Each input image can be a photograph, synthetic image created by computer, frame from a video, or standard Snellen acuity eye chart -- as long as there is accompanying depth information. An eye chart is very revealing, since it shows what the patient would see during an eye examination, and provides an accurate picture of his or her vision. Using wavefront aberration measurements, we determine a discrete blur function by sampling at a set of focusing distances, specified as a set of depth planes that discretize the three-dimensional space. For each depth plane, we construct an object-space blur filter. VSI methodolgy comprises several steps:
  1. creation of a set of depth images,
  2. computation of blur filters,
  3. stratification of the image,
  4. blurring of each depth image,
  5. and composition of the blurred depth images to form a single vision-simulated image.
VSI provides images and videos of simulated vision to enable a patient's eye doctor to see the specific visual anomalies of the patient. In addition to blur, VSI could reveal to the doctor the multiple images or distortions present in the patient's vision that would not otherwise be apparent from standard visual acuity measurements. VSI could educate medical students as well as patients about the particular visual effects of certain vision disorders (such as keratoconus and monocular diplopia) by enabling them to view images and videos that are generated using the optics of various eye conditions. By measuring PRK/LASIK patients pre- and post-op, VSI could provide doctors with extensive, objective, information about a patient's vision before and after surgery. Potential candiates contemplating surgery could see simulations of their predicted vision and of various possible visual anomalies that could arise from the surgery, such as glare at night. The current protocol, where patients sign a consent form that can be difficult for a layperson to understand fully, could be supplemented by the viewing of a computer-generated video of simulated vision showing the possible visual problems that could be engendered by the surgery.
* * *
8 juin 2006 à 14 heures
salle FO6, IUT de Metz
Nouvelles classes de graphes et ordonnancement
par
Cheikh Brahim Ould El Mounir
Université d'Amiens
Nous considérons un ensemble de tâches qui sont exécutées en une unité de temps chacune et k processeurs identiques. Ces tâches sont sujettes à des contraintes de précédence et des délai de communication (le délai de communication est le temps qu'il faut pour qu'un processeur informe un autre processeur que l'exécution de la tâche est terminée). Nous supposons que le délai de communication est constant et est égal à 0 ou à 1. Le graphe correspondant aux contraintes de précédence est un graphe orienté sans cycle (DAG) où l'ensemble des sommets représente l'ensemble des tâches (un sommet par tâche) et les arcs représentent les contraintes de précédences. Un tel graphe est appelé task-graph. Une des classes de graphes les plus connues des task-graph sont les graphes série-parallèle (VSP) introduites par Tarjan en 1982.
Nous allons présenter de nouvelles variantes des graphes série-parallèle ainsi que leurs algorithmes de reconnaissance associés. Ensuite, nous présenterons des solutions au problème d'ordonnancement cité plus haut sur ces nouvelles classes de graphes.
* * *
1 juin 2006 à 14 heures
salle FO6, IUT de Metz
The Splicing Operation on words and languages
par
K. G. Subramanian
Christian College, Madras
The operation of Splicing was introduced by Head (1987) while modelling the behaviour of DNA molecules under certain recombinant behaviour. This gave rise to a new operation in formal language theory. Subsequently theoretical studies on splicing have been made by many researchers in language theory giving rise to a rich theory of different splicing systems on linear words, circular words, images and so on. In this talk it is proposed to make a survey of some of these in the context of formal language theory.
* * *
18 mai 2006 à 14 heures
salle FO6, IUT de Metz
Window subsequence for compressed texts
par
Patrick Cegielski
Université Paris XII
Given two strings (a text t of length n and a pattern p ) and a natural number w, window subsequence problems consist in deciding whether p occurs as a subsequence of t and/or finding the number of size (at most) w windows of text t which contain pattern p as a subsequence, i.e. the letters of pattern p occur in the text window, in the same order as in p, but not necessarily consecutively (they may be interleaved with other letters). We are searching for subsequences in a text which is compressed using Lempel-Ziv-like compression algorithms, without decompressing the text, and we would like our algorithms to be almost optimal, in the sense that they run in time O(m) where m is the size of the compressed text. The pattern is uncompressed (because the compression algorithms are evolutive: various occurrences of a same patterns look different in the text).
* * *
2 février 2006 à 14 heures
salle FO6, IUT de Metz
Automates cellulaires et modélisation : quels sont les effets de l'asynchronisme ?
par
Nazim Fates
LORIA
Les automates cellulaires sont une classe de systèmes dynamiques discrets qui sont fréquemment utilisés pour modéliser des systèmes complexes dans lesquels la dynamique est spécifiée de façon locale. Dans leur acception classique, les automates cellulaires sont définis sur une grille régulière et avec un synchronisme parfait des transitions. Néanmoins, ces deux hypothèses ont peu de chances de représenter fidèlement ce qui se déroule à une échelle microscopique. Nous nous interrogeons donc sur la capacité des automates cellulaires à garder leur comportement lorsqu'ils sont soumis à de petites pertubrations de synchronisme. Nous présenterons des résulats qui se basent sur des simulations numériques et sur des résultats analytiques issus de la théorie des processus stochastiques.
* * *
26 janvier 2006 à 14 heures
salle FO6, IUT de Metz
Symport/antiport ou la puissance de la communication.
par
Serghei Verlan
Université de Paris XII
Symport/antiport est un mécanisme de transport intermembranaire dans les cellules vivantes. Nous le présentons brièvement et nous montrons sa formalisation à l'aide de la théorie des langages formels. Ensuite, nous montrons des résultats inattendus concernant la puissance d'expression et de modélisation du modèle obtenu.
* * *
19 janvier 2006 à 14 heures
salle FO6, IUT de Metz
Présentation des problèmes de maximisation des multiflots entiers et de minimisation des multicoupes : étude du cas particulier des grilles.
par
Marie-Christine Costa
Cnam, Paris
Soit G = (V, E) un graphe dont les arêtes sont pondérées par des entiers positifs et une liste de K paires {source, puits} de sommets. Le problème du mulitflot entier consiste à maximiser la somme des flots entiers routés entre chaque paire de sommets tout en respectant les contraintes de capacité sur les arêtes. Le problème de la multicoupe consiste à sélectionner un ensemble d'arêtes de poids total minimal de façon à séparer chaque paire de sommets. Si K = 1 on retrouve un problème de max flot-min coupe qui se résout simplement mais les deux problèmes sont connus pour être NP-difficiles pour K > 1 sauf dans des cas très particuliers. De nombreux articles, souvent très récents, traitent de ces problèmes qui ont des applications, par exemple, en télécommunications ou routage.
Dans cet exposé nous commencerons par définir les problèmes et plusieurs cas particuliers comme le problème de la coupe multiterminaux ou celui de la recherche de K chemins de longueur totale minimale sous contraintes de capacité. Nous donnerons une modélisation mathématique des problèmes et nous mettrons en évidence la relation de dualité qui existe entre multiflot et multicoupe. Cette dualité est utilisée dans la résolution des problèmes et l'une de ses conséquences est la « condition de coupe » : la capacité de toute multicoupe est supérieure à la valeur de tout multiflot.
Nous présenterons ensuite les résultats connus concernant la complexité, l'approximation et la résolution de ces problèmes: ces résultats dépendent de divers paramètres comme le type de graphe considéré ou le nombre et la situation des sources et des puits. Nous verrons que l'orientation du graphe est un facteur important dans l'analyse de la difficulté d'un problème.
Dans la deuxième partie de l'exposé, nous traiterons le cas particulier des grilles et nous présenterons un algorithme polynomial dans les grilles uniformes. Ce cas est particulièrement intéressant pour plusieurs raisons : à cause de ses applications, parce que la résolution utilise la dualité et des résultats importants de d'Okamura et Seymour et de Frank et enfin parce qu'il est à la frontière entre les cas « faciles » et « difficiles ».
Nous n'abordons ni les problèmes continus, ni ceux avec des coûts ni le problème des flots concurrents mais nous remarquerons que la recherche d'un multiflot qui satisfait des demandes et la recherche d'un multiflot maximal borné pas des demandes sont en fait des problèmes généraux de maximisation de multiflot.
* * *
9 décembre 2004 à 14 heures
salle FO6, IUT de Metz
Making Cortically-Inspired Sensorimotor Control Realistic for Robotics Design of an Extended Parallel Cellular Programming Model
par
Stéphane Vialle
Supelec, Metz
This seminar will introduce a multi-layer software architecture, that allows smart design and implementation of complex cortical neural networks, and efficient parallel execution on multiprocessor machines. The developer implements cortical networks sticking to their natural fine grained formalism, without caring about its mapping on coarse grained parallel computers. The developer can use a set of graphical tools to easily develop and debug the cortical systems.
Some experiments of new cortical model design on multiprocessor PCs are introduced, and some performance measurements are given. This software suite is operational and currently in use in our laboratory to control a robotic arm through cortical neural networks running on multiprocessor PCs.
* * *
2 décembre 2004 à 14 heures
salle FO6, IUT de Metz
Une théorie des codes dans les sous-monoïdes du monoïde libre
par
Jean Néraud
LIFAR, Université de Rouen
Un sous-ensemble X du monoïde libre A* est un code à longueur variable (ou, plus simplement, un code) si tout mot de X* (l'ensemble des produits de mots de X) se factorise en fait de façon unique comme concaténation de mots de X.La théorie classique des codes est constituée par de nombreux résultats tout aussi importants que difficiles à établir, comme l'illustre l'ouvrage de J. Berstel et D. Perrin « Theory of Codes » (Academic Press, 1985). Un des résulats les plus célèbres dans ce domaine, dû à M. P. Schützenberger, stipule l'équivalence, pour une large classe de codes contenant les codes rationnels, entre les deux notions suivantes :
  1. – la maximalité en tant que code (au sens de l'inclusion) ;
  2. – le fait que tout mot de A* puisse être facteur d'un mot de X*. Cette propriété est appellée densité de X* dans A*, ou encore complétude de X.
Un certain nombre d'auteurs se sont préoccupés de l'extension de ces résultats à un contexte de localité : un tel point de vue apparaît en effet implicitement présent dans le contexte de la dynamique symbolique. De par son algébricité, le concept de code dans un sous-monoïde de A* apparaît paticulièrement bien adapté. Nous relaterons quelques-uns des résultats que nous avons obtenus ces dernières années, en développant le plus récent, qui énonce une formule de complétion dans le cadre des sous-monoïdes rationnels. Les preuves de ces résultats permettent d'établir, dans un contexte plus général, ceux de la théorie classique.
* * *
25 novembre 2004 à 14 heures
salle FO6, IUT de Metz
Activités du thème IHM de l'équipe CMI du LITA
par
Benoît Martin
LITA, Université Paul Verlaine - Metz
Cet exposé a pour but de présenter les activités du thème IHM de l'équipe CMI du LITA. En premier lieu, les activités passées seront très brièvement abordées afin de comprendre l'évolution des travaux. En second lieu, toutes les activités du thème seront présentées à travers différents résumés: multi-modalité, géométrie hyperbolique et info-mobilité. L'objectif de cet exposé est de mieux comprendre l'activité du thème IHM mais également de susciter d'éventuelles collaborations au sein du LITA. Le contenu sera volontairement général afin de pouvoir présenter l'ensemble des activités. D'autres exposés pourront être proposés afin d'approfondir une partie ou une autre.
* * *
18 novembre 2004 à 14 heures
salle FO6, IUT de Metz
Sur la décomposition 2-join
par
Michaël Rao
LITA, Université Paul Verlaine - Metz
La décomposition modulaire est une décomposition de graphe très connue et très utilisée. Elle est basée sur la notion de « module ». Cette notion de module peut être généralisée à la notion de « split », et on peut définir la décomposition split, qui est une généralisation de la décomposition modulaire. Fabien de Montgolfier a montré que l'on peut également généraliser la définition du module à celle d'un « 2-join ».
Un 2-join dans un graphe G=(V,E) est une partition {V1,V2} de V telle qu'il existe W1 sous-ensemble de V1 et W2 sous-ensemble de V2 tels que les arêtes dans le graphe entre V1 et V2 soient les arrêtes entre W1 et W2 ou entre V1\W1 et V2\W2.
* * *
4 novembre 2004 à 14 heures
salle FO6, IUT de Metz
"Descente Infinie" Induction Principle and Saturation-based Theorem Provers
par
Sorin Stratulat
LITA, Université Paul Verlaine - Metz
I present a uniform representation and a methodology for building induction provers based on the Fermat's "descente infinie" induction principle. In a previous talk, I have presented an example of using this principle to build implicit induction provers, like Spike and QuodLibet.
In this talk, I present a methodology to design inference systems for saturation-based theorem provers that has the advantage to make a clear separation between logic and computation. Firstly, I introduce an abstract inference system defining the available set of induction hypotheses, i.e. the not-yet certified information that can be safely used during the reasoning process. Its inference rules are then instantiated modularly with different reasoning techniques in order to obtain concrete procedures, as it is shown for a couple of existing inference systems.
* * *
7 avril 2005 à 14 heures
salle FO6, IUT de Metz
Pourquoi est-il si difficile de prouver qu'un problème a une borne inférieure de complexité ? Un point de vue logique
par
Étienne Grandjean
GREYC, université de Caen
L'un des objectifs premiers de la complexité algorithmique est d'analyser en quoi beaucoup de problèmes naturels sont intrinsèquement difficiles à résoudre. Qu'en est-il actuellement de cet objectif dans les faits ? Quoique l'on soupçonne que la classe si importante des problèmes NP-complets est formée de problèmes non polynomiaux (la conjecture NP≠P) ou même exponentiels, on ne sait toujours pas prouver pour aucun problème NP-complet naturel aucune borne inférieure de complexité non triviale (non linéaire en temps) sur aucun modèle de calcul de portée générale (de type RAM).
Dans cet exposé, on donnera quelques résultats expliquant, de notre point de vue, cette difficulté étonnante à prouver des bornes inférieures de complexité :
  1. – la grande majorité des problèmes NP-complets naturels sont dans NLIN (sont reconnaissables en temps non déterministe linéraire) ;
  2. – beaucoup de ces problèmes sont même encore plus faciles :
    1. certains problèmes de graphes (exemples : cycle hamiltonien et non planarité) sont reconnus sur RAMs en temps non déterministe linéaire O(n) en le nombre n de sommets du graphe concerné, donc indépendamment de son nombre d'arètes ;
    2. d'autres problèmes (Sac à dos, Clique, etc) sont résolubles par RAMs en temps linéaire O(n) et espace sous-linéaire O(√n) (et donc en temps déterministe sous-exponentiel 2O(√n) ;
    3. enfin, divers problèmes NP-complets paramètrés classiques, typiquement k-Vertex-cover (recouvrement d'un graphe par k sommets), sont résolubles en temps polynomial, et souvent linéaire, en utilisant seulement un nombre limité f(k) de pas non déterministes, c'est-à-dire un nombre de pas non déterministes dépendant du paramètre k, mais indépendant de la taille de la donnée.
Enfin, on montrera comment sur tous ces points (résultats de complétude, bornes inférieures ou bornes supérieures de complexité), la logique (sur les structures finies) joue un rôle essentiel. On décrira quelques résultats (très partiels) en matière de bornes inférieures.
* * *
31 mars 2005 à 14 heures
salle FO6, IUT de Metz
Kimberling's sequence revisited
par
Gencho Skordev
Université de Breme
Clark Kimberling defined in Journal of Integer Sequences (2000) a set S of positive integers as follows:
  1. 1 belongs to S;
  2. if the positive integer x belongs to S, then 2x and 4x-1 belong to S;
  3. S is the smallest set of positive integers with these properties.
Hence S = (sn)nwritten in the natural order is:
1, 2, 3, 4, 6, 7, 8, 11, 12, 14, 15, 16...
An unexpected relation of this sequence with the Fibonacci word (fn)nwas found by Kimberling:
Theorem (sn+1modulo 2)n= (fn)n.
Remind that the Fibonacci word is the fixed point of the morphism (substitution) m on the two letter 0, 1 alphabet: m(0) = 01, m(1) = 0. An explanation, new proof and a general framework of this theorem is proposed.
* * *
24 mars 2005 à 14 heures
salle FO6, IUT de Metz
Des modèles de mélange aux cartes auto-organisatrices pour la fouille de données visuelle
par
Priam Rodolphe
Université de Rennes
Le traitement statistique des échantillons de données multimédia, génomique et web requiert de nouvelles méthodes exploratoires adaptées à leurs grandes dimensions. Le modèle de mélange exprime élégamment sa puissance et sa flexibilité en analyse des données puisqu'il donne des résultats particulièrement pertinents pour la classification automatique. Nous étudions le modèle de mélange par ses variantes auto-organisées : les lois du mélange y sont contraintes afin que leurs moyennes forment une surface discrète sur laquelle se projettent les données.
L'exposé s'articule comme suit. Nous posons le cadre du modèle de mélange de lois ainsi que son estimation par algorithme EM (Expectation-Maximization) et son application en classification. Nous présentons les méthodes de visualisation à base de mélange en nous centrant sur la famille des cartes auto-organisatrices (Kohonen), et notamment le cas des tableaux de contingence et de leur double représentation lignes/colonnes. Nous illustrons les méthodes sur des données réelles et donnons des perspectives détaillées.
* * *
17 mars 2005 à 14 heures
salle FO6, IUT de Metz
Graphes parfaits et coloration des sommets d'un graphe
par
Hacene Ait Haddadene
Faculté de Mathématiques, Alger
L'introduction des graphes parfaits remonte au début des années soixante à l'époque où C.Berge a introduit ce concept en s'intéressant aux travaux de C.Schannon en théorie de l'information sur la capacité d'un canal de communication.
Le problème de coloration des sommets d'un graphe est NP-complet, donc on ne connaît pas à ce jour d'algorithme en temps polynomial permettant de le résoudre à coup sûr. Ce problème devient polynomial dans le cas des graphes parfaits . Bien que polynomial, cet algorithme de Grötschell, Lovasz et Schrijver n'est pas efficace sur le plan pratique. En plus de sa complexité semblant être très élevée, cet algorithme ne permet pas de comprendre la structure combinatoire des graphes parfaits. D'où l'intérêt de rechercher de simples algorithmes combinatoires pour ce problème.
Dans cet exposé, nous allons essayé de présenter l'historique du cheminement de l'étude des graphes parfaits et son lien avec le problème de la coloration des sommets d'un graphe. Particulièrement, notre contribution dans ce cadre ainsi que certains liens seront présentés.
* * *
10 mars 2005 à 14 heures
salle FO6, IUT de Metz
Vérification de propriétés temporelles reconsidérée
par
Stephan Merz
LORIA
L'algorithme classique pour la vérification de formules en logique temporelle par rapport à de systèmes de transitions consiste en deux phases : d'abord on construit un automate de Büchi qui correspond à la négation de la formule à vérifier, puis on cherche à détecter certains cycles dans le produit du système de transitions et de l'automate obtenu. La génération de l'automate de Büchi est d'une complexité exponentielle (PSPACE), tandis que la vérification est linéaire dans la taille du produit, et est souvent faite « à la volée », c'est-à-dire sans jamais calculer le produit de forme explicite. Dans cet exposé je vais présenter un nouvel algorithme qui permet d'entrelacer ces deux étapes. Dans cette approche, la formule en logique temporelle est traduite en un automate alternant faible (en complexité linéaire de la taille de la formule) dont le graphe des configurations correspond à un automate de Büchi généralisé. La vérification se base ensuite sur une version de l'algorithme de Tarjan et construit le graphe de configurations (de taille exponentielle) à la volée. Cette démarche évite la construction explicite d'un automate de Büchi ce qui peut entraîner de gains significatifs en temps d'exécution et en mémoire quand la formule à vérifier est de grande taille. L'algorithme a été implémenté au sein du vérificateur SPIN ce qui nous permet de valider notre approche.
* * *
3 mars 2005 à 14 heures
salle FO6, IUT de Metz
Critiques des modèles de langage statistique
par
Kamel Smaili
LORIA
Dans cet exposé nous montrons les limites des modèles de langage statistique utilisés actuellement dans les systèmes de reconnaissance de la parole. Nous proposerons ensuite quelques pistes et quelques solutions originales pour pallier les insuffisances de ces modèles.
* * *
10 février 2005 à 14 heures
salle FO6, IUT de Metz
Graph homomorphisms with local constraints
par
Jan Kratochvil
Charles University, Prague
A homomorphism between two graphs is a vertex mapping which preserves edges, and hence neighborhoods of vertices. We will show that imposing further local constraints (bijectivity, injectivity or surjectivity) leads to notions that have been studied before, from different points of view and for different motivations. These will be both theoretical (graph covers stemming from topological graph theory) and practical (distance constrained labellings stemming from the very practically motivated frequency assignment problem). Algorithmic and computational complexity issues will be discussed.
* * *
27 janvier 2005 à 14 heures
salle FO6, IUT de Metz
Adaptation de maillage anisotrope pour des applications en mecanique des fluides
par
Pascal Frey
Université Pierre et Marie Curie
L'adaptation de maillages permet d'améliorer la convergence des algorithmes numériques ainsi que la précision des solutions numériques dans de nombreuses applications de calcul scientifique. Cette technique repose sur plusieurs composantes qui seront présentées : estimateur d'erreur a posteriori, métriques anisotropes et méthodes de maillages adaptatives. Des exemples de calculs en mécanique des fluides viendront étayer ces résultats théoriques.
* * *
13 janvier 2005 à 14 heures
salle FO6, IUT de Metz
Subexponential parameterized algorithms
par
Fedor Fomin
Université de Bergen
Parameterized algorithms have been introduced in the nineties by Downey and Fellows as another attack against NP-hard problems. The basic idea is that a (natural) parameter has to be part of the problem input and the question is whether there is an efficient algorithm to solve the problem assuming that the parameter has a fixed value. By now "parameterized algorithms" has become one of the important domains in "algorithms". In the talk we discuss some of the results from Robertson-Seymour Graph Minors Project and recent techniques for obtaining subexponential parameterized algorithms.
* * *
6 janvier 2005 à 14 heures
salle FO6, IUT de Metz
Calculer géométriquement sur le plan
par
Jérôme Durand-Lose
Université d'Orléans
Cet exposé se place dans l'étude des modèles du calcul continus. Nous y montrons que la géométrie plane permet de calculer. Nous définissons un calcul géométrique et utilisons la continuité de l'espace et du temps pour stocker de l'information au point de provoquer des accumulations et atteindre une autre puissance de calcul.
Dans le monde des automates cellulaires, on parle souvent de particules ou de signaux (qui forment des lignes discrètes sur les diagrammes espace-temps) tant, pour analyser une dynamique que, pour concevoir des automates cellulaires particuliers. Le point de départ de nos travaux est d'envisager des versions continues de ces signaux. Nous définissons un modèle de calcul continu, les machines à signaux, qui engendre des figures géométriques suivant des règles strictes. Ce modèle peut se comprendre comme une extension continue des automates cellulaires.
L'exposé commence par une présentation des automates cellulaires et la mise en avant d'exemples de particules/signaux tirés de la littérature. De là, nous abstrayons le modèle, les machines à signaux.
Dans un premier temps, nous montrons comment tout calcul au sens de Turing (par la simulation de tout automate à deux compteurs) peut y être mené. Nous montrons également comment modifier une machine de manière à réaliser des transformations géométriques (translations, homothéties) sur les diagrammes engendrés. Nous construisons également les itérations automatiques de ces constructions de manière à contracter le calcul à une bande (espace borné) puis, à un triangle (temps également borné).
Dans un second temps, nous nous intéressons aux points d'accumulation. Nous montrons que la prévision de l'apparition d'une accumulation est indécidable. Ce problème est même Σ20-complet (hiérarchie arithmétique), en construisant pour tout automate à deux compteurs une machine à signaux et une configuration initiale simulant l'automate pour toutes les valeurs possibles.
Avec quelques exemples, nous montrons l'existence d'accumulations, non pas en un point, mais sur un segment ou un Cantor. Nous introduisons alors une restriction sur les règles assurant qu'il ne peut y avoir que des accumulations sur des points isolés. Il est toujours possible de mener tout calcul malgré cette contrainte. Par ailleurs, les accumulations sont « propres », ce qui permet d'avoir une capacité de calcul semblables à celles sur les ordinaux ou de l'utilisation d'un « trou noir » (infinité d'itérations pendant une durée finie bornée).
* * *
19 décembre 2002 à 14 heures
salle FO6, IUT de Metz
Automates sur les ordres linéaires
par
Véronique Bruyère
Université de Mons
Dans cet exposé, on parlera d'automates acceptant des mots indicés par des ordres linéaires. Ces automates sont des objets simples, qui généralisent de façon naturelle les automates sur les mots finis, les mots infinis, les mots bi-infinis et les mots indicés par des ordinaux.
Les langages de mots acceptés par ces automates sont aussi les langages décrits par des opérations rationnelles bien choisies (Théorème à la Kleene). Celles-ci généralisent les opérations rationnelles connues par les mots indicés par les ordinaux.
Grâce à des exemples clairs, on présentera ces automates et les opérations rationnelles associées. On présentera aussi une hiérarchie où les langages sont classés selon les opérations rationnelles utilisées pour les décrire. Chaque classe sera caractérisée par des automates particuliers et par des ordres particuliers.
Cette recherche a été faite en collaboration avec Olivier Carton (IGM, Marne-la-Vallée).
* * *
12 décembre 2002 à 14 heures
salle FO6, IUT de Metz
Complexity Hierarchies on Turing Machines and Cellular Automata
par
Chuzo Iwamoto
Université d’Hiroshima - Université de Metz
It is known that a slight increase of a time or space bound yields a new complexity class: For any computable functions t1(n) and t2(n) such that:
  1. t2(n)≠O(t1(n));
  2. t2(n)-space Turing machines (TMs) are strictly more powerful than t1(n)-space TMs;
  3. t2(n)·log(t1(n))-time TMs are strictly more powerful than t1(n)-time TMs.
In this talk, we present an improved space-hierarchy theorem for TMs with restricted tape symbols. We also present time-hierarchy theorems based on cellular automata in the Euclidean and hyperbolic planes.
* * *
5 décembre 2002 à 14 heures
salle FO6, IUT de Metz
Deux modèles de calcul (bio)moleculaire
par
Serghei Verlan
Université de Metz
Les calculs moléculaires sont un nouveau paradigme de calcul qui utilisent les manipulations de (bio)molécules pour résoudre des problèmes de calculabilité.
L'idée principale de cette approche est qu'on code des données dans des molécules, particulièrement dans les molécules d'ADN, et qu'on utilise après des techniques de chimie et de biologie moléculaire pour effectuer des opérations calculatoires.
Afin de modéliser le processus, plusieurs modèles de calcul ont été proposés et étudiés du point de vue de leur puissance de calcul et de la possibilité de les réaliser en laboratoire.
Dans l'exposé proposé, on s'intéresse plus particulièrement à deux de ces modèles, les « systèmes distribués à changement de phase » créés récemment par Gh. Paun, les « systèmes distribués à changement de phase étendus » introduits par M. Margenstern et Yu. Rogozhin.
* * *
28 novembre 2002 à 14 heures
salle FO6, IUT de Metz
Décomposition modulaire de graphes et problèmes NP-complets
par
Michaël Rao
Université de Metz
La décomposition modulaire est une décomposition d'un graphe, qui peut être representée par un arbre enraciné, où chaque noeud a une étiquette et éventuellement un graphe associé. Cette décomposition a été très étudiée, et il existe des algorithmes linéaires pour la calculer.
On veux se servir de la décomposition modulaire dans le but de résoudre efficacement des problèmes NP-complets sur certaines classes de graphes.
On verra dans un premier temps quels sont les sous problèmes à résoudre sur les nœuds de l'arbre de décomposition modulaire pour certains problèmes.
Ensuite nous verons une application de cette méthode à la classe des graphes sans P5 et gems induits, dont on a une caractérisation des graphes dans l'arbre de décomposition modulaire.
* * *
21 novembre 2002 à 14 heures
salle FO6, IUT de Metz
Algorithmes qui donnent des certificats pour la reconnaissance de graphes d'intervalles et de graphes de permutation
par
Dieter Kratsch
Université de Metz
Un certificat est une pièce justificative pour montrer que la sortie d'un algorithme n'était pas altérée par un bug dans une implémentation de l'algorithme. On cherche des algorithmes pour un problème de décision qui donnent un certificat pour la réponse « oui » et aussi un certificat pour la réponse « non » sans prendre plus de temps que le meilleur algorithme (sans certificat) connu.
On présente un algorithme linéaire pour la reconnaissance des graphes d'intervalles qui donnent comme certificat un modèle d'intervalles (oui) et un triple astéroidal (non). On présente un algorithme linéaire pour la reconnaissance des graphes de permutation qui donnent comme certificat une permutation (oui) et un « chemin transposé » (non). Les certificats pour « oui » sont standard. Nos certificats pour « non » peuvent être authentifiés en un temps O(n), c'est-à-dire que l'authentification se fait plus vite que la reconnaissance.
Tous les precedents algorithmes de reconnaissance pour les deux classes de graphes connu n'arrivent pas à donner des certificats pour « oui » et « non ».
* * *
14 novembre 2002 à 14 heures
salle FO6, IUT de Metz
Recherche de complexité dans les automates cellulaires grâce aux algorithmes évolutionnaires
par
Emmanuel Sapin
Université de Bourgogne
Cet exposé présente une approche évolutionnaire de la recherche d'automates cellulaires complexes au sens de Wolfram. A l'aide d'un système de classification automatique, nous avons isolés plusieurs automates cellulaires complexes à deux dimensions. D'après les critères proposés par Wolfram, ces automates ne pouvent être considérés comme appartenant aux classes 1, 2 ou 3. Pourtant, contrairement au jeu de la vie, la plupart d'entre eux ne produisent pas spontanément de glisseurs à partir d'amas de cellules générés aléatoirement avec densité 1/2. A l'aide d'un algorithme génétique, nous avons fait évoluer ces automates dans le but de faire émerger de nouveaux automates à deux dimensions supportant des glisseurs. Nous avons obtenus non seulement des automates ayant le comportement recherché, mais également des automates supportant des canons à glisseurs. Ces résultats montrent que l'algorithmique évolutionnaire peut s'avérer efficace pour la recherche d'automates cellulaires ayant des comportements spécifiques. Nous estimons que l'approche proposée est une piste prometteuse pour la recherche de nouveaux automates cellulaires ayant, à l'instar du jeu de la vie, la propriété d'être des calculateurs universels. Nous proposerons des perspectives de recherche allants dans ce sens.
* * *
7 novembre 2002 à 14 heures
salle FO6, IUT de Metz
Rough sets, une approche de la fouille de données
par
Éric Sanjuan
IUT de Metz
Introduite à l'origine par Z. Pawlak pour optimiser les très larges systèmes de gestion de bases de données relationnelles, la théorie des ensembles d'approximation s'applique aujourd'hui naturellement à la fouille de données. L'exposé comprendra trois courtes parties correspondant chacune à un aspect de cette théorie :
  1. nous rappellerons d'abord la définition originale des ensembles d'approximation ainsi que leur structure algébrique multivaluée. Nous montrerons comment l'étude de ces algèbres permet de définir des langages d'interrogation souple de bases de données.
  2. nous introduirons ensuite les notions de système d'information et de décision considérés par cette théorie ainsi que les méthodes qu'elle propose d'extraction de connaissances (règles de classification et d'association). Usuellement présentées en termes de recherche d'implicants premiers, les algorithmes utilisés s'énoncent plus naturellement dans la théorie des hypergraphes.
  3. enfin nous aborderons la notion d'espace de dépendance introduite par Pawlak et Novotny, que l'on peut facilement rattacher à la notion classique de dépendance fonctionnelle. Nous présenterons alors de manière très simple le théorème de Guigues et Duquenne sur les bases des systèmes de fermeture (ou des treillis de Galois). Ce théorème issu d'une autre approche de la fouille des données, permet en effet de résumer dans le cas fini, l'ensemble des dépendances exactes en un sous-ensemble réduit, unique et sans redondances.
* * *
24 octobre 2002 à 14 heures
salle FO6, IUT de Metz
Complexité intentionnelle du langage LOOP
par
Pierre Valarcher
Université de Rouen
On étudit le langage LOOP du point de vue de son pouvoir algorithmique. On cherche à répondre à la question: y a t'il des algorithmes non programmable alors que la fonction est représentable dans un tel langage ? On répond positivement en étudiant l'algorithme du minimum de deux entiers.
* * *
10 octobre 2002 à 14 heures
salle FO6, IUT de Metz
Formules 2-CNF insatisfaisables minimales
par
Christian Choffrut
Université Paris 7
Une conjonction de clauses (une formule CNF) est insatisfaisable si il n'existe aucune affectation de variables qui la rende vraie. De plus, elle est insatisfaisable minimale si la suppression de l'une quelconque de ses clauses la rend satisfaisable. Le problème de déterminer si une formule CNF donnée est insatisfaisable minimale est DP-complet où DP représente toutes les intersections d'un problème dans NP d'un problème coNP. Récemment, il a été prouvé que si la différence entre le nombre de clauses et le nombre de variables était fixé, le problème devenait polynomial.
Nous étudions le cas plus simple des formules 2-CNF (toutes les clauses sont des disjonctions d'au plus deux littéraux) pour lesquelles le problème d'insatisfaisabilité est complet dans NL. Nous montrons que les formules 2-CNF insatisfaisables minimales avec n variables ont au moins n + 1 clauses (ce qui est bien connu et en fait général quelque soit la taille de chaque clause) et au plus 2n clauses. Nous caractérisons les formules 2-CNF insatisfaisables minimales avec un nombre maximal de clauses, (donc 2n clauses). Dans une autre direction, c'est-à-dire en étudiant les formules 2-CNF insatisfaisables minimales de taille minimale, nous introduisons une notion de simplification de formules 2-CNF qui nous permet d'éliminer les variables qui apparaissent exactement une fois postivement et une fois négativement et nous montrons qu'il existe pour tout entier pair de variables, disons sur 2n variables, une unique 2-CNF insatisfaisable minimale ayant un nombre minimal de clauses et qui possèdent exactement 3n clauses. Enfin, nous donnons un algorithme linéaire qui décide si une formule 2-CNF donnée est insatisfaisable minimale.
* * *
20 mars 2003 à 14 heures
salle FO6, IUT de Metz
Graphes dynamiques pour les systemes pair-a-pair
par
Pierre Fraigniaud
LRI, Orsay
A content-addressable network (CAN) is a distributed lookup table that can be used to implement peer-to-peer (P2P) systems. A CAN allows the discovery and location of data and/or resources, identified by keys, in a distributed network (e.g., Internet), in absence of centralized server or any hierarchical organization. Several networks have been recently described in the literature, and some of them have led to the development of experimental systems. We present a new CAN, called D2B. Its main characteristics are: simplicity, provability, and scalability. D2B allows the number of nodes n to vary between 1 and |K| where K is the set of keys managed by the network. In term of performances, any join or leave of a user implies a constant expected number of link modifications, and, with high probability (w.h.p.), at most O(log(n)) link modifications. The latency of a lookup routing is O(log(n)), w.h.p., in the sense that a key is at most O(log(n)) hops away from a consumer. A join involves key redistribution among two nodes (which is the minimum possible), including the node joining the system. Similarly, a leave involves key redistribution among at most three nodes. The set of keys is fairly distributed among nodes, in the sense that every node is responsible for an expected number of |K|/n keys, and, w.h.p., O(|K|·log(n)/n) keys. The traffic load incurred by lookup routing is also fairly distributed, and the expected congestion of a node is O(log(n)/n). Finally, a parameter d allows a trade-off between the degree of the network, which increases linearly with d, and the diameter of the network, which decreases logarithmically with d. Hence, a large d allows faster lookup routing, at the price of a slight increase of the latency for joining and leaving the network. We believe that these properties make D2B currently the most promising network for a practical and efficient use of CANs.
* * *
13 mars 2003 à 14 heures
salle FO6, IUT de Metz
Programmation par réécriture de multi-ensembles
par
Jean-Pierre Banâtre
Université de Rennes I
Le modèle Gamma a été proposé il y a une quinzaine d'années comme un formalisme permettant de construire des programmes sans séquentialité artificielle. La structure de donnée essentielle est le multi-ensemble et la structure de contrôle de base opère comme un transformateurde multi-ensembles. Fondamentalement, le modèle peut être vu comme l'évolution globale d'une collection de valeurs atomiques interagissant de manière assez libre.
Intuitivement, Gamma est souvent introduit via la métaphore de la réaction chimique. L'unique structure de données (le multi-ensemble) peut être vu comme une solution chimique. Un programme est une paire (condition de réaction, action). L'exécution consiste à remplacer les éléments satisfaisant la condition de réaction par les éléments produits par application de l'action. Le résultat est obtenu lorsqu' aucune réaction n'est plus possible (un état stable est atteint).
Gamma a été une source d'inspiration très riche dans un nombre de domaines assez inattendus tels que le développement de programmes parallèles, le calcul de processus, les architectures logicielles, etc.
Notre exposé va passer en revue le concept de multi-ensemble, faire un historique du formalisme Gamma et présenter plusieurs exemples de programmes développés dans ce cadre.
* * *
20 février 2003 à 14 heures
salle FO6, IUT de Metz
Une métaphore topologique pour un langage de simulation non-conventionnel et son application à la simulation de processus biologiques
par
Jean-Louis Giavitto
Université d’Evry
Dans ce travail, nous proposons d'aborder la notion de programme sous un point de vue topologique : un calcul consiste à spécifier un chemin dans un certain espace et à associer des actions élémentaires à chaque étape de ce déplacement. Cette nouvelle approche est mise en oeuvre dans un langage de programmation expérimental appelé MGS et dédié à la simulation de processus biologique.
MGS introduit la notion de collection topologique : un ensemble de valeurs organisées par une relation de voisinage permettant de définir une notion de chemin et de sous-collection. Le mécanisme de calcul est la transformation : une transformation consiste à sélectionner une sous-collection définie par un chemin C dans une collection A, et à le remplacer par une nouvelle sous-collection B = f(A, voisins(A)).
Le changement de la structure topologique de la collection permet de faire varier le modèle de calcul sous-jacent. MGS permet ainsi de présenter de manière unifiée dans le même langage de programmation plusieurs modèles de calculs développés indépendamment comme la réécriture de multi-ensembles (Gamma, CHAM et système de Paun), la réécriture de mots (système de Lindenmayer) ou les automates cellulaires.
Dans cette présentation nous évoquerons plusieurs applications, en particulier en relation avec des problèmes de modélisation en biologie.
* * *
6 février 2003 à 14 heures
salle FO6, IUT de Metz
Self-Assembling Finite Automata and Grammars with Scattered Nonterminals
par
Martin Kutrib
Université de Giessen
A self-assembling finite automaton is assembled on demand during its computation from copies out of a finite set of items. The items are pieces of a finite automaton which are connected to the already existing automaton by overlaying states. Depending on the allowed number of such interface states, the degree, infinite hierarchies of properly included language families are shown.
The model is a natural and unified generalization of regular and context-free languages since degrees one and two are characterizing the finite and pushdown automata, respectively. Moreover, by means of different closure properties nondeterministic and deterministic language families are separated.
Considering grammars with scattered nonterminals which can be thought of as having sentential forms where some instances of a nonterminal may be coupled, we have a second approach that naturally extends the generative capacity of context-free grammars. If the degree of synchronous rewriting is bounded, then we obtain again an infinite hierarchy of separated language families. It turned out that for certain types automata and grammars are matching.
* * *
30 janvier 2003 à 14 heures
salle FO6, IUT de Metz
MPEG4 Virtual Environment and mobility
par
Frédéric Vexo
École polytechnique de Lausanne
This talk will provide an overview of several research and development projects which deal with the production, the diffusion and the interaction of inhabited virtual environment on low performance device or/and with low bandwidth availability.
For example: the new breed of Personal Digital Assistants (PDA) and mobile phones have enough computing power to display 3D graphics. These new mobile devices (handhelds) have some interesting communication and interaction possibilities as well. Moreover, on a variety of devices a MPEG-4 compliant animation engine (body player) has been designed to synthesize virtual human full-body animations in interactive multimedia applications for the web. We believe that a full-body player can provide a more expressive and interesting interface than the use of animated faces only (talking heads). I will show one of the first implementations of a MPEG-4 animation engine with deformable models (it uses the MPEG-4 Body Definition Parameters and Deformation Tables). Several potential applications are overviewed.
* * *
23 janvier 2003 à 14 heures
salle FO6, IUT de Metz
k-fermat cellular automata
par
Friedrich von Haeseler
Université de Louvain
In this talk we introduce the class of k-fermat cellular automata (CA). Roughly speaking is a k-fermat CA characterized by a certain self-similarity of the time evolution of the CA. We discuss several different aspects of k-fermat CA.
* * *
16 janvier 2003 à 14 heures
salle FO6, IUT de Metz
Algèbres de Hopf de fonctions symétriques et quasi symétriques
par
Gérard Duchamp
Université de Rouen
Les algèbres de Hopf correspondent à deux opérations combinatoires extrêmement simples et courantes. La première (le produit) est celui des fonctions selon une « table de multiplication » comme celle des écoliers, la deuxieme (le coproduit) à deux visages tout aussi élémentaires l'un que l'autre : le premier est le « doublement des variables » que l'on connait bien dans les formules d'addition, le second est celui des décompositions d'objets. Nous montrerons en particulier comment cette idée simple nous a permis de résoudre la question des éléments primitifs de l'algèbre de convolution des permutations.
* * *
13 décembre 2001 à 14 heures
salle FO6, IUT de Metz
Sur la reconnaissance des sous-graphes induits
par
Daniel Meister
Université de Metz
Une classe de graphe peut être décrite par quelques propriétés de ses membres qui peuvent, quelquefois, être interprétées comme un ensemble de sous-graphes induits interdits. Un algorithme de reconnaissance pour une telle classe de graphes pourrait utiliser une déscription par des graphes induits interdits. Une des classes les plus connues est la classe des cographes qui est égale à la classe de tous les graphes non contenants un chemin induit à quatre sommets (P4). La complexité d'un tel algorithme de reconnaissance dépend essentiellement de la complexité de la reconnaissance de quelques graphes induits.
L'exposé donne la définition d'une certaine forme de difficulté pour comparer la complexité de reconnaissance de deux graphes et montre quelques résultats qui bornent la complexité de reconnaissance de certains graphes.
* * *
6 décembre 2001 à 14 heures
salle FO6, IUT de Metz
Ordering relations for q-boson operators
par
Gerard Duchamp
Université de Rouen
* * *
29 novembre 2001 à 14 heures
salle FO6, IUT de Metz
Sur les graphes sans P5 et sans gem
par
Dieter Kratsch
Université de Metz
En utilisant la decomposition modulaire d'un graphe nous arrivons a presenter un theoreme de caracterisation de classe de graphes sans P5 et sans gem. En effet nous donnons une liste complete de tous les graphes premiers sans P5 et sans gem.
En utilisant notre theoreme de caracterisation on construit des algorithmes efficaces pour la reconnaissance de graphes sans P5 et sans gem, et en plus pour les problemes NP-complets Weighted Independent Set et Clique sur les graphes sans P5 et sans gem.
* * *
22 novembre 2001 à 14 heures
salle FO6, IUT de Metz
Data Mining : Spécificités et Applications
par
Rico Rakotomalala
Université Lyon 2
Le terme « Data Mining » est aujourd'hui galvaudé, mis à toutes les sauces notamment dans le monde industriel. Notre objectif est de resituer la démarche de l'Extraction de Connaissances à Partir de Données. Nous mettrons alors en exergue ses spécificités par rapport aux domaines déjà connus telles que la statistique : elles tiennent à la fois des sources de données utilisées et des méthodes mises en oeuvre. Nous nous attarderons sur quelques unes de ces méthodes. Enfin, nous développerons une application typique de Data Mining, le « text mining », dans lequel une grande partie de l'arsenal du Data Mining est mis à contribution. Le séminaire sera conclu par une démonstration logicielle sur données artificielles et réelles.
* * *
15 novembre 2001 à 14 heures
salle FO6, IUT de Metz
Sur les nombres d'Erdös-Woods
par
Patrick Cegielski
Université Paris XII
Un intervalle [a,a+d] d'entiers naturels vérifie la propriéeté de n'avoir aucun élément premier avec simultanément ses deux bornes, si aucun de ses éléments, à savoir a+1, a+2, ..., a+d-1, n'est premier avec les deux extrémités a et a+d. Nous montrons que l'ensemble des tels a et l'ensemble des tels d sont récursifs. Un programme generant les premiers nombres conduit a de nombreux problemes ouverts, proches de ceux poses par la suite des nombres premiers.
* * *
8 novembre 2001 à 14 heures
salle FO6, IUT de Metz
Embeddings in k-connected graphs of pathwidth k
par
Andrzej Proskurowski
* * *
20 juin 2002 à 14 heures
salle FO6, IUT de Metz
Sur la largeur arborescente d'un graphe planaire et de son dual
par
Ioan Todinca
Université d'Orléans
Nous donnons une preuve simple du résultat suivant, conjecturé par Robertson et Seymour et prouvé par D. Lapoire : la largeur arborescente d'un graphe planaire diffère de celle de son dual d'au plus une unité. Nous montrons que les séparateurs minimaux d'un graphe planaire peuvent être vus comme des courbes de Jordan. Une triangulation minimale (au sens des graphes triangulés, i.e. sans cycle induit ayant quatre sommets ou plus) d'un graphe planaire correspond à une famille de courbes de Jordan deux à deux parallèles. Nous introduisons une notion de région-bloc formée par ces courbes et nous montrons comment associer les cliques maximales de la triangulation à des régions-bloc minimales. Ensuite, nous montrons comment à partir d'une triangulation H du graphe construire une triangulation du dual dont la largeur (la taille de la clique de cardinal maximum) dépasse celle de H d'au plus un.
* * *
6 juin 2002 à 14 heures
salle FO6, IUT de Metz
De la classification de données textuelles à la recherche d'information: une approche discrète
par
Éric Sanjuan
Université de Metz
Nous présentons un système de recherche d'information (RI) des donnés textuelles qui intègre les résultats d'une classification automatique. Dans ce système, une requête est modélisée par un ensemble gradué de thèmes (les classes) grâce à une généralisation de la notion d'ensemble d'approximation (Rough Set), défini par Pawlak. Le plongement de ces ensembles gradués dans une algèbres de Heyting permet de doter ce système d'un puissant langage logique d'interrogation et de représentation des connaissances.
Ce système RI a été expérimenté à l'unité de recherche de l'INIST (CNRS) sur des donnés de classification obtenues avec NEURODOC, un logiciel de classification automatique qui applique une variante de la méthode des k-means axial introduite par Alain Lelu selon une approche Neuronale.
Cependant ce système RI est aussi adapté à l'utilisation de résultats issues d'autres méthodes. Nous présenterons ainsi une méthode originale, introduite par Fidelia Ibekwe, de classification de données textuelles qui repose sur la reconnaissance de relations linguistiques et le calcul d'un graphe réduit de ces relations.
Références
  1. R. Baeza-Yates, B. Ribeiro - Neto, Modern Information Retrieval, ACM Press, Addison-Wesley, 1999, 510 p.
  2. Z. Pawlak, Rough Sets, Theoretical Aspects of Reasoning about Data, Kluwer, Dordrecht, 1991.
  3. A. Lelu, Modèles neuronaux pour l'analyse de données documentaires et textuelles, Thèse de doctorat de l'Université de Paris 6, 1993.
  4. F. Ibekwe - Sanjuan, A linguistic and mathematical method for mapping thematic trends from texts, ECAI 98, Henri Prade (ed.), John Willey and Sons, Ltd (1998) pp. 170 -- 174.
* * *
30 mai 2002 à 14 heures
salle FO6, IUT de Metz
Reversibility and Cellular Automata
par
Thomas Worsch
Université de Karlsruhe
Reversibility of computations has become a topic in which researchers from several disciplines are interested. After a short review of the origins of these interests we will concentrate on reversible simulations. That is the task to simulate a possibly irreversible computation on a reversible model of computation. In particular we will give an overview of the state of the art of simulations on reversible cellular automata. We will conclude with an outline of our current research which is concerned with the improvement of the time overhead of reversible simulations of cellular automata on infinite configurations.
* * *
23 mai 2002 à 14 heures
salle FO6, IUT de Metz
Recognition of interval graphs
par
Lorna Stewart
Université d'Alberta, Canada
A graph is an interval graph if it is the intersection graph of intervals on the real line. We survey the history of interval graph recognition algorithms, and describe the recent, easily implementable algorithm of Corneil, Olariu, and Stewart. This algorithm is based upon the well-known lexicographic breadth-first search (LBFS) paradigm.
* * *
4 avril 2002 à 14 heures
salle FO6, IUT de Metz
The GNU Eiffel Compiler
par
Dominique Colnet
LORIA, Nancy
Visite guidée du langage Eiffel et des outils de SmallEiffel. Présentation du principe et des mécanismes de la « programmation par contrats ». Présentation de la notion d'agent Eiffel (fermeture lexicale avec évaluation partielle). Utilisation des agents dans le cadre de la nouvelle bibliothèque graphique Picasso.
* * *
28 mars 2002 à 14 heures
salle FO6, IUT de Metz
Linear cellular automata on finitely generated abelian groups - revisited
par
Gencho Skordev
Université de Brême
A new method for the investigation of self-similarity and automaticity properties of the orbits of finite initial configurations w.r.t. linear cellular automata with states in finite field is discussed.
* * *
14 mars 2002 à 14 heures
salle FO6, IUT de Metz
Prédicats morphiques et extensions
par
Olivier Carton
Université de Marne-la-Vallée
Nous considérons la structure (N,<,P) des entiers naturels munis de l'ordre, étendue par un prédicat unaire P. Nous montrons que pour un prédicat morphique P, la théorie monadique du second ordre associée MTh(N,<,P) est décidable. Ce résultat étend les résultats précédents de Elgot et Rabin (1966) et Maes (1999). La solution est obtenue par des méthodes de théorie des semigroupes, qui sont reliées à l'approche par automates de Elgot et Rabin. Finalement, nous montrons comment ces méthodes permettent d'obtenir une large classe de prédicats P pour lesquels la théorie MTh(N,<,P) est décidable.
Travail en collaboration avec W. Thomas.
* * *
7 mars 2002 à 14 heures
salle FO6, IUT de Metz
New Results on Graph Subcoloring
par
Fedja Fomin
Université de Paderborn
A subcoloring is a vertex coloring of a graph in which every color class induces a disjoint union of cliques. We derive a number of results on the combinatorics, the algorithmics, and the complexity of subcolorings.
On the negative side, we prove that 2-subcoloring is NP-hard for comparability graphs, and that 3-subcoloring is NP-hard for AT-free graphs and for complements of planar graphs. On the positive side, we derive polynomial time algorithms for 2-subcoloring of complements of planar graphs, and for r-subcoloring of interval and of permutation graphs. Moreover, we prove asymptotically best possible upper bounds on the subchromatic number of interval graphs and permutation graphs in terms of the number of vertices.
* * *
28 février 2002 à 14 heures
salle FO6, IUT de Metz
Pourquoi les dynamistes s'intéressent aux automates cellulaires
par
François Blanchard
CNRS
Un automate cellulaire unidimensionnel F d'alphabet A est souvent considéré comme agissant sur l'ensemble des suites doublement infinies A. Il s'agit alors d'un système dynamique topologique au sens classique du terme : A, muni de la topologie produit, est un compact métrique sur lequel l'application F agit continuement.
Les AC en tant que systèmes dynamiques sont un vrai réservoir de questions ouvertes, issues, directement ou non, de la problématique de Wolfram. Leur étude est d'une simplicité comparable à celle des applications de l'intervalle, mais avec des propriétés assez différentes, pour l'instant bien moins connues, et dont la description pose des problèmes particuliers. Nous passerons en revue les phénoménes d'attraction, liés à la non-surjectivité, et ceux apparaissant dans le comportement local : points d'équicontinuité, sensibilité aux conditions initiales.
* * *
14 février 2002 à 14 heures
salle FO6, IUT de Metz
Solving systems of algebraic equations
par
Przemyslaw Kiciak
Université de Varsovie
Systems of algebraic equations are often solved via the recursive subdivision of the appropriate domain. In the context of the problem of computing the common curve of two parametric (Bézier) patches, the implementation of adaptivity of the divisions will be discussed. The relevant theorems make it possible to implement tests, which determine the necessary level of division. A hybrid procedure, which divides the domain and then computes the common arcs of pieces of the patches may thus be fast as well as reliable. Remarks concerning the general case of solving a system of d equations with d unknowns will also be given. Some experimental results will also be discussed.
* * *
7 février 2002 à 14 heures
salle FO6, IUT de Metz
Récurrence et Réécriture
par
Claude Kirchner
LORIA, Nancy
Inductive proofs can be built either explicitly by making use of an induction principle or implicitly by using the so-called induction by rewriting and inductionless induction methods. When mechanizing proof construction, explicit induction is used in proof assistants and implicit induction is used in rewrite based automated theorem provers. The two approaches are clearly complementary but up to now there was no framework able to encompass and to understand uniformly the two methods. In this paper, we propose such an approach based on the general notion of deduction modulo. We extend slightly the original version of the deduction modulo framework and we provide modularity properties for it. We show how this applies to a uniform understanding of the so called induction by rewriting method and how this relates directly to the general use of an induction principle.
Travail en commun avec Éric Deplagne.
* * *
24 janvier 2002 à 14 heures
salle FO6, IUT de Metz
Logique, automates et systèmes de numération
par
Alexis Bès
Université Paris XII
Je présenterai dans cet exposé de synthèse quelques aspects des liens entre les questions de décidabilité et de définissabilité en logique, les automates finis et les systèmes de numération sur les entiers (et les réels). J'expliquerai d'abord l'utilisation des automates pour montrer la décidabilité des théories logiques (ex: arithmétique de Presburger, arithmétique de Skolem...), puis montrerai qu'en retour les arguments de définissabilité logique peuvent se montrer assez efficaces dans l'étude de problèmes combinatoires ou de décision liés aux automates et aux systèmes de numération, comme le théorème de Cobham.
* * *
17 janvier 2002 à 14 heures
salle FO6, IUT de Metz
Hight Order et Induction en B
par
Dominique Cansell
Université de Metz - LORIA, Nancy
Lors de cet exposé je ferai le bilan sur plusieurs travaux sur B et l'induction (preuve et définitions). La méthode B est une méthode dédiée essensiellement au développement de système (critique, réactif, logiciel ou non). Nous avons voulu montrer que B peut être utilisé dans d'autre cas comme pouvoir prouver des théorèmes (même d'ordre supérieur) de mathématicien.
Le premier travail a été réalisé avec la collaboration de Jean-Raymond Abrial et Guy Laffitte. La méthode B ne permettait pas de faire des preuves en logique d'ordre supérieur. Pour faire des preuves par récurrence il faut pouvoir quantifier sur les prédicats. Cela a été permis en quantifiant sur les ensembles car en théorie des ensembles on peut quantifier sur tous les sous-ensembles d'un ensemble.
Pour simplifier les preuves et surtout pour faire des preuves « abstraites », nous avons défini un langage de structuration qui permet de définir des structures mathématiques et leurs théorèmes associés. Nous avons également développé un outil qui traduit des structures en machine B. Nous pouvons, ainsi, utiliser l'Atelier B pour prouver les théorèmes de ces structures.
titre d'exemple nous avons defini des structures qui permettent de démontrer le théorème de Zermelo qui dit que tout ensemble peut être bien ordonné (si l'on dispose de l'axiome du choix). Pour cela il a fallu définir les transfinis associés à un ensemble qui sont eux mêmes un point fixe etc...
Les deux travaux suivants ont été réalisé avec Dominique Méry.
Nous avons utilisé B pour construire des algorithmes itératifs (corrects!) qui calculent la valeur d'une fonction (définie récursivement).
* * *
3 décembre 1998 à 14 heures
salle FO6, IUT de Metz
Les systèmes fonctionnels : fonctions contre algorithmes
par
Loïc Colson
Université Paris VII
Les systèmes fonctionnels (ou lambda-calculs typés) sont des modèles de calculs récursifs dont la récursion générale est absente et dont les programmes ont la caracteristique principale de toujours terminer. Pourtant des théorèmes de représentation assurent que la classe des fonctions calculables par de tels programmes est très grande (bien plus grande que ce qu'on utilise en informatique en général). Le problème est que l'algorithme implementé par ce programme pour calculer une fonction particuliere peut être très mauvais du point de vue de son comportement (en particulier du point de vue complexité).
On discutera des theorèmes de limitation du pouvoir expressif algorithmique d'un petit système fonctionnel (la récursion primitive) et on montrera comment résoudre ce problème par l'introduction de fonctionnelles en programmation.
* * *
26 novembre 1998 à 14 heures
salle FO6, IUT de Metz
Optimisations Matérielles et Logicielles dans le cadre du projet de Gestion Electronique de Documents STRETCH
par
Marc-Michel Pic et Bernard Goossens
CEA, Saclay et LIAFA, Université Paris VII
Nous présentons une synthese de travaux sur l'étude comparée de la finitude de différents types de présentations de monoïdes enrichie par des résultats nouveaux. Les monoïdes simplifiables admettent des présentations comme monoïdes mais aussi des présentations comme monoïdes simplifiables monolatèrement ou bilatèrement. Les monoïdes immersibles dans un groupe admettent, en outre, des présentations de Malcev. A. I. Malcev a donné le premier exemple d'un monoïde simplifiable qui n'est pas immersible dans un groupe. S. I. Adjan a prouvé qu'il n'est pas possible de remplacer la règle de simplification monolatère ou bilatère par un nombre fini de relateurs. Nous montrons ensuite que tout sous-monoïde finiment engendré d'un monoïde libre admet une présentation de Malcev finie. Gupta, Albert et Lawrence ont prouvé que tout système d'équations sur un alphabet fini est équivalent à un sous-système fini. Nous prouvons que cette propriété est équivalente à la propriété noethérienne que toute chaîne strictement ascendante de congruences résolvantes dans un monoïde libre est finie et aussi à la propriété artinienne que toute chaine strictement descendante d'idéaux clos du monoïde des endomorphismes d'un monoïde libre est finie.
* * *
19 novembre 1998 à 14 heures
salle FO6, IUT de Metz
Sur la conjecture de PARKER
par
Maurice Nivat
Université Paris VII
* * *
12 novembre 1998 à 14 heures
salle FO6, IUT de Metz
Algorithmes de pavage
par
Éric Rémila
Université de Saint-Étienne
Fixons un jeu de pavés-modèles. Un algorithme de pavage est un algorithme qui, étant donnée une figure finie F du plan, fournit un pavage de F par des copies des pavés-modèles (ou indique l'impossibilité). Bien que le problème général du pavage d'une figure soit NP-complet, il existe des algorithmes de pavage très élégants, en temps polynomial, dans le cas particulier où le jeu de pavés-modèles est très simple (pavage par dominos, par des barres de longueur fixée, ou par des barres de longueur au moins égale à 2).
Le but de l'exposé est de présenter des algorithmes de pavage. Un intérêt tout particulier sera accordé à la notion de groupe de pavage, qui sous-tend certains de ces algorithmes en permettant de structurer l'ensemble des pavages d'une figure par une relation d'ordre.
* * *
5 novembre 1998 à 14 heures
salle FO6, IUT de Metz
Pseudo-Boolean Constraint Logic Programming: From Theory to Practice
par
Alexander Bockmayr
Max-Plank Institute, Saarbrücken - LORIA, Nancy
Constraint programming has become a powerful new methodology for modeling and solving many practical problems. In this talk, we give an overview of our work on pseudo-Boolean constraint logic programming. Pseudo-Boolean constraints are equations and inequalities between integer polynomials in 0-1 variables. They combine propositional logic with arithmetic.
Our results range from theoretical work on the complexity of cutting plane proofs up to efficient algorithms and software systems for the solution of large practical problems.
* * *
22 octobre 1998 à 14 heures
salle FO6, IUT de Metz
Algorithmes optimaux pour les problèmes NP suivant L. Levin
par
Jean-Yves Marion
LORIA, Nancy
Inverser une fonction F consiste à trouver pour chaque x, un temoin w, tel que F(w)=x. Un probleme NP peut se definir en terme d'inversion d'une fonction particulière. L. Levin (co-decouvreur avec S. Cook de la NP-complétude) a proposé un algorithme optimal pour les problèmes d'inversion. Je presenterai cet algorithme qui utilise un interpreteur universel efficace et s'appuie sur la théorie algorithmique de l'information.
* * *
15 octobre 1998 à 14 heures
salle FO6, IUT de Metz
Sur la finitude de différentes types de présentations de monoïdes
par
Jean-Claude Spehner
Université de Mulhouse
Nous présentons une synthese de travaux sur l'étude comparée de la finitude de différents types de présentations de monoïdes enrichie par des résultats nouveaux. Les monoïdes simplifiables admettent des présentations comme monoïdes mais aussi des présentations comme monoïdes simplifiables monolatèrement ou bilatèrement. Les monoïdes immersibles dans un groupe admettent, en outre, des présentations de Malcev. A. I. Malcev a donné le premier exemple d'un monoïde simplifiable qui n'est pas immersible dans un groupe. S. I. Adjan a prouvé qu'il n'est pas possible de remplacer la règle de simplification monolatère ou bilatère par un nombre fini de relateurs. Nous montrons ensuite que tout sous-monoïde finiment engendré d'un monoïde libre admet une présentation de Malcev finie. Gupta, Albert et Lawrence ont prouvé que tout système d'équations sur un alphabet fini est équivalent à un sous-système fini. Nous prouvons que cette propriété est équivalente à la propriété noethérienne que toute chaîne strictement ascendante de congruences résolvantes dans un monoïde libre est finie et aussi à la propriété artinienne que toute chaine strictement descendante d'idéaux clos du monoïde des endomorphismes d'un monoïde libre est finie.
* * *
24 juin 1999 à 14 heures
salle FO6, IUT de Metz
Résolution de la contrainte de tri en O(n·log(n)) (travail commun avec Noëlle Bleuzen Guernalec)
par
Alain Colmerauer
LIM, Université d'Aix-Marseille 1
L'exposé, qui sera fait par Alain Colmerauer, portera sur un algorithme de complexité O(n·log(n)) pour résoudre le problème suivant : on se donne 2n intervalles a1,...,a2n dans un ensemble totalement ordonné, comme les entiers ou les réels. Trouver les 2n intervalles b1,...,b2n, les plus petits possibles pour l'inclusion, tels qu'on ait l'équivalence de contraintes :
(xn+1,...,x2n) = tri(x1, ... ,xn) avec x1∈a1 ... x2n∈a2n

(xn+1,...,x2n) = tri(x1,...,xn) avec x1∈b1 ... x2n∈b2n
Ici tri(x1,...,xn) désigne le n-uplet (x1,...,xn) trié dans l'ordre (non strictement) croissant.
* * *
10 juin 1999 à 14 heures
salle FO6, IUT de Metz
Cellular automata and the simulation of Bolzmann lattice-gaz
par
Gianpiero Cattaneo
Université Milan II
* * *
3 juin 1999 à 14 heures
salle FO6, IUT de Metz
Génération de permutations sur réseaux linéaires
par
Maurice Tchuenté
Université de Ngaoundéré, Cameroun
* * *
20 mai 1999 à 14 heures
salle FO6, IUT de Metz
Présentation du projet RÉSÉDAS
par
André Schaff
Université Nancy 1
* * *
6 mai 1999 à 14 heures
salle FO6, IUT de Metz
Billard universel sur le reseau hexagonal avec voisinage de cardinalite 3
par
Anahi Gajardo
Universite du Chili, Santiago du Chili
Dans le but de réduire le nombre d'états et la cardinalité du voisinage suffisant pour l'universalité des automates cellulaires, on a étudié l'universalité sur le reseau hexagonal, ou le voisinage est de cardinalité 3. Sur ce réseau, 3 états sont suffisants pour l'universalité.
Dans cet exposé on prouve l'universalité d'un automate cellulaire à blocs sur le réseau hexagonal, avec 2 états. Bien que ce modèle ne suit pas un automate cellulaire classique avec 2 états (on peut le simuler avec 7 états), les règles de transition sont très simples et elles peuvent donner des idées pour le trouver.
* * *
29 avril 1999 à 14 heures
salle FO6, IUT de Metz
Décomposition et composition d'automates temporisés
par
Antoine Petit
ENS de Cachan
Les automates temporisés, introduits par Alur et Dill en 1990, sont un des modèles les plus utilisés pour étudier les systèmes temps-réel. Nous proposons dans cet exposé, basé sur un travail commun avec Patricia Bouyer, un théorème de décomposition de ces automates temporisés. A cet effet, nous définissons une nouvelle opération simple et naturelle de composition entre automates temporisés, indexée par l'ensemble des horloges remises à zéro, généralisant l'opération classique de concaténation non-temporisée. Nous étendons ensuite les célèbres théorème de Kleene et de Büchi sur les automates non temporisés en remplaçant simplement les objets de base de manière à prendre le temps en compte et la concaténation et les itérations finie et infinie par la nouvelle composition temporisée et les itérations induites. Nous obtenons ainsi la caractérisation algébrique la plus simple existant, au moins à notre connaissance, pour les langages reconnaissables de mots temporisés.
* * *
8 avril 1999 à 14 heures
salle FO6, IUT de Metz
Phénomènes de seuil pour le problème SAT et ses variantes
par
Nadia Creignou
Université de Caen
Il y a quelques annees, un phénomène fort intriguant a été mis en évidence pour la satisfaisabilité des formules 3CNF, un phénomène de seuil : étant donnée une formule 3CNF aléatoire avec L clauses et n variables, si le rapport nombre de clauses sur nombre de variables, L/n, est supérieur à une certaine constante c alors la formule est presque sûrement insatisfaisable et inversement, si L/n est inférieur à c alors la formule est prèsque sûrement satisfaisable.
Dans un premier temps nous présenterons les notions, issues de la théorie des graphes aléatoires, qui permettent de décrire et d´étudier de tels phénomènes. Ensuite nous ferons un tour d´horizon des résultats connus à ce jour sur les phénomènes de seuil et le problème SAT (et ses variantes).
* * *
1 avril 1999 à 14 heures
salle FO6, IUT de Metz
Interprétation d'images et graphe sémantique: le problème des mises en correspondance non univoques
par
Aline Deruyver
IUT de Starsbourg
L'appariement de données avec un graphe sémantique est souvent associé à la notion de compréhension. Ce problème est difficile à résoudre pour deux raisons: l'aspect hautement combinatoire de la recherche de l'appariement et la rareté, dans la pratique, des relations d'appariement bijectives. L'aspect hautement combinatoire peut être réduit grâce à une vérification locale de la satisfaction de contraintes. La non bijectivité de l'appariement peut être contournée par l'introduction de deux nouvelles notions: la notion de contrainte à deux niveaux, et la notion de consistance d'arc faible.
L'appariement est une fonction non injective dès lors que l'on travaille sur des images sur-segmentées, ce qui est une situation très fréquente. La perte du caractère fonctionnel de l'appariement intervient lorsqu'un objet imprévu apparaît, par exemple une tumeur sur une image médicale anatomique. Dans ces deux cas, les données ne peuvent pas être associées au graphe sémantique avec une approche classique. Nous présenterons au cours de ce séminaire une nouvelle approche pour résoudre ces problèmes.
* * *
25 mars 1999 à 14 heures
salle FO6, IUT de Metz
Sur les codes bifixes
par
Véronique Bruyère
Le problème suivant a été beaucoup considéré en théorie des codes à longueur variable : « étant donne un code X ayant la propriété P, existe-t'il un code maximal Y contenant P et ayant toujours la propriété P ? » On demande si possible que la construction de Y soit effective.
Dans l'exposé, je m'attacherai à etudier ce problème pour la propriété P « être bifixe rationnel ». La construction d'un code maximal Y a été proposee dans un article de Zhang et Shen en 1995. Avec Dominique Perrin, nous avons obtenu en 1998 une construction plus simple qui, nous l'espérons, permet de mieux comprendre la classe des codes bifixes.
* * *
18 mars 1999 à 14 heures
salle FO6, IUT de Metz
Fractal structure and automaticity in the time evolution of cellular automata and related systems
par
Gencho Skordev
Université de Brême
  1. Fractals generated by m-Fermat cellular automata (e.g. linear cellular automata with states in a finite field). Applications - fractal structures of Gaussian binomial coefficients and Stirling numbers.
  2. Fractals associated with m-Carlitz sequences of polynomials, Applications - fractals associated with the sequence of Legendre polynomials and the zero Bessel function.
  3. Fractals associated with random multiplication of polynomials.
  4. Self-similar functions generated by cellular automata.
  5. Automaticity of double sequences generated by m-Fermat cellular automata.
  6. Automaticity of double sequences generated by m-Carlitz sequences of polynomials.
  7. Automaticity of coarse-graining invariant orbits of one-dimensional linear cellular automata.
* * *
11 mars 1999 à 14 heures
salle FO6, IUT de Metz
Peut-on toujours prédire le parcours d'un train sur un circuit donné ?
par
Maurice Margenstern
Université de Metz
On fixe un ciruit ferroviaire, décrit par des portions de voies droites ou courbes et des aiguillages de trois types, fixe, à bascule et mémorisant. à partir d'un circuit donné, éventuellement infini, avec une configurtation initiale donnée des aiguillages, est-il possible de prévoir le trajet suivi par un train lancé sur le circuit à partir d'une position donnée ? La réponse est non. On exposera ici une solution nouvelle à ce problème résolu en 1994.
* * *
4 mars 1999 à 14 heures
salle FO6, IUT de Metz
TiPi2, un processeur pour exécuter plusieurs flots simultanés
par
Bernard Goossens
Université Paris VII
Bientôt cent millions de transistors sur une puce. Cela veut dire que par rapport aux circuits d'aujourd'hui, ceux de demain seront dix fois plus complexes. Et ceux d'apres-demain, cent fois. Autrement dit, un processeur actuel représentera un dixième de celui de demain et un centième de celui d'après-demain. Que faire d'un si grand nombre de transistors supplémentaires ? Une idée est d'intégrer dans un seul circuit l'équivalent d'un multiprocesseur. L'exposé, après avoir présenté brièvement l'état de l'art des processeurs, montrera les quelques options possibles pour un multiprocesseur en un boitier et en détaillera une en présentant l'architecture du processeur TiPi2.
* * *
25 février 1999 à 14 heures
salle FO6, IUT de Metz
Sémantique des programmes récursifs-parallèles et méthodes pour leur analyse
par
Olga Kouchnarenko
Université de Franche Comté
Ce travail s'inscrit dans le cadre des travaux consacrés au développement des modèles sémantiques destinés aux langages de programmation concurrents. Une particularité de notre étude réside dans la prise en compte explicite d'une récursivité au niveau des programmes parallèles. Notre but est de présenter un modèle abstrait du langage RPC et d'en étudier les propriétés.
Nous avons développé un modèle théorique abstrait du comportement des programmes RPC. Notre modèle donne naissance à des systèmes de transitions potentiellement infinis à cause de la récursivité. Dans ce cadre, la plupart des problèmes de vérification deviennent indécidables. Cependant il est possible de munir notre modèle d'une structure de système de transitions bien structuré. Ce fait permet de montrer la décidabilité de plusieurs problèmes classiques (atteignabilité, inévitabilité, terminaison,...). Ainsi, ce modèle présente un bon équilibre entre un pouvoir d'expression non-trivial et la possibilité de décider de nombreuses propriétés comportementales.
Nous abordons également les problèmes liés à la formalisation de la stratégie d'implémentation de RPC sur une machine parallèle de l'IPVT RAN. Ce cadre permet de comprendre pourquoi toute propriété de sûreté ou de terminaison démontrée pour notre modèle abstrait est vraie pour la réalisation effective. Ces travaux font partie du projet européen INTAS-RFFI.
* * *
11 février 1999 à 14 heures
salle FO6, IUT de Metz
Predicats de verite syntaxique dans l'arithmetique du second ordre (travail en collaboration avec Loïc Colson)
par
Serge Grigorieff
Université Paris VII
Le problème de l'imprédicativité a été soulevé par Poincaré au début du siècle. Il s'agit de la circularité des définitions en mathématiques. Nous proposons une approche prédicative de l'imprédicativité a l'aide de la notion de prédicats de vérité syntaxique (stp en abrégé). Un stp T en arithmétique du second ordre est un ensemble de formules closes tel que :
  1. T(u=v) si et seulement si les deux termes clos du premier ordre u et v ont la même valeur ;
  2. T(A→B) si et seulement si T(A)⇒T(B) ;
  3. T(∀X.A) si et seulement si T(A[X←D]) pour toute formule D(x) a une variable libre définissant une partie de ℕ.
C'est dans la dernière clause qu'apparaît la différence par rapport à la définition usuelle de la sémantique de Tarski. Cette clause explicite la circularité intrinsèque puisque la formule A[X←D] peut être beaucoup plus complexe que A. On note aussi qu'un stp est un objet du second ordre alors que la vérité Tarskienne est un objet d'ordre trois. Nous montrons que l'existence d'un stp est prouvable dans la théorie des ensembles et qu'en fait elle équivaut prédicativement a la cohérence de l'arithmétique du second ordre.
* * *
28 janvier 1999 à 14 heures
salle FO6, IUT de Metz
Calculabilité et algorithmes : la thèse de Church est-elle vraie ?
par
Lioudmila Pavalotskaya
MPEI Moscou
* * *
21 janvier 1999 à 14 heures
salle FO6, IUT de Metz
Sur la décomposition de problèmes de satisfaction de contraintes
par
Philippe Jégou
LIM, Université de Aix-Marseille I
Le problème CSP est NP-Complet. Par CSP, on entend problèmes de satisfaction de contraintes (à domaines finis) ; on dit aussi réseaux de contraintes. Compte-tenu de la complexité du problème, certains auteurs ont tenté de contourner, à défaut de réduire, la difficulté en proposant des méthodes de décomposition basées sur la structure du réseau de contraintes. Ces methodes s'appuient sur des propriétes algorithmiques et combinatoires des graphes ou hypergraphes induits par le réseau. Nous rappellerons dans un premier temps les résultats obtenus, principalement ceux proposés par Dechter et Pearl, et essayerons d'en cerner les limites. Nous montrerons ensuite comment une approche alternative pour la décomposition peut s'opérer en s'affranchissant des problèmes occasionnés par les méthodes précitées. Apres avoir décrit cette approche, nous présenterons et analyserons les résultats expérimentaux obtenus.
Afin de rendre le propos accessible, cet exposé débutera par la présentation d'un bref état de l'art sur la thématique CSP : définition, problèmes, méthodes énumératives, algorithmes de propagation de contraintes, et classes polynomiales structurelles.
* * *
14 janvier 1999 à 14 heures
salle FO6, IUT de Metz
Optimisation des communications dans le cadre des systèmes d'équations récurrentes affines : diffusion et localisation
par
Vincent Loechner
Université de Metz
L'optimisation des communications est une question cruciale dans l'écriture de programmes parallèles efficaces. Nous avons developpé un algorithme permettant de trouver des transformations espaces-temps affines par variable, efficaces en terme de communications. Le probleme original est décrit sous forme de système d'équations récurrentes affines parametres, équivalent à un nid de boucles à assignation unique. Nous nous placons dans le cadre classique de l'owner computes rule, et dans le modèle « look-forwards ». Les communications résultent de l'image par les transformations espace-temps des dépendances entre les calculs. Nous faisons la distinction entre trois types de communications :
  1. – communications locales, entre processeurs a distance constante ;
  2. – communications distantes ;
  3. – diffusions (broadcast), si l'architecture le permet.
Notre algorithme intègre la possibilité de broadcast anticipé, et nous donnons une méthode de calcul de la mémoire globale nécessaire dans ce cas. Alors que les communications locales et les diffusions sont realisées de manière relativement efficace sur la plupart des architectures parallèles, les communications distantes sont source d'irrégularite. Ces irregularités peuvent d'une part induire des goulots d'étranglement sur le reseau de communication, et sont d'autre part pénalisantes dans le cas de construction de circuits dediés. L'analyse de dependances est realisée par le calcul des ensembles d'utilisation et d'emission correspondant à chaque dépendance. Ces ensembles sont des polyèdres convexes paramétrés, et leur analyse nous permet d'exprimer des contraintes affines sur les matrices de transformations espace-temps, de maniere à privilégier la localisation d'abord, puis les diffusions et les communications locales plutôt que les communications distantes ensuite. La meilleure solution est trouvée en construisant un arbre de solutions, en calculant un ensemble de contraintes sur les transformations espace-temps et un volume de communications résiduelles à chaque noeud de l'arbre.Cet algorithme sera implémenté dans le logiciel OPERA au courant de l'année.
* * *
7 janvier 1999 à 14 heures
salle FO6, IUT de Metz
Interprétation de spécifications temporelles à l'aide d'un outil de preuve
par
Dominique Cansell
Université de Metz - LORIA, Nancy
Ce travail, développé au sein de l'équipe MODEL du LORIA, s'inscrit dans le cadre du développement d'outils pour le langage TLA+ de Leslie Lamport
Les langages de spécification permettent de donner une description précise d'un cahier des charges parfois confus, car le plus souvent écrit dans une langue naturelle ; l'obtention d'une spécification formelle à partir d'une expression informelle ou semi-formelle des besoins est une tâche très complexe car elle met en jeu différents mécanismes incluant des processus cognitifs et des modèles formels. La validation de la spécification obtenue est alors une étape importante, afin de s'assurer de l'adéquation des deux expressions des besoins. Nous avons développé un outil simple de validation de spécifications temporelles TLA à l'aide de l'outil Logic-Solver, le langage de théorie de l'AtelierB. Nous avons analysé quelques spécifications formelles, afin d'établir une correspondance entre la spécification formelle et la spécification informelle. Cette technique est parfois appelée animation de spécification mais nous préférons l'appeler interprétation.
Nous sommes restés proche du langage TLA. Comme il est fondé sur une sémantique des traces, l'interprétation d'une spécification TLA est obtenue en construisant, à l'aide du Logic-Solver, des traces de propriétés que l'utilisateur peut parcourir à sa guise. De plus le Logic-Solver nous a permi de rester dans l'esprit du langage non-typé de Leslie Lamport fondé sur la théorie des ensembles. L'exposé presentera TLA(+), le Logic-Sover et notre interprète
* * *
4 décembre 1997 à 14 heures
salle FO6, IUT de Metz
Multiplier par 10 la performance du processeur. L'architecture du processeur Tipi
par
Bernard Goossens
Université Paris VII
* * *
27 novembre 1997 à 14 heures
salle FO6, IUT de Metz
Natural Computing : The Church-Turing Thesis Revisited
par
Max Garzon
Université de Memphis
* * *
20 novembre 1997 à 14 heures
salle FO6, IUT de Metz
La détection de bords : du modèle à l'algorithme
par
Aline Deruyver
Université de Strasbourg
* * *
13 novembre 1997 à 14 heures
salle FO6, IUT de Metz
Un fragment décidable de la logique linéaire du second ordre
par
Guy Perrier
LORIA, Nancy
* * *
6 novembre 1997 à 14 heures
salle FO6, IUT de Metz
Réseaux d'automates: Systèmes dynamiques, Structures pour le calcul parallèle
par
Ibrahima Sakho
Université de Metz
* * *
21 octobre 1997 à 14 heures
salle FO6, IUT de Metz
Shuffling Languages and Posets: Are two Models of Concurrency Equivalent?
par
Zoltán Ésik
Université József Attila, Szeged
* * *
16 octobre 1997 à 14 heures
salle FO6, IUT de Metz
Synchronisation d'automates cellulaires et tolérance aux pannes
par
Jean-Baptiste Yunès
Université Paris 7
* * *
9 octobre 1997 à 14 heures
salle FO6, IUT de Metz
A simple self-reproducing cellular automaton with shape-encoding mechanism
par
Kenichi Morita
Université d'Hiroshima
* * *
4 juin 1998 à 14 heures
salle FO6, IUT de Metz
Deux études de CAO directement liées à des problèmes de fabrication : le raccordement G2 entre surfaces rationnelles et le raccordement G1 entre surfaces à l'aide de cyclides de Dupin
par
Jean-Luc Beauchat
ENSAM de Metz
* * *
29 mai 1998 à 14 heures
salle FO6, IUT de Metz
New definition of topological chaos with application to cellular automata dynamics
par
Gianpiero Cattaneo
Université de Milan
* * *
7 mai 1998 à 14 heures
salle FO6, IUT de Metz
Les algorithmes génétiques et les problèmes d'optimisation discrète : exemples d'applications en génie industriel
par
Marie-Claude Portmann
École des Mines de Nancy
* * *
23 avril 1998 à 14 heures
salle FO6, IUT de Metz
Complexité des systèmes de réécriture
par
Hélène Touzet
* * *
19 mars 1998 à 14 heures
salle FO6, IUT de Metz
Bornes récursives pour le théorème de Hignam
par
Adam Cichon
* * *
12 mars 1998 à 14 heures
salle FO6, IUT de Metz
Récurrences faibles et Complexités algorithmiques
par
Jean-Yves Marion
* * *
26 février 1998 à 14 heures
salle FO6, IUT de Metz
Contribution à l'analyse et à la réalisation d'un système de CAO à base de caractéristiques de forme
par
Cathy Poinsignon
* * *
19 février 1998 à 14 heures
salle FO6, IUT de Metz
Une nouvelle approche pour la modélisation et la gestion des contraintes en CAO
par
Sandrine Leinen
* * *
29 janvier 1998 à 14 heures
salle FO6, IUT de Metz
L'offre HPC Silicon/Cray (1ere partie) ; description de l'Origin2000 et de son environnement logiciel (2e partie)
par
Ghislain De Jacquelot
Silicon/Cray
* * *
22 janvier 1998 à 14 heures
salle FO6, IUT de Metz
Le modèle PDN
par
Giuseppe Bério
Université de Turin
* * *
15 janvier 1998 à 14 heures
salle FO6, IUT de Metz
La construction formulatoire mathématique ou : comment coder un algorithme par une fonction ?
par
Azzédine Kaced
Université de Metz
* * *
8 janvier 1998 à 14 heures
salle FO6, IUT de Metz
Automates de Büchi non ambigus
par
Olivier Carton
Université de Marne-la-Vallée
* * *
19 décembre 1996 à 14 heures
salle FO6, IUT de Metz
Génération aléatoire des structures arborescentes et applications
par
René Schott
LORIA, Nancy
* * *
5 décembre 1996 à 14 heures
salle FO6, IUT de Metz
Algorithmes du lancer de rayons
par
Michaël Krajecki
* * *
28 novembre 1996 à 14 heures
salle FO6, IUT de Metz
Decidable and undecidable fragments of the elementary theory of free monoids
par
Sergei Adian
Institut Steklov, Moscou
* * *
21 novembre 1996 à 14 heures
salle FO6, IUT de Metz
Vers la modélisation déclarative de graphes
par
Aristide Grange
Université de Metz
* * *
14 novembre 1996 à 14 heures
salle FO6, IUT de Metz
À propos d'un service fondamental pour assurer la tolérance aux pannes : le Group Membership Service
par
Bernadette Charron-Bost
École Polytechnique
* * *
7 novembre 1996 à 14 heures
salle FO6, IUT de Metz
Automates cellulaires sur les graphes de Cayley
par
Zsuzsanna Roka
Université de Metz
* * *
24 octobre 1996 à 14 heures
salle FO6, IUT de Metz
Bijections séquentielles
par
Christian Choffrut
LITP, Université de Paris VII
* * *
10 octobre 1996 à 14 heures
salle FO6, IUT de Metz
Problèmes de décidabilité pour les systèmes de réécriture de mots
par
Guillaume Watier
* * *
3 octobre 1996 à 14 heures
salle FO6, IUT de Metz
Nouveautés en réseaux de neurones, jeux à jetons sur un graphe et machines de Turing
par
Maurice Margenstern
Université de Metz
* * *
12 juin 1997 à 14 heures
salle FO6, IUT de Metz
Cellular automata and chaos, II
par
Gianpiero Cattaneo
Université de Milan
* * *
5 juin 1997 à 14 heures
salle FO6, IUT de Metz
Systolic automata
par
Jozef Gruska
Université de Brno
* * *
29 mai 1997 à 14 heures
salle FO6, IUT de Metz
Cellular automata and chaos, I
par
Gianpiero Cattaneo
Université de Milan
* * *
10 mai 1997 à 14 heures
salle FO6, IUT de Metz
Substitutions explicites et forte normalisation
par
Pierre Lescanne
Université de Nancy 1
* * *
13 mars 1997 à 14 heures
salle FO6, IUT de Metz
Recherche d'un ensemble fini de points ayant un ensemble de cordes donné
par
Maurice Nivat
LIAFA, Paris VII
* * *
6 mars 1997 à 14 heures
salle FO6, IUT de Metz
Bases de données déductives
par
Françoise Gire
LIAFA, Paris VII
* * *
20 février 1997 à 14 heures
salle FO6, IUT de Metz
Lois 0-1 en logique
par
Thierry Lacoste
LIM, Université de Marseille
* * *
6 février 1997 à 14 heures
salle FO6, IUT de Metz
Automates finis à plusieurs rubans
par
Serge Grigorieff
LIAFA, Université Paris VII
* * *
30 janvier 1997 à 14 heures
salle FO6, IUT de Metz
On mix operation
par
Manfred Kudlek
Université de Hambourg
* * *
16 janvier 1997 à 14 heures
salle FO6, IUT de Metz
Algorithmes parallèles de recherche de preuve
par
Jean-Yves Marion
Université de Nancy 2
* * *
9 janvier 1997 à 14 heures
salle FO6, IUT de Metz
Dernières nouvelles de SAT
par
Daniel Singer
Université de Metz
* * *
21 décembre 1995 à 14 heures
salle FO6, IUT de Metz
Comment accélérer la recherche de preuve en logique linéaire
par
Jean-Yves Marion
Université de Metz
* * *
11 décembre 1995 à 14 heures
salle FO6, IUT de Metz
Machines de Turing universelles non-effaçantes
par
Maurice Margenstern
Université de Metz
* * *
7 décembre 1995 à 14 heures
salle FO6, IUT de Metz
Sémantique du parallélisme
par
Zineb Habbas
Université de Metz
* * *
30 novembre 1995 à 14 heures
salle FO6, IUT de Metz
Petites machines de Turing universelles
par
Maurice Margenstern
Université de Metz
* * *
20 novembre 1995 à 14 heures
salle FO6, IUT de Metz
Décidabilité/indécidabilité de l'arrêt
par
Maurice Margenstern
Université de Metz
* * *
17 juin 1996 à 14 heures
salle FO6, IUT de Metz
Prototyper la déduction automatique en termes de réécriture
par
Hélène Kirchner
LORIA, Nancy
* * *
10 juin 1996 à 14 heures
salle FO6, IUT de Metz
Une nouvelle approche pour des machines de Turing universelles très petites
par
Maurice Margenstern
Université de Metz
* * *
6 juin 1996 à 14 heures
salle FO6, IUT de Metz
A 0-1 Law for Planar Maps
par
Kevin Compton
Université du Michigan, Ann Arbor
* * *
30 mai 1996 à 14 heures
salle FO6, IUT de Metz
Systemes de numeration redondants, calcul-en ligne et operateurs « boite noire »
par
Jean-Michel Muller
LIP, ENS de Lyon
* * *
23 mai 1996 à 14 heures
salle FO6, IUT de Metz
Sur les fonctions calculables par les machines de Turing
par
Lioudmila Pavlotskaïa
MPEI, Moscou
* * *
9 mai 1996 à 14 heures
salle FO6, IUT de Metz
Introduction à l'algorithmique parallèle
par
Francine Herrmann
Université de Metz
* * *
6 mai 1996 à 14 heures
salle FO6, IUT de Metz
Problèmes de satisfaction de contraintes
par
Pierre-Paul Merel
* * *
2 mai 1996 à 14 heures
salle FO6, IUT de Metz
Fonctions calculables en ligne
par
Hratchya Pélibossian
* * *
28 mars 1996 à 14 heures
salle FO6, IUT de Metz
Axiomatique du modeleur BRep
par
Jean-François Dufour
* * *
21 mars 1996 à 14 heures
salle FO6, IUT de Metz
Schématisation d'ensembles infinis de termes en démonstration automatique
par
Ali Amaniss
* * *
14 mars 1996 à 14 heures
salle FO6, IUT de Metz
Specifications opérationnelles structurées pour le vrai parallélisme
par
Juan Echague
Université de Montevideo, Uruguay
* * *
7 mars 1996 à 14 heures
salle FO6, IUT de Metz
Automates cellulaires et images
par
Jacques Mazoyer
LIP, ENS de Lyon
* * *
22 février 1996 à 14 heures
salle FO6, IUT de Metz
Computational power of neural networks
par
Hava Siegelmann
Technion, Israël
* * *
8 février 1996 à 14 heures
salle FO6, IUT de Metz
Universalité des réseaux d'interaction
par
Denis Béchet
CRIN, Nancy
* * *
1 février 1996 à 14 heures
salle FO6, IUT de Metz
Complexité d'automates cellulaires
par
Martín Matamalá
Université du Chili, Santiago
* * *
22 janvier 1996 à 14 heures
salle FO6, IUT de Metz
Small Deterministic Turing Machines
par
Manfred Kudlek
Université de Hambourg
* * *
18 janvier 1996 à 14 heures
salle FO6, IUT de Metz
Ordinateurs quantiques
par
Jean-Paul Delahaye
LIFL, Université de Lille 1
* * *
11 janvier 1996 à 14 heures
salle FO6, IUT de Metz
Spécifications du calcul
par
Abdelouahed Zakari
Université de Metz
* * *
7 juillet 2011 à 14 heures 0
E203, UFM-MIM
On the Permuted Perceptron Problem - A New Formulation and Approach
par
Tiru S. Arthanari
University of Auckland Business School, Nouvelle-Zélande
The permuted perceptron problem (PPP) has received renewed interest due to its application in Cryptanalysis. Simulated annealing and other hybrid meta-heuristics are applied to attack this problem. Difference of convex functions approach is also combined with simulated annealing to solve problem instances of PPP.
In this talk after a brief review of the state of art of PPP approaches a new model for approaching the PPP will be introduced. This is a parametric minimum cost bipartite flow formulation with special cost structure. We have not worked on the computational efficiency of this approach, but highlight why this approach might yield better results.
* * *