An efficient solver for weighted Max-SAT

We present a new branch and bound algorithm for weighted Max-SAT, called Lazy which incorporates original data structures and inference rules, as well as a lower bound of better quality. We provide experimental evidence that our solver is very competitive and outperforms some of the best performing Max-SAT and weighted Max-SAT solvers on a wide range of instances.

How hard is a commercial puzzle: the eternity II challenge

Recently, edge matching puzzles, an NP-complete problem, have received, thanks to money-prized contests, considerable attention from wide audiences. We consider these competitions not only a challenge for SAT/CSP solving techniques but also as an opportunity to showcase the advances in the SAT/CSP community to a general audience. This paper studies the NP-complete problem of edge matching puzzles focusing on providing generation models of problem instances of variable hardness and on its resolution through the application of SAT and CSP techniques. From the generation side, we also identify the phase transition phenomena for each model. As solving methods, we employ both; SAT solvers through the translation to a SAT formula, and two ad-hoc CSP solvers we have developed, with different levels of consistency, employing several generic and specialized heuristics. Finally, we conducted an extensive experimental investigation to identify the hardest generation models and the best performing solving techniques.

Edge matching puzzles as hard SAT/CSP benchmarks

Recently, edge matching puzzles, an NP-complete problem, have rececived, thanks to money-prized contests, considerable attention from wide audiences. We consider these competitions not only a challenge for SAT/CSP solving techniques but also as an opportunity to showcase the advances in the SAT/CSP community to a general audience. This paper studies the NP-complete problem of edge matching puzzles focusing on providing generation models of problem instances of variable hardness and on its resolution through the application of SAT and CSP techniques. From the generation side, we also identify the phase transition phenomena for each model. As solving methods, we employ both; SAT solvers through the translation to a SAT formula, and two ad-hoc CSP solvers we have developed, with different levels of consistency, employing several generic and specialized heuristics. Finally, we conducted an extensive experimental investigation to identify the hardest generation models and the best performing solving techniques.

Kiinnirullaimen dynamiikan ja värähtelyjen simulointi

Diplomityössä tutkittiin kaupallisen monikappaledynamiikkaohjelmiston soveltuvuutta kiinnirullaimen dynamiikan ja värähtelyjen tutkimiseen. Erityisen kiinnostuneita oltiin nipin kuvauksesta sekä nipissä tapahtuvista värähtelyistä. Tässä diplomityössä mallinnettiin kiinnirullaimen ensiö- ja toisiokäytöt sekä tampuuritela. Malli yhdistettiin myöhemmin Metso Paper Järvenpäässä rinnakkaisena diplomityönä tehtyyn malliin, joista muodostui kahteen ratkaisijaan perustuva simulointimalli. Simulointimalli rakennettiin käyttämään kahta erillistä ratkaisijaa, joista toinen on mekaniikkamallin rakentamisessa käytetty ADAMS-ohjelmisto ja toinen säätöjärjestelmää ja hydraulipiirejä kuvaava Simulink-malli. Nipin mallintamiseksi tampuuritela ja rullaussylinteri mallinnettiin joustaviksi käyttäen keskitettyjen massojen menetelmää. Siirtolaitteissa sekä runkorakenteissa tapahtuvat joustot kuvattiin yhden vapausasteen jousi-vaimennin voimilla kuvattuina järjestelminä. Tässä diplomityössä on myös keskitytty esittelemään ADAMS-ohjelmiston toimintaa ohjeistavasti sekä käsittelemään parametrisen mallintamisen etuja. Työssä havaittiin monikappaledynamiikan soveltuvuus kiinnirullaimen dynamiikan sekä dynaamisten voimien aiheuttamien värähtelyjen tutkimiseen. Suoritetuista värähtelymittauksista voitiin tehdä vain arvioita. Mallin havaittiin vaativan lisätutkimusta ja kehitystyötä

Functional error modeling for uncertainty quantification in hydrogeology

Approximate models (proxies) can be employed to reduce the computational costs of estimating uncertainty. The price to pay is that the approximations introduced by the proxy model can lead to a biased estimation. To avoid this problem and ensure a reliable uncertainty quantification, we propose to combine functional data analysis and machine learning to build error models that allow us to obtain an accurate prediction of the exact response without solving the exact model for all realizations. We build the relationship between proxy and exact model on a learning set of geostatistical realizations for which both exact and approximate solvers are run. Functional principal components analysis (FPCA) is used to investigate the variability in the two sets of curves and reduce the dimensionality of the problem while maximizing the retained information. Once obtained, the error model can be used to predict the exact response of any realization on the basis of the sole proxy response. This methodology is purpose-oriented as the error model is constructed directly for the quantity of interest, rather than for the state of the system. Also, the dimensionality reduction performed by FPCA allows a diagnostic of the quality of the error model to assess the informativeness of the learning set and the fidelity of the proxy to the exact model. The possibility of obtaining a prediction of the exact response for any newly generated realization suggests that the methodology can be effectively used beyond the context of uncertainty quantification, in particular for Bayesian inference and optimization.

Verkkokäyttöisten tahtimoottorien käynnistyshäiriön tutkiminen

Diplomityössä tutkitaan verkkokäyttöisten harjattomasti magnetoitujen tahtimoottorien käynnistyshäiriötä, jossa moottori magnetoituu vasta useiden sekuntien kuluttua magnetoinnin kytkemisestä magnetointilaitteiston normaalista toiminnasta huolimatta. Syy magnetoitumisen viivästymiseen on magnetointikoneen oikosulkeutuminen roottorin ylijännitesuojana toimivan tyristorihaaran kautta siitä huolimatta, että tyristorihaaran tyristorien on tarkoitus olla johtamattomassa tilassa magnetointikoneen alkaessa syöttää magnetointivirtaa. Syitä tyristorien johtavana pysymiseen magnetoinnin kytkennän jälkeen etsitään tahtimoottorin käynnistyskokeista saatujen mittaustulosten sekä SMT- ja FCSMEK-laskentaohjelmilla tehtyjen käynnistyssimulointien avulla. Samalla arvioidaan ohjelmien käyttökelpoisuutta käynnistyshäiriön ennakoimisessa. Diplomityössä esitetään syyt kahden esimerkkikoneen magnetoitumisen viivästymiseen sekä muutoksia roottoripiiriin ja käynnistysproseduuriin, joiden avulla tutkittu käynnistyshäiriö voitaisiin tulevaisuudessa todennäköisesti välttää.

Cerimetric determination of simvastatin in pharmaceuticals based on redox and complex formation reactions

Two sensitive spectrophotometric methods are described for the determination of simvastatin (SMT) in bulk drug and in tablets. The methods are based on the oxidation of SMT by a measured excess of cerium (IV) in acid medium followed by determination of unreacted oxidant by two different reaction schemes. In one procedure (method A), the residual cerium (IV) is reacted with a fixed concentration of ferroin and the increase in absorbance is measured at 510 nm. The second approach (method B) involves the reduction of the unreacted cerium (IV) with a fixed quantity of iron (II), and the resulting iron (III) is complexed with thiocyanate and the absorbance measured at 470 nm. In both methods, the amount of cerium (IV) reacted corresponds to SMT concentration. The experimental conditions for both methods were optimized. In method A, the absorbance is found to increase linearly with SMT concentration (r = 0.9995) whereas in method B, the same decreased (r = -0.9943). The systems obey Beer's law for 0.6-7.5 and 0.5-5.0 µg mL-1 for method A and method B, respectively. The calculated molar absorptivity values are 2.7 X 10(4) and 1.06 X 10(5) Lmol-1 cm-1, respectively; and the corresponding sandel sensitivity values are 0.0153 and 0.0039µg cm-2, respectively. The limit of detection (LOD) and quantification (LOQ) are reported for both methods. Intra-day and inter-day precision, and accuracy of the methods were established as per the current ICH guidelines. The methods were successfully applied to the determination of SMT in tablets and the results were statistically compared with those of the reference method by applying the Student's t-test and F-test. No interference was observed from the common excipients added to tablets. The accuracy and validity of the methods were further ascertained by performing recovery experiments via standard addition procedure.

Tool-supported invariant-based programming

The development of correct programs is a core problem in computer science. Although formal verification methods for establishing correctness with mathematical rigor are available, programmers often find these difficult to put into practice. One hurdle is deriving the loop invariants and proving that the code maintains them. So called correct-by-construction methods aim to alleviate this issue by integrating verification into the programming workflow. Invariant-based programming is a practical correct-by-construction method in which the programmer first establishes the invariant structure, and then incrementally extends the program in steps of adding code and proving after each addition that the code is consistent with the invariants. In this way, the program is kept internally consistent throughout its development, and the construction of the correctness arguments (proofs) becomes an integral part of the programming workflow. A characteristic of the approach is that programs are described as invariant diagrams, a graphical notation similar to the state charts familiar to programmers. Invariant-based programming is a new method that has not been evaluated in large scale studies yet. The most important prerequisite for feasibility on a larger scale is a high degree of automation. The goal of the Socos project has been to build tools to assist the construction and verification of programs using the method. This thesis describes the implementation and evaluation of a prototype tool in the context of the Socos project. The tool supports the drawing of the diagrams, automatic derivation and discharging of verification conditions, and interactive proofs. It is used to develop programs that are correct by construction. The tool consists of a diagrammatic environment connected to a verification condition generator and an existing state-of-the-art theorem prover. Its core is a semantics for translating diagrams into verification conditions, which are sent to the underlying theorem prover. We describe a concrete method for 1) deriving sufficient conditions for total correctness of an invariant diagram; 2) sending the conditions to the theorem prover for simplification; and 3) reporting the results of the simplification to the programmer in a way that is consistent with the invariantbased programming workflow and that allows errors in the program specification to be efficiently detected. The tool uses an efficient automatic proof strategy to prove as many conditions as possible automatically and lets the remaining conditions be proved interactively. The tool is based on the verification system PVS and i uses the SMT (Satisfiability Modulo Theories) solver Yices as a catch-all decision procedure. Conditions that were not discharged automatically may be proved interactively using the PVS proof assistant. The programming workflow is very similar to the process by which a mathematical theory is developed inside a computer supported theorem prover environment such as PVS. The programmer reduces a large verification problem with the aid of the tool into a set of smaller problems (lemmas), and he can substantially improve the degree of proof automation by developing specialized background theories and proof strategies to support the specification and verification of a specific class of programs. We demonstrate this workflow by describing in detail the construction of a verified sorting algorithm. Tool-supported verification often has little to no presence in computer science (CS) curricula. Furthermore, program verification is frequently introduced as an advanced and purely theoretical topic that is not connected to the workflow taught in the early and practically oriented programming courses. Our hypothesis is that verification could be introduced early in the CS education, and that verification tools could be used in the classroom to support the teaching of formal methods. A prototype of Socos has been used in a course at Åbo Akademi University targeted at first and second year undergraduate students. We evaluate the use of Socos in the course as part of a case study carried out in 2007.

Methods and Models for Accelerating Dynamic Simulation of Fluid Power Circuits

The objective of this dissertation is to improve the dynamic simulation of fluid power circuits. A fluid power circuit is a typical way to implement power transmission in mobile working machines, e.g. cranes, excavators etc. Dynamic simulation is an essential tool in developing controllability and energy-efficient solutions for mobile machines. Efficient dynamic simulation is the basic requirement for the real-time simulation. In the real-time simulation of fluid power circuits there exist numerical problems due to the software and methods used for modelling and integration. A simulation model of a fluid power circuit is typically created using differential and algebraic equations. Efficient numerical methods are required since differential equations must be solved in real time. Unfortunately, simulation software packages offer only a limited selection of numerical solvers. Numerical problems cause noise to the results, which in many cases leads the simulation run to fail. Mathematically the fluid power circuit models are stiff systems of ordinary differential equations. Numerical solution of the stiff systems can be improved by two alternative approaches. The first is to develop numerical solvers suitable for solving stiff systems. The second is to decrease the model stiffness itself by introducing models and algorithms that either decrease the highest eigenvalues or neglect them by introducing steady-state solutions of the stiff parts of the models. The thesis proposes novel methods using the latter approach. The study aims to develop practical methods usable in dynamic simulation of fluid power circuits using explicit fixed-step integration algorithms. In this thesis, twomechanisms whichmake the systemstiff are studied. These are the pressure drop approaching zero in the turbulent orifice model and the volume approaching zero in the equation of pressure build-up. These are the critical areas to which alternative methods for modelling and numerical simulation are proposed. Generally, in hydraulic power transmission systems the orifice flow is clearly in the turbulent area. The flow becomes laminar as the pressure drop over the orifice approaches zero only in rare situations. These are e.g. when a valve is closed, or an actuator is driven against an end stopper, or external force makes actuator to switch its direction during operation. This means that in terms of accuracy, the description of laminar flow is not necessary. But, unfortunately, when a purely turbulent description of the orifice is used, numerical problems occur when the pressure drop comes close to zero since the first derivative of flow with respect to the pressure drop approaches infinity when the pressure drop approaches zero. Furthermore, the second derivative becomes discontinuous, which causes numerical noise and an infinitely small integration step when a variable step integrator is used. A numerically efficient model for the orifice flow is proposed using a cubic spline function to describe the flow in the laminar and transition areas. Parameters for the cubic spline function are selected such that its first derivative is equal to the first derivative of the pure turbulent orifice flow model in the boundary condition. In the dynamic simulation of fluid power circuits, a tradeoff exists between accuracy and calculation speed. This investigation is made for the two-regime flow orifice model. Especially inside of many types of valves, as well as between them, there exist very small volumes. The integration of pressures in small fluid volumes causes numerical problems in fluid power circuit simulation. Particularly in realtime simulation, these numerical problems are a great weakness. The system stiffness approaches infinity as the fluid volume approaches zero. If fixed step explicit algorithms for solving ordinary differential equations (ODE) are used, the system stability would easily be lost when integrating pressures in small volumes. To solve the problem caused by small fluid volumes, a pseudo-dynamic solver is proposed. Instead of integration of the pressure in a small volume, the pressure is solved as a steady-state pressure created in a separate cascade loop by numerical integration. The hydraulic capacitance V/Be of the parts of the circuit whose pressures are solved by the pseudo-dynamic method should be orders of magnitude smaller than that of those partswhose pressures are integrated. The key advantage of this novel method is that the numerical problems caused by the small volumes are completely avoided. Also, the method is freely applicable regardless of the integration routine applied. The superiority of both above-mentioned methods is that they are suited for use together with the semi-empirical modelling method which necessarily does not require any geometrical data of the valves and actuators to be modelled. In this modelling method, most of the needed component information can be taken from the manufacturer’s nominal graphs. This thesis introduces the methods and shows several numerical examples to demonstrate how the proposed methods improve the dynamic simulation of various hydraulic circuits.

Kernel-Based Ranking. Methods for Learning and Performance Estimation

Machine learning provides tools for automated construction of predictive models in data intensive areas of engineering and science. The family of regularized kernel methods have in the recent years become one of the mainstream approaches to machine learning, due to a number of advantages the methods share. The approach provides theoretically well-founded solutions to the problems of under- and overfitting, allows learning from structured data, and has been empirically demonstrated to yield high predictive performance on a wide range of application domains. Historically, the problems of classification and regression have gained the majority of attention in the field. In this thesis we focus on another type of learning problem, that of learning to rank. In learning to rank, the aim is from a set of past observations to learn a ranking function that can order new objects according to how well they match some underlying criterion of goodness. As an important special case of the setting, we can recover the bipartite ranking problem, corresponding to maximizing the area under the ROC curve (AUC) in binary classification. Ranking applications appear in a large variety of settings, examples encountered in this thesis include document retrieval in web search, recommender systems, information extraction and automated parsing of natural language. We consider the pairwise approach to learning to rank, where ranking models are learned by minimizing the expected probability of ranking any two randomly drawn test examples incorrectly. The development of computationally efficient kernel methods, based on this approach, has in the past proven to be challenging. Moreover, it is not clear what techniques for estimating the predictive performance of learned models are the most reliable in the ranking setting, and how the techniques can be implemented efficiently. The contributions of this thesis are as follows. First, we develop RankRLS, a computationally efficient kernel method for learning to rank, that is based on minimizing a regularized pairwise least-squares loss. In addition to training methods, we introduce a variety of algorithms for tasks such as model selection, multi-output learning, and cross-validation, based on computational shortcuts from matrix algebra. Second, we improve the fastest known training method for the linear version of the RankSVM algorithm, which is one of the most well established methods for learning to rank. Third, we study the combination of the empirical kernel map and reduced set approximation, which allows the large-scale training of kernel machines using linear solvers, and propose computationally efficient solutions to cross-validation when using the approach. Next, we explore the problem of reliable cross-validation when using AUC as a performance criterion, through an extensive simulation study. We demonstrate that the proposed leave-pair-out cross-validation approach leads to more reliable performance estimation than commonly used alternative approaches. Finally, we present a case study on applying machine learning to information extraction from biomedical literature, which combines several of the approaches considered in the thesis. The thesis is divided into two parts. Part I provides the background for the research work and summarizes the most central results, Part II consists of the five original research articles that are the main contribution of this thesis.

Model based analysis of the post-combustion calcium looping process for carbon dioxide capture

This thesis presents a one-dimensional, semi-empirical dynamic model for the simulation and analysis of a calcium looping process for post-combustion CO2 capture. Reduction of greenhouse emissions from fossil fuel power production requires rapid actions including the development of efficient carbon capture and sequestration technologies. The development of new carbon capture technologies can be expedited by using modelling tools. Techno-economical evaluation of new capture processes can be done quickly and cost-effectively with computational models before building expensive pilot plants. Post-combustion calcium looping is a developing carbon capture process which utilizes fluidized bed technology with lime as a sorbent. The main objective of this work was to analyse the technological feasibility of the calcium looping process at different scales with a computational model. A one-dimensional dynamic model was applied to the calcium looping process, simulating the behaviour of the interconnected circulating fluidized bed reactors. The model incorporates fundamental mass and energy balance solvers to semi-empirical models describing solid behaviour in a circulating fluidized bed and chemical reactions occurring in the calcium loop. In addition, fluidized bed combustion, heat transfer and core-wall layer effects were modelled. The calcium looping model framework was successfully applied to a 30 kWth laboratory scale and a pilot scale unit 1.7 MWth and used to design a conceptual 250 MWth industrial scale unit. Valuable information was gathered from the behaviour of a small scale laboratory device. In addition, the interconnected behaviour of pilot plant reactors and the effect of solid fluidization on the thermal and carbon dioxide balances of the system were analysed. The scale-up study provided practical information on the thermal design of an industrial sized unit, selection of particle size and operability in different load scenarios.

Effets de la vibration des muscles sur les mécanismes neuronaux et la fonction du membre supérieur et inférieur des personnes ayant une hémiparésie chronique

Cette thèse vise à répondre à trois questions fondamentales: 1) La diminution de l’excitabilité corticospinale et le manque d’inhibition intracorticale observés suite à la stimulation magnétique transcrânienne (SMT) du cortex moteur de la main atteinte de sujets hémiparétiques sont-ils aussi présents suite à la SMT du cortex moteur de la jambe atteinte? 2) Est-ce que les altérations dans l’excitabilité corticomotrice sont corrélées aux déficits et incapacités motrices des personnes ayant subi un accident vasculaire cérébral depuis plus de 6 mois? 3) La vibration musculaire, étant la source d’une forte afférence sensorielle, peut-elle moduler l’excitabilité corticomotrice et améliorer la performance motrice de ces personnes? Premièrement, afin d’appuyer notre choix d’intervention et d’évaluer le potentiel de la vibration mécanique locale pour favoriser la réadaptation des personnes ayant une atteinte neurologique, nous avons réalisé une révision en profondeur de ses applications et intérêts cliniques à partir d’informations trouvées dans la littérature scientifique (article 1). La quantité importante d’information sur les effets physiologiques de la vibration contraste avec la pauvreté des études qui ont évalué son effet thérapeutique. Nous avons trouvé que, malgré le manque d’études, les résultats sur son utilisation sont encourageants et positifs et aucun effet adverse n’a été rapporté. Dans les trois autres articles qui composent cette thèse, l’excitabilité des circuits corticospinaux et intracorticaux a été étudiée chez 27 sujets hémiparétiques et 20 sujets sains sans atteintes neurologiques. Les fonctions sensorimotrices ont aussi été évaluées par des tests cliniques valides et fidèles. Tel qu’observé à la main chez les sujets hémiparétiques, nous avons trouvé, par rapport aux sujets sains, une diminution de l’excitabilité corticospinale ainsi qu’un manque d’inhibition intracorticale suite à la SMT du cortex moteur de la jambe atteinte (article 2). Les sujets hémiparétiques ont également montré un manque de focus de la commande motrice lors de l’activation volontaire des fléchisseurs plantaires. Ceci était caractérisé par une augmentation de l’excitabilité nerveuse des muscles agonistes, mais aussi généralisée aux synergistes et même aux antagonistes. De plus, ces altérations ont été corrélées aux déficits moteurs au membre parétique. Le but principal de cette thèse était de tester les effets potentiels de la vibration des muscles de la main (article 3) et de la cuisse (article 4) sur les mécanismes neuronaux qui contrôlent ces muscles. Nous avons trouvé que la vibration augmente l’amplitude de la réponse motrice des muscles vibrés, même chez des personnes n’ayant pas de réponse motrice au repos ou lors d’une contraction volontaire. La vibration a également diminué l’inhibition intracorticale enregistrée au quadriceps parétique (muscle vibré). La diminution n’a cependant pas été significative au niveau de la main. Finalement, lors d’un devis d’investigation croisé, la vibration de la main ou de la jambe parétique a résulté en une amélioration spécifique de la dextérité manuelle ou de la coordination de la jambe, respectivement. Au membre inférieur, la vibration du quadriceps a également diminuée la spasticité des patients. Les résultats obtenus dans cette thèse sont très prometteurs pour la rééducation de la personne hémiparétique car avec une seule séance de vibration, nous avons obtenu des améliorations neurophysiologiques et cliniques.

Scheduled service network design for integrated planning of rail freight transportation

Cette thèse étudie une approche intégrant la gestion de l’horaire et la conception de réseaux de services pour le transport ferroviaire de marchandises. Le transport par rail s’articule autour d’une structure à deux niveaux de consolidation où l’affectation des wagons aux blocs ainsi que des blocs aux services représentent des décisions qui complexifient grandement la gestion des opérations. Dans cette thèse, les deux processus de consolidation ainsi que l’horaire d’exploitation sont étudiés simultanément. La résolution de ce problème permet d’identifier un plan d’exploitation rentable comprenant les politiques de blocage, le routage et l’horaire des trains, de même que l’habillage ainsi que l’affectation du traffic. Afin de décrire les différentes activités ferroviaires au niveau tactique, nous étendons le réseau physique et construisons une structure de réseau espace-temps comprenant trois couches dans lequel la dimension liée au temps prend en considération les impacts temporels sur les opérations. De plus, les opérations relatives aux trains, blocs et wagons sont décrites par différentes couches. Sur la base de cette structure de réseau, nous modélisons ce problème de planification ferroviaire comme un problème de conception de réseaux de services. Le modèle proposé se formule comme un programme mathématique en variables mixtes. Ce dernie r s’avère très difficile à résoudre en raison de la grande taille des instances traitées et de sa complexité intrinsèque. Trois versions sont étudiées : le modèle simplifié (comprenant des services directs uniquement), le modèle complet (comprenant des services directs et multi-arrêts), ainsi qu’un modèle complet à très grande échelle. Plusieurs heuristiques sont développées afin d’obtenir de bonnes solutions en des temps de calcul raisonnables. Premièrement, un cas particulier avec services directs est analysé. En considérant une cara ctéristique spécifique du problème de conception de réseaux de services directs nous développons un nouvel algorithme de recherche avec tabous. Un voisinage par cycles est privilégié à cet effet. Celui-ci est basé sur la distribution du flot circulant sur les blocs selon les cycles issus du réseau résiduel. Un algorithme basé sur l’ajustement de pente est développé pour le modèle complet, et nous proposons une nouvelle méthode, appelée recherche ellipsoidale, permettant d’améliorer davantage la qualité de la solution. La recherche ellipsoidale combine les bonnes solutions admissibles générées par l’algorithme d’ajustement de pente, et regroupe les caractéristiques des bonnes solutions afin de créer un problème élite qui est résolu de facon exacte à l’aide d’un logiciel commercial. L’heuristique tire donc avantage de la vitesse de convergence de l’algorithme d’ajustement de pente et de la qualité de solution de la recherche ellipsoidale. Les tests numériques illustrent l’efficacité de l’heuristique proposée. En outre, l’algorithme représente une alternative intéressante afin de résoudre le problème simplifié. Enfin, nous étudions le modèle complet à très grande échelle. Une heuristique hybride est développée en intégrant les idées de l’algorithme précédemment décrit et la génération de colonnes. Nous proposons une nouvelle procédure d’ajustement de pente où, par rapport à l’ancienne, seule l’approximation des couts liés aux services est considérée. La nouvelle approche d’ajustement de pente sépare ainsi les décisions associées aux blocs et aux services afin de fournir une décomposition naturelle du problème. Les résultats numériques obtenus montrent que l’algorithme est en mesure d’identifier des solutions de qualité dans un contexte visant la résolution d’instances réelles.

Microstructural and metabolic changes in the brains of concussed athletes

Les commotions cérébrales ont longtemps été considérées comme une blessure ne comportant que peu ou pas de conséquences. Cependant, la mise à la retraite forcée de plusieurs athlètes de haut niveau, liée au fait d'avoir subi des commotions cérébrales multiples, a porté cette question au premier plan de la culture scientifique et sportive. Malgré la sensibilisation croissante du public et la compréhension scientifique accrue des commotions cérébrales, il reste encore beaucoup d’inconnus au sujet de ces blessures. En effet, il est difficile de comprendre comment cette atteinte peut avoir des effets si profonds malgré le fait qu’elle n’entraîne apparemment pas de conséquences physiques apparentes lorsque les techniques traditionnelles d’imagerie cérébrale sont utilisées. Les techniques de neuroimagerie fonctionnelle ont cependant contribué à répondre aux nombreuses questions entourant les conséquences des commotions cérébrales ainsi qu'à accroître la compréhension générale de la physiopathologie de commotions cérébrales. Bien que les techniques de base telles que l'imagerie structurelle comme les scans TC et IRM soient incapables de détecter des changements structurels dans la grande majorité des cas (Ellemberg, Henry, Macciocchi, Guskiewicz, & Broglio, 2009; Johnston, Ptito, Chankowsky, & Chen, 2001), d'autres techniques plus précises et plus sensibles ont été en mesure de détecter avec succès des changements dans le cerveau commotionné. Des études d’IRM fonctionelle ont entre autres établi une solide relation entre les altérations fonctionnelles et les symptômes post-commotionels (Chen, Johnston, Collie, McCrory, & Ptito, 2007; Chen et al., 2004; Chen, Johnston, Petrides, & Ptito, 2008; Fazio, Lovell, Pardini, & Collins, 2007). Les mesures électrophysiologiques telles que les potentiels évoqués cognitifs (ERP) (Gaetz, Goodman, & Weinberg, 2000; Gaetz & Weinberg, 2000; Theriault, De Beaumont, Gosselin, Filipinni, & Lassonde, 2009; Theriault, De Beaumont, Tremblay, Lassonde, & Jolicoeur, 2010) et la stimulation magnétique transcrânienne ou SMT (De Beaumont, Brisson, Lassonde, & Jolicoeur, 2007; De Beaumont, Lassonde, Leclerc, & Theoret, 2007; De Beaumont et al., 2009) ont systématiquement démontré des altérations fonctionnelles chez les athlètes commotionnés. Cependant, très peu de recherches ont tenté d'explorer davantage certaines conséquences spécifiques des commotions cérébrales, entre autres sur les plans structural et métabolique. La première étude de cette thèse a évalué les changements structurels chez les athlètes commotionnés à l’aide de l'imagerie en tenseur de diffusion (DTI) qui mesure la diffusion de l'eau dans la matière blanche, permettant ainsi de visualiser des altérations des fibres nerveuses. Nous avons comparé les athlètes commotionnés à des athlètes de contrôle non-commotionnés quelques jours après la commotion et de nouveau six mois plus tard. Nos résultats indiquent un patron constant de diffusion accrue le long des voies cortico-spinales et dans la partie du corps calleux reliant les régions motrices. De plus, ces changements étaient encore présents six mois après la commotion, ce qui suggère que les effets de la commotion cérébrale persistent bien après la phase aiguë. Les deuxième et troisième études ont employé la spectroscopie par résonance magnétique afin d'étudier les changements neurométaboliques qui se produisent dans le cerveau commotionné. La première de ces études a évalué les changements neurométaboliques, les aspects neuropsychologiques, et la symptomatologie dans la phase aiguë post-commotion. Bien que les tests neuropsychologiques aient été incapables de démontrer des différences entre les athlètes commotionnés et non-commotionnés, des altérations neurométaboliques ont été notées dans le cortex préfrontal dorsolatéral ainsi que dans le cortex moteur primaire, lesquelles se sont avérées corréler avec les symptômes rapportés. La deuxième de ces études a comparé les changements neurométaboliques immédiatement après une commotion cérébrale et de nouveau six mois après l’atteinte. Les résultats ont démontré des altérations dans le cortex préfrontal dorsolatéral et moteur primaire dans la phase aiguë post-traumatique, mais seules les altérations du cortex moteur primaire ont persisté six mois après la commotion. Ces résultats indiquent que les commotions cérébrales peuvent affecter les propriétés physiques du cerveau, spécialement au niveau moteur. Il importe donc de mener davantage de recherches afin de mieux caractériser les effets moteurs des commotions cérébrales sur le plan fonctionnel.

Traduction statistique vers une langue à morphologie riche : combinaison d’algorithmes de segmentation morphologique et de modèles statistiques de traduction automatique

Les systèmes statistiques de traduction automatique ont pour tâche la traduction d’une langue source vers une langue cible. Dans la plupart des systèmes de traduction de référence, l'unité de base considérée dans l'analyse textuelle est la forme telle qu’observée dans un texte. Une telle conception permet d’obtenir une bonne performance quand il s'agit de traduire entre deux langues morphologiquement pauvres. Toutefois, ceci n'est plus vrai lorsqu’il s’agit de traduire vers une langue morphologiquement riche (ou complexe). Le but de notre travail est de développer un système statistique de traduction automatique comme solution pour relever les défis soulevés par la complexité morphologique. Dans ce mémoire, nous examinons, dans un premier temps, un certain nombre de méthodes considérées comme des extensions aux systèmes de traduction traditionnels et nous évaluons leurs performances. Cette évaluation est faite par rapport aux systèmes à l’état de l’art (système de référence) et ceci dans des tâches de traduction anglais-inuktitut et anglais-finnois. Nous développons ensuite un nouvel algorithme de segmentation qui prend en compte les informations provenant de la paire de langues objet de la traduction. Cet algorithme de segmentation est ensuite intégré dans le modèle de traduction à base d’unités lexicales « Phrase-Based Models » pour former notre système de traduction à base de séquences de segments. Enfin, nous combinons le système obtenu avec des algorithmes de post-traitement pour obtenir un système de traduction complet. Les résultats des expériences réalisées dans ce mémoire montrent que le système de traduction à base de séquences de segments proposé permet d’obtenir des améliorations significatives au niveau de la qualité de la traduction en terme de le métrique d’évaluation BLEU (Papineni et al., 2002) et qui sert à évaluer. Plus particulièrement, notre approche de segmentation réussie à améliorer légèrement la qualité de la traduction par rapport au système de référence et une amélioration significative de la qualité de la traduction est observée par rapport aux techniques de prétraitement de base (baseline).