Orientador: Walter A. Carnielli / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Científica / Made available in DSpace on 2018-07-21T14:44:37Z (GMT). No. of bitstreams: 1 Pela_RubenAlekxander_M.pdf: 2604511 bytes, checksum: 865f3288939547006b92be6353ab4141 (MD5) Previous issue date: 1996 / Resumo: O propósito deste trabalho é mostrar que o conceito de computabilidade sobre estruturas abstratas - apesar de não acrescentar nada genuinamente novo ao conceito clássico de computação, formalizado pela teoria da recursão, pode ser útil do ponto de vista matemático se visto como um conceito genuíno de computação. Tomamos como motivação, de um lado, o problema proposto por Arnold de decidir algoritmicamente se um ponto fixo de uma equação diferencial é ou não estável, e de outro, uma solução negativa deste problema que utiliza o conceito clássico de função computável. A partir da discussão gerada em torno desta solução, tentamos mostrar que o conceito de Turing-computabilidade é inadequado, sob um certo ponto de vista, para tratar problemas deste tipo. Tentamos mostrar que os modelos de computabilidade sobre estruturas abstratas propostos por Moschovakis, Friedman e Blum et al. podem ser usados para tratar o problema de uma forma mais 'realista'. Também discutimos alguns aspectos da teoria de computabilidade sobre os reais e sua relação com sistemas dinâmicos com o objetivo de enfatizar nosso ponto de vista. Além disso, discutimos brevemente algumas implicações desta análise para a Tese de Church-Turing. / Abstract: Not informed. / Mestrado / Mestre em Matemática

Orientador : Cid Carvalho de Souza / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-07-28T19:54:03Z (GMT). No. of bitstreams: 1 Rodrigues_MaikolMagalhaes_M.pdf: 4069676 bytes, checksum: b0b8e4bc9cdbe5bfc3fb90f34a46b43e (MD5) Previous issue date: 2001 / Resumo: Este trabalho de mestrado procurou estudar e resolver o problema de planejamento de viagens de linhas de ônibus da região metropolitana de São Paulo. Para tanto foi proposta uma ferramenta computacional capaz de gerar automaticamente as programações de viagens para uma linha de ônibus urbano. A programação de viagens tem um grande impacto não só na qualidade do serviço prestado aos passageiros da linha mas também no custo operacional das empresas de transporte. Portanto, o problema aqui estudado é de grande relevância prática e social. Os dados de entrada incluem uma curva com a demanda horária de passageiros da linha e um conjunto de restrições operacionais relativas à frota e aos funcionários. Na saída, deve-se produzir uma tabela com os horários das viagens além da escala de serviço completa dos carros e dos funcionários que irão operar na linha. Os algoritmos propostos por essa dissertação concentram-se no desenvolvimento de heurísticas baseadas em modelos de Programação Linear Inteira para resolver o problema de programação de viagens. Estes algoritmos foram implementados como parte de uma ferramenta computacional e os resultados são comparados com as soluções adotadas atualmente pelas empresas de transportes urbano. A análise dos resultados computacionais mostra que é possível obter reduções substanciais nos custos da operação sem que com isso haja uma redução na qualidade de serviço / Abstract: This dissertation aimed at studying and solving a real world trip planning problem. The problem considered arises from the daily operation of an urban transit bus company that serves the metropolitan area of the city of São Paulo, in Brazil. In this work we present a software that automatically generates a planning for the trips of a urban bus line. The trip planning has an enormous impact not only on the quality of the service offered to the passengers but also on the operational cost of the transportation companies. Therefore, the problem tackled here is of great importance for practical and social reasons. The input data includes the hourly demand of passengers and a set of operational constraints related to the vehicles and the employees. In the output, the trip time table as well as the vehicle and the crew schedules are produced. All the proposed algorithms in this work focus on the design of heuristics based on Integer Linear Programming models for the problem. The algorithms are implemented as part of a software whose results are compared with the solutions adopted in the bus companies nowadays. The analysis of our experiments indicates that it was possible to achieve a substantial cost reduction without loss in the quality of service / Mestrado / Mestre em Ciência da Computação

Orientador: Claudio Leonardo Lucchesi / Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-14T23:05:02Z (GMT). No. of bitstreams: 1 Silva_CandidaNunesda_D.pdf: 1443438 bytes, checksum: c37eb2de501a4f5b10d9c8681c3a0971 (MD5) Previous issue date: 2009 / Resumo: Esta tese trata de fluxos inteiros e colorações em grafos, problemas intimamente relacionados. Concentramos nossa atenção nas Conjeturas de Tutte sobre 5-, 4- e 3-fluxos, as quais foram propostas entre as décadas de 50 e 70 e permanecem abertas até hoje. Apresentamos três abordagens para o ataque das conjeturas, com ênfase na Conjetura dos 3-Fluxos. Na primeira abordagem propomos o estudo dos grafos fluxo-críticos, aqueles que não admitem um k-fluxo, mas que passam a admitir quando sujeitos a uma simples operação de redução. O interesse no estudo dessa classe de grafos vem da observação de que todo contra-exemplo mínimo para qualquer uma das conjeturas de Tutte é fluxo-crítico. Na segunda abordagem estudamos a conexidade cíclica do contra-exemplo mínimo para uma conjetura equivalente à Conjetura dos 3-Fluxos. Na terceira abordagem buscamos uma nova demonstração do Teorema de Grötzsch, o qual é o dual planar da Conjetura dos 3-Fluxos, que não utilize a Fórmula de Euler como a demonstração original. / Abstract: The theme of this thesis is nowhere-zero flows and colourings of graphs, two subjects that are closely related. We focus mainly on the three Conjectures of Tutte concerning 5-, 4- and 3-nowhere-zero flows. These conjectures were proposed, respectively, in the 50's, 60's and 70's; all of them remain open so far. In this thesis we present three different approaches for the study of Tutte's Conjectures, with emphasis on the 3-Flow Conjecture. In the first approach, we introduce the concept of flow-critical graph. A graph is flowcritical if it does not admit a nowhere-zero k-flow but, when a simple reduction operation is applied, the resulting graph does admit a nowhere-zero k-flow. The motivation for the study of such graphs is due to the observation that any minimum counterexample for any of Tutte's conjectures lies in this particular class. In the second approach, we study the cyclic-connectivity of a minimum counterexample for an equivalent version of the 3-Flow Conjecture. In the third approach, we give a new proof for Gr¨otzsch's Theorem that differs from the original in the fact that it does not depend on Euler's Formula. / Doutorado / Teoria dos Grafos / Doutor em Ciência da Computação

Orientador: Ricardo Dahab / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto da Computação / Made available in DSpace on 2018-08-02T03:39:47Z (GMT). No. of bitstreams: 1 Miranda_RogerioAlbertoni_M.pdf: 2899328 bytes, checksum: d0afff8b4bc78bf95a3670fb021de8ec (MD5) Previous issue date: 2002 / Resumo: Sistemas de chave pública tem sua segurança depositada sobre um problema matemático unanimemente considerado difícil pela comunidade científica. De modo geral, a dificuldade do problema cresce exponencialmente no número de bits das chaves utilizada por tal sistema. Sistemas criptográficos baseados em curvas elípticas, propostos em 1985 a partir de idéias matemáticas conhecidas desde o século XIX, são sistemas que permitem que níveis desejáveis de segurança sejam obtidos com valores muito pequenos de chave, quando comparados com outros sistemas de chave pública como RSA e ElGamal. Por isso, eles têm despertado um progressivo interesse, especialmente para aplicações com sérias restrições de recurso, tal como é o caso de smart cards, handhelds, telefones celulares, aplicações web, etc. Nesta dissertação, apresentamos e discutimos cada um dos elementos que compõem um sistema criptográfico baseado em curvas elípticas, dando ênfase na descrição detalhada dos critérios de seleção de um conjunto de algoritmos eficientes para as operações aritméticas envolvidas, a partir de diversas contribuições na literatura relacionada. Também descrevemos cada um dos passos de nossa implementação de um ECC completo e analisamos os resultados finais obtidos a partir desta implementação / Mestrado / Mestre em Ciência da Computação

Orientador: Flavio Keidi Miyazawa / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-04T11:49:51Z (GMT). No. of bitstreams: 1 Bracht_EvandroCesar_M.pdf: 694440 bytes, checksum: b7f0c4ac260849f98329f238c91ec2bd (MD5) Previous issue date: 2004 / Resumo: Em um problema de classificação tradicional temos um conjunto de n objetos e um conjunto de m classes e queremos classificar cada objeto como pertencente a uma classe, de modo que esta classificação seja consistente com alguns dados que temos sobre o problema. Este trabalho apresenta um estudo do problema de classificação métrica através de algoritmos aproximados. Os algoritmos aproximados conhecidos para este problema são baseados na solução de grandes programas lineares e são impraticáveis para instâncias de tamanho moderado e grande. Apresentamos um algoritmo 8 log n-aproximado, analisado pela técnica primal-dual, que apesar de possuir fator de aproximação maior que os algoritmos anteriores, pode ser aplicado a grandes instâncias. Mostramos também que este fator de aproximação é justo, exceto por um fator constante. Obtivemos resultados experimentais usando instâncias geradas computacionalmente e instâncias de processamento de imagens com o novo algoritmo e com outros dois algoritmos baseados na resolução de programas lineares. Para estas instâncias o algoritmo proposto apresentou soluções de boa qualidade com um ganho considerável no tempo computacional / Abstract: In a traditional classification problem, we have a set of n objects and a set of m labels (or classes). We wish to assign one of m labels (or classes) to each one of n objects, in a way that is consistent with some observed data that we have about the problem. In this work we present a study of approximation algorithms for the metric labeling problem. The known approximation algorithms for this problem are based on solutions of large linear programs and are impractical for moderate and large size instances. We present an 8 log n-approximation algorithm analyzed by a primal-dual technique which, although has a factor greater than the previous algorithms, can be applied to large sized instances. We also show that the analysis is tight, up to a constant factor. We obtained experimental results on computational generated and image processing instances with the new algorithm and two other LP-based approximation algorithms. For these instances our algorithm presents good quality solutions with a considerable gain of computational time / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

Esta tese apresenta a formulação de uma extensão da tabela de decisão adaptativa, denominada Tabela de Decisão Adaptativa Estendida (TDAE), que tem por objetivo apoiar aplicações de tomada de decisão multicritério. É implementado um algoritmo de tomada de decisão para a TDAE que incorpora os mecanismos de tabelas de decisão tradicionais, técnicas adaptativas e procedimentos de métodos multicritério. A descrição e execução do algoritmo e a aplicabilidade da TDAE em problemas de decisão multicritério são mostradas numa aplicação particular. É apresentada uma avaliação de desempenho do algoritmo de decisão, em relação ao custo de tempo e de memória exigidos para a sua execução. Uma ferramenta de apoio à decisão baseada na TDAE é descrita e implementada. Os resultados do trabalho mostram que a TDAE é viável e pode ser uma opção alternativa de dispositivo para apoiar processos decisórios de problemas de decisão multicritério. / This thesis presents the formulation of an extension of the adaptive decision table called Table of Extended Adaptive Decision (TDAE), which aims at supporting applications of multicriteria decision making. A decision making algorithm is implemented for the TDAE embodying the traditional decision tables mechanisms, adaptive techniques, and multicriteria methods procedures. The description and implementation of the algorithm and the applicability of TDAE in multicriteria decision problems are shown in a particular application. A perform evaluation of the decision algorithm is presented in relation to time and memory costs required for its implementation. A tool for decision support based on TDAE is described and implemented. The results of the study show that TDAE is viable and can be a device alternative option to support the decision making problems of multicriteria decision.

Este trabalho apresenta um estudo sobre a razão assintótica de pior caso para alguns algoritmos aproximados utilizados para solucionar o problema de Bin Packing unidimensional ( BPP). Este é um problema clássico de otimização combinatória que serve de modelo para uma série de problemas que ocorrem no mundo real. No BPP, dada uma lista com n itens de tamanhos no intervalo (0,

Esta tese de mestrado se propõe a resolver alguns problemas interessantes na área de Computação e Matemática, utilizando técnicas de Análise Combinatória, Teoria dos Grafos, Funções Geratrizes, Programação Dinâmica e Álgebra Linear. No decorrer da tese são abordados 3 problemas cujas soluções apresentam enfoque original, sob o ponto de vista da Teoria da Computação. O primeiro problema é o problema de Ulam (no capítulo referente a este problema, um novo algoritmo heurístico que interpreta o papel de um dos jogadores é apresentado). O segundo problema trata da contagem do número de matrizes de sinais alternantes e o último problema trata da contagem do número recobrimentos por dominós de uma dada figura plana (ou pareamentos perfeitos em grafos bipartidos).

O processo de avaliação e seleção de um modelo de processo para desenvolvimento de software não é uma tarefa simples. Envolve experiências dos desenvolvedores, identificação das reais necessidades, conhecimento suficiente do modelo de processo e estudo das alternativas para tomar uma decisão. A elaboração deste trabalho tem por objetivo proporcionar alguma forma de ajuda aos desenvolvedores na tarefa de avaliar e selecionar um modelo de processo específico. A seguinte contribuição é alcançada: uma análise de informações a respeito dos modelos de processo, uma análise sobre as organizações que os utilizam e um esquema para seleção que possibilita a geração de alternativas, baseadas nas informações colhidas e analisadas, de introdução dos modelos de processo no desenvolvimento de softwares aeroespaciais. A criação de um esquema para seleção de modelos de processo de desenvolvimento de software envolve um conjunto extenso de informações, experiências e percepções. Este trabalho tratará parte deste universo, modelando essas informações, proporcionando um conjunto de alternativas e sugestões para dar subsídios aos desenvolvedores de softwares aeroespaciais, para a decisão final sobre o uso dos modelos de processo selecionados.

Este trabalho propõe o estudo dos espaços coerentes do ponto de vista da teoria dos topos, ou seja, consiste em uma análise, em termos de topos, das principais categorias de espaços coerentes. Os espaços coerentes constituem um tipo de domínio que apresenta algumas particularidades que o distinguem dos demais, por exemplo, considera admissíveis no conjunto de funções somente aquelas que, além de contínuas no sentido de Scott - preservam supremos de conjuntos dirigidos, também são estáveis e lineares. Um topos e uma categoria Cartesiana fechada com classificador de subobjetos. Isso faz com que todo topos se comporte como Set (conjuntos como objetos e funções como morfismos), ou seja, uma categoria na qual as interpretações de suas construções básicas seguem a Teoria dos Conjuntos. Entre as categorias de Espaços Coerentes, tem-se a categoria STAB, cujos objetos são os espaços coerentes e os morfismos são funções estáveis entre esses espaços, que é uma categoria cartesiana fechada. Isto significa que STAB é uma categoria especial no sentido computacional: além de possuir o produto binário para todos os seus objetos, STAB apresenta objeto exponencial e morfismo de avaliação, garantindo significado para processos computacionais. A subcategoria LIN da categoria STAB, cujos morfismos são as funções lineares, não é uma categoria cartesiana fechada. Entretanto, LIN é uma categoria monoidal simétrica que e fechada. Este, condição e suficiente para que em LIN também se tenha a garantia de se obter significado para processos computacionais. Apresenta-se então, uma interpretação computacional da estrutura destas categorias e uma análise das mesmas do ponto de vista de topos, isto é, da existência ou não de classificador de subobjetos. / This work proposes the study of coherent spaces from the point of view of the Topos Theory, that is, it consists of an analysis of the main categories of coherent spaces in terms of topos. The coherent spaces make up a kind of domain which presents some peculiarities that separate it from the rest, for example, in the complex whole of the functions it only considers permissible, those which, apart from being continuous in the sense of Scott - preserving supremo of directed sets, it is also stable and linear. A topos is a Cartesian closed with subobject classifier. This makes topos behaves like Set (sets as objects and functions as morphisms), that is, a category in which the interpretations of its basic constructions follow the Theory of Sets. Among the categories of Coherent Spaces, there is the STAB category, a closed Cartesian category, the objects of which are the coherent spaces, having morphisms as stable functions among these spaces. This means that STAB is a special category in the computational sense: apart from having a binary product for all its objects, STAB presents an exponential object and a morphism of evaluation, ensuring meaning for computational processes. The subcategory LIN of the STAB category, the morphisms of which are linear functions, is not a closed Cartesian category. However, LIN is a symmetrical monoidal category which is closed. This condition is sufficient to also have in LIN the guarantee of obtaining meaning for computational processes. Thus, a computational interpretation of the structure of these categories will be presented, as well as an analysis of them from the point of view of the Topos Theory, that is, if subobject classifier exists or not.