Doutorado em Ciência da Computação

Atenção! O edital referente ao processo seletivo e arquivos pertinentes ao curso estão disponíveis no site do curso.
Os resultados dos processos seletivos serão divulgados no site do curso.

Trabalhos

Trabalhos Disponíveis

TRABALHO Ações
Programação de Espaços Inteligentes Utilizando Modelos em Tempo de Execução
Curso Doutorado em Ciência da Computação
Tipo Tese
Data 04/04/2017
Área CIÊNCIA DA COMPUTAÇÃO
Orientador(es)
  • Fabio Moreira Costa
Orientando(s)
  • Leandro Alexandre Freitas
Banca
  • Arlindo Flávio da Conceição
  • Fabio Moreira Costa
  • Fabrizzio Alphonsus Alves de Melo Nunes Soares
  • Francisco José da Silva e Silva
  • Jó Ueyama
  • Ricardo Couto Antunes da Rocha
  • Ronaldo Alves Ferreira
Resumo O crescimento e a popularização cada vez maior da conectividade sem fio e dos dispositivos móveis, tem permitido a construção de espaços inteligentes que antes eram vislumbrados apenas na proposta de computação ubíqua do cientista da Xerox PARK, Mark Weiser. Esses espaços inteligentes são compostos por diversos recursos computacionais, como dispositivos, serviços e aplicações, além de usuários, que devem ser capazes de se associar a esses recursos. Entretanto, a programação destes ambientes é uma tarefa desafiadora, uma vez que os espaços inteligentes possuem uma natureza dinâmica, os recursos se apresentam de forma heterogênea e é necessário que as interações entre usuários e dispositivos sejam coordenadas. Neste trabalho desenvolvemos uma nova abordagem para programação de espaços inteligentes, por meio de modelos em tempo de execução. Para isso, propomos uma linguagem de modelagem de alto nível, denominada Smart Space Modeling Language (2SML), em que o usuário é capaz de modelar o espaço inteligente com todos os elementos que dele podem fazer parte. Esse modelo desenvolvido pelo usuário é interpretado e realizado no espaço físico por uma máquina de execução de modelos, denominada Smart Space Virtual Machine (2SVM), cujo desenvolvimento é parte deste trabalho.
Download
Novas Abordagens de Aprendizado Semisupervisionado por Conectividade Ótima
Curso Doutorado em Ciência da Computação
Tipo Tese
Data 19/12/2016
Área CIÊNCIA DA COMPUTAÇÃO
Orientador(es)
  • Marcelo Henriques de Carvalho
Orientando(s)
  • Willian Paraguassu Amorim
Banca
  • Alexandre Xavier Falcão
  • Bruno Magalhaes Nogueira
  • Edson Takashi Matsubara
  • Flávio Keidi Miyazawa
  • Hemerson Pistori
  • Marcelo Henriques de Carvalho
  • Moacir Antonelli Ponti
Resumo A anota¸c˜ao de grandes bases de dados por um classificador ´e um problema cujo desafio
aumenta `a medida que o n´umero de amostras supervisionadas usadas para treinar o classificador reduz em compara¸c˜ao com o n´umero de amostras n˜ao supervisionadas. Neste
contexto, m´etodos de aprendizagem semisupervisionados visam a descoberta e propaga¸c˜ao
de r´otulos para amostras informativas entre as n˜ao supervisionadas, de tal forma que a
sua adi¸c˜ao `a classe correta no conjunto de treinamento possa melhorar o desempenho de
classifica¸c˜ao. Esta tese de doutorado apresenta uma s´erie de novas abordagens de aprendizado semisupervisionado com base na metodologia adotada por Floresta de Caminhos
´ Otimos (OPF). Esta metodologia interpreta o problema de reconhecimento de padr˜oes
como um problema de busca em grafo, onde os n´os s˜ao amostras de treinamento, os arcos s˜ao definidos por uma dada rela¸c˜ao de adjacˆencia, e os caminhos s˜ao avaliados por
alguma fun¸c˜ao de conectividade. N´os prot´otipos s˜ao identificados entre as amostras de
treinamento e a competi¸c˜ao entre eles faz com que cada amostra seja conquistada (rotulada) pelo prot´otipo que lhe oferece um caminho ´otimo. O resultado ´e um classificador —
floresta de caminhos ´otimos enraizado no conjunto de prot´otipos. Classificadores podem
ser criados por uma ou m´ultiplas execu¸c˜oes do algoritmo OPF para diferentes grafos e
fun¸c˜oes de conectividade. Apresentamos duas abordagens (OPFSEMI e OPFSEMImst)
para o problema de r´otulo ´unico, que diferem entre si em rela¸c˜ao aos prot´otipos finais
e ao n´umero de execu¸c˜oes do algoritmo OPF. Tamb´em propomos uma abordagem semisupervisionada mais adequada para o problema multir´otulos do que as anteriores. Este ´e
um problema desafiador, especialmente quando a solu¸c˜ao adota a transforma¸c˜ao de dados
de multir´otulos em dados de r´otulo ´unico, o que pode afetar o desempenho na fronteira
entre classes. Para resolver este problema, melhoramos a atribui¸c˜ao de multit´otulos adicionando uma etapa final no processo de treinamento de OPFSEMImst. O m´etodo, chamado
OPFSEMImst+knn, cria uma floresta de caminhos ´otimos enraizada nos m´aximos de uma
fun¸c˜ao de densidade de probabilidade, estimada a partir de um grafo k-NN. Finalmente,
propomos uma abordagem de aprendizagem ativa baseada em OPFSEMImst (OPFSEMI).
O m´etodo seleciona amostras informativas para a supervis˜ao de especialistas, de modo
que o n´umero de itera¸c˜oes no aprendizado ativo (esfor¸co do usu´ario) ´e reduzido.
Download
Application of GPU Computing to Urban Traffic Problems
Curso Doutorado em Ciência da Computação
Tipo Tese
Data 30/11/2016
Área CIÊNCIA DA COMPUTAÇÃO
Orientador(es)
  • Hugo Alexandre Dantas do Nascimento
Orientando(s)
  • Walid Abdala Rfaei Jradi
Banca
  • Eduardo Camponogara
  • Esteban Walter Gonzalez Clua
  • Fabio Moreira Costa
  • Henrique Mongelli
  • Hugo Alexandre Dantas do Nascimento
  • Ricardo Couto Antunes da Rocha
  • Wellington Santos Martins
Resumo O presente trabalho estuda e propõe algoritmos e implementações paralelas baseadas
em GPU para o problema de alocação macroscópica de tráfego urbano em redes de
grande porte, promovendo uma investigação aprofundada de cada sub-problema que deve
ser resolvido de forma eficiente durante o processo de atribuição de tráfego. Entre as
principais contribuições deste trabalho, estão: 1) o primeiro algoritmo baseado em GPU
para a enumeração de ciclos sem corda; 2) um novo algoritmo de caminho mínimo
paralelo que tira vantagem de algumas propriedades comuns das redes de tráfego urbano;
Um refinamento na implementação de redução paralela proposta por um dos líderes
no mercado de GPU, o que resultou em uma aceleração de 2,8x em relação à sua
versão original; 3) e, finalmente, um algoritmo paralelo para o problema de alocação
macroscópica de tráfego, 39x mais rápido do que a abordagem equivalente sequencial
quando aplicado a redes de larga escala.
O objetivo principal desta tese é de contribuir para a expansão do software PET-Gyn, propondo estruturas de dados de GPU eficientes e algoritmos paralelos para uma resolução
mais rápida de dois problemas bem conhecidos na literatura: O Problema de Alocação
de Tráfego e a Enumeração de Ciclos sem Corda. Quando aplicados a conjuntos de entrada difíceis, os experimentos realizados mostraram uma clara vantagem dos algoritmos
paralelos sobre suas versões sequenciais.
Download
Alocação de Recursos em Redes sem Fio OFDM Multiusuário Utilizando Modelagem Multifractal Adaptativa
Curso Doutorado em Ciência da Computação
Tipo Tese
Data 22/11/2016
Área CIÊNCIA DA COMPUTAÇÃO
Orientador(es)
  • Flávio Henrique Teles Vieira
Orientando(s)
  • Flávio Geraldo Coelho Rocha
Banca
  • Flávio Henrique Teles Vieira
  • Kleber Vieira Cardoso
  • Lee Luan Ling
  • Rodrigo Pinto Lemos
  • Sibelius Lellis Vieira
  • Vinicius da Cunha Martins Borges
Resumo Neste trabalho, com o objetivo de descrever características do tráfego de redes, tais como longa-dependência entre amostras, autossimilaridade e comportamento multiescala, propõe-se um Modelo Multifractal Adaptativo baseado em uma cascata multiescala no domínio Wavelet. O desempenho do modelo proposto é comparado a outros modelos presentes na literatura. Também é proposto um processo envelope para o tráfego de redes
que leva em consideração parâmetros do Modelo Multifractal Adaptativo proposto. Além disso, deduz-se uma equação para o cálculo da probabilidade de transbordo do buffer, tanto para um sistema de comunicação simplificado com servidor único, fila única e buffer finito, quanto para um ambiente multiusuário de rede sem fio baseado na tecnologia OFDM. Para tanto, utiliza-se a curva de serviço do escalonador round-robin da rede OFDM. Utilizando-se do processo envelope e da curva de serviço, obtém-se por meio do Cálculo de Rede a estimativa para o retardo máximo experimentado pelos usuários da rede OFDM. Em seguida, assume-se um ambiente de rede similar ao de uma rede LTE e propõe-se para essa rede um escalonador de recursos sensível às condições do canal de comunicação e à probabilidade de transbordo do buffer. Com base no escalonador apresentado, propõe-se uma curva de serviço mínima para o usuário da rede LTE e por meio dessa, propõe-se uma abordagem para garantia de retardo.
Definitividade de Formas Quadráticas – Uma Abordagem Polinomial
Curso Doutorado em Ciência da Computação
Tipo Tese
Data 18/11/2016
Área CIÊNCIA DA COMPUTAÇÃO
Orientador(es)
  • Diane Castonguay
Orientando(s)
  • Jesmmer da Silveira Alves
Banca
  • André da Cunha Ribeiro
  • Carmen Centeno
  • Diane Castonguay
  • Edson Ribeiro Alvares
  • Fabio Henrique Viduani Martinez
  • Humberto José Longo
Resumo Formas quadráticas são expressões algébricas que têm papel importante em diferentes áreas da ciência da computação, matemática, física, estatística e outras. Abordamos nesta tese formas quadráticas racionais e formas inteiras, com coeficientes racionais e inteiros respectivamente. Os métodos existentes para reconhecimento de formas quadráticas racionais têm complexidade de tempo exponencial ou usam aproximações que deixam o resultado menos confiável. Apresentamos um algoritmo polinomial que aprimora o melhor caso do reconhecimento de formas quadráticas para tempo constante. Ainda mais, novas estratégias foram usadas para garantir a confiabilidade dos resultados, representando números racionais como frações de inteiros, e para identificar combinações lineares que são linearmente independentes, usando a redução de Gauss. Sobre o reconhecimento de formas inteiras, identificamos que os algoritmos existentes têm complexidade de tempo exponencial para o tipo fracamente não-negativa e polinomial para o tipo fracamente positiva. No entanto, o grau do polinômio depende da dimensão da álgebra e pode ser muito grande. Apresentamos um algoritmo polinomial para o reconhecimento de formas inteiras fracamente positivas. Este algoritmo identifica restrições hipercríticas avaliando todo subgrafo com 9 vértices do grafo associado à forma inteira. Através da busca em profundidade, uma estratégia similar pôde ser usada no reconhecimento do tipo fracamente positiva. Por fim, mostramos que o reconhecimento de formas inteiras pode ser feito através de mutações na matriz de troca relacionada.
Download
Construção de Visualização de Matrizes Origem-Destino no Cenário do Tráfego Urbano com Foco em Avaliação de Usabilidade
Curso Doutorado em Ciência da Computação
Tipo Tese
Data 29/09/2016
Área CIÊNCIA DA COMPUTAÇÃO
Orientador(es)
  • Hugo Alexandre Dantas do Nascimento
Orientando(s)
  • Halley Wesley Alexandre Silva Gondim
Banca
  • Carla Maria Dal Sasso Freitas
  • Eduardo Simões de Albuquerque
  • Fabrizzio Alphonsus Alves de Melo Nunes Soares
  • Hugo Alexandre Dantas do Nascimento
  • JUNIA COUTINHO ANACLETO
  • Maria Cristina Ferreira De Oliveira
Resumo
Download
Metaheurísticas para o Problema da Mochila Multidimensional
Curso Doutorado em Ciência da Computação
Tipo Tese
Data 22/08/2016
Área CIÊNCIA DA COMPUTAÇÃO
Orientador(es)
  • Edson Norberto Caceres
Orientando(s)
  • Bianca de Almeida Dantas
Banca
  • Edna Ayako Hoshino
  • Edson Norberto Caceres
  • Henrique Mongelli
  • Luiz Satoru Ochi
  • Paulo Aristarco Pagliosa
  • Simone de Lima Martins
Resumo O problema da mochila multidimensional é amplamente conhecido na área de otimização combinatória e possui diversas aplicações práticas, tais como, dimensionamento de cargas, orçamento de capital, alocação de recursos em sistemas distribuídos, entre outros. Apesar de sua popularidade, sua solução não é trivial, de fato, ele pertence a uma classe de problemas conhecidos como NP-difíceis, para os quais não são conhecidos algoritmos polinomiais capazes de obter uma solução exata para todas as instâncias. Essa situação motiva a busca por técnicas alternativas para obter soluções em menor tempo, ainda que aproximadas e, nesse cenário, as metaheurísticas têm se mostrado de especial interesse, pois são capazes de alcançar soluções de boa qualidade para uma ampla variedade de problemas. Entretanto, mesmo as metaheurísticas podem ser relativamente demoradas, em especial para instâncias de tamanho grande, o que encoraja a aplicação de técnicas, como as estratégias de paralelização, para reduzir os seus tempos de execução ou, ainda, melhorar a qualidade das soluções. Neste trabalho, apresenta-se o estudo, implementação e análise de um conjunto de metaheurísticas para a solução do problema da mochila multidimensional. São apresentadas e avaliadas diferentes alternativas para a paralelização e os resultados obtidos são comparados com os de outros trabalhos da literatura pesquisada. Para comprovar que os bons resultados possibilitados pelo uso das metaheurísticas estudadas não foram obtidos ao acaso, as soluções foram validadas com a utilização de testes estatísticos.
Download
Estudo, Definição e Proposta de Representação de Interface Web Visando à Atividade de Teste de Software
Curso Doutorado em Ciência da Computação
Tipo Tese
Data 01/04/2016
Área CIÊNCIA DA COMPUTAÇÃO
Orientador(es)
  • Auri Marcelo Rizzo Vincenzi
Orientando(s)
  • Rodrigo Funabashi Jorge
Banca
  • Andrea Padovan Jubileu
  • Auri Marcelo Rizzo Vincenzi
  • Cássio Leonardo Rodrigues
  • Celso Gonçalves Camilo Junior
  • Celso Socorro Oliveira
  • Plínio de Sá Leitão Júnior
Resumo O objetivo principal da Engenharia de Software é dar subsídios para desenvolvimento de software, desde a sua especificação até sua implantação e manutenção, aplicando métodos, processos e ferramentas, buscando uma maior qualidade no software produzido. Uma das atividades para se buscar a qualidade desejada é a atividade de teste de software. Essa atividade pode se tornar bastante complexa, dependendo das características e dimensões do produto de software a ser desenvolvido e, desse modo, está sujeita a diversos tipos de problemas que acabam resultando na obtenção de um produto com defeitos, prejudicando assim a qualidade do mesmo. Apesar da complexidade e das limitações existentes, encontram-se na literatura diferentes técnicas que podem ser utilizadas para gerar dados de teste para satisfazer os diversos critérios de teste de software existentes, procurando assim reduzir o custo dos testes. Porém, a geração de dados de teste é um problema indecidível, devido à complexidade e o tamanho de programas. Um dos fatores que aumentam a complexidade é o uso de interfaces do usuário (UI – User Interfaces), presentes em muitas aplicações. Essa complexidade é resultante do elevado número de combinações de entrada disponível, tornando praticamente impossível realizar os testes UI de forma manual. Dentre as alternativas que viabilizam a automatização uma das mais reconhecidas e vantajosas é o teste de UI baseado em modelos. Esta técnica passa pela construção de um modelo a partir da estrutura da interface da aplicação a ser testada e os dados de teste são gerados a partir desse modelo. Porém, um fator problemático desta abordagem reside na construção do modelo. Este processo pode ser demorado e dispendioso e, em alguns casos, pode ser bastante complicado e não atingir um objetivo satisfatório por não conseguirem representar, por meio do modelo proposto, características reais da aplicação. Ao estudar o estado da arte de teste UI, observou-se que existem ferramentas que permitem realizar tais testes automaticamente, mas essas ainda possuem algumas limitações, principalmente decorrentes do modelo de representação da interface adotado por elas.
Desse modo, a proposta dessa tese é propor um modelo de representação de UI que traga benefícios em relação às representações hoje existentes na literatura. Com a proposta deste modelo é possível representar com o maior nível de detalhes uma interface gráfica para aplicações de software. Um estudo preliminar, comparando o modelo proposto com outros disponíveis na literatura, evidencia os benefícios alcançados.
Download
A Method for Selecting Components to Design Unit Testing Based on Multiobjective Real Context
Curso Doutorado em Ciência da Computação
Tipo Tese
Data 15/02/2016
Área CIÊNCIA DA COMPUTAÇÃO
Orientador(es)
  • Auri Marcelo Rizzo Vincenzi
Orientando(s)
  • Eduardo Noronha de Andrade Freitas
Banca
  • Arilo Cláudio Dias Neto
  • Auri Marcelo Rizzo Vincenzi
  • Cássio Leonardo Rodrigues
  • Fabiano Cutigi Ferrari
  • Plínio de Sá Leitão Júnior
  • Sandra Camargo Pinto Ferraz Fabbri
Resumo A seleção combinada de algumas unidades de código para o desenvolvimento de testes unitários é um elemento desafiador para a comunidade de teste, principalmente no contexto de sistemas legados. A característica combinatorial desta seleção é caracterizada como um problema NP-Difícil, especialmente para sistemas de médio e grande porte.Nesse sentido, o Teste de Software Baseado em Busca (SBST do inglês) torna-se o alvo
central de investigação deste trabalho de doutorado, especialmente, por meio do emprego de abordagem evolucionária multiobjetivo para priorização de artefatos para o emprego de testes unitários. O objetivo é priorizar as unidades do código de modo que aquelas que apresentarem maiores chances de, se testadas primeiro, maximizarem a detecção de defeitos em menor tempo, apareçam primeiro na listagem das unidades priorizadas. Além do número de defeitos e tempo requerido para teste, outras variáveis, tais como complexidade, frequência de mudanças, dentre outras, devem ser consideradas. A existência de objetivos conflitantes caracterizam o problema como multi-objetivo. Experimentos com cenários reais da indústria de software foram desenvolvidos, inicialmente com a aplicação de um algoritmo genético monoobjetivo, buscando verificar a aplicabilidade de heurísticas
evolucionárias neste contexto, e também a investigação inicial das métricas a serem aplicadas e seu processo de automatização.
Download
SOLUÇÕES PARA OS PROBLEMAS DA SOMA MÁXIMA E DO K-ÉSIMO MENOR ELEMENTO DE UMA SEQUÊNCIA USANDO O MODELO BSP/CGM
Curso Doutorado em Ciência da Computação
Tipo Tese
Data 15/12/2015
Área CIÊNCIA DA COMPUTAÇÃO
Orientador(es)
  • Edson Norberto Caceres
Orientando(s)
  • Anderson Corrêa de Lima
Banca
  • Edson Norberto Caceres
  • Fabio Henrique Viduani Martinez
  • Hemerson Pistori
  • Nalvo Franco de Almeida Junior
  • Philippe Olivier Alexandre Navaux
  • Siang Wun Song
  • Wellington Santos Martins
Resumo Neste trabalho são propostos algoritmos paralelos para os seguintes problemas: a subsequência de soma máxima, a submatriz de soma máxima, o hiper-retângulo de soma máxima e a seleção do k-ésimo menor elemento de um sequência não ordenada. Todos os problemas tratados possuem aplicações em diversas áreas da ciência, com destaque para biologia computacional, visão computacional, análise de volumes rochosos e de ordem. No projeto de nossos algoritmos adotamos uma extensão do modelo BSP/CGM de computação paralela e mostramos que, além do ambiente de memória distribuída, o modelo BSP/CGM também pode ser utilizado em arquiteturas com memória compartilhada e com múltiplos núcleos, tais como as GPUs. Diferentemente de soluções anteriores, nossos algoritmos e implementações utilizam novas estratégias na solução de cada problema. Apresentamos algoritmos paralelos para subproblemas relacionados ao problema da soma máxima, para os quais, de acordo com o nosso melhor conhecimento, a literatura não apresenta soluções no modelo BSP/CGM. As implementações
foram construídas utilizando CUDA, MPI e OpenMP. Por fim, destacamos que nossos algoritmos são competitivos, quando comparados com as respectivas soluções sequenciais e paralelas já existentes.
Download
Sobre Alianças Defensivas e Ofensivas Globais em Alguns Produtos de Grafos Simpliciais
Curso Doutorado em Ciência da Computação
Tipo Tese
Data 30/10/2015
Área CIÊNCIA DA COMPUTAÇÃO
Orientador(es)
  • Rommel Melgaço Barbosa
Orientando(s)
  • Leila Roling Scariot da Silva
Banca
  • Fernando Marques Federson
  • José Plínio de Oliveira Santos
  • Mitre Costa Dourado
  • Robson Silva
  • Rommel Melgaço Barbosa
  • Thierson Couto Rosa
Resumo A aliança é um conceito introduzido por Hedetniemi, Hedetniemi e Kristiansen em 2004, onde foram classificadas em defensiva, ofensiva ou poderosa. Informalmente, podemos entender uma aliança como uma coleção de entidades tal que a união é mais forte do que o indivíduo. Uma aliança, de qualquer entidade, pode tanto servir para proteção contra ataques, quanto para aumentar a capacidade para atacar outras entidades. Toda aliança é global se for um conjunto dominante. A complexidade computacional e aplicações para a defesa nacional, redes de computadores, distribuição computacional e redes sociais são exemplos que motivam os estudos sobre alianças em grafos. Neste trabalho nós lidamos com alguns limites e fórmulas fechadas de algumas famílias de produto lexicográfico para obter o número mínimo da aliança defensiva global e aliança ofensiva global e apresentamos uma relação entre grafos gerais e sua aliança defensiva global para prisma complementar, bem como obtivemos limites para algumas famílias de grafos como grafos simplicias.
Reconhecimento polinomial de álgebras cluster de tipo finito
Curso Doutorado em Ciência da Computação
Tipo Tese
Data 09/09/2015
Área CIÊNCIA DA COMPUTAÇÃO
Orientador(es)
  • Diane Castonguay
Orientando(s)
  • Elisângela Silva Dias
Banca
  • Diane Castonguay
  • Humberto Josè Longo
  • Marcelo Henriques de Carvalho
  • Mitre Costa Dourado
  • Raff Schiffler
Resumo As álgebras cluster formam uma classe de álgebras comutativas introduzida no início do milênio por Fomin e Zelevinsky. Elas são definidas de forma construtiva a partir de um conjunto de variáveis geradoras (variáveis cluster) agrupadas em subconjuntos sobrepostos (clusters) de cardinalidade fixa. Desde a sua criação, a teoria das álgebras cluster encontrou aplicações em diversas áreas da matemática e afins. Nesta tese, estudamos, com foco computacional, o reconhecimento das álgebras cluster de tipo finito. Em 2006, Barot, Geiss e Zelevinsky mostraram que uma álgebra cluster é de tipo finito se o grafo associado é ciclicamente orientado, isto é, todos os ciclos sem corda do grafo são ciclicamente orientados, e se a matriz antissimetrizável associada possui uma companheira quase-Cartan positiva. Em um primeiro momento, estudamos os dois tópicos de forma independente. Em relação à primeira parte do critério, elaboramos um algoritmo que lista todos os ciclos sem corda (polinomial no tamanho destes ciclos) e outro que verifica se um grafo é ciclicamente orientado e, em caso positivo, lista todos os seus ciclos sem corda (polinomial na quantidade de vértices). Relacionado à segunda parte do critério, desenvolvemos alguns resultados teóricos e elaboramos um algoritmo polinomial que verifica se uma matriz companheira quase-Cartan é positiva. Este último algoritmo é utilizado para provar que o problema de decidir se uma matriz antissimetrizável tem uma companheira quase-Cartan positiva para grafos gerais está na classe NP. Conjecturamos que este problema pertence à classe NP-completa. Mostramos que o mesmo pertence à classe de problemas polinomiais para grafos ciclicamente orientados e, por fim, mostramos que decidir se uma álgebra cluster é de tipo finito também pertence a esta classe.
Download
Pipelines automatizados para genômica e transcritômica
Curso Doutorado em Ciência da Computação
Tipo Tese
Data 29/07/2015
Área CIÊNCIA DA COMPUTAÇÃO
Orientador(es)
  • Nalvo Franco de Almeida Junior
Orientando(s)
  • Christiane Nishibe
Banca
  • Edson Norberto Caceres
  • Flábio Ribeiro de Araújo
  • Marcelo de Macedo Brígido
  • Maria Emilia Machado Telles Walter
  • Nalvo Franco de Almeida Junior
  • Tainá Raiol Alencar
Resumo Avanços das tecnologias de genômica e transcritômica resultaram no aumento expressivo do volume de sequências geradas, tornando indispensável o uso de técnicas e ferramentas computacionais para analisar os dados e produzir uma melhor caracterização e compreensão dos organismos estudados. Entretanto, o grande número de programas disponíveis e a variedade de formatos de dados produzidos dicultam a escolha do conjunto de softwares apropriados para cada análise. Este trabalho apresenta pipelines automatizados para análises genômicas e transcritômicas. O primeiro objetiva a construção de contigs de bactérias, a partir de reads paired-end, a serem posteriormente anotados e analisados por um conjunto de programas que investigam diferentes aspectos do genoma. Esse pipeline foi utilizado para um conjunto de cepas de interesse da bactéria Mycobacterium bovis. Os resultados gerados propiciaram relevantes avanços no grande objetivo do projeto de genômica de M. bovis, que é a erradicação da Tuberculose Bovina, doença causada por essa bactéria, incluindo a determinação de um método mais eciente para o diagnóstico da doença. O segundo pipeline visa determinar genes diferencialmente expressos entre diferentes amostras que possuem replicatas, tendo como estudos de caso três projetos de transcritoma, dois envolvendo linfócitos T humanos e um envolvendo células de camundongo sob efeito de infecção causada por fungo. Ambos os pipelines foram desenvolvidos com o objetivo de minimizar a participação do usuário nos passos intermediários e também minimizar a exigência de experiência no uso dos pacotes eprogramas utilizados.
Download
Sobre convexidade em prismas complementares
Curso Doutorado em Ciência da Computação
Tipo Tese
Data 10/04/2015
Área CIÊNCIA DA COMPUTAÇÃO
Orientador(es)
  • Rommel Melgaço Barbosa
Orientando(s)
  • Márcio Antônio Duarte
Banca
  • Carla Silva Oliveira
  • Erika Morais Martins Coelho
  • Hebert Coelho da Silva
  • Horácio Hideki Yanasse
  • Jayme Luiz Szwarcifiter
  • Rommel Melgaço Barbosa
Resumo Neste trabalho, apresentamos alguns resultados relacionados, principalmente às propriedades algorítmicas e de complexidade de um produto de grafos chamado prisma complementar. Respondendo algumas questões deixadas em aberto por Haynes, Slater e vander Merwe, mostramos o problema de clique, conjunto independente e conjunto com kdominantes é NP-Completo para prismas complementares em geral. Além disso, mostramos resultados de NP-completude em relação ao cálculo de alguns parâmetros da convexidade P3 para o prisma complementar de grafos em geral, como o número P3, número envoltório P3 e número de Carathéodory. Mostramos que o cálculo do número P3 é NPcompleto para o prisma complementar de grafos em geral. Já para o número envoltório P3, mostramos que o mesmo pode ser calculado de forma eficiente em tempo polinomial. Para o número de Carathéodory, mostramos que é NP-completo para os prismas complementares de grafos bipartidos, mas que para árvores, este pode ser calculado em tempo polinomial e ainda, para classe dos cografos, o cálculo do número de Carathéodory do prisma complementar desses é 3. Encontramos também, uma relação entre a cardinalidade de um conjunto de Carathéodory de um grafo qualquer e um conjunto de Carathéodory do seu prisma complementar. Por fim, estabelecemos um limite superior do cálculo dos parâmetros: número geodésico, número envoltório e número de Carathéodory para operações prisma complementar de grafos caminho, ciclos e completos considerando as convexidades P3 e geodésica.
Download
Sobre Grafos com r Tamanhos Diferentes de Conjuntos Independentes Maximais e Algumas Extensões
Curso Doutorado em Ciência da Computação
Tipo Tese
Data 01/10/2014
Área CIÊNCIA DA COMPUTAÇÃO
Orientador(es)
  • Rommel Melgaço Barbosa
Orientando(s)
  • Márcia Rodrigues Cappelle Santana
Banca
  • Hebert Coelho da Silva
  • Humberto José Longo
  • José Plínio de Oliveira Santos
  • Nair Maria Maia de Abreu
  • Rommel Melgaço Barbosa
Resumo Nesta tese, apresentamos alguns resultados relativos, principalmente, aos tamanhos de conjuntos independentes maximais em alguns grafos. Mostramos que para inteiros r e D com r ≥ 2 e D ≥ 3, há um número finito de grafos conexos de grau mínimo pelo menos dois, grau máximo até D e cintura pelo menos sete que tem tamanhos de conjuntos independentes maximais de até r tamanhos diferentes. Além disso, provamos outros resultados que restringem os graus de tais grafos e que generalizam resultados já conhecidos sobre grafos bem-cobertos. Foram estudados a estrutura e o reconhecimento dos grafos bem-cobertos G de ordem n(G) sem vértice isolado que têm número de independência n(G)−k para algum inteiro não negativo k; Para k = 1, apresentamos uma descrição estrutural completa destes grafos e para um k geral, porém fixo, descrevemos um algoritmo de reconhecimento de tempo polinomial. Consideramos grafos G sem vértice isolado cuja diferença entre o maior e o menor conjuntos independentes maximais é no máximo k para algum inteiro k não negativo. Obtivemos um limite superior sobre o número de independência destes grafos. Apresentamos um algoritmo polinomial para reconhecimento de alguns produtos complementares, o qual inclui todos os prismas complementares. Apresentamos também alguns resultados sobre prismas complementares bem-cobertos. Mostramos que se G não é um grafo bem-coberto e seu prisma complementar é bem-coberto, então G tem somente dois tamanhos de conjuntos independentes maximais que são consecutivos. Apresentamos um limite superior para a quantidade de tamanhos de conjuntos independentes maximais em prismas complementares e também outros resultados relacionados à bem-cobertura. Para o produto Cartesiano do grafo Pn , o caminho de tamanho n, n ≥ 2 e Cm , o ciclo de tamanho m, m ≥ 3, denotado por Pn Cm e chamado de grade cilíndrica, apresentamos um limite inferior para a quantidade de tamanhos de conjuntos independentes maximais.
Download
Página 3 de 3 (15 de 55 registros).