208 research outputs found
Pratiques et compétences en éducation aux médias et à l’information
No full textInternational audienceCet article porte sur la question des pratiques et des compétences en éducation aux médias et à l’information. Trois auteures s’approprient et problématisent ces notions, complexifiées et précisées par l’usage des qualificatifs « médiatiques »,« informationnelles » ou « numériques », etobservées au croisement de la recherche et des activités courantes effectuées parles acteurs de l’EMI. Laëtitia Pierrot rend compte des processus sociaux par lesquels les pratiques numériques se construisent au sein de groupes sociaux. Elle considère les pratiques, médiatiques ou numériques, comme des actions instrumentées et socialisées et elle a procédé à l’analyse de traces numériques de lycéens pour en faire la démonstration. Camille Tilleul interroge les pratiques médiatiques dans les relations qu’elles entretiennent avec des compétences qu’elles sont dites évoquer ou développer. Elle s’intéresse à la diversité des pratiques médiatiques en tant que facteur de développement des compétences considérées constitutives de la littératie médiatique. Adeline Entraygues étudie la relation entre pratiques informationnelles juvéniles et culture de l’information. Pour ce faire, elle s’emploie à distinguer les pratiques prescrites des pratiques informelles effectuées par des personnes mineures sur les réseaux sociauxnumériques
2-Stack Sorting is polynomial
No full text23 pagesIn this article, we give a polynomial algorithm to decide whether a given permutation is sortable with two stacks in series. This is indeed a longstanding open problem which was first introduced by Knuth. He introduced the stack sorting problem as well as permutation patterns which arises naturally when characterizing permutations that can be sorted with one stack. When several stacks in series are considered, few results are known. There are two main different problems. The first one is the complexity of deciding if a permutation is sortable or not, the second one being the characterization and the enumeration of those sortable permutations. We hereby prove that the first problem lies in P by giving a polynomial algorithm to solve it. This article strongly relies on a previous article in which 2-stack pushall sorting is defined and studied
2-stack pushall sortable permutations
No full text41 pagesIn the 60's, Knuth introduced stack-sorting and serial compositions of stacks. In particular, one significant question arise out of the work of Knuth: how to decide efficiently if a given permutation is sortable with 2 stacks in series? Whether this problem is polynomial or NP-complete is still unanswered yet. In this article we introduce 2-stack pushall permutations which form a subclass of 2-stack sortable permutations and show that these two classes are closely related. Moreover, we give an optimal O(n^2) algorithm to decide if a given permutation of size n is 2-stack pushall sortable and describe all its sortings. This result is a step to the solve the general -stack sorting problem in polynomial time
Inventing Malayaness: Race, Education and Englishness in Colonial Malaya
No full text<p>Koh, Adeline. Inventing Malayanness: Race, Education and Englishness in Colonial Malaya. A thesis submitted in partial fulfillment of the requirements for a degree of Doctor of Philosophy (Comparative Literature). University of Michigan at Ann Arbor, 2008. DOI: http://dx.doi.org/10.6084/m9.figshare.754578</p>
<p>Description: This dissertation focuses on late nineteenth and twentieth century Orientalized representations of British Malaya in the work of Joseph Conrad, Somerset Maugham and Anthony Burgess. It argues that racial logics reflected within this Anglophone expatriate literature influenced colonial and postcolonial politics in Malaysia and Singapore.</p>
<p>COPYRIGHT:</p>
<p>Please note the file included on this site contains a version of this work which is licensed under a Creative Commons CC-BY-NC-ND license. This means that you are free:</p>
<p>- to copy, share and distribute the work</p>
<p>Under the following conditions</p>
<p>- Attribution — You must attribute the work in the manner specified by the author or licensor (but not in any way that suggests that they endorse you or your use of the work).</p>
<p>- Noncommercial — You may not use this work for commercial purposes.</p>
<p>- No Derivative Works — You may not alter, transform, or build upon this work.</p>
<p>Find out more about the license here: http://creativecommons.org/licenses/by-nc-nd/2.0/</p>
<p>More on the author here: www.adelinekoh.org</p
2-Stack Sorting is polynomial
No full text23 pagesIn this article, we give a polynomial algorithm to decide whether a given permutation is sortable with two stacks in series. This is indeed a longstanding open problem which was first introduced by Knuth. He introduced the stack sorting problem as well as permutation patterns which arises naturally when characterizing permutations that can be sorted with one stack. When several stacks in series are considered, few results are known. There are two main different problems. The first one is the complexity of deciding if a permutation is sortable or not, the second one being the characterization and the enumeration of those sortable permutations. We hereby prove that the first problem lies in P by giving a polynomial algorithm to solve it. This article strongly relies on a previous article in which 2-stack pushall sorting is defined and studied
Algorithmic and combinational results on permutation classes
No full textCette thèse porte sur l'étude des classes de permutations à motifs exclus. Une analyse combinatoire des permutations via leur décomposition par substitution permet d'obtenir des résultats algorithmiques. La première partie de la thèse étudie la structure des classes de permutations. Plus précisément on donne un algorithme pour calculer une spécification combinatoire pour une classe de permutations données par sa base de motifs exclus. La spécification est obtenue si et seulement si la classe contient un nombre fini de permutations simples, cette condition étant testée par l'algorithme lui-même. Cet algorithme puise sa source dans les travaux de Albert et Atkinson établissant qu'une classe ayant un nombre fini de permutations simples a une base finie et une série génératrice algébrique. Les méthodes développées utilisent la théorie des langages et des automates, les ensembles partiellement ordonnés, l'introduction de motifs obligatoires. La seconde partie de la thèse donne un algorithme polynomial décidant si une permutation donnée en entrée est triable par deux piles connectées en série. L'existence d'un algorithme polynomial résolvant cette question est un problème longtemps resté ouvert, que l'on clôt dans cette thèse en introduisant une nouvelle notion, le tri par sas, en utilisant un codage des procédures de tri par un bi-coloriage du diagramme des permutations. Puis on résout le problème général en montrant qu'une procédure de tri général correspond à plusieurs étapes de tri par sas.This work is dedicated to the study of pattern closed classes of permutations. Algorithmic results are obtained thanks to a combinatorial study of permutation classes through their substitution decomposition. The first part of the thesis focuses on the structure of permutation classes. More precisely, we give an algorithm which derives a combinatorial specification for a permutation class given by its basis of excluded patterns. The specification is obtained if and only if the class contains a finite number of simple permutations, this condition being tested algorithmically. This algorithm takes its root in the theorem of Albert and Atkinson stating that every permutation class containing a finite number of simple permutations has a finite basis and an algebraic generating function, and its developments by Brignall and al. The methods involved make use of languages and automata theory, partially ordered sets and mandatory patterns. The second part of the thesis gives a polynomial algorithm deciding whether a permutation given as input is sortable trough two stacks in series. The existence of a polynomial algorithm answering this question is a problem that stayed open for a long time, which is solved in this thesis by introducing a new notion, the pushall sorting, which is a restriction of the general stack sorting. We first solve the decision problem in the particular case of the pushall sorting, by encoding the sorting procedures through a bicoloring of the diagrams of the permutations. Then we solve the general base by showing that a sorting procedure in the general case corresponds to several steps of pushall sorting which have to be compatible.PARIS7-Bibliothèque centrale (751132105) / SudocSudocFranceF
Simple permutations poset
No full textThis article studies the poset of simple permutations with respect to the pattern involvement. We specify results on critically indecomposable posets obtained by Schmerl and Trotter in [11] to simple permutations and prove that if σ, π are two simple permutations such that π < σ then there exists a chain of simple permutations σ^(0) = σ, σ^(1) , . . . , σ^(k) = π such that |σ^(i) | − |σ^(i+1) | = 1 - or 2 when permutations are exceptional- and σ^(i+1) < σ^(i) . This characterization induces an algorithm polynomial in the size of the output to compute the simple permutations in a wreath-closed permutation class
A study on the effect of shopping centre layout design on shoppers behaviour / Dina Adeline L. Kading
No full textThis study focuses on the effect of shopping center layout design on shoppers' behaviour. The objectives of this project is to study on the detailed layout of shopping center, interiorly and exteriorly, to identify general information concerning shoppers behaviour whereby it can be interrelated to how do the layout affecting shoppers behaviour, and finally to observe and study about the shopping center layout design and to make sure how does it affect on local shoppers behaviour. Sources of the data and information are gathered by the author from literature review of previous researches, published articles and books, and supported by the opinions of shoppers through structured questionnaires. From the survey, analysis and findings, the author noted that majority shoppers are satisfied on both interior and exterior layout of the case study. Attractive shopping environment, appealing exterior features, effortless in finding the entrance, sufficient car parks, these are some of the reason that make shoppers happy with the shopping complex. It is hoped that this project could clearly explain the interior and exterior layout of a shopping complex that affect the shoppers' behaviour and given better understanding to other readers about detailed shopping center layout design
On dots in boxes, or Permutation pattern classes and regular languages
No full textThis thesis investigates permutation pattern classes in a language theoretic context. Specifically
we explored the regularity of sets of permutations under the rank encoding. We found that the
subsets of plus- and minus-(in)decomposable permutations of a regular pattern class under the
rank encoding are also regular languages under that encoding. Further we investigated the sets of
permutations, which in their block-decomposition have the same simple permutation, and again
we found that these sets of permutations are regular languages under the rank encoding. This
natural progression from plus- and minus-decomposable to simple decomposable permutations led
us further to the set of simple permutations under the rank encoding, which we have also shown
to be regular under the rank encoding. This regular language enables us to find the set of simple
permutations of any class, independent of whether the class is regular under the rank encoding.
Furthermore the regularity of the languages of some types of classes is discussed. Under the
rank encoding we show that in general the skew-sum of classes, separable classes and wreath classes
are not regular languages; but that the direct-sum of classes, and with some restrictions on the
cardinality of the input classes the skew-sum and wreath sum of classes in fact are regular under
this encoding.
Other encodings such as the insertion encoding and the geometric grid encoding are discussed
and in the case of the geometric grid encoding alternative and constructive ways of retrieving the
basis of a geometric grid class are suggested.
The aforementioned results of the rank encoding have been implemented, amongst other previously
shown results, and tested. The program is available and accessible to everyone. We show
that the implementation for finding the block-decomposition of a permutation has cubic time complexity
with respect to the length of the permutation. The code for constructing the automaton
that accepts the language of all plus-indecomposable permutations of a regular class under the
rank encoding has quadratic time complexity with respect to the alphabet of the language. The
procedure to find the automaton that accepts the language of minus-decomposable permutations
has complexity O(k⁵) and we show that the implementation of the automaton to find the language
of simple permutations under the rank encoding has time complexity O(k⁵ 2ᵏ), where k is the size
of the alphabet. Further we show benchmark testing on previous important results involving the
rank encoding on classes and their bases
- …
