Dans cette recherche, on s’intéresse à l’étude asymptotique des méthodes de points intérieurs pour la programmation linéaire. En se basant sur les travaux de Schrijver et Padberg, nous proposons deux nouveaux pas de déplacement pour accélérer la convergence de l'algorithme de Karmarkar et réduire sa complexité algorithmique. Le premier pas est une amélioration modérée du comportement de l'algorithme, le deuxième représente le meilleur pas de déplacement fixe obtenu jusqu'à présent. Ensuite nous proposons deux approches paramétrées de la l'algorithme de trajectoire centrale basé sur les fonctions noyau. La première fonction généralise la fonction noyau proposé par Y. Q. Bai et al., la deuxième est la première fonction noyau trigonométrique qui donne la meilleure complexité algorithmique, obtenue jusqu'à présent. Ces propositions ont apporté des nouvelles contributions d'ordre algorithmique, théorique et numérique. / In this research, we are interested by asymptotic study of interior point methods for linear programming. By basing itself on the works of Schrijver and Padberg, we propose two new displacement steps to accelerate the convergence of Karmarkar's algorithm and reduce its algorithmic complexity. The first step is a moderate improvement of the behaviour of this algorithm; the second represents the best fixed displacement step obtained actually. We propose two parameterized approaches of the central trajectory algorithm via a kernel function. The first function generalizes the kernel function given by Y. Q. Bai et al., the second is the first trigonometric kernel function that gives the best algorithmic complexity, obtained until now. These proposals have made new contributions of algorithmic, theoretical and numerical order.

Finding of collision free path is central in creation of mobile, autonomous robot. Goal of this paper is to show the most important algorithms implementing such solutions. It also describes application that is being created to allow students experiment with these methods. For this purpose it uses library that was introduced by Jakub Rusnák in 2017, which means this is a continuation and possibly extension of his work.

Recent advances in VLSI technology, and wireless communication have enabled the development of tiny, low-cost sensor nodes that communicate over short distances. These sensor nodes, which consist of sensing, data processing, and wireless communication capabilities, suggest the idea of sensor networks based on collaborative effort of a large number of sensor nodes. Sensor networks hold the promise for numerous applications such as intrusion detection, weather monitoring, security and tactical surveillance, distributed computing, and disaster management. Several new protocols and algorithms have been proposed in the recent past in order to realize these applications. In this thesis, we consider the problem of routing in Wireless Sensor Networks (WSNs). Routing is a challenging problem in WSNs due to the inherent characteristics which distinguish these networks from the others. Several routing algorithms have been proposed for WSNs, each considering a specific network performance objective such as long network lifetime (ChangandTassiulas,2004), end-to-end delay guarantees (T.Heetal,2003), and data fusion (RazvanCristescuetal,2005) etc. In this thesis, we utilize the Potential-based Routing Paradigm to develop routing algorithms for different performance objectives of interest in WSNs. The basic idea behind the proposed approach is to assign a scalar called the potential to every sensor node in the network. Data is then forwarded to the neighbor with highest potential. Potentials cause the data to flow along certain paths. By defining potential fields appropriately, one can cause data to flow along preferred paths, so that the given performance objective is achieved. We have demonstrated the usefulness of this approach by considering three performance objectives, and defining potentials appropriately in each case. The performance objectives that we have considered are (i) maximizing the time to network partition, (ii) maximizing the packet delivery ratio, and (iii) Data fusion. In an operational sensor network, sensor nodes’ energy levels gradually deplete, leading eventually to network partition. A natural objective is to route packets in such a way that the time to network partition is maximized. We have developed a potential function for this objective. We analyzed simple network cases and used the insight to develop a potential function applicable to any network. Simulation results showed that considerable improvements in time to network partition can be obtained compared to popular approaches such as maximum lifetime routing, and shortest hop count routing. In the next step, we designed a potential function that leads to routes with high packet delivery ratios. We proposed a “channel-state aware” potential definition for a simple 2-relay network and performed a Markov-chain based analysis to obtain the packet delivery ratio. Considerable improvement was observed compared to a channel-state-oblivious policy. This motivated us to define a channel-state-dependent potential function for a general network. Simulation results showed that for a relatively slowly changing wireless network, our approach can provide up to 20% better performance than the commonly-used shortest-hop-count routing. Finally, we considered the problem of correlated data gathering in sensor networks. The routing approach followed in literature is to construct a spanning tree rooted at the sink. Every node in the tree aggregates its data with the data from its children in order to reduce the number of transmitted bits. Due to this fact, the total energy cost of the data collection task is a function of the underlying tree structure. Noting that potential based routing schemes also result in a tree structure, we present a potential definition that results in the minimum energy cost tree under some special conditions. Specifically, we consider a scenario in which sensor nodes’ measurements are quantized to K values. The task at the sink is to construct a histogram of measurements of all sensor nodes. Sensor nodes do not directly send their measurements to sink. Instead, they construct a temporary histogram using the data from its children and forward it to its parent node in the tree. We present a potential definition that results in the minimum energy cost tree under some conditions on sensor nodes’ measurements. We include both the transmission energy cost as well as the energy cost associated with the aggregation process.

Dans cette thèse, sur la base de l'approche du mode local "étendu" et de la théorie générale de la substitution isotopique, nous obtenons un ensemble de relations analytiques simples entre les paramètres spectrocopiques (fréquences harmoniques, coefficients d'anharmonicité, paramètres rovibrationels, différents types de paramètres d'interaction de Fermi et de Coriolis) des molécules de CH2D2, CH3D et CHD3. Tous ces paramètres sont exprimés en termes de relations simples à partir des paramètres spectroscopiques de la molécule mère CH4. Des calculs tests avec des relations isotopiques montrent que même sans introduire d'informations majeures sur les espèces isotopiques, les résultats numériques de ces calculs sont en bon accord avec les données expérimentales et les calculs ab initio. A partir de le théorie des opérateurs de perturbation et des propriétés de symétrie des molécules axiales XYZ3 (C3v), nous déterminons des formules générales permettant la détermination des paramètres spectroscopiques sous la forme de fonctions des paramètres structuraux et des paramètres de la fonction potentiel intramoléculaire. Nous présentons aussi une approche permettant la détermination du hamiltonien de molécules polyatomiques qui permet de résoudre le problème de la description de la surface d'énergie potentielle via la construction et la diagonalisation d'une matrice hamiltonienne de grande dimension. / In this thesis, on the base of the "expanded", local mode approach and general isotopic substitution theory we obtain sets of simple analytical relations between spectroscopic parameters (harmonic frequencies, anharmonic coefficients, ro-vibrational parameters, different kinds of Fermi and Coriolis-type interaction parameters) of the CH2D2, CH3D and CHD3 molecules. All of them are expressed as simple functions of spectroscopic parameters of the mother CH4 molecule. Test calculations with the isotopic relations show that even without including prior informations about the isotopic species, numerical results of calculations are in a good agreement both with experimental data and results of ab initio calculations. On the base of operators perturbation theory and the symmetry properties of the axially symmetric XYZ3 (C3v) type molecules, we derive general formulae for the determination of the spectroscopic parameters in the form of functions of structural parameters and parameters of the intramolecular potential function. We present also an approach for determination of the Hamiltonian of polyatomic molecules that allows to solve the problem of potential energy surface determination via the construction and the diagonalization of a Hamiltonian matrix of large dimension.

We employ the empirical potential function Airebo to computationally model free-standing Carbon-12 graphene in a classical setting. Our objective is to measure the mean square displacement (MSD) of atoms in the system for different average temperatures and Carbon-13 isotope concentrations. From results of the MSD we aim to develop a technique that employs Transmission Electron Microscopy (TEM), using high-angle annular dark filed (HAADF) detection, to obtain atomic-resolution images. From the thermally diffusive images, produced by the vibrations of atoms, we intent to resolve isotopes types in graphene. For this, we establish a relationship between the full width half maximum (FWHM) of real-space intensity images and MSD for temperature and isotope concentration changes. For the case of changes in the temperature of the system, simulation results show a linear relationship between the MSD as a function of increased temperature in the system, with a slope of 7.858×10-6 Å2/K. We also note a power dependency for the MSD in units of [Å2] with respect to the FWHM in units of [Å] given by FWHM(MSD)=0.20MSD0.53+0.67. For the case of increasing isotope concentration, no statistically significant changes to the MSD of 12C and 13C are noted for graphene systems with 2,000 atoms or more. We note that for the experimental replication of results, noticeable differences in the MSD for systems with approximately 320,000 atoms must be observable. For this, we conclude that isotopes in free-standing graphene cannot be distinguished using TEM.

La problématique de cette thèse concerne la reconstruction statistique itérative 3D de l'arbre coronaire, à partir d'un nombre très réduit d'angiogrammes coronariens (5 images). Pendant un examen rotationnel d'angiographie RX, seules les projections correspondant à la même phase cardiaque sont sélectionnées afin de vérifier la condition de non variabilité spatio-temporelle de l'objet à reconstruire (reconstruction statique). Le nombre restreint de projections complique cette reconstruction, considérée alors comme un problème inverse mal posé. La résolution d'un tel problème nécessite une procédure de régularisation. Pour ce faire, nous avons opté pour le formalisme bayésien en considérant la reconstruction comme le champ aléatoire maximisant la probabilité a posteriori (MAP), composée d'un terme quadratique de vraisemblance (attache aux données) et un a priori de Gibbs (à priori markovien basé sur une interprétation partielle de l'objet à reconstruire). La maximisation MAP adoptant un algorithme d'optimisation numérique nous a permis d'introduire une contrainte de lissage avec préservation de contours des reconstructions en choisissant adéquatement les fonctions de potentiel associées à l'énergie à priori. Dans ce manuscrit, nous avons discuté en détail des trois principales composantes d'une reconstruction statistique MAP performante, à savoir (1) l'élaboration d'un modèle physique précis du processus d'acquisition, (2) l'adoption d'un modèle à priori approprié et (3) la définition d'un algorithme d'optimisation itératif efficace. Cette discussion nous a conduit à proposer deux algorithmes itératifs MAP, MAP-MNR et MAP-ARTUR-GC, que nous avons testés et évalués sur des données simulées réalistes (données patient issues d'une acquisition CT- 64 multi-barrettes). / The problematic of this thesis concerns the statistical iterative 3D reconstruction of coronary tree from a very few number of coronary angiograms (5 images). During RX rotational angiographic exam, only projections corresponding to the same cardiac phase are selected in order to check the condition of space and time non-variability of the object to reconstruct (static reconstruction). The limited number of projections complicates the reconstruction, considered then as an illness inverse problem. The answer to a similar problem needs a regularization process. To do so, we choose baysian formalism considering the reconstruction as a random field maximizing the posterior probability (MAP), composed by quadratic likelihood terms (attached to data) and Gibbs prior (prior markovian based on a partial interpretation of the object to reconstruct). The MAP maximizing allowed us using a numerical optimization algorithm, to introduce a smoothing constraint and preserve the edges on the reconstruction while choosing wisely the potential functions associated to prior energy. In this paper, we have discussed in details the three components of efficient statistical reconstruction MAP, which are : 1- the construction of precise physical model of acquisition process; 2- the selection of an appropriate prior model; and 3- the definition of an efficient iterative optimization algorithm. This discussion lead us to propose two iterative algorithms MAP, MAP-MNR and MAP-ARTUR-GC, which we have tested and evaluated on realistic simulated data (Patient data from 64-slice CT).