La complexité implicite (ICC) vise à donner des caractérisations de classes de complexité dans des langages de programmation ou des logiques, sans faire référence à des bornes sur les ressources (temps, espace mémoire). Dans cette thèse, nous étudions l’approche de la logique linéaire à la complexité implicite. L’objectif est de donner des caractérisations de classes de complexité, à travers des variantes du lambda-calcul qui sont typables dans de tels systèmes. En particulier, nous considérons à la fois une perspective monovalente et une perspective polyvalente par rapport à l’ICC. Dans le premier cas, le but est de caractériser une hiérarchie de classes de complexité à travers un lambda-calcul élémentaire typé dans la logique linéaire élémentaire (ELL), où la complexité ne dépend que de l’interface d’un programme, c’est à dire son type. La deuxième approche rend compte à la fois des fonctions calculables en temps polynomial et de la normalisation forte, à travers des termes du lambda-calcul pur qui sont typés dans un système inspiré par la logique linéaire Soft (SLL); en particulier, par rapport à l’approche logique ordinaire, ici nous abandonnons la modalité “!” en faveur de l’emploi des types stratifiés, vus comme un raffinement des types intersection non associatifs, afin d’améliorer la typabilité et, en conséquence, l’expressivité. Enfin, nous explorons l’utilisation des types intersection, privés de certaines de leurs propriétés, vers une direction plus quantitative que l’approche qualitative habituelle, afin d’obtenir une borne sur le calcul de lambda-termes purs, en obtenant en plus une caractérisation de la normalisation forte. / In this thesis we explore the linear logic approach to implicit computational complexity, through the design of type assignment systems based on light linear logic, or heavily inspired by them, with the purpose of giving a characterization of one or more complexity classes, through variants of lambda-calculi which are typable in such systems. In particular, we consider both a monovalent and a polyvalent perspective with respect to ICC. In the first one the aim is to characterize a hierarchy of complexity classes through an elementary lambda-calculus typed in Elementary Linear Logic (ELL), where the complexity depends only on the interface of a term, namely its type. The second approach gives an account of both the functions computable in polynomial time and of strong normalization, through terms of pure lambda-calculus which are typed in a system inspired by Soft Linear Logic (SLL); in particular, with respect to the usual logical take, in the latter we give up the “!” modality in favor of employing stratified types as a refinement of non-associative intersection types, in order to improve typability and, as a consequence, expressivity.Finally we explore the use of intersection types, deprived of some of their usual properties, towards a more quantitative approach rather than the usual qualitative one, namely in order to compute a bound on the computation of pure lambda-terms, obtaining in addition a characterization of strong normalization.

A noção de tipo é intrínseca ao raciocínio humano, na medida que os seres humanos tendem a "classificar" os objetos segundo seu use e seu comportamento como parte do processo de resolução de problemas. Tal classificação dos objetos implica numa abstração das características irrelevantes dos mesmos,permitindo dessa maneira uma simplificação importante da complexidade do universo de discurso Por outro lado, certos problemas são altamente complexos e requerem um tratamento diferenciado.Esses problemas exigem, para sua resolução, um grande conhecimento do universo de discurso. O ponto critico nesta situação é que o domínio do problema não é exato como poderia ser um domínio matemático. Pelo contrario, ele inclui geralmente aspectos ambíguos e pouco formais que dificultam seu entendimento. Tal domínio a chamado de senso comum e é objeto de estudo de uma linha da computação, a Inteligência Artificial (IA). Para [KRA 87], entre outros, as soluc6es pare muitos problemas de IA dependern mais da capacidade de adquirir e manipular conhecimento do que de algoritmos sofisticados. Por este motivo, existem na IA muitos tipos de linguagens que tentam, de di verses maneiras,facilitar a representação de conhecirnentos sobre universos de discurso de problemas particulares. São as chamadas Linguagens de Representação de Conhecimento. A noção de tipo e implícita nas linguagens de representação de conhecimento, uma vez que tal noção é natural no raciocínio humano e esta intimamente ligada ao conceito de abstração. Este trabalho visa explicitar a noção de tipo subjacente ao núcleo definido da linguagem RECON-II. Para isto, foi realizado um estudo semântico prévio para identificar os tipos semânticos da linguagem. A partir da noção semântica dos tipos foi possível definir a correspondente sintática e finalmente, descrever um Sistema de Tipos para RECON-II. Um Sistema de Tipos consiste numa Linguagem de Tipos (tipos básicos + construtores de tipos) e num Sistema de Dedução que relaciona as expresses da linguagem objeto (linguagem de programação com as expresses da linguagem de tipos. Para a primeira etapa realizada neste trabalho, a determinação da semântica da linguagem, foi utilizado o método algébrico. Nele toda expressão RECON-II é um termo de uma assinatura Z, de modo quo cada assinatura Z determina um conjunto de expressos RECON-UL Mas, por outro lado, uma assinatura também determina um conjunto de álgebras. Dessas álgebras-Z só um subconjunto significativo para as expressões RECON-II. As álgebras-Z significativas são aquelas que satisfazem a assinatura-Z mais um conjunto E de axiomas. A assinatura-Z junto como o conjunto E de axiomas constituem o quo se denomina Tipo Abstrato de Dados, T=CZ, E), e as álgebras-Z significativas são os chamados modelos-Z do tipo T. Assim, uma expressão RECON-II a e um elemento da álgebra de termos quo g uma Álgebra gerada a partir do E. Essa álgebra, 44 4-) conjunto das expressi5es_: RECON-II significativas, e o modelo inicial de tais expressões WOG 781 Dado um tipo abstrato T existe um único modelo para T, ou uma classe de modelos, não isomórficos, denominada MCT>. No segundo caso, asses modelos constituem uma "quasi" ordem parcial com modelo inicial e terminal. A existência e unicidade do modelo inicial para qualquer tipo T foi demonstrada por [GOG 77] Com Σ = (S, F). a (Ws )para 9 S, e o conjunto dos termos de "sort." e. Na RECON-II, são os termos de uma categoria sintática determinada. As categorias sintáticas principais são : Conceitos, Relações, Funções e Redes. Um tipo semântico para s E S é um subconjunto M(T) S M(T) quo satisfaz os axiomas E exigidos de (WΣ) s, constituindo o tipo abstrato T .s.(por exemplo TConceitos, TRedes, etc.) Por último foi definido o Sistema de Tipos, que consiste numa estrutura sintática adequada para os tipos semânticos de cada expressão-RECON e, para cada expressão de tipo, um conjunto de regras de inferências que permuta, a partir de uma expressão-RECON inferir seu tipo mais geral. / The notion of type is intrinsic to human reasoning, since human beings tend to classify objects according their use and behaviour as part of the problem solving process. By classifying objects, their irrevelant characteristics are abstrated; in this way, the complexity of the universe of discourse is much reduced. On the other hand, certain problems are higly complex and require a differentiated treatament. In order to solve these problems, a great knowledge of de universe of discourse is needed. The critical proint in this situation is that the domain of the problem isn't as precise as a matliematic domain. On the contrary, it generally, includes ambiguous and not very formal aspects wich make its uderstanding difficult.. Such a domains is known as common sense and this is the object of studies of one line of Computer Science, Artificial Intelligence CAI). For [KRA 871, among others, the solutions for many AI problems depend on the ability for acquiring and manipulating knowledge rather than on sophisticated algorithm. For this reason, there are in AI many type of languages that attemps in different ways, to represent the UD of a particular problem. These languagesare known as Knowledge Representation Languages. The notion of type is implicit in Knowledge Representation Languages, since it is natural in human reasoning and closely rrelated to the concept of abstraction. This work intends to make the notion of type intrinsic to the RECON-II's kernel language, explicity. In order to do this, a preliminary semantic stidy was carriedaut to identify the semantic types of the languages. From the semantic notion of the types it was possible to define the sintactic counterpart and finally to describe a Type System for RECON- II. A Type System conssit of a type language (basic types + types constructors) end a deduction system that relattes expressions in the language object (programming language) to the expressions in the type language. In the first step of this work, language semantic determination, the algebric method was used. In it every RECON-II expression is one term of a signature 2, so Chet every signature 2 determines a RECON-II expressions set. On the other hand, a signature also determines a set of algebras. Out of these 2-algebras only one subset is significant to the RECON-II expressions. The significant 2-algebras are those t.het satisfy the 2-signature and a' set E of axioms. Together the 2-siganture and the set E of axioms, constitute what is called Abstract Data Type T = (2, E) and the significant E-algebras are the so-called Z-models of type T. Therefore a RECON-II expressions a is an element, of the wich is an algebra generated from E. This 2- 211)1`.9 is the set. of Sl !.171-11. RECON-II expressions, and is the initia; model of such expressions CLOG 78]. Given an abstract type T there is one single model for T or one class of nonisomorphic models denominated M(T). In the second cas,4, these models constitute a "quasi" partial order with an initial and terminal model. the exixstence nad uniqueness of the inititia1 model for any type T was shown at. CLOG 773. With r = <SS, F ) , (W ) for s S. is the set of terms of e sort. In RECON-II, those are •he term of determinate sintactic category. The main -sintactic categories are Concepts, Relations, Functions and Nets. A semantic type for s E S is s subset MCI') S MCT> that satisfies the axioms E required from C.W_), constituting the 8 2- abstract type T (for instance Tconcepts, Tnets, etc.). 8 Finally, the type systems was defined, consisting a syntatic structure suitable for the semantic types of each RECON-II expressions and for every type expressions, a set of inference rules wich allows infering its more general type from a RECON-II expressions.

La modularité est un enjeu important en programmation, surtout quand on l’enrichit avec des preuves, comme dans les langages avec des types dépendants. Typer est un tel langage, et afin d’augmenter sa modularité et de lui ajouter un moyen de faire la surcharge d’opérateurs, on s’inspire d’Agda et Coq et on l’étend avec les arguments instances, qui généralisent les classes de types de Haskell. Un aspect qui distingue notre conception est que comme Typer généralise les définitions, la généralisation des contraintes de classe est grandement facilitée. Pour pouvoir faire les preuves de lois de classes, on doit également ajouter l’élimination dépendante des types inductifs au langage, dont certains aspects sont en retour facilités par les arguments instances. Sur la base de ces deux fonctionnalités, on offre également une solution au problème de la cécité booléenne, tel que décrit par Harper. / Modularity is an important concern for software development, especially when the latter is enriched with proofs in a language with dependent types. Typer is such a language, and in order to increase its modularity, and also provide a way to overload operators, we take inspiration from Agda and Coq and extend it with instance arguments, a generalization of Haskell’s type classes. An aspect that sets our design apart is that since Typer generalizes definitions, it greatly simplifies the generalization of class constraints. In order to allow writing proofs for class laws, we must also implement the dependent elimination of inductive types. In return, instance arguments facilitate some details of dependent elimination. Using both features, we suggest a solution to the problem of Boolean Blindness.

Higher-order recursion schemes are systems of equations that are used to define finite and infinite labelled trees. Since, as Ong has shown, the trees defined have a decidable monadic second order theory, recursion schemes have drawn the attention of research in program verification, where they sit naturally as a higher-order, functional analogue of Boolean programs. Driven by applications, fragments have been studied, algorithms developed and extensions proposed; the emerging theme is called higher-order model checking. Kobayashi has pioneered an approach to higher-order model checking using intersection types, from which many recent advances have followed. The key is a characterisation of model checking as a problem of intersection type assignment. This dissertation contributes to both the theory and practice of the intersection type approach. A new, fixed-parameter polynomial-time decision procedure is described for the alternating trivial automaton fragment of higher-order model checking. The algorithm uses a novel, type-directed form of abstraction refinement, in which behaviours of the scheme are distinguished according to the intersection types that they inhabit. Furthermore, by using types to reason about acceptance and rejection simultaneously, the algorithm is able to converge on a solution from two sides. An implementation, Preface, and an extensive body of evidence demonstrate empirically that the algorithm scales well to schemes of several thousand rules. A comparison with other tools on benchmarks derived from current practice and the related literature puts it well beyond the state-of-the-art. A generalisation of the intersection type approach is presented in which higher-order model checking is seen as an instance of exact abstract interpretation. Intersection type assignment is used to characterise a general class of safety checking problems, defined independently of any particular representation (such as automata) for a class of recursion schemes built over arbitrary constants. Decidability of any problem in the class is an immediate corollary. Moreover, the work looks beyond whole-program verification, the traditional territory of model checking, by giving a natural treatment of higher-type properties, which are sets of functions.

This study aims to evaluate a Scandinavian approach to outdoor learning, which is used in the UK. The approach, known as ‘Forest School’ involves children and young people spending regular time in natural woodland working on practical projects. Forest School promotes a child-led ethos, so children are encouraged to choose their own activities (Forest School Association, 2013). A Realist Synthesis (Pawson, 2006) was undertaken to develop an understanding of how Forest School works, according to existing research. Features of the context, change mechanisms and outcomes were abstracted to form a set of hypotheses. In line with a Realistic Evaluation (Pawson and Tilley, 1997), these hypotheses were tested through a case study of Forest School involving 14-16 year old pupils with special educational needs (SEN). Drawing on interview, observation, questionnaire and documentary evidence, the initial programme specification was refined through thematic analysis (Braun and Clarke, 2006) to create programme specification 2. Participants checked this in a Realist Interview (Pawson and Tilley, 1997) and a final programme specification was produced. The final programme specification presents findings through context + mechanism = outcome configurations. The study extends existing research by finding that Forest School can support confidence, social skills, language and communication, motivation and concentration, physical skills, knowledge and understanding of the world and emotional well-being and behaviour in young people aged 14-16 with SEN. The study further indicates that Forest School works differently for different pupils, depending on their individual characteristics. Strategies for best practice were illuminated which may be useful to other Forest School practitioners, such as a high level of adult practical skills. The evaluation has implications for professionals working with young people as it highlights how Forest School can promote positive outcomes for some young people aged 14-16 with SEN.

The aims of this dissertation study are 1) to examine how the interplay of motivation, artifacts, and task interconnectedness affect users' flow experience, 2) to understand users' multitasking patterns by analyzing approaches and strategies in multitasking environments through a participatory design session, and 3) to come up with design insights and implications for desired multitasking environments based on findings from the quantitative and qualitative data analysis and synthesis. This dissertation employed the PAT (Person-Artifact-Task) model to examine factors that affect users' flow experience in computer-mediated multitasking environments. Particularly, this study focused on users' flow experience - sense of control, focused attention, curiosity, intrinsic interest and interactivity - in the context of multitasking. The dissertation begins with perspectives on human multitasking research from various disciplines. Emphasis is placed on how researchers have defined the term multitasking and the scope of previous multitasking research. In addition, this study provides definitions of the term task switching, which also has been used to describe human multitasking. The second section of this dissertation focuses on the literature, which characterizes factors and theoretical frameworks of human multitasking research. In this section, human multitasking factors were classified into internal and external factors to analyze factors from the micro to the macro perspective. More detailed definitions and comparisons are also addressed. To summarize and conclude the literature review, this study provides a synthesis framework of internal and external factors of human multitasking contexts. In section III, this dissertation introduces theoretical frameworks that include the constructs of the PAT (Person-Artifact-Task) model and flow model. The next three sections present the research design and two research methods - the experiment and participatory design. The results and discussion section includes the implications of interpreting people's flow experience with motivation, artifact (technology affordance type), and task interconnectedness through the PAT model. The study findings and implications should extend our understanding of multitasking behaviors and contexts and how the interplay of person, artifact, and task factors affects humans' flow experience. A concluding chapter explores future work and design implications on how researchers and designers can take contextual factors into consideration to identify the most effective multitasking in computer-mediated environments. / text

The research in this thesis explores Citizenship Education pedagogy at secondary school level in Ontario, Canada. Citizenship Education is a complex subject area and its teaching and learning within the classroom is contentious. The literature indicates the value of student voice and technology; however the ways in which these pedagogical tools can be incorporated into the Citizenship Education classroom have not been explored in great detail. This study uses a Practitioner Inquiry approach within an Action Research model to investigate the research question; how can student voice and technology be used in the engagement of students within the subject area of Citizenship Education in the classroom. The methods developed and used to collect the data for the study served a dual purpose of engaging and empowering the participants within the research and were based on the ethical considerations of researching with young people. The thesis uses an adapted interpretive ecological framework for the conceptualization, interpretation, and analysis of the findings from the study. It provides a rich and detailed description of the context, processes, and considerations that are involved in incorporating student voice and technology within the Citizenship Education classroom through the Action Research design. The results show that student voice and technology can be used pedagogically to help young people construct their own meanings of citizenship and a Critical Citizenship Education framework was developed to support adoption of these approaches more widely. Future directions for research into the use of innovative approaches to the teaching and learning of Citizenship Education in the classroom are considered.

This thesis investigates the influence of regional culture on young people's decision making when considering post-sixteen educational choices and directions from school. The data is provided by life story interviews with young people - aged eighteen to twenty years, 'born and bred' in Lincolnshire - who have followed four pathways from compulsory education. Within the context of Lincolnshire the influence of rurality is a major element of regional culture and figures in much of the discussion and analysis. The work of Pierre Bourdieu in defining culture through field and habitus is used as a theoretical perspective in the data analysis and conclusions. The research highlights the continued importance of family and community habitus in the decision-making processes of young people. The interviews are used to consider the relative field positions important in defining individuals' post-sixteen pathways. The nature of rurality as a social construct rather than simply a reflection of physical geography is discussed and conclusions offered as to its possible effect on preferred post-sixteen pathways. The relative importance given to physical and social characteristics of rurality is used to construct a series of cultural indicators for rural communities. The data would support the conclusion that new initiatives designed to increase participation rates in post-sixteen education are having some effect, but only among those young people predisposed through family habitus to continuing education. Those young people whose family habitus most closely coincides with pedagogic authority are most likely to operate comfortably within the educational habitus and hence continue with formal education beyond sixteen. The thesis suggests the real differences in habitus between urban and rural communities requires a shift in the policy debate if rural people are to participate fully in the notion of lifelong learning. NB. This ethesis has been created by scanning the typescript original and contains some inaccuracies. In case of difficulty, please refer to the original text.

Even though information scientists generally recognize that relevance judgments are multidimensional and dynamic, there is still discussion and debate regarding the degree to which certain internal (cognition, personality) and external (situation, social relationships) factors affect the use of criteria in reaching those judgments. Much of the debate centers on the relationship of those factors to the criteria and reliable methods for measuring those relationships. This study researched the use of relevance criteria to select an information source by undergraduate students whose task it is to create a course schedule for a semester. During registration periods, when creating their semester schedules, students filled out a two-part questionnaire. After completion of the questionnaire the students completed a Myers-Briggs Type Indicator instrument in order to determine their personality type. Data was analyzed using one-way ANOVAS and Chi-Square. A positive correlation exists between personality type as expressed by the MBTI and the information source selected as most important by the subject. A correlation also exists between personality type and relevance criteria use. The correlation is stronger for some criteria than for others. Therefore, one can expect personality type to have an effect on the use of relevance criteria while selecting information sources.

Mémoire numérisé par la Direction des bibliothèques de l'Université de Montréal.