abstract: In this thesis, we consider the problem of fast and efficient indexing techniques for time sequences which evolve on manifold-valued spaces. Using manifolds is a convenient way to work with complex features that often do not live in Euclidean spaces. However, computing standard notions of geodesic distance, mean etc. can get very involved due to the underlying non-linearity associated with the space. As a result a complex task such as manifold sequence matching would require very large number of computations making it hard to use in practice. We believe that one can device smart approximation algorithms for several classes of such problems which take into account the geometry of the manifold and maintain the favorable properties of the exact approach. This problem has several applications in areas of human activity discovery and recognition, where several features and representations are naturally studied in a non-Euclidean setting. We propose a novel solution to the problem of indexing manifold-valued sequences by proposing an intrinsic approach to map sequences to a symbolic representation. This is shown to enable the deployment of fast and accurate algorithms for activity recognition, motif discovery, and anomaly detection. Toward this end, we present generalizations of key concepts of piece-wise aggregation and symbolic approximation for the case of non-Euclidean manifolds. Experiments show that one can replace expensive geodesic computations with much faster symbolic computations with little loss of accuracy in activity recognition and discovery applications. The proposed methods are ideally suited for real-time systems and resource constrained scenarios. / Dissertation/Thesis / M.S. Electrical Engineering 2012

Orientador: Edson do Carmo Inforsato / Banca: Edilson Moreira de Oliveira / Banca: Leda Rodrigues de Assis Favetta / Banca: Maria Guiomar Tomazello / Banca: Maria Cristina de Senzi Zancul / Resumo: A humanidade vive hoje uma crise ambiental sem precedentes. Fundamentado na teoria da complexidade, esse trabalho apresenta a crise - Krísis (termo grego que significa decisão) como um momento no qual decisão e incerteza são interdependentes. Apresenta a Educação Ambiental como um saber para superar a crise, e como uma reflexão possível para a construção de um saber ambiental consistente na formação dos professores de Biologia. Um saber que, entre outras coisas, possa assentar a educação e a sociedade sobre novas bases epistemológicas, impulsionando novos pontos de vistas e estratégias na convergência educação e ambiente. A partir desses pressupostos teóricos esse trabalho procurou identificar as ideias dos professores de Biologia do município de Piracicaba e dos alunos concluintes de um Curso de Ciências Biológicas do município sobre educação ambiental e entender como a universidade contribui para formação desses professores em relação à essa temática. Os resultados indicam que o professor de Biologia ainda necessita de uma formação mais crítica em relação à educação ambiental, e que, numa perspectiva complexa, essa formação necessita ser tratada de forma mais rigorosa no Curso de Biologia pesquisado para que os profissionais formados possam atuar efetivamente na formação cidadã para uma sociedade mais sustentável. / Abstract: The Humanity lives today an unprecedented environmental crisis. Based on complexity theory, this paper presents the crisis - Kris (Greek term that means the decision) as a time when the decision and uncertainty are interdependent. The paper presents an environmental education as knowledge to overcome the crisis, and as a possible reflection to build a consistent environmental knowledge in the biology teachers training. That knowledge, among other things, can be based on new epistemological bases of education and society, triggering new views and strategies in the convergence of education and environment. From these theoretical presuppositions that thesis sought to identify the biology teachers and graduating Biological Sciences students ideas, in Piracicaba, about an environmental education and understand how the university contributes to teachers training related to this theme. The results indicate that the biology teacher still needs critical training of the environmental education, and that in a complex perspective, this training needs to be treated stricter in the researched Biology Course, just like that trained professionals can effectively work in civic education in order to have a more sustainable society. / Doutor

Systems chemistry aims at studying and developing "smart" materials displaying reactivity to external stimuli, metabolism, self-repair abilities and self-replication properties. These features constitute the principal characteristics of living systems that smart materials tend to mimic. The synthesis strategies of these materials are still in their infancy, and identifying the mechanisms underlying emergent phenomena could lead to a better control and use of these behaviours in the synthesis of new materials. The complex dynamics of biological systems usually arises from the coupling of compartmentalised units in which nonlinear chemical reactions take place. In this thesis, we are interested in the complex dynamics emerging from such compartmentalisation of a reactive system. First, we analyse the impact of fluctuations of concentration on the dynamics of a chemical oscillatory reaction, namely the Belousov-Zhabotinsky reaction. We show that oscillations are more robust against fluctuations than other behaviours generated by the reaction (birhythmicity, chaos, ) and highlight different mechanisms by which oscillations can arise from fluctuations. Then, we study a model for chemical chaos, the so-called Willamowsky-Rössler model, in which we incorporate fluctuations and crowding effects. Fluctuations have a destructive effect on chaotic dynamics but when the reaction takes place on a surface where the different species can diffuse and react, a synergy develops between fluctuations, crowding effects and the mobility of the particles. This synergy enhances the re-emergence of chaos and the development of new behaviours. Finally, we show throughout different modelling approaches that compartmentalisation effects play a central role in the intracellular calcium dynamics and emphasise how microscopic properties of the system shape the global behaviour of this system. Compartmentalised nonlinear dynamics thus offer a wide range of future prospects for the synthesis of smart materials and fosters the development of nanoreactors based on these properties. / Doctorat en Sciences / info:eu-repo/semantics/nonPublished

IoT is a rapidly growing area with products in the consumer, commercial and industrial market. Collecting data with multiple small and often battery-powered devices sets new challenges for both security and communication. There has been a distinct lack of a IoT specific communication protocols. The industry has had to use bulky interfaces not suitable for resource-constrained devices. MQTT is a standardised communication protocol made for the IoT industry. MQTT does however not have built-in security and it is up to the developers to implement a suitable security countermeasure. To evaluate how different security countermeasures impact MQTT in complexity, current consumption and security the following research questions are answered. How do you derive a measurement from the SEF that can be compared with a current consumption measurement? Which level of security, according to the SEF, will RSA, AES and TLS provide to MQTT when publishing a message to a broker? What level of complexity is added to MQTT when using chosen security countermeasure? Which of the analysed security countermeasure upholds an adequate security level while also having a low current consumption? To answer the above research questions an experiment approach has been used. Implementations of TLS, RSA and AES have been evaluated to measure how they affect the security level and current consumption of an MQTT publication, compared to no security countermeasures at all.Both RSA and AES had the same security level, but the current consumption for RSA was four times higher. The experiment showed that the security level is significantly higher for TLS, while it also has the highest current consumption. The security countermeasure evaluated differs greatly. TLS provides complete protections, while RSA and AES lacks authentication and does not ensure integrity and non-repudiation.Even if the current consumption for TLS is higher, the security it provides make it unreasonable to recommend any of the other security countermeasure implementations.

In the essay Unit Manager´s daily study of relationships in municipal elderly care, my purpose is to investigate how unit managers in elderly care have interpreted their assignments based on the organizational framework politics, organizations, employees, care recipents and relatives. Previous research shows that unit managers as intermediaries has a complex mission. The intermediary lives between various interests, which constitutes the complexity of the profession as unit manager. That is to say, different demands are made on unit managers, where the organization from above sets requirements such as efficiency and results and down the organizations requires confirmation and understanding. To answer my question How do eight unit managers in elderly care understand their mission based on the organizational framework I saw the most relevant use of interview as a relevant method. My purpose and question was based on social interaction where qualitative research is an appropriate method of using when you cannot measure social interaction with numbers. To analyze my material, I use Erving Goffman`s theory that the individual includes many different roles that are part of our inner self. The theoretical concepts I use are role, facade and expressivity. The result of my study shows that the unit managers committment contains care recipents, staff, financial responsibility and to lead and distribute employees. Politics feels close but still far away for the unit managers where the current political plan governs. The unit managers need support from the organization. The assignment includes work with motivating employees which includes questions related to relations and communication. Relationship to employees is of great importance. Unit managers responsibility for the care recipents and employees deals with handling and to cope situations where both care recipents participate and are being listened to

Three archaeological cases from different areas of the Andes are employed to study the rise of social and cultural complexity in varying social and economic contexts, with the intention of distinguishing certain environmental and cultural factors in each case. The purpose also is to search not only for differences but for commonalities to be used for cross-cultural comparisons and to learn more about the developmental cultural history of the societies representing these cases. / En el presente trabajo se analizan tres casos de diferentes áreas de los Andes para estudiar el incremento de la complejidad cultural en contextos sociales y económicos variados con el fin de distinguir factores definidos de carácter ambiental y cultural en cada caso. El propósito final es el de la búsqueda de diferencias, así como de las características en común que se utilizan para hacer comparaciones culturales y para aprender más acerca de la historia del desarrollo cultural de las sociedades que representan estos ejemplos.

Shingled Magnetic Recording (SMR) technology is important in the immediate need for expansion of magnetic hard disk beyond the limit of current disk technology. SMR provides a solution with the least change from current technology among contending technologies. Robust easy to implement Digital Signal Processing (DSP) techniques are needed to achieve the potentials of SMR. Current DSP techniques proposed border on the usage of Two Dimensional Magnetic Recording (TDMR) techniques in equalisation and detection, coupled with iterative error correction codes such as Low Density Parity Check (LDPC). Currently, Maximum Likelihood (ML) algorithms are normally used in TDMR detection. The shortcomings of the ML detections used is the exponential complexities with respect to the number of bits. Because of that, reducing the complexity of the processes in SMR Media is very important in order to actualise the deployment of this technology to personal computers in the near future. This research investigated means of reducing the complexities of equalisation and detection techniques. Linear equalisers were found to be adequate for low density situations. Combining ML detector across-track with linear equaliser along-track was found to provide low complexity, better performing alternative as compared to use of linear equaliser across track with ML along track. This is achieved if density is relaxed along track and compressed more across track. A gain of up to 10dB was achieved. In a situation with high density in both dimensions, full two dimensional (2D) detectors provide better performance. Low complexity full 2D detector was formed by serially concatenating two ML detectors, one for each direction, instead of single 2D ML detector used in other literature. This reduces complexity with respect to side interference from exponential to linear. The use of a single bit parity as run length limited code at the same time error correction code is also presented with a small gain of about 1dB at BER of 10^-5 recorded for the situation of high density.

Les décompositions de graphes, lorsqu’elles sont de petite largeur, sont souvent utilisées pour résoudre plus efficacement des problèmes étant difficiles dans le cas de graphes quelconques. Dans ce travail de thèse, nous nous intéressons aux limites liées à ces décompositions, et à la construction d’obstructions certifiant leur grande largeur. Dans une première partie, nous donnons un algorithme généralisant et unifiant la construction d’obstructions pour différentes largeurs de graphes, en temps XP lorsque paramétré par la largeur considérée. Nous obtenons en particulier le premier algorithme permettant de construire efficacement une obstruction à la largeur arborescente en temps O(ntw+4). La seconde partie de notre travail porte sur l’étude du problème ENSEMBLE [σ, ρ]-DOMINANT, une généralisation des problèmes de domination sur les graphes et caractérisée par deux ensembles d’entiers σ et ρ. Les diverses études de ce problème apparaissant dans la littérature concernent uniquement les cas ou le problème est FPT, lorsque paramétré par la largeur arborescente. Nous montrons que ce problème ne l’est pas toujours, et que pour certains cas d’ensembles σ et ρ, il devient W[1]-difficile lorsque paramétré par la largeur arborescente. Dans la dernière partie, nous étudions la complexité d’un nouveau problème de coloration appelé k-COLORATION ADDITIVE, combinant théorie des graphes et théorie des nombres. Nous montrons que ce nouveau problème est NP-complet pour tout k ≥ 4 fixé, tandis qu’il peut être résolu en temps polynomial sur les arbres pour k quelconque et non fixé. / Graphs decompositions of small width are usually used to solve efficiently problems which are difficult in general. In this thesis, we focus on some limits of these decompositions, and the construction of some obstructions certifying a large width. First, we give a generic algorithm unifying obstructions’ construction for several graph widths, in XP time when parameterized by the considered width. In particular, it gives the first algorithm computing efficiently an obstruction to tree-width in time O(ntw+4). Secondly, we study the parameterized complexity of [σ, ρ]-DOMINATING SET, a generalization of some domination problems characterized by two sets of integers σ and ρ. All known studies focused only on cases where this problem is FPT when parameterized by tree-width. In this work, we show that there are some cases where the problem is no longer FPT, and become W[1]-hard instead. Finally, we study the computational complexity of a new coloration problem, named k-ADDITIVE COLORING, which combines both graph theory and number theory. We show that this new problem is NP-complete for any fixed number k ≥ 4, while it can be solved in polynomial time on trees for any k.

Esta dissertação utiliza simulações computacionais visando investigar a influência de alguns fatores lingüísticos na organização lexical de verbos, analisando os processos de aquisição e uso. Os fatores testados são: freqüência de observação na linguagem, polissemia e complexidade sintática. Os dados utilizados foram obtidos por meio de tarefas psicolingüísticas de nomeação de ações, realizadas por crianças e adultos (falantes do Português brasileiro), posteriormente representados como grafos. Com base nos fatores lingüísticos, foram formuladas hipóteses relativas ao desenvolvimento da língua, testadas por meio de simulações computacionais denominadas ‘involuções’. Os testes incluem métricas da teoria dos grafos e medidas de similaridade de conjuntos (coeficiente de Jaccard e suas componentes). Os resultados obtidos apontam para uma confirmação das hipóteses formuladas. Adicionalmente, permitiram verificar algumas características do desenvolvimento lingüístico, como o aumento do vocabulário e uma progressiva especialização. / This dissertation uses computational simulations designed to investigate the influence of three linguistic factors in the lexical organization of verbs, analyzing the process of acquisition and use. The tested factors are: frequency of observation in the language, polysemy and syntactic complexity. The data used were obtained from psycholinguistic action naming tasks performed by children and adults (speakers of Brazilian Portuguese), and subsequently represented as graphs. Based on linguistic factors, hypotheses were formulated concerning the development of language, tested through simulations called ‘involutions’. Tests include graph theory metrics and set similarity measures (Jaccard’s coefficient and its components). Results suggest a confirmation of the given hypotheses. Additionally, allowed verification of some language development features, such as vocabulary growth and a progressive specialization.

Dois temas são característicos do contexto atual das organizações. Um, já consolidado, é o aumento da velocidade das inovações; o outro, é a necessidade de incorporar a perspectiva emergente da sustentabilidade nas práticas de inovação. A Teoria Neoschumpeteriana busca obter um domínio desses fenômenos dinâmicos da realidade econômica, em que a inovação, principalmente a tecnológica, é identificada como a força maior que propulsiona a dinâmica econômica. Entretanto, Hanusch e Pyka (2007) criticam a Teoria Neoschumpeteriana por entenderem que o desenvolvimento dos sistemas econômicos modernos incorpora a inovação tecnológica, assim como também a inovação organizacional, institucional e social e, por isso, os novos frameworks para estudos de sistemas econômicos, precisariam incorporar características de complexidade através do trânsito em diferentes teorias relevantes, levando em conta as raízes da Teoria Neoschumpeteriana, o que eles próprios não fazem. Assim, o objetivo geral de pesquisa foi o de propor um framework interteórico e complexo sobre a dinâmica da inovação e fazer a sua aplicação no Instituto Rio-Grandense do Arroz - IRGA. A metodologia utilizada foi de estudo de caso. Os dados foram coletados através de entrevistas e documentos. Cada uma das etapas realizadas na metodologia foi apoiada num estudo, a priori, sobre métodos que capturavam características de complexidade. A utilização de uma lógica abdutiva, prevista na metodologia, com constantes idas e vindas entre os conceitos teóricos construídos a priori e as informações advindas do campo empírico, fez emergir o conceito teórico de sistema econômico, como uma configuração complexa de múltiplos níveis de regras que se relacionam ao longo do tempo e se sucedem. Neste sentido, a presente pesquisa avançou ao identificar a emergência de regras, oriunda das teorias usadas, como uma qualidade nova e central, que em múltiplos níveis, compõe as configurações, que evoluem ao longo do tempo. Este avanço possibilitou estudar a história econômica do IRGA, não da perspectiva operacional, mas da perspectiva das regras genéricas, de maior nível, e das regras de menor nível associadas à regra genérica, numa perspectiva de configurações dinâmicas que evoluem, focado em inovações. A lógica abdutiva possibilitou avanços metodológicos na aplicação do método de análise qualitativa comparativa (QCA) no estudo das dinâmicas de configurações, já que o método tinha até então, sido aplicado numa abordagem estática. Os resultados indicaram, ainda, a presença de cinco regras genéricas no contexto de pesquisa do IRGA. O IRGA inseriu predominantemente, em suas atividades, de pesquisa a regra genérica de mais produtividade agrícola. As regras genéricas de gestão ambiental da propriedade agrícola, aumento do consumo do arroz, aumento da renda para o produtor foram inseridas nas atividades de pesquisa de modo marginal. A regra genérica denominada de negócios ambientais nas beneficiadoras de arroz ainda não foi inserida nas atividades de pesquisa do IRGA. A dinâmica de inserção destas regras genéricas no IRGA ocorre através de oito configurações de regras de nível zero e de segunda ordem, que seguem um conjunto de fases que foram denominadas de pré-distúrbio, origem, adoção, retenção e declínio. Uma característica nesta dinâmica é de que somente ocorreu a mudança de fase da regra genérica quando determinadas regras de segundo e de ordem zero estavam presentes. Como as fases de evolução das regras genéricas ocorreram em diferentes anos, no período entre 1969 e 2009, a combinação destas fases gerou seis configurações temporais de regras para inovação no IRGA. / Two themes are characteristic of the organizations on the current context. One is already established that is the increasing innovations speed. The other one is the need to incorporate the sustainability‘s emerging perspective in innovation practices. The Neo-Schumpeterian Theory seeks to obtain a domain on these dynamic phenomena of the economic reality, in which the innovation, especially technological, is identified as its greater propellent force. However, Hanusch and Pyka (2007) criticize the Neo-Schumpeterian Theory for understanding that the development of modern economic systems incorporate the technological innovation, as well as the organizational innovation, institutional, and social. Therefore, the new frameworks for the economic systems studies would need to incorporate some complexity features through traffic in different and relevant theories, taking into account the Neo-schumpeterian Theory roots, which they themselves do not do. Thus, the overall objective of this research was to propose an inter-theoretical and complex framework on the innovation dynamics and to make its application at the IRGA (Instituto Rio-Grandense de Arroz - Rice Institute of Rio Grande do Sul State, Brazil). We used the case study methodology. Data were collected by some interviews and from some documents. Each of the used methodology steps was supported in a priori study on methods that captured the complexity characteristics. The economic system‘s theoretical concept as a complex configuration of the multiple rules levels related over the time, and that succeed itself, came from an abductive logic use from the methodology, with constant goings and comings among the theoretical concepts a priori constructed, and from the empirical information from the field. In this sense, this research has advanced when identified the rules emergence, derived from the used theories as a new quality and centered, which at multiple levels composes the configurations that evolve over the time. This advance allowed the IRGA‘s economic history study, not from the operational perspective, but from the general rules perspectives of highest level and from the lowest level associated with the general rules perspectives, at a dynamic configurations perspective that evolve focusing on innovations. The abductive logic allowed the methodological advances in the method application of comparative and qualitative analysis (CQA) in the study of the configurations dynamics, since the method had until then been applied on a static approach. The results also indicated the presence of five generic rules in the context of the IRGA research. The IRGA inserted predominantly the general rule of most agricultural productivity in its research activities. The general rules of the farm environmental management, the increased rice consumption, and the increased income for producers have been included in the research activities marginally. The general rule of environmental affairs in the rice processing has not been incorporated into the IRGA research activities. The insertion dynamic of these general rules occurs through eight rules of level zero and second order configurations, which follow a stages set that were identified as pre-disturbance, origin, adoption, retention, and decay. A dynamic characteristic is that there was only a phase change of the general rule when certain rules of the second and zero order were present. As the phases of the generic rules development occurred in different years, from 1969 to 2009, these phases combination generated six rules temporal configurations for innovation in the IRGA.