No description available.

There are a wide range of techniques on offer to decision makers choosing between options where each option exhibits a range of attributes. Many of these techniques involve eliciting weights to represent the relative importance of each attribute. This thesis offers a mathematical explanation for the consistent differences in the distribution of weights experienced when a fixed sum method, Point Allocation (PA), and a fixed scale method, Direct Rating (DR), are used. Fixed scale and fixed sum simulations, sampling from the Uniform distribution, produce different weight profiles matching those found in practical applications. Formulae are found representing the distribution of weights produced by the simulations. These enable ranked weights to be calculated, which can be used as surrogates for 'true' weights. In particular, a second major aspect of the study concerns the discovery of a family of piecewise probability density functions to represent the distributions of ranked weights generated using the DR method. The means of the distributions are the Rank Order Distribution (ROD) surrogate weights. These are compared with the Rank Order Centroid (ROC) weights. As the number of attributes in a decision problem increases, the ROD weights approximate to the more easily calculated Rank Sum weights. An interactive survey is conducted, using students and the internet, to compare the PA and DR methods in terms of their ease of use, time taken, accuracy achieved, and user's confidence, in producing weights that represented a series of known "true" weights presented in graphical form. Statistical analysis found significant effects of method, time, accuracy achieved, and confidence of participants, favouring the DR approach. The methods are also compared as a means of obtaining the importance weights given by students to seven listed attributes of universities. A significant difference is found between the pattern of decision weights produced using the two methods confirming previously published studies.

This thesis investigates the possibility of approximating stationary solutions of stochastic differential equations using numerical methods. We consider a particular class of stochastic differential equations, which are known to generate random dynamical systems. The existence of stochastic stationary solution is proved using global attractor approach. Euler's numerical method, applied to the stochastic differential equation, is proved to generate a discrete random dynamical system. The existence of stationary solution is proved again using global attractor approach. At last we prove that the approximate stationary point converges in mean-square sense to the exact one as the time step of the numerical scheme diminishes.

De nombreux problèmes de la vie réelle sont NP-Difficiles et ne peuvent pas être résolus en temps polynomial. Deux paradigmes notables pour les résoudre quand même sont: l'approximation et la complexité paramétrée. Dans cette thèse, on présente une nouvelle technique appelée "gloutonnerie-Pour-La-Paramétrisation". On l'utilise pour établir ou améliorer la complexité paramétrée de nombreux problèmes et également pour obtenir des algorithmes paramétrés pour des problèmes à cardinalité contrainte sur les graphes bipartis. En vue d'établir des résultats négatifs sur l'approximabilité en temps sous-Exponentiel et en temps paramétré, on introduit différentes méthodes de sparsification d'instances préservant l'approximation. On combine ces "sparsifieurs" à des réductions nouvelles ou déjà connues pour parvenir à nos fins. En guise de digestif, on présente des résultats de complexité de jeux comme le Bridge et Havannah. / Several real-Life problems are NP-Hard and cannot be solved in polynomial time.The two main options to overcome this issue are: approximation and parameterized complexity. In this thesis, we present a new technique called greediness-For-Parameterization and we use it to improve the parameterized complexity of many problems. We also use this notion to obtain parameterized algorithms for some problems in bipartite graphs. Aiming at establishing negative results on the approximability in subexponential time and in parameterized time, we introduce new methods of sparsification that preserves approximation. We combine those "sparsifiers" with known or new reductions to achieve our goal. Finally, we present some hardness results of games such as Bridge and Havannah.

Nous détaillons dans cette thèse des algorithmes modérément exponentiels pour l'approximation du problème MAX SAT. Nous discutons d'une méthode générique pour la conception d'algorithmes exponentiels réalisant des schémas d'approximation dans un cadre plus général. Enfin, nous présentons des résultats paramétrés pour des problèmes de coupe à cardinalité contrainte. / We give in this thesis some moderately exponential algorithms for the MAX SAT problem. We discuss a very general method to conceive efficient exponential algorithms that give approximation scheme. In the end, we present some parameterized results for CUT problem with constrained cardinality.

Ces dernières décennies, de nouvelles méthodes numériques connues sous le nom de « méthodes sans maillage » ont été développées. Contrairement à la MEF, ces méthodes n'utilisent qu'un ensemble de noeuds répartis dans le domaine sans demander un maillage de celui-ci. Jusqu'à présent, aucune de ces méthodes n'est parvenue à satisfaire les utilisateurs de la MEF. Dans cette thèse, nous proposons une méthode sans maillage, utilisant les approximations de Taylor. Cette méthode a l'avantage de n'utiliser que des points sur la frontière. En effet, l'EDP est résolue sous sa forme forte dans le domaine et les conditions aux limites sont appliquées par la méthode des moindres carrés. Cette méthode a été introduite, il y a 3 ans par S. Zeze dans sa thèse. Les tests académiques effectués en linéaire ont montré que cette méthode est très précise et que la convergence est améliorée en augmentant le degré, comme dans la p-version des EF. Nos travaux de thèse sont une suite des travaux de S. Zeze et ils visent à rendre plus robuste la méthode et aussi à élargir son champ d'application. Dans un premier temps, nous faisons une analyse mathématique de la méthode. Cette analyse passe par l'analyse des séries calculées. Le but de cette analyse est d'évaluer le domaine de convergence de la solution. Les résultats obtenus ont montré que pour certains problèmes, il faut subdiviser le domaine en quelques sous domaines et faire une résolution par sous domaine. La suite de nos travaux a donc été d'établir une technique de raccordement qui permettra d'assurer les conditions de transmission aux interfaces, dans le cas d'une résolution par sous domaine. En dernière partie, nous étendons l'application de la méthode aux problèmes non linéaires, en la couplant à une méthode de linéarisation / In these last decades, new numerical methods known as « meshless methods » have been developped. Contrary to the FEM, these methods uses only a set of nodes in the domain, without need of any mesh. Until now, any of these methods has convinced users of FEM. In this paper, we present a new meshless method using Taylor series expansion. In this method, the PDE is solved quasi exactly in the domain and the boundary conditions are applied by using a least square method. Then only the boundary discretisation is needed so the proposed method is a « true boundary meshless method ». This technique has been proposed for the first time by S. Zeze in his PhD thesis. The study of some linear problems has shown that this technique leads to a very good accuracy and that the convergence can be improved by increasing approximation degree. Our work is a continuation of S. Zeze work, and it consists to make the proposed method more robust and to extend its range of application. For that, we first make an analysis of the series computed by the method. The aim of this analysis was to evaluate the domain of validity of these series. This analysis showed that, for some problems, an accuracy cannot be obtained without splitting the domain in subdomains and making a resolution by subdomains. Therefore the second part of our work was to define a technique which will ensure the continuity at the interface between subdomains, in the case of a resolution by subdomains. The last part of our work was dedicated to non-linear problems. We establish an algorithm to show how the proposed method can deal with nonlinear-problems

Cette thèse comporte deux parties indépendantes. Dans la première partie, nous nous intéressons à l’analyse asymptotique de quelques statistiques sur les arbres binaires de recherche (ABR). Dans la deuxième partie, nous nous intéressons à l’étude du problème du collectionneur de coupons impatient. Dans la première partie, en suivant le modèle introduit par Aguech, Lasmar et Mahmoud [Probab. Engrg. Inform. Sci. 21 (2007) 133—141], on définit la profondeur pondérée d’un nœud dans un arbre binaire enraciné étiqueté comme la somme de toutes les clés sur le chemin qui relie ce nœud à la racine. Nous analysons alors dans ABR, les profondeurs pondérées des nœuds avec des clés données, le dernier nœud inséré, les nœuds ordonnés selon le processus de recherche en profondeur, la profondeur pondérée des trajets, l’indice de Wiener pondéré et les profondeurs pondérées des nœuds avec au plus un enfant. Dans la deuxième partie, nous étudions la forme asymptotique de la courbe de la complétion de la collection conditionnée à T_n≤ (1+Λ), Λ>0, où T_n≃n ln⁡n désigne le temps nécessaire pour compléter la collection. Puis, en tant qu’application, nous étudions les automates déterministes et accessibles et nous fournissons une nouvelle dérivation d’une formule due à Korsunov [Kor78, Kor86] / This Phd thesis is divided into two independent parts. In the first part, we provide an asymptotic analysis of some statistics on the binary search tree. In the second part, we study the coupon collector problem with a constraint. In the first part, following the model introduced by Aguech, Lasmar and Mahmoud [Probab. Engrg. Inform. Sci. 21 (2007) 133—141], the weighted depth of a node in a labelled rooted tree is the sum of all labels on the path connecting the node to the root. We analyze the following statistics : the weighted depths of nodes with given labels, the last inserted node, nodes ordered as visited by the depth first search procees, the weighted path length, the weighted Wiener index and the weighted depths of nodes with at most one child in a random binary search tree. In the second part, we study the asymptotic shape of the completion curve of the collection conditioned to T_n≤ (1+Λ), Λ>0, where T_n≃n ln⁡n is the time needed to complete accessible automata, we provide a new derivation of a formula due to Korsunov [Kor78, Kor86]