Over the past two decades, holistic and systemic approaches to second language development have begun to draw the attention of scholars in the field of SLA. These studies are primarily informed by complexity theory, which emerged from the general systems theory. General systems theory, however, has another important theoretical offshoot in social sciences, namely autopoietic systems theory. An investigation of conceptual tools drawn from the latter theory has been absent in the field of second language education. This paper seeks to explore how systemic thinking has improved the field’s understanding of the complexity of the L2 development. It then explores the possibilities for incorporating autopoietic systems theory into complexity thinking to better understand the dynamics of L2 development at personal and social levels. Finally, it will highlight two insights from a systemic analysis of language development in L2 classroom groupings. These insights build on each other to describe L2 development from a systemic perspective. By exploring and bringing together these theoretical perspectives, this paper hopes to shed light on how complexity theory can provide a systemic description of L2 development.

A constraint satisfaction problem (CSP) can be represented as two structures: the structure induced by the variables and the structure induced by the constraint language. Both these parameters are amenable to restrictions which affects the complexity of the resulting problems. In this thesis we shall use both constraint language restrictions and structural restrictions in order to create problems that can be solved as efficiently as possible. The language restrictions are based on creating a language that in terms of frozen partial clone theory has the largest number of polymorphic functions. Such a language can according to the Galois connection between functions and relations be implemented by as many languages as possible and is therefore the Boolean language with the lowest complexity. The structural restrictions are mainly based on limiting the number of times a variable is allowed to occur in an instance. We shall prove that the easiest language does not contain a Delta-matroid relation and is NP-complete even with the very restricted structure where no variable can occur in more than two constraints. We also give a branch-and-reduce algorithm for this problem with time complexity O(1.0493^n). This problem is then related to the exponential-time hypothesis, which postulates that k-SAT is not sub-exponential for k >= 3. We show that the exponential-time hypothesis holds if and only if this restricted problem is not sub-exponential, if and only if all NP-complete Boolean languages are not sub-exponential. In the process we also prove a stronger version of Impagliazzo's sparsification lemma for k-SAT; namely that all finite, NP-complete Boolean languages can be sparsified into each other. This should be contrasted with Santhanam's negative result which states that the same does not hold for all infinite Boolean languages.

The Constraint Satisfaction Problem (CSP) is a fundamental NP-complete problem with many applications in artificial intelligence. This problem has enjoyed considerable scientific attention in the past decades due to its practical usefulness and the deep theoretical questions it relates to. However, there is a wide gap between practitioners, who develop solving techniques that are efficient for industrial instances but exponential in the worst case, and theorists who design sophisticated polynomial-time algorithms for restrictions of CSP defined by certain algebraic properties. In this thesis we attempt to bridge this gap by providing polynomial-time algorithms to test for membership in a selection of major tractable classes. Even if the instance does not belong to one of these classes, we investigate the possibility of decomposing efficiently a CSP instance into tractable subproblems through the lens of parameterized complexity. Finally, we propose a general framework to adapt the concept of kernelization, central to parameterized complexity but hitherto rarely used in practice, to the context of constraint reasoning. Preliminary experiments on this last contribution show promising results.

No description available.

Context. Almost all of the modern computers today have a CPU withmultiple cores, providing extra computational power. In the new ageof big data, parallel execution is essential to improve the performanceto an acceptable level. With parallelisation comes new challenges thatneeds to be considered. Objectives. In this work, parallel algorithms are compared and analysedin relation to their sequential counterparts, using the Java platform.Through this, find the potential speedup for multithreading andwhat factors affects the performance. In addition, provide source codefor multithreaded algorithms with proven time complexities. Methods. A literature study was conducted to gain knowledge anddeeper understanding into the aspects of sorting algorithms and thearea of parallel computing. An experiment followed of implementing aset of algorithms from which data could be gather through benchmarkingand testing. The data gathered was studied and analysed with itscorresponding source code to prove the validity of parallelisation. Results. Multithreading does improve performance, with two threadsin average providing a speedup of up to 2x and four threads up to3x. However, the potential speedup is bound to the available physicalthreads of the CPU and dependent of balancing the workload. Conclusions. The importance of workload balancing and using thecorrect number of threads in relation to the problem to be solved,needs to be carefully considered in order to utilize the extra resourcesavailable to its full potential.

Cette thèse porte sur la modélisation et la résolution de différents problèmes de tournées de véhicules et plus particulièrement sur des problèmes de transport de personnes. Ces problèmes, demandent, entre autre, de respecter une qualité de service minimale pour les solutions proposées. Pour résoudre ces problèmes, plusieurs méthodes d'optimisation de type métaheuristique sont proposées pour obtenir des solutions de bonne qualité dans des temps raisonnables. Trois problèmes sont traités successivement : le DARP, le TDVRP, le SDARP. Le premier est un problème de transport à la demande (DARP - Dial-A-Ride Problem) qui est le problème de transport de personnes le plus connu de la littérature. Il est proposé dans ce chapitre une méthode de type ELS qui a été comparée aux meilleures méthodes publiées. Les tests montrent que la méthode ELS est compétitive en termes de temps de calcul et de qualité des résultats. Le deuxième problème est une extension du problème de tournées de véhicules (VRP - Vehicle Routing Problem) dans lequel les temps de trajet entre les sommets varient au cours de la journée (TDVRP - Time Dependent Vehicle Routing Problem). Dans ce problème, une distinction existe entre les temps de conduite et les temps de travail des chauffeurs. La différence entre les deux correspond aux temps de pause. Ils sont utilisés ici durant les tournées pour éviter aux chauffeurs de conduire durant les périodes à fort ralentissement du trafic. La méthode proposée permet entre autre de positionner stratégiquement ces pauses afin de réduire le temps de conduite et de proposer de nouvelles solutions. Le dernier problème traité concerne la résolution d'un DARP stochastique. Dans ce problème, les temps de trajet entre les clients ne sont plus déterministes, et ils sont modélisés par une loi de probabilité. L'objectif est de déterminer des solutions robustes aux fluctuations des temps de trajets sur les arcs. Une première approche a permis de calculer des solutions robustes qui ont une probabilité importante d'être réalisables, une seconde approche a permis de générer un ensemble de solutions offrant un équilibre entre la robustesse et le coût. / In this thesis, we are interested in modeling and solving various vehicle routing problems (VRP), especially passenger transportation problems. These problems aim at finding solutions which guarantee a required quality of service. Several metaheuristics are proposed to obtain high quality solutions within reasonable time. Three problems are addressed: the Dial-A-Ride Problem (DARP), the Time-Dependent Vehicle Routing Problem (TDVRP) and the Stochastic DARP (SDARP). The DARP is a well-known on-demand transportation problem. We propose an Evolutionary Local Search (ELS) method. It relies on a new randomized constructive heuristic and on adaptive probabilities for selecting neighborhood structures. This approach is compared with existing methods on classical instances. Results show the interest of the proposed method. The TDVRP is an extension of VRP in which the transportation time varies throughout the day. The driving time is separated from the drivers working time and the difference corresponds to the resting time. The resting time is used to avoid driving during highly congested periods. The proposed method set these resting times in order to reduce the driving time. Hence new solutions avoiding congestion as much as possible are proposed. In the SDARP, the travel time between clients is stochastic and thus follows a probability distribution. The objective is to compute robust solutions, i.e. solutions which handle variations of the transportation time. Two approaches are proposed for this problem. The first one produces robust solutions that have a significant probability of staying feasible. The second one generates a set of compromise solutions, balancing the robustness and the cost.

The main aim of this study is to investigate human understanding of process models and to develop an improved understanding of its relevant influence factors. Aided by assumptions from cognitive psychology, this article attempts to address specific deductive reasoning difficulties based on process models. The authors developed a research model to capture the influence of two effects on the cognitive difficulty of reasoning tasks: (i) the presence of different control-flow patterns (such as conditional or parallel execution) in a process model and (ii) the interactivity of model elements. Based on solutions to 61 different reasoning tasks by 155 modelers, the results from this study indicate that the presence of certain control-flow patterns influences the cognitive difficulty of reasoning tasks. In particular, sequence is relatively easy, while loops in a model proved difficult. Modelers with higher process modeling knowledge performed better and rated subjective difficulty of loops lower than modelers with lower process modeling knowledge. The findings additionally support the prediction that interactivity between model elements is positively related to the cognitive difficulty of reasoning. Our research contributes to both academic literature on the comprehension of process models and practitioner literature focusing on cognitive difficulties when using process models.

Computational thinking (CT) is gaining recognition as an important skill for students, both in computer science and other disciplines. Although there has been much focus on this field in recent years, it is rarely taught as a formal course, and there is little consensus on what exactly CT entails and how to teach and evaluate it. This research addresses the lack of resources for integrating CT into the introductory computer science curriculum. The question that we aim to answer is whether CT can be evaluated in a meaningful way. A CT framework that outlines the skills and techniques comprising CT and describes the nature of student engagement was developed; this is used as the basis for this research. An assessment (CT test) was then created to gauge the ability of incoming students, and a CT-specfic computer game was developed based on the analysis of an existing game. A set of problem solving strategies and practice activities were then recommended based on criteria defined in the framework. The results revealed that the CT abilities of first year university students are relatively poor, but that the students' scores for the CT test could be used as a predictor for their future success in computer science courses. The framework developed for this research proved successful when applied to the test, computer game evaluation, and classification of strategies and activities. Through this research, we established that CT is a skill that first year computer science students are lacking, and that using CT exercises alongside traditional programming instruction can improve students' learning experiences.

Dans cette thèse, nous donnons de nouveaux résultats sur la taille moyenne d’enveloppes convexes de points choisis dans un convexe. Cette taille est connue lorsque les points sont choisis uniformément (et indépendamment) dans un polytope convexe, ou un convexe suffisamment «lisse» ; ou encore lorsque les points sont choisis indépendamment selon une loi normale centrée. Dans la première partie de cette thèse, nous développons une technique nous permettant de donner de nouveaux résultats lorsque les points sont choisis arbitrairement dans un convexe, puis «bruités» par une perturbation aléatoire. Ce type d’analyse, appelée analyse lissée, a initialement été développée par Spielman et Teng dans leur étude de l’algorithme du simplexe. Pour un ensemble de points arbitraires dans une boule, nous obtenons une borne inférieure et une borne supérieure de cette complexité lissée dans le cas de perturbations uniformes dans une boule en dimension arbitraire, ainsi que dans le cas de perturbations gaussiennes en dimension 2. La taille de l'enveloppe convexe de points choisis uniformément dans un convexe, peut avoir un comportement logarithmique si ce convexe est un polytope ou polynomial s’il est lisse. Nous construisons un convexe produisant un comportement oscillant entre ces deux extrêmes. Dans la dernière partie, nous présentons un algorithme pour engendrer efficacement une enveloppe convexe aléatoire de points choisis uniformément et indépendamment dans un disque sans avoir à engendrer explicitement tous les points. Il a été implémenté en C++ et intégré dans la bibliothèque CGAL. / In this thesis, we give some new results about the average size of convex hulls made of points chosen in a convex body. This size is known when the points are chosen uniformly (and independently) in a convex polytope or in a "smooth" enough convex body. This average size is also known if the points are independently chosen according to a centered Gaussian distribution. In the first part of this thesis, we introduce a technique that will give new results when the points are chosen arbitrarily in a convex body, and then noised by some random perturbations. This kind of analysis, called smoothed analysis, has been initially developed by Spielman and Teng in their study of the simplex algorithm. For an arbitrary set of point in a ball, we obtain a lower and a upper bound for this smoothed complexity, in the case of uniform perturbation in a ball (in arbitrary dimension) and in the case of Gaussian perturbations in dimension 2. The asymptotic behavior of the expected size of the convex hull of uniformly random points in a convex body is polynomial for a "smooth" body and polylogarithmic for a polytope. In the second part, we construct a convex body so that the expected size of the convex hull of points uniformly chosen in that body oscillates between these two behaviors when the number of points increases. In the last part, we present an algorithm to generate efficiently a random convex hull made of points chosen uniformly and independently in a disk. We also compute its average time and space complexity. This algorithm can generate a random convex hull without explicitly generating all the points. It has been implemented in C++ and integrated in the CGAL library.

Cette thèse est consacrée à une étude d'un point de vue général de jeux d'accessibilité dans des systèmes munis de compteurs. Dans ce type de jeux, l'objectif de l'un des deux joueurs est d'atteindre une configuration particulière, qui est composée d'un sommet de l'arène où le jeu se déroule et d'un n-uplet de valeurs pour les compteurs. Ces valeurs de compteurs sont mises à jour, généralement par des additions de vecteurs, lorsqu’un arc est emprunté. Le problème de décision associé à un jeu d’accessibilité est de savoir si le joueur en question a une stratégie gagnante depuis une configuration donnée. Lorsque ce problème est décidable, on s’intéresse à la possibilité de décrire l’ensemble de ces configurations dites gagnantes. Au cours de l’étude, des caractéristiques des jeux d’accessibilités avec des compteurs sont mises en parallèle, en cherchant des similarités, ou au contraire des différences, au niveau de la décidabilité et de la complexité du problème de décision, quand l’une de ces caractéristiques est modifiée. On retiendra en tant que caractéristique majeure le comportement quand un compteur devrait devenir négatif. Nous nous focalisons principalement sur trois sémantiques. Nous considérons également d’autres caractéristiques selon lesquelles il était possible de comparer décidabilité et complexité. Nous nous penchons sur un modèle intitulé « robot games », sur lequel nous obtenons des résultats majeurs : un algorithme de complexité asymptotiquement optimale en dimension un et une preuve d’indécidabilité en dimension trois. / This thesis is devoted to a general study of a reachability games on systems with counters. In this kind of games, the objective of one of two players is to reach a particular configuration, which is a pair composed of a vertex of the game arena and a tuple of values for the counters. The values of the counters are updated, usually by vector additions, when a edge is taken. The decision problem associated with a reachability game is whether a player has a winning strategy for the game from a given configuration, in other words whether the configuration is winning. When the problem of determining the winner from a given configuration is decidable, we wonder whether it is even possible to describe the set of winning configurations. In our study, we look at various features of counter reachability games, finding similarities or, on the contrary, differences with regard to decidability or complexity of the decision problem, when one of the features is modified. The main feature that we consider is what happens when a counter should become negative. We focus primarily on three semantics. We also consider other features that allow to compare decidability and complexity. We introduce a model, called “robot games”, on which we obtain our main results: an algorithm with an optimal complexity for dimension one, and undecidability for dimension three.