A homomorphism from a graph G to a graph H is a function from V (G) to V (H) that preserves edges. Many combinatorial structures that arise in mathematics and in computer science can be represented naturally as graph homomorphisms and as weighted sums of graph homomorphisms. In this thesis we study the complexity of various problems related to graph homomorphisms.

Atualmente, a Energia com valor econômico, tecnológico, social e ambiental, tem sido abordada de forma essencialmente reducionista. Ou seja, separando-a de seu contexto, subdividindo-a em partes e isolando cada uma destas. Separaram-se as demandas econômicas das demandas da natureza, disto decorreram diversos problemas ambientais. A abordagem reducionista ultrapassa o domínio energético e afeta a sociedade moderna de forma geral. No começo do século XX, o pensamento científico reducionista começou a ruir com diversas descobertas ocorridas, em especial, as da Física Moderna e emergiu com grande força um novo paradigma. Chamado de sistêmico ou complexo, este paradigma surge não apenas por questões teóricas, mas, sobretudo, por questões práticas. Este trabalho tratará de examinar a questão da Energia de um enfoque complexo. Assim, será mostrada uma nova abordagem para as interações da Energia com a Biosfera, a esfera social e a esfera econômica. Assim é possível avaliar melhor as questões tecnológicas, econômicas, sociais, ambientais e políticas. A transmissão desse novo paradigma se daria, em boa parte, através da Educação. No trabalho se dará um exemplo aplicado a uma disciplina de graduação do ciclo básico do curso de Engenharia Elétrica da Escola Politécnica da Universidade de São Paulo: PEA 2200 - Energia, Meio Ambiente e Sustentabilidade. / Currently, the Energy, with economic, technological, social and environmental value, has been studied through an essentially reductionist form. In other words, separating it from its context, subdividing it into parts and isolating each one of them. The economic demands were separated from the demands of nature, and from this environmental problems have elapsed. The reductionist approach overcomes the energetic domain and affects the modern society in general. In the beginning of the XX century, the reductionist scientific thought started to collapse mainly with the discoveries of Modern Physics and a new paradigm emerged with great force. Called systemic or complex, this paradigm is born not just because of theoretical aspects but, above all, because of practical aspects. This work examines the aspect of Energy in a complex approach. With this, a new approach for the interactions of Energy with the biosphere, the social sphere and the economical sphere, will be shown. With this it is possible to evaluate the technological, economical and political aspects better. The new paradigm can be transmitted, mainly, through Education. The following study applies this new concept in one of the basic subjects in the Electrical Engineering course of the Escola Politécnica da Universidade de São Paulo: PEA 2200 - Energy, Environment and Sustainability.

A educação ambiental vem sendo disseminada por grande parte das escolas do país, conforme atestam pesquisas oficiais, mas uma lenta transformação a acompanha no que diz respeito à mudança dos princípios do modelo de desenvolvimento industrial, que enfatiza o consumismo como estratégia de reprodução. Ao mesmo tempo em que as pesquisas sugerem uma ampliação da consciência ambiental da sociedade como um todo, percebe-se um acirramento dos problemas socioambientais e soluções sendo alcançadas em escala inferior ao patamar considerado desejado. Onde estaria, então, o problema? Qual a razão desta possível defasagem educação ambiental x resultados? Foi com o intuito de responder a estas perguntas que essa tese foi realizada. Parte-se de uma percepção de que a Educação Ambiental praticada na escola reflete e acentua o paradigma moderno hegemônico, que se baseia em uma concepção dualista homem / natureza, em que uma está a serviço do outro, sem promover o questionamento sobre os desdobramentos da adoção dos valores da sociedade de consumo no desequilíbrio da vida no planeta. Essa dicotomia entre cultura e natureza, sociedade e ciência, sujeito e objeto se reflete na busca de soluções parciais, incompletas, visando-se apenas a uma parte do problema socioambiental, que não é visto como um sistema complexo. A educação ambiental realizada nessas bases dificulta a reunião das condições necessárias à mudança das estruturas da atual sociedade brasileira e à busca das soluções dos seus problemas socioambientais. Nessa perspectiva, esse trabalho objetiva criar subsídios para um caminho para a educação ambiental que possa contribuir para uma visão complexa da realidade e dos problemas socioambientais, na busca de soluções mais abrangentes. Para isto procura entender: a) como a teoria da complexidade poderia colaborar para esta mudança; b) em quais modelos práticos e teóricos a Educação Ambiental se dá no Brasil, ou seja, quais as diversas tendências da educação ambiental brasileira; e c) como esses modelos se expressam nas práticas dos professores analisando-se artigos publicados em anais de seminários, congressos e/ou encontros sobre o tema.

Orientador: Marisa Trench de O. Fonterrada / Banca: Alberto Tsuyoshi Ikeda / Banca: Maria Teresa Alencar de Brito / Resumo: Em virtude da Lei nº 11.769/2008, que dispõe sobre a obrigatoriedade do ensino da Música na Educação Básica, foram observadas lacunas de pesquisas em relação aos conhecimentos atuais para atender as demandas didáticas nesse nível pedagógico. Nesse sentido, o presente estudo visou verificar e registrar a existência da música, dos jogos e brincadeiras musicais da tradição na cultura da escola estudada. Objetivou, por outro viés, localizar um aspecto da vida social, representado pelo jogo e a brincadeira musicais, considerados como tema da educação musical, da educação geral e de estudos sociais. Pretendeu, além disso, analisar a viabilidade de sua utilização em aulas de Educação Musical e Arte-Educação, no ensino fundamental. Devido às múltiplas propostas inseridas no interior da temática, surgidas ao se trabalhar com a cultura popular, adotou-se como ponto de partida as relações de complexidade existentes no objeto a ser pesquisado. O estudo destas relações foi embasado no pensamento sistêmico, na teoria da complexidade aplicada à Educação e fundamentou-se, também, metodologicamente, em autores da área das Ciências Sociais, o que resultou em um estudo de caso com abordagem qualitativa realizada junto ao corpo discente de uma escola pública de ensino fundamental II, na cidade de São Paulo. Realizaram-se levantamento e registro, por meio de entrevistas, caderno de campo, questionários e gravações em vídeo. Ao final da investigação, analisou-se o material recolhido relativo ao tema da pesquisa, além de outros, conexos ou transversais com os seguintes resultados: os jogos e brincadeiras musicais e a educação musical se imbricam em questões técnicas musicais criadas pela ação de jogar e brincar, na sensibilização pela música, por meio dos elementos de natureza social e relacionados com o... (Resumo completo, clicar acesso eletrônico abaixo) / Abstract: student body from a public school in basic education II, in the city of Sao Paulo. The study aimed to verify the existence of traditional music, musical ludic activities and frolics, as well as to deepen its investigation and register its presence in the culture of the studied school, in case it was, indeed, present. Furthermore, it aimed to locate an aspect of social life, which is musical ludic activity and frolic, considered a matter of music education, education and social studies. It intended to analyze the feasibility of its use in Music Education and Art Education classes in primary school. Due to the multiple proposals contained within the theme, encountered when working with popular culture, the complex relations that exist within the object of research were adopted as a starting point. The study of these relations was grounded in Maturana's systems thinking (1998, 2001), Maturana; Verden-Zöller (2004) and in the complexity theory applied to Education, as it is presented in Edgard Morin's proposal (2011a, 2011b). It was also based, methodologically, in Fernandes (1979), Cândido (1975) and Magnani (1998), amongst others, in the Social Sciences area. Surveys and records were made, through interviews, field notes, questionnaires and video recordings. At the end of the study, the collected material and the content related to the research topic, in addition to others, connected or transverse, were analyzed. It was established that the study proposals achieved their goals. It is intended to forward the prepared material... (Complete abstract click electronic access below) / Mestre

Functional magnetic resonance imaging has been recently the most common tool for examining the neural activity in human and animals. The goal of a typical data-mining challenge is the localisation of brain areas activated during a cognitive task which is usually performed using a linear model or correlation methods. For this purpose several authors have proposed the use of methods evaluating signal complexity which could possibly overcome some of the shortcomings of the standards methods due to their independence on a priori knowledge of data characteristics. This work explains possibilities of using such methods including aspects of their configuration and it proposes an evaluation of performance of the methods applied on simulated data following expected biological characteristics. The results of the evaluation of performance showed little advantage of these methods over the standard ones in cases when the standard methods were possible to apply. However, some of the methods evaluating signal complexity were found useful for determining the regularity of signals which is a feature that cannot be assessed by the standard methods. Optimal parameters of the methods evaluating signal regularity were determined on simulated data and finally the methods were applied on the data examining emotional processing of...

There are several approaches for creating double-ended heaps from the single-ended heaps. We build on one of them, the leaf correspondence heap, to create a generic double ended heap scheme called L-correspondence heap. This will broaden the class of eligible base single-ended heaps (e.g. by Fibonacci heap, Rank-pairing heap) and make the operations Decrease and Increase possible. We show this approach on specific examples for three different single-ended base heaps and give time complexity bounds for all operations. Another result is that for these three examples, the expected amortized time for Decrease and Increase operations in the L-correspondence heap is bounded by a constant.

Title: Flows and cuts with constraints Author: Dušan Knop Department: Department of applied mathematics Supervisor: Doc. Mgr. Petr Kolman, PhD, Department of applied mathematics Abstract: In this thesis we study the problem of length bounded cuts between two vertices of a graph. In this problem the task is to find a set of edges such that after its removal the minimal distance between the two vertices is as prescribed. The work provides a basic overview of the literature on this problem and presents it in the context of other theoretical problems. It also offers some applications of length bounded cuts and flows. We describe some heuristics for data reduction. The main result of this thesis is a polynomial time algorithm in series-parallel graphs for problem of length bounded cut, which is NP-hard in general. Keywords: cuts, series-parallel graphs, algorithm, complexity

This work introduces two new parameterizations of graph problems generalizing vertex cover which fill part of the space between vertex cover and clique width in the hierarchy of graf parameterizations. We also study parameterized complexity of Hamiltonian path and cycle, vertex coloring, precoloring extension and equitable coloring parameterized by these two parameterizations. With the exception of precoloring extension which is W[1]-hard in one case, all the other problems listed above are tractable for both parameterizations. The boundary between tractability and intractability of these problems can therefore be moved closer to parameterization by clique width.

Submitted by Cássia Santos (cassia.bcufg@gmail.com) on 2016-03-09T12:12:20Z No. of bitstreams: 2 Dissertação - Maria da Conceição Rodrigues dos Santos - 2010.pdf: 1309156 bytes, checksum: 587cba90cb284781d6bde1736fbfb384 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2016-03-10T11:50:54Z (GMT) No. of bitstreams: 2 Dissertação - Maria da Conceição Rodrigues dos Santos - 2010.pdf: 1309156 bytes, checksum: 587cba90cb284781d6bde1736fbfb384 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2016-03-10T11:50:54Z (GMT). No. of bitstreams: 2 Dissertação - Maria da Conceição Rodrigues dos Santos - 2010.pdf: 1309156 bytes, checksum: 587cba90cb284781d6bde1736fbfb384 (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2010-11-30 / It is reference to this study the work of the physical chemist Ilya Prigonine based on ideas of complexity and chaos responsible for a deep change in science, originally triggered by thermodynamics followed by the theory of relativity and quantic physics. The study aims to examine the influence of the prigogineane work on the formation of the new episteme behind all these changes, in the face of the paradigmatic rupture of the contemporary thought. The study will also understand the new knowledge body which these investigated changes are about to model along with the issues of contemporary world, like those regarding the science and philosophy, the boundaries of growth, sustainable development and the emergency of a new model of rationality. / É referência para este estudo a obra do físico-químico Ilya Prigogine, nucleada pelas idéias de complexidade e caos, que apontam para uma profunda transformação da ciência, originariamente desencadeada pela termodinâmica, seguida de perto pela teoria da relatividade e pela física quântica. O trabalho tem por meta examinar o alcance da obra prigogineana na conformação da nova episteme que subjaz a tais mudanças, em face da ruptura paradigmática que instaura o pensamento contemporâneo. De resto, importará ao estudo entrever o novo corpo de saber que as mudanças investigadas estão a modelar, em concurso com questões prementes do mundo contemporâneo, como as que dizem respeito à crise na ciência e na filosofia, aos limites do crescimento, ao desenvolvimento sustentável e à emergência de um novo modelo de racionalidade.

Este trabalho liga os conceitos da Teoria da Complexidade (TC) à Contabilidade por meio da utilização da aprendizagem baseada em problemas (ABP) no âmbito do ensino e nasce da necessidade de reforçar a aquisição de autonomia, habilidade de solução de problemas e o aprendizado. A TC ampara a forma de pensar em diversas áreas, sendo uma vasta tendência anti-reducionista presente em vários setores da ciência que ressalta os aspectos de descontinuidade, contradição, não-linearidade, multiplicidade e aleatoriedade, não reduzindo propriedades emergentes. Por sua vez a ABP é vista como a interação dinâmica entre os agentes que leva a emergência de novas características auto-organizadoras, a novos entendimentos acerca dos problemas em que soluções são construídas coletivamente e essa metodologia aplicada à Contabilidade implica em não isolá-la em partes incomunicáveis. O problema proposto questiona se a ABP provê maiores ganhos de autonomia, aprendizagem e habilidade de solução de problema aos estudantes de Contabilidade. O estudo possui um enfoque exploratório ao enfatizar a ABP como abordagem complexa na educação, e também, um caráter correlacional ao desenvolver um quase-experimento. Para testar a hipótese de que a utilização da ABP na Contabilidade fornece mais autonomia, aprendizagem e habilidade de solução de problema, um quase-experimento foi desenvolvido em duas etapas, com dois grupos de estudantes de graduação em Contabilidade. Na primeira etapa, foi aplicada ao grupo experimental a metodologia de ABP, já no grupo de controle, a metodologia tradicional expositiva. Na segunda etapa os grupos se invertem, revezando-se nas metodologias de ensino aplicadas. Questionários e depoimentos escritos pelos alunos captam a percepção discente, e a solução de caso de ensino e testes de conhecimento de Contabilidade foram utilizados para ratificar as percepções. Os resultados mostram que os alunos expostos a ABP percebem maior ganho de autonomia, de aprendizagem e de habilidade de solução de problema, comparados aos alunos expostos ao ensino tradicional. Os resultados dos pós-teste e testes de avaliação de conhecimento ratificam o melhor desempenho dos estudantes expostos a ABP. Apesar de se mostrar uma metodologia superior nas análises aqui levantadas, a ABP não parece ser substituta de metodologias tradicionais, mas sim, um poderoso complemento. / This piece of work performs a connection between the concepts of the Complexity Theory and Problem Based Learning (PBL), and then, analyzes its application to accounting teaching. It origins from the necessity to add theories to the accounting teaching that reinforce the acquisition of autonomy, problem solving ability and learning. At first instant, Complexity Theory emerges to support different forms of thinking among several areas of knowledge. It refers to a vast tendency anti-reductionist which evolved from many fields in scientific research. Complex epistemology takes form as it puts focus on the aspects of discontinuity, contradiction, non-linearity, multiplicity and randomness instead of reduce its emergence. PBL is the dynamic interaction among agents that lead it to the emergence of new selforganizing features, new understandings on problems to which solutions are collectively built. See Accounting under ideas of Complexity implies not to isolate this science in incommunicable parts, contrarily, it implies to contextualize the Accounting studies in its many functions on the research of organizations assets and its role on society as general. In Accounting, the divided view of reality brings the need of new paradigms to translate the assets performance and entities results, paradigms that support new ways of thinking and are able to be spread by people that act in these contexts. To test the hypotheses that in the student perceptions, a Complex approach to reality in Accounting education provides more autonomy, problem solving ability and learning, compared to a traditional approach, a quasiexperiment is performed in two steps with the participation of students divided in two groups. Firstly, to the experimental group it is applied the PBL methodology and to the control group, traditional methodology is developed, both exposed to a Cost Accounting course. At second step, groups are inverted and alternate in the teaching methods. Questionnaires, statements written by students and case studies solutions are utilized as pre and pos-tests providing data that feed analyzes on this research. To sum it up, this study has an exploratory feature when emphasize PBL as a Complex approach in education, and as well, this study has a correlacional feature when performs a quasi-experiment. The results show us that students participating in PBL Cost Accounting courses perceive more acquisitions of autonomy, knowledge and problem solving ability compared to students that participated in traditional courses. Results in Cost Accounting knowledge evaluation via pos-test and questionnaires, used as students perceptions confirmation tools, reaffirm the better performance of students exposed to PBL courses. Such methodology, despite the fact of being superior in the hypotheses tested in the research, it does not seem to be the traditional methodologies substitute; however, it fits more as a complement to existing tools, since in many learning profile there are students who take advantage from PBL potential and see it as valid option, but in some cases, there are people who do not present affinity with this methodology, according to students statements and performance.