A comparação de sequências finitas é uma ferramenta que é utilizada para a solução de problemas em várias áreas. Comparamos sequências inferindo quais são as operações de edição de substituição, inserção e remoção de símbolos que transformam uma sequência em uma outra. As matrizes de pontuação são estruturas largamente utilizadas e que definem um custo para cada tipo de operação de edição. Uma matriz de pontuação G é indexada pelos símbolos do alfabeto. A entrada de G na linha A, coluna B mede o custo da operação de edição para substituir o símbolo A pelo símbolo B. As matrizes de pontuação induzem funções que atribuem uma pontuação para um conjunto de operações de edição. Algumas dessas funções para a comparação de duas e de várias sequências são estudadas nesta tese. Quando cada símbolo de cada sequência é editado exatamente uma vez para transformar uma sequência em outra, o conjunto de operações de edição pode ser representado por uma estrutura conhecida por alinhamento. Descrevemos uma estrutura para representar o conjunto de operações de edição que não pode ser representado por um alinhamento convencional e descrevemos um algoritmo para encontrar a pontuação de uma sequência ótima de operações de edição usando um algoritmo conhecido para encontrar a pontuação de um alinhamento convencional ótimo. Considerando três diferentes funções induzidas de pontuação, caracterizamos, para cada uma delas, a classe das matrizes para as quais as funções induzidas de pontuação são métricas nas sequências. Dadas duas matrizes de pontuação G e G\', dizemos que elas são equivalentes para uma dada função que é induzida por uma matriz de pontuação e que avalia a qualidade de um alinhamento se, para quaisquer dois alinhamentos A e B, vale o seguinte: o alinhamento A é ``melhor\'\' do que o alinhamento B considerando a matriz G se e somente se A é ``melhor\'\' do que o alinhamento B considerando a matriz G\'. Neste trabalho, determinamos condições necessárias e suficientes para que duas matrizes de pontuação sejam equivalentes. Finalmente, definimos três novos critérios para pontuar alinhamentos de várias sequências. Todos os critérios consideram o comprimento do alinhamento além das operações de edição por ele representadas. Para cada um dos critérios definidos,propomos um algoritmo e o problema de decisão correspondente mostramos ser NP-completo. / Comparison of finite sequences is a tool used to solve problems in several areas. In order to compare sequences, we infer which are the edit operations of substitution, insertion and deletion of symbols that transform one sequence into another. Scoring matrices are a widely used structure to define a cost for each type of edit operation. A scoring matrix G is indexed by symbols of an alphabet. The entry in G in row A and column B measures the cost of the edit operation for replacing symbol A by symbol B. Scoring matrices induce functions that assign a score for a set of edit operations. Some of these functions for comparing two and multiple sequences are studied in this thesis. If each symbol is edited exactly once for transforming a sequence into another, the set of edit operations can be represented by a structure called alignment. We describe a structure to represent the set of edit operations that cannot be represented by a conventional alignment and we design an algorithm to find the cost of an optimal sequence of edit operations by using a known algorithm to find the cost of an optimal alignment. Considering three different kinds of induced scoring functions, we characterize, for each one of them, the class of matrices for which the induced scoring functions are metrics on sequences. Given two scoring matrices G and G\', we say they are equivalent for a given function that is induced by a scoring matrix and that evaluates the quality of an alignment if, for any two alignments A and B of two sequences, we have the following: alignment A is ``better\'\' than B considering scoring matrix G if and only if A is ``better\'\' than B considering scoring matrix G\'. In this work, we determine necessary and sufficient conditions for scoring matrices to be equivalent. Finally, we define three new criteria for scoring alignments of several sequence. Every criterion considers the length of the alignment and the edit operations represented by it. An algorithm for each criterion is studied and the corresponding decision problem is shown to be NP-complete.

ALVES, Francisco Regis Vieira. Aplicações da sequência Fedathi na promoção do raciocínio intuitivo no cálculo a várias variáveis. 2011. 398f. Tese (Doutorado em Educação) – Universidade Federal do Ceará, Faculdade de Educação, Programa de Pós-Graduação em Educação Brasileira, Fortaleza-CE, 2011. / Submitted by Maria Josineide Góis (josineide@ufc.br) on 2012-07-11T14:43:16Z No. of bitstreams: 1 2011_Tese_ FRVALVES.pdf: 14201518 bytes, checksum: 22b6bb75fce50eeb927d7cdec1d5d361 (MD5) / Approved for entry into archive by Maria Josineide Góis(josineide@ufc.br) on 2012-07-11T15:04:21Z (GMT) No. of bitstreams: 1 2011_Tese_ FRVALVES.pdf: 14201518 bytes, checksum: 22b6bb75fce50eeb927d7cdec1d5d361 (MD5) / Made available in DSpace on 2012-07-11T15:04:21Z (GMT). No. of bitstreams: 1 2011_Tese_ FRVALVES.pdf: 14201518 bytes, checksum: 22b6bb75fce50eeb927d7cdec1d5d361 (MD5) Previous issue date: 2011 / Este estudo trata do ensino/aprendizagem do Cálculo Diferencial e Integral a Várias Variáveis - CVV. Seu objetivo geral foi a identificação/descrição das categorias do raciocínio intuitivo ao longo das fases de ensino da metodologia nominada Sequência Fedathi. A estruturação e a concepção de situações didáticas de ensino envolvendo situações-problema diferenciadas, entretanto, com respeito aos rituais algorítmicos identificados nos livros didáticos de CVV, foram atingidos com base numa visão de complementaridade entre a Teoria das Representações Semióticas e as categorias do raciocínio intuitivo descrita por Fischbein (1987), exploradas nas quatro fases previstas pela Sequência Fedathi. Assim, iniciamos o trabalho com o levantamento e compreensão do ensino e da aprendizagem do Cálculo em Uma Variável Real – CUV e dos poucos estudos científicos desenvolvidos, tanto no Brasil como no Exterior acerca do ensino do CVV. Damos ênfase final à descrição da transição interna do CUV para o CVV, o que não se observa em estudos acadêmicos. Em seguida, com a intenção de delinear, caracterizar, discutir e compreender a natureza do principal raciocínio que tencionamos registrar, discutimos a natureza epistemológica, filosófica e psicológica do raciocínio intuitivo, suas categorias (intuição afirmativa, intuição conjectural e intuição antecipatória) e outras faculdades psíquicas vinculadas a este, nomeadas por percepção e insight. Depois de caracterizar um ensino de CVV apoiado na crença e na certeza matemática, apresentamos e discutimos os principais elementos da Sequência Fedathi e das teorias propostas por Fischbein (1987) e Duval (1991; 1995a). Em seguida, no que diz respeito ao desenvolvimento da pesquisa e a investigação de campo, com arrimo no viés de complementaridade destas teorias, analisamos obras didáticas reconhecidas de CVV, que servem como referência de estudo, com a intenção de identificar e superar possíveis entraves no tocante à elaboração das atividades aplicadas aos estudantes. Os dados empíricos foram obtidos por meio de documentos produzidos por um grupo de oito estudantes escolhidos em uma amostra total de 80 alunos do curso de Licenciatura em Matemática do Instituto Federal de Educação, Ciência e Tecnologia – IFCE – Fortaleza, no período de 2009/2010, matriculados na disciplina Cálculo III, por meio de entrevistas semiestruturadas efetuadas durante e após as atividades, de modo individual e com o registro visual do momento em que desenvolveram suas estratégias. Todavia, para efeito de discussão no corpo da tese, apresentamos apenas oito estudantes. No final deste estudo, podemos dizer que a exploração didática de categorias do raciocínio intuitivo (intuição afirmativa, intuição conjectural e intuição antecipatória), com base em uma mediação didática que envolveu a exploração de registros de representação semiótica, pode proporcionar a evolução do conhecimento do estudante a respeito dos conceitos principais do CVV. Para tanto, o apoio computacional, com o emprego de softwares como o Geogebra e do CAS Maple, pode indicar elementos mais significativos no que diz respeito à transição interna do CUV para o CVV. Outro ponto relevante concerne à importância do estímulo à elaboração de imagens mentais produzidas pelo ensino que estimula a intuição matemática, a produção de metáforas e a apreensão perceptual dos objetos em 3D do CVV e, deste modo, a evolução de crenças e valores epistêmicos não contraditórios relativos às propriedades formais do CVV.