Search

Recent research literature seems to expose and challenge a tacit and widespread conception that the knowledge required for teaching mathematics in school is situated outside the school’s professional and cultural environment, and that the authority over this knowledge rests in groups that do not include school teachers. Taking this scenario into account, the mathematics teachers’ undergraduate degree program of the Federal University of Rio de Janeiro (UFRJ) launched a new experience in 2015, in which mathematical content modules are taught jointly by a school teacher and a university lecturer. The experience holds an institutional intentionality: to integrate professional knowledge emerging from school practice as a formal component of pre-service undergraduate mathematics teachers’ education. This paper focuses on a research project – Shared Teaching Practices – developed in the context of this experience. More specifically, we discuss prospective teachers’ expectations towards the lectures taught by the two teachers, especially the role of the school teacher in module’s conduction. Results indicate a shift in the participants’ perception regarding their own professional disciplinary body of knowledge, and the role of this body of knowledge in their formal pre-service education.

A necessidade de integrar a prática docente da educação básica à formação inicial de professores tem sido amplamente reconhecida tanto pela literatura de pesquisa em educação matemática brasileira e internacional, como pela legislação brasileira. Neste trabalho, apresentamos um modelo em implantação na Universidade Federal do Rio de Janeiro, no qual a condução da aula em disciplinas do curso de licenciatura em Matemática é compartilhada por um professor da Universidade e um professor da educação básica. Uma etapa piloto foi aplicada durante o 1º semestre letivo de 2015, e o modelo está sendo ampliado a partir do 2º semestre do mesmo ano. Descrevemos a estrutura utilizada no modelo e discutimos as perspectivas para sua ampliação. Resultados da etapa piloto sugerem que se estabeleceu na disciplina um ambiente em que todos os atores envolvidos – professor da universidade, professor da escola e alunos de licenciatura – assumiram, em certo sentido, um papel de aprendizes.

Reversals and transpositions are two classic genome rearrangement operations. Reversals occur when a chromosome breaks at two locations called breakpoints and the DNA between the breakpoints is reversed. Transpositions occur when two adjacent blocks of elements exchange position. This paper presents a polynomial-time approximation algorithm for the Sorting by Reversals and Transpositions Problem. Our algorithm applies to both signed and unsigned versions of the problem, and it treats both cases in a unified manner. We prove an approximation factor of 2 for signed permutations and 2k for the unsigned case, where k is the approximation factor of the algorithm used for cycle decomposition, but in our practical experiments our algorithm found results with approximation ratio better than 1.5 in more than 99% of the signed permutations and better than 1.8 in more than 97% of the unsigned permutations. Our analysis also shows that our algorithm outperforms any other approach known to date.

Orientador: João Meidanis Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Reconstrução filogenética é o campo da Biologia Computacional dedicado a inferir um histórico evolutivo a partir de dados biológicos do presente. Nesta tese de doutorado, apresentamos três trabalhos sobre diferentes problemas relacionados ao tema. O primeiro visa reconstruir o ancestral comum a três genomas de entrada. Apesar da entrada aparentemente limitada, este problema pode ser aplicado para determinar ancestrais em árvores de topologia já conhecida. Nosso trabalho introduz uma forma de representar genomas através de matrizes. A partir disto, definimos o problema da mediana de matrizes, que, dadas três matrizes A, B e C, consiste em encontrar uma matriz M que minimize a soma d(A,M) + d(B,M) + d(C,M), onde d(X,Y) é o posto da matriz Y-X. Para resolver tal problema, apresentamos um algoritmo aproximado que garante resultados no mínimo tão bons quanto um dos genomas de entrada, mas que, em experimentos simulando a evolução de genomas, teve resultados muito mais próximos do ótimo. Além disso, mostramos também uma heurística que traduz uma matriz qualquer, como a resultante do nosso algoritmo, de volta para um genoma. No segundo, o objetivo é reconstruir genomas ancestrais a partir dos históricos evolutivos de suas famílias de genes. Para isto, estendemos o esquema de programação dinâmica do software DeCo, que constrói florestas retratando a evolução de adjacências. Nossa implementação, em vez de escolher apenas as adjacências de uma solução mais parcimoniosa, explora todo o espaço de soluções, escolhendo adjacências em função da sua maior frequência. Com esta abordagem, conseguimos reduzir significativamente o número de inconsistências ao avaliar múltiplas instâncias sobre os mesmos genes. Finalmente, discutimos uma ferramenta capaz de auxiliar na reconstrução de genomas ancestrais, considerando os genomas de espécies descendentes e sem a necessidade dos históricos de todas as famílias de genes. Esta ferramenta é a estrutura de dados chamada árvore PQR, que não só detecta se a entrada tem a propriedade dos uns consecutivos, como também indica os obstáculos que possivelmente impedem a instância de ter a propriedade. Isto é importante porque, ao reconstruir genomas ancestrais, erros na entrada são muito comuns e podem muito facilmente impedir a instância de ter a propriedade dos uns consecutivos. Aqui, consolidamos o conhecimento sobre os algoritmos online e offline para árvores PQR em um único artigo. Com isto, avançamos em três diferentes direções o conhecimento nas áreas de Reconstrução Filogenética e de Biologia Computacional Abstract: Phylogenetic reconstruction is the field of computational biology dedicated to infer evolutionary history from given extant biologic data. In this PhD thesis, we present three works on different issues related to the topic. The first aims to reconstruct the common ancestor to three input genomes. Despite the apparently limited input, this problem can be applied to determine ancestors in trees whose topology is already known. Our work introduces a way to represent genomes using matrices. From this, we define the matrix median problem, which consists of, given three matrices A, B and C, find a matrix M that minimizes the sum d(A,M) + d(B,M) + d(C,M), where d(X,Y) is the rank of the matrix Y-X. To solve this problem, we present an approximate algorithm that ensures results at least as good as one of the input genomes, but that, in the experiments simulating the evolution of genomes, got much closer to optimal results. Furthermore, we also show a heuristic that translates any matrix, like the ones returned by our algorithm, back to a genome. In the second, the goal is to reconstruct ancestral genomes from the evolutionary histories of their respective gene families. For this, we extend the dynamic programming scheme of DeCo, that builds forests depicting the evolution of adjacencies. Our implementation, instead of choosing just the adjacencies of one most parsimonious solution, explores the entire solution space, choosing adjacencies in function of their larger frequency. Using this approach, we managed significantly reduce the number of inconsistencies while evaluating multiple instances on the same genes. Finally, we discuss a tool to assist in the reconstruction of ancient genomes, considering the genomes of descendant species, without the need for the histories of all the gene families. This tool is the data structure called PQR-tree, which not only detects whether the entry has the consecutive ones property, but also the obstacles that possibly prevent the instance from having said property. This is important because, while reconstructing ancient genomes, entry errors are very common and can very easily prevent the instance from having the consecutive ones property. Here, we consolidate the knowledge on the online and offline algorithms for PQR trees in a single paper. With these, we moved knowledge in phylogenetic reconstruction and computational biology forward in three different directions Doutorado Ciência da Computação Doutor em Ciência da Computação CAPES FAPESP 2012/13865-7, 2013/07868-6

Orientadores: Paulo Sérgio Martins Pedro, Edson Luiz Ursini Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Tecnologia Resumo: Este trabalho procura solucionar um dos problemas mais críticos das redes it Flying AdHoc (FANET), que é a questão da coordenação da recarga de baterias de drones que voam em forma de enxame (Swarms). Para que as recargas sejam realizadas da melhor maneira possível, é desejável que o número de dispositivos de carregamento (estações base) não seja excessivamente alto principalmente devido ao alto custo de implantação. Por outro lado, também é necessário que, quando os drones quiserem recarregar, sempre haja uma fonte de energia disponível. Ou seja, buscamos o equilíbrio entre o número economicamente viável de estações de recarga e o abastecimento adequado dos drones quando isso for necessário. Para essa finalidade, propomos agentes (drones) munidos de inteligência interna, ou seja, com preditores internos que fornecem inteligência na tentativa de prever a próxima taxa de presença nesse dispositivo de carregamento e dessa maneira poder decidir se deve ou não ir abastecer. O ideal é que a previsão seja sempre a melhor possível. Assim, o drone deveria ir quando prevê que deve ir e não deveria ir quando prevê não ir. A utilização do equilíbrio de Nash para este problema, sendo possível pela utilização da modelagem via o Problema El Farol Bar (PEFB), permite o desenvolvimento de uma analogia sem o conluio dos agentes na coordenação da simulação da recarga desse conjunto de drones. Ou seja, com relação à coordenação do enxame para a recarga das baterias não haverá gasto de energia em comunicação, embora esta continue nas demais tarefas inerentes ao {\it swarm} de drones. A verificação da adequação da proposta é feita por meio de Simulação Baseada em Agentes e neste modelo são utilizadas três políticas diferentes para a tomada de decisão do melhor preditor para cada drone. Isso permite verificar o desempenho na operação do sistema por meio do Equilíbrio de Nash. No atual estado dessa analogia considera-se que, caso os drones forem para a estação de recarga e a mesma estiver cheia, não haverá recarga possível porque o sistema estará sobrecarregado. Neste estudo estão incluídas análises microscópicas e macroscópicas do desempenho do swarm. A análise microscópica é a avaliação do desempenho das recompensas de cada preditor em relação a um conjunto de parâmetros de simulação, visando um aumento da eficácia no desempenho microscópico. A análise macroscópica é a avaliação do desempenho do atendimento global do sistema com os três tipos de políticas. Esta última análise é usada como base para o desenvolvimento da analogia de recarga dos drones. Dessa maneira, avalia-se o desempenho dos melhores conjuntos de simulação para a recarga dos drones que permitem abastecer abaixo do limiar de recarga (número de posições disponível de recarga), mas que estão relativamente próximos a esse limiar Abstract: This work seeks to solve one of the most critical problems of the Flying AdHoc (FANET) networks, which is the issue of coordinating the recharging of drones that fly in the form of Swarms. For recharging to be done in the best possible way, it is desirable that the number of charging devices (base stations) did not be excessively high due to the high implementation cost. Conversely, it is also necessary that, when drones want to recharge, they must have a source of energy available. In other words, we search for a balance between the economically viable number of charging stations and the adequate energy supply for the drones when necessary. For this, we propose agents (drones) equipped with internal intelligence, that is, with internal predictors that provide intelligence to attempt to predict the next attendance rate in the charging device and thus be able to decide whether go or not go to the recharging. Ideally, the forecast should be as best as possible. Therefore, the drone should go when it predicts it should go and it shouldn't go when it predicts not to go. The Nash equilibrium usage for this problem is made possible by the modeling via the El Farol Bar Problem (EFBP), which allows the development of this analogy without the collusion of agents in coordinating the simulation of the recharge of this set of drones. In other words, there will be no energy expenditure on communication about the drones' battery recharging coordination, although the communication will continue in the other tasks inherent to the swarm of drones. The verification of the suitability of the proposal is done through Agent-Based Simulation and are used three different policies for the best predictor decision by each drone. This will allow us to verify the performance in the operation of the system through a Nash Equilibrium. In the current state of this analogy is considered that if the drones go to the charging station and it is full, there will be no possible charging because the system is overloaded. This study includes microscopic and macroscopic analysis. Microscopic analysis is the evaluation of the performance of the rewards of each predictor concerning a set of simulation parameters, aiming at a microscopic behavior performance improvement. A macroscopic analysis is the evaluation of the performance of the global service of the system with three types of policies. This latter analysis is used as a basis for evaluating the drone's recharge analogy. In this way, the performance of the best simulation sets for the recharge of drones is evaluated, which allows supplying below the control threshold (attendance below than the number of recharge positions), but which are relatively close to the threshold Mestrado Sistemas de Informação e Comunicação Mestre em Tecnologia CAPES 001

Orientadores: Paulo Sérgio Martins Pedro, Edson Luiz Ursini Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Tecnologia Resumo: A definição de modos de operação no projeto de um sistema de tempo real tem sido um recurso utilizado para se agregar benefícios ao sistema, dentre eles a adequação dinâmica da operação do sistema para uma determinada fase de operação. Tradicionalmente, as mudanças no modo de operação são realizadas de maneira reativa, ou seja, o sistema altera seu modo em resposta a um evento interno ou externo. Esse trabalho apresenta uma proposta de um modelo proativo para mudanças de modo em sistemas de tempo real de criticalidade mista. Nessa abordagem foram integrados algoritmo de predição e lógica difusa ao escalonamento de mudanças de modo utilizando as políticas de escalonamento Earliest-Deadline-First (EDF) e Fixed-Priority Preemptive Systems (FPPS). Essa abordagem visa a programação proativa de mudanças de modo baseada em valores observados e preditos de variáveis de estado como a lassidão de pior caso das instâncias das tarefas em espera ou em estado de execução a fim de minimizar a perda de prazo das tarefas de baixa criticalidade. Para avaliação de viabilidade, a abordagem proposta foi moldada em um modelo de simulação por eventos discretos que posteriormente fora validado com um modelo analítico (análise de escalonabilidade de pior caso). Oito estudos de caso foram implementados para avaliar o impacto das mudanças de modos proativas na perda de prazo das tarefas. Os resultados mostraram ganhos na adoção da abordagem de previsão para ambos os paradigmas de escalonamento, apresentando uma redução significativa no número de prazos perdidos para tarefas de baixa criticidade Abstract: The definition of modes of operation in the design of a real-time system has been a feature used to add benefits to the system, such as the dynamic adaptation of the systems operation to a specific phase of operation. Traditionally, the changes in mode of operation have been accomplished in a reactive manner, i.e. the system changes its mode in response to an internal or external event. This work presents a proposal for proactive mode-changes in mixed-criticality real-time systems. In this approach, prediction algorithms and fuzzy were integrated into mode-changes using Earliest-Deadline-First (EDF) and Fixed-Priority Preemptive Systems (FPPS) scheduling policies. The aim of this approach is the proactive scheduling for mode-changes based on observed and predicted values of the state variables such as the worst-case laxity of waiting or running tasks. For feasibility evaluation, the proposed approach was modeled on a discrete event simulation model that was later validated with an analytical model (worst case scalability analysis). Eight case studies were implemented to assess the impact of proactive mode-changes on missed deadlines of tasks. The results showed that the approach using prediction for both scheduling paradigms represented a significant reduction in the number of missed deadlines for low-criticality tasks Doutorado Sistemas de Informação e Comunicação Doutor em Tecnologia

Orientadores: Zanoni Dias, Ulisses Martins Dias Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação Resumo: Rearranjos de Genomas são eventos que afetam longos trechos de um genoma durante a evolução. Dentre os rearranjos mais estudados, temos a reversão, que inverte a ordem e a orientação de um bloco consecutivo de genes, e a transposição, que troca a ordem relativa de dois blocos adjacentes. Modelos matemáticos vêm sendo utilizados para estimar a distância evolutiva entre diferentes organismos por rearranjos de genomas. A representação de um genoma se dá, na maioria das vezes, pela atribuição de um número único para cada gene e, ao supor que não existem genes repetidos, essa representação pode ser vista como uma permutação. Supondo que os dois genomas a serem comparados compartilham o mesmo conjunto de genes, calcular a distância evolutiva entre eles se torna o problema de encontrar o menor número de rearranjos necessários que transforma uma permutação em outra. Nesta tese, apresentamos diversos resultados envolvendo problemas de rearranjos de genomas: (i) provas de NP-dificuldade para quatro problemas cuja complexidade era desconhecida; (ii) um algoritmo polinomial exato para um problema cuja complexidade era desconhecida; e (iii) algoritmos de aproximação e provas de NP-dificuldade para problemas onde a representação dos genomas não considera apenas a ordem dos genes. Descrevemos estas contribuições com maior profundidade nos parágrafos a seguir. Dentre os problemas que envolvem rearranjos de genomas, existem quatro versões que permitem o uso de reversões e transposições ao mesmo tempo e que, apesar dos diversos algoritmos propostos nos últimos 20 anos, permaneciam com complexidade desconhecida. A primeira contribuição apresentada é a prova de NP-dificuldade desses quatro problemas. Uma das variações dos problemas de rearranjos de genomas consideram que cada rearranjo pode afetar apenas um pequeno número de genes, também conhecidos como rearranjos curtos e super curtos. Neste contexto, nossa segunda contribuição é a prova de que o único problema cuja complexidade era desconhecida envolvendo reversões super curtas e transposições super curtas admite um algoritmo polinomial exato. A grande maioria das abordagens em problemas de rearranjos existentes na literatura focaram apenas na ordem relativa dos genes de um genoma, desconsiderando outras características importantes existentes no genoma. Recentemente, pesquisadores mostraram que considerar as regiões existentes entre cada par de genes, chamadas de regiões intergênicas, pode resultar em melhores estimadores de distância em dados reais. Desta forma, nossa terceira contribuição investiga a incorporação das regiões intergênicas em modelos já existentes para reversões e transposições, tanto na abordagem sem restrições como na abordagem que considera apenas rearranjos super curtos, onde investigamos diversos algoritmos de aproximação para problemas que são NP-difíceis ou possuem complexidade desconhecida Abstract: Genome rearrangements are events that affect large stretches of a genome during evolution. Two of the most studied rearrangements are reversals, which reverses the order and orientation of a consecutive block of genes, and transpositions, which exchanges the relative order of two adjacent blocks. Mathematical models have been used to estimate the evolutionary distance between different organisms by genome rearrangements. The representation of a genome is very often made by assigning a unique number to each gene. If we assume no repeated genes, this representation can be seen as a permutation. By considering that the two genomes to be compared share the same set of genes, finding the evolutionary distance between them becomes the problem of finding the smallest number of genome rearrangements needed to transform one permutation into the other. In this thesis, we present several results involving genome rearrangement problems: (i) proofs of NP-hardness for four problems whose complexity was unknown; (ii) an exact polynomial algorithm for a problem whose complexity was unknown; and (iii) approximation algorithms and proofs of NP-hardness for problems where the genome representation carry more information than only the gene order. We describe these contributions in more depth in the following paragraphs. Among the problems involving genome rearrangements, four versions that allow the use of reversals and transpositions at the same time remained with unknown complexity despite the various algorithms proposed in the last 20 years. The first contribution presented is then the proofs of NP-hardness for these four problems. A variant of genome rearrangement problems considers that each rearrangement can affect only a small number of genes, also known as short and super short rearrangements. In this context, our second contribution is proof that the only problem involving super short reversals and super short transpositions whose complexity was unknown admits an exact polynomial algorithm. Most of the approaches for genome rearrangement problems in the literature so far have focused only on the relative order of genes in a genome, disregarding other important features presented in it. Recently, researchers have shown that considering the regions between each pair of genes, called intergenic regions, can result in better distance estimators in real data. Thus, our third contribution investigates the incorporation of intergenic regions in existing models for reversals and transpositions, both in the unrestricted and size restricted versions (i.e. super short operations), where we propose several approximation algorithms for problems that are either NP-hard or with unknown complexity Doutorado Ciência da Computação Doutor em Ciência da Computação CAPES CNPQ 140466/2018-5