| 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
|
| Coorientador(es) |
|
| 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
|
| Coorientador(es) |
|
| Orientando(s) |
|
| 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
|
| Coorientador(es) |
|
| 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) |
|
| Coorientador(es) |
|
| 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
|
| Coorientador(es) |
|
| 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 |
|
|
| Estimativas de Dark Silicon em Projetos de Sistemas Multicore |
|
| Curso |
Mestrado em Ciência da Computação |
| Tipo |
Dissertação |
| Data |
16/09/2016 |
| Área |
CIÊNCIA DA COMPUTAÇÃO |
| Orientador(es) |
- Ricardo Ribeiro dos Santos
|
| Coorientador(es) |
|
| Orientando(s) |
- Tony Carlos Bignardi dos Santos
|
| Banca |
- Edson Borin
- Fabio Iaione
- Liana Dessandre Duenha Garanhani
- Ricardo Ribeiro dos Santos
|
| Resumo |
A demanda por computação de alto desempenho continua a crescer de forma significativa. Apesar da indústria entregar aos consumidores sistemas computacionais mais eficientes, limitações físicas e restrições tecnológicas colocam em risco a evolução para as próximas gerações de processadores. O aumento exponencial de dissipação de potência estática devido ao incremento da corrente de fuga em transistores com escala de integração abaixo de 90nm limita a fração de área do circuito que se pode manter ativa no momento da execução O termo dark silicone utilizado para indicar a fração de área do chip que deve ter frequência de clock reduzida para manter restrições térmicas de potência do projeto. Algumas alternativas para contornar a necessidade de subutilizar uma parte da área do chip estão a adoção de hardware especializado e exploração de paralelismo. Essas alternativas possibilitam que uma parte da área do chip seja utilizada para execução de código em frequências menores visando não extrapolar o orçamento de potência. Observa-se assim a necessidade de técnicas e ferramentas para o projeto de sistemas cientes de dark silicon. Este trabalho tem como objetivo identificar e mensurar a área de dark silicon em projetos de sistemas computacionais com tecnologia abaixo de 90nm, utilizando-se de uma metodologia baseada no cálculo da densidade de potência de um projeto base (90nm) e da adoção de um circuito de referência. Experimentos foram realizados considerando projetos de processadores multicore comerciais para estimar o dark silicon presente nesses projetos considerando suas evoluções tecnológicas. Adicionalmente, um experimento de exploração do espaço de projeto foi realizado, com o intuito de validar as estimativas de dark silicon and buscar alternativas para utilização eficiente da área do chip diante das restrições físicas de projeto. |
| Download |
|
|
| Uma ferramenta para integração de dados de expressão diferencial e interação funcional |
|
| Curso |
Mestrado em Ciência da Computação |
| Tipo |
Dissertação |
| Data |
02/09/2016 |
| Área |
MATEMÁTICA DA COMPUTAÇÃO |
| Orientador(es) |
- Nalvo Franco de Almeida Junior
|
| Coorientador(es) |
|
| Orientando(s) |
- Rodolpho Gheleri de Oliveira Lima
|
| Banca |
- Luciana Montera Cheung
- Nalvo Franco de Almeida Junior
- Said Sadique Adi
- Tainá Raiol Alencar
|
| Resumo |
Este trabalho descreve o desenvolvimento de duas ferramentas computacionais: um pipeline para análise de expressão diferencial de genes e outra para a visualização gráfica de resultados de express~ao diferencial, chamada DEPICTViz, que agrega ao resultado da análise de expressão diferencial informacões de interação funcional de proteínas. O pipeline desenvolvido realiza o mapeamento de reads no genoma de referência, a ordenação dos reads mapeados, a construção e união de transcritos e a analise de expressão diferencial. A ferramenta DEPICTViz foi desenvolvida para a visualização de experimentos de expressão diferencial de genes e interação de
proteínas. DEPICTViz foi testada com sucesso em vários estudos de caso. |
| Download |
|
|
| Inferência de redes de regulação gênica a partir de dados de expressão gênica e conhecimento biológico a priori |
|
| Curso |
Mestrado em Ciência da Computação |
| Tipo |
Dissertação |
| Data |
23/08/2016 |
| Área |
CIÊNCIA DA COMPUTAÇÃO |
| Orientador(es) |
- Carlos Henrique Aguena Higa
|
| Coorientador(es) |
|
| Orientando(s) |
|
| Banca |
- Carlos Henrique Aguena Higa
- Leonardo Rippel Salgado
- Renato Porfirio Ishii
- Said Sadique Adi
|
| Resumo |
Neste trabalho, nós estudamos um problema comum na Biologia Sistêmica, o qual é a inferência ou engenharia reversa da rede de regulação gênica a partir de dados de expressão gênica. Nós endereçamos este problema usando o formalismo Booleano, onde a expressão de um gene é representado apenas por dois possíveis valores: 0 (não expressado) ou 1 (expressado). Além disso, nossa metodologia é baseada na abordagem de seleção de característica e utilizamos um algoritmo chamado IFFS - improved forward floating selection. Realizamos experimentos para comparar 2 medidas de interação gênica usada na função critério do algoritmo, o coeficiente de determinação e a informação mútua computada através da entropia de Shannon e de Tsallis. Também incorporamos uma fonte de conhecimento biológico a priori das interações dos genes a partir de um banco de
dados chamado STRING. Para validar a metodologia, utilizamos dados das competições DREAM e um conjunto de dados de um estudo do ciclo-celular da levedura. Os resultados mostraram que, geralmente, a informação mútua desempenha um resultado levemente melhor do que o coeficiente de determinação, e que incorporando o conhecimento biológico melhora os resultados. Todo esse conjunto de algoritmos estão implementados na linguagem R e futuram estarão completamente disponível como o pacote Measures_GRN do R em https://github.com/camila-koike/Measure_GRN. |
| 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) |
|
| Coorientador(es) |
|
| Orientando(s) |
|
| 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 |
|
|
| Seleção de Instâncias Baseado em Aprendizado de Métricas para K Vizinhos Mais Próximos |
|
| Curso |
Mestrado em Ciência da Computação |
| Tipo |
Dissertação |
| Data |
22/08/2016 |
| Área |
CIÊNCIA DA COMPUTAÇÃO |
| Orientador(es) |
|
| Coorientador(es) |
|
| Orientando(s) |
- Eduardo Zárate Guerreiro Max
|
| Banca |
- Edson Takashi Matsubara
- Eraldo Luis Rezende Fernandes
- Rafael Geraldeli Rossi
- Ricardo Marcondes Marcacini
|
| Resumo |
A seleção de instâncias, em aprendizado de máquina, procura identificar instâncias relevantes e remover as instâncias que são redundantes ou prejudiciais do conjunto original. Classificadores baseados em instâncias, como o K Vizinhos Mais Próximos (k-NN), são fortemente beneficiados com esta seleção, podendo prover uma classificação mais rápida, uma diminuição nos requisitos de armazenamento e uma diminuição na sensibilidade ao ruído. Um fundamento essencial a esses algoritmos são as métricas de distância entre os exemplos. Nesse trabalho de mestrado, é proposto um algoritmo de seleção de instâncias com aprendizado de métricas denominado Seleção de Instância sobre Aprendizado de Métrica (Instance Selection on Metric Learning, ISML) para o Classificador K Vizinhos Mais Próximos. O método de aprendizado de métricas, chamado de k-Neighborhood Components Analysis (kNCA), é aplicado ao conjunto de dados para melhorar a seleção e reduzir a relação de compromisso (trade-off ) entre número de instâncias de treino e acurácia. Foram realizados experimentos para comparar métodos tradicionais da literatura de seleção de instâncias. Os resultados são promissores principalmente em cenários de redução extrema de exemplos, redução maior que 50% dos dados originais, onde a proposta ISML obtém melhor ROC AUC em 11 dos 12 conjunto de dados quando comparado com outros três métodos de seleção de instância.
|
| Download |
|
|
| Histograma de Palavras Visuais para Caracterização de Texturas e Cenas Dinâmicas |
|
| Curso |
Mestrado em Ciência da Computação |
| Tipo |
Dissertação |
| Data |
17/08/2016 |
| Área |
CIÊNCIA DA COMPUTAÇÃO |
| Orientador(es) |
|
| Coorientador(es) |
|
| Orientando(s) |
- Wesley Eiji Sanches Kanashiro
|
| Banca |
- Hemerson Pistori
- Jonathan de Andrade Silva
- Wesley Nunes Goncalves
|
| Resumo |
A caracterização de vídeos vem sendo pesquisada cada vez mais na área de visão computacional por ser um tema desafiador. Caracterizar vídeos não é uma tarefa trivial, pois é preciso levar em consideração tanto a informação espacial (aparência), quanto a informação temporal (movimento). As texturas dinâmicas são um caso particular de vídeos, que podem ser definidas como movimentos de padrões que apresentam propriedades estacionárias ao longo do espaço e tempo. Exemplos de textura dinâmica podem ser encontrados em situações do dia-a-dia como por exemplo, em sequências de imagens de ondas do mar, fumaça, fogo, escada rolante, entre outras. Outro caso particular de vídeos são as cenas dinâmicas, que são composições de uma ou mais texturas dinâmicas, mas com um local ou cenário caracterizando-as. Este trabalho tem por objetivo estender o Histograma de Palavras Visuais (BoVW) para caracterização de texturas e cenas dinâmicas. O BoVW é aplicado em três planos ortogonais do vídeo para que sejam obtidas informações espaciais e de movimento, melhorando assim, a caracterização de vídeos. Para avaliar a proposta deste trabalho, experimentos foram realizados em duas bases de vídeos: tráfego de carros e cenas dinâmicas. Os resultados foram comparados com os obtidos por métodos da literatura e em ambas as bases de vídeos, o método proposto apresentou resultados promissores. Na base de cenas dinâmicas, pode-se concluir que a inclusão da informação de movimento para caracterização dos vídeos aumentou consideravelmente a taxa de classificação correta. Enquanto que na base de tráfego de carros, a informação temporal não influenciou de forma tão considerável a taxa de classificação correta, apesar de contribuir de certa forma na caracterização dos vídeos.
|
| Download |
|
|
| Classificação de Séries Temporais baseada em Análise de Recorrência e Extração de Características |
|
| Curso |
Mestrado em Ciência da Computação |
| Tipo |
Dissertação |
| Data |
03/08/2016 |
| Área |
CIÊNCIA DA COMPUTAÇÃO |
| Orientador(es) |
|
| Coorientador(es) |
|
| Orientando(s) |
|
| Banca |
- Eraldo Luis Rezende Fernandes
- Paulo Aristarco Pagliosa
- Renato Porfirio Ishii
- Rodrigo Fernandes de Mello
|
| Resumo |
A identificação de padrões em fluxos de dados contínuos tem despertado o interesse científico, seja na detecção de falhas em sistemas, identificação de operações fraudulentas em transações bancárias, propagação de doenças ou ainda na preservação do meio ambiente. A categorização destes dados, concomitante com a ampliação do sensoriamento e monitoramento de diversos outros domínios, motiva a busca por soluções práticas e eficientes que auxiliem na busca por padrões recorrentes. A extração de conhecimento dos dados, quando dependentes do tempo, exige um tratamento especial e a mineração dos dados apresenta-se como uma atividade valiosa. Neste trabalho, é proposta uma abordagem chamada DSP-Class para classificação de séries temporais utilizando Descritores de Textura aplicados em Gráficos de Recorrência (RP). São utilizados 14 conjuntos de dados reais relacionados a vocalizações de aves, identificação de insetos, categorização de reações químicas, dentre outros. O objetivo desta pesquisa é verificar a utilização das características texturais de RPs em algoritmos de aprendizagem, tais como Support Vector Machine (SVM) e C5:0, aplicando a Decomposição de Modo Empírico (EMD) na classificação de séries temporais. Também é analisada a influência estocástica-determinística presentes nos fluxos. Verifica-se desempenho ruim do algoritmo 1NN, considerado estado-da-arte, em séries predominantemente estocásticas ou determinísticas e desempenho 67:66% superior da abordagem DSP-Class, uma vez que as características texturais distinguem classes de séries temporais mais satisfatoriamente que a busca por similaridade utilizada no algoritmo 1NN nos dados analisados. Verifica-se inclusive, resultados 18;67% superiores àqueles obtidos por pesquisas semelhantes que utilizam outras características presentes em séries temporais. |
| Download |
|
|
| Problema das pseudo-arborescências capacitadas com a localização de facilidades |
|
| Curso |
Mestrado em Ciência da Computação |
| Tipo |
Dissertação |
| Data |
22/07/2016 |
| Área |
CIÊNCIA DA COMPUTAÇÃO |
| Orientador(es) |
|
| Coorientador(es) |
|
| Orientando(s) |
- Fabio Henrique Noboru Abe
|
| Banca |
- Anderson Vicoso de Araujo
- Cid Carvalho de Souza
- Edna Ayako Hoshino
- Fabio Henrique Viduani Martinez
|
| Resumo |
Neste trabalho apresentamos o problema das pseudo-arborescências capacitadas com localização de facilidades, um problema novo e relacionado a dois outros problemas clássicos: o problema do roteamento de veículos
capacitado e o problema da localização de facilidade capacitada. O problema estudado é uma generalização do problema da pseudo-arborescência capacitada, em inglês capacitated ring tree problem. Propomos neste estudo duas formulações em programação linear inteira para modelar o problema. A primeira é uma formulação estendida baseada em partição de conjuntos e a segunda é uma formulação compacta baseada em fluxos. Propomos também dois algoritmos exatos para resolver o problema. Um deles utiliza a técnica de branch-and-price com a formulação estendida e o outro é um algoritmo do tipo branch-and-bound baseado na formulação compacta. Implementamos também uma heurística primal e uma heurística de pricing com o objetivo de melhorar o desempenho dos métodos exatos. Experimentos computacionais realizados em um grupo de instâncias testes mostram que a formulação estendida fornece limitantes muito mais apertados do que a formulação compacta. Além disso, as heurísticas foramrelevantes para acelerar os métodos de branch-and-price e branch-and-bound, em especial a heurística primal. |
| Download |
|
|
| FlexRank: Um Rankeador Lexicográfico Rápido |
|
| Curso |
Mestrado em Ciência da Computação |
| Tipo |
Dissertação |
| Data |
29/06/2016 |
| Área |
CIÊNCIA DA COMPUTAÇÃO |
| Orientador(es) |
|
| Coorientador(es) |
|
| Orientando(s) |
|
| Banca |
- Anderson Vicoso de Araujo
- Bruno Magalhaes Nogueira
- Edson Takashi Matsubara
- Eraldo Luis Rezende Fernandes
|
| Resumo |
O uso de Aprendizado de Máquina (AM), tem sido amplamente utilizado em problemas reais nos últimos anos. Este trabalho propõe o uso de técnicas em AM para problemas com dados textuais, com abordagem em algoritmos baseados em regras lexicográficas e legitimamente rankeadores. Com a popularização dos dados em meio digitais, torna-se interessante aplicar técnicas de AM para melhor organizar as informações contidas neste vasto campo de bases textuais. O aprendizado supervisionado, uma área de AM, com uso de algoritmos de rankeamento é uma alternativa viável para ambientes que possuem poucos dados rotulados. Logo, para alcançar os desafios deste trabalho é proposto o algoritmo FLEXRANK que tem o objetivo de rankear conjuntos textuais massivos. Para realizar tal feito FLEXRANK conta com uma estratégia simples que utiliza apenas atributos relevantes e por conseguinte realiza lexicograficamente a ordenação dos exemplos em um conjunto de dados. Deste modo, inicialmente são apresentados os tipos de algoritmos de AM, medidas de avaliação em algoritmos de classificação, rankeamento e abordagem dos algoritmos LEXRANK e FLEXRANK proposto neste trabalho. Trabalhos que possuem correlação de ranking de textos, especialmente aqueles que atuam em mineração de textos, são abordados neste estudo. Destaca-se também estudos anteriores com foco a balizar os experimentos e resultados acalçados ao longo deste trabalho. FLEXRANK foi avaliado empiricamente sobre uma série de conjuntos de dados em comparação com os algoritmos SVM, Árvores de Decisão, Naive Bayes, KNN e LEXRANK. Os resultados demonstram que para os problemas de classificação de textos massivos, FLEXRANK tem resultados comparáveis, por meio de Curva ROC AUC, a SVM e mais rápido do que Árvores de Decisão para classificar novos exemplos.
|
| Download |
|
|
| Uma Abordagem para Classificação de Séries Temporais Baseada em Modelo Autorregressivo e Gráfico de Recorrência |
|
| Curso |
Mestrado em Ciência da Computação |
| Tipo |
Dissertação |
| Data |
25/05/2016 |
| Área |
CIÊNCIA DA COMPUTAÇÃO |
| Orientador(es) |
|
| Coorientador(es) |
|
| Orientando(s) |
|
| Banca |
- Eraldo Luis Rezende Fernandes
- Paulo Aristarco Pagliosa
- Renato Porfirio Ishii
- Ricardo Araújo Rios
|
| Resumo |
Atualmente, os estudos sobre o problema da classificação de séries temporais tem se concentrado em elaborar abordagens em dois formatos: baseado em funções de distância entre itens do conjunto de dados, e baseado em um procedimento de dois estágios, onde as séries temporais são transformadas em vetores de características, permitindo o emprego de técnicas de classificação convencionais. Neste contexto, não tem sido notado na literatura
estudos baseados na análise de propriedades intrínsecas do processo gerador da série temporal como, por exemplo, o determinismo. Neste trabalho de mestrado, é proposta uma abordagem para o problema da classificação de séries temporais, projetada em dois estágios e baseada na análise de propriedades intrínsecas de determinismo e de estocasticidade. Primeiramente, cada série temporal é processada pelo modelo autorregressivo (AR) e pelo Gráfico de Recorrências, para modelar as influências estocásticas e determinísticas, presentes nas séries temporais. Posteriormente, são extraídas características, a partir da nova representação, que compõem o novo espaço característico. Para a classificação em si, optou-se pelo SVM em seu formato convencional. Tomou-se como abordagem de referência da literatura, o classificador 1-NN com funções de distâncias Euclidiana, DTW e DTW otimizado por janela de busca. Os experimentos foram executados sobre os conjuntos de dados do repositório UCR. Os resultados finais mostram que o desempenho de classificação é competitivo, ou superior, a melhor configuração 1-NN em 19 de 41 conjuntos de dados. Não obstante, os resultados evidenciam, também, a necessidade de uma investigação mais aprofundada sobre as influências das propriedades intrínsecas, e outras técnicas da área de análise de séries temporais, quando aplicadas na tarefa de classificação.
|
| 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
|
| Coorientador(es) |
|
| Orientando(s) |
|
| 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 |
|
|
| Atributos de Ponto de Interesse e Casamento de Modelos para Contagem de Insetos-Praga em Cultura de Soja |
|
| Curso |
Mestrado em Ciência da Computação |
| Tipo |
Dissertação |
| Data |
31/03/2016 |
| Área |
CIÊNCIA DA COMPUTAÇÃO |
| Orientador(es) |
|
| Coorientador(es) |
|
| Orientando(s) |
|
| Banca |
- Denilson de Oliveira Guilherme
- Edson Takashi Matsubara
- Hemerson Pistori
- Lucas Castro Torres
- Marco Hiroshi Naka
|
| Resumo |
Neste trabalho é apresentado uma aplicação para a contagem de insetos em plantações de soja, o objetivo desta aplicação é ser uma ferramenta para o auxílio de agrônomos e técnicos agrícolas na inspeção de cultivos de soja. A aplicação utiliza imagens aéreas, capturadas por Veículos Aéreos não Tripulados, para a contagem dos insetos, e com esta informação o especialista pode definir se existe infestação de insetos na plantação ou não, decidindo se é necessária a aplicação de inseticidas. Para a identificação e contageßm dos insetos, técnicas de visão computacional baseadas em Pontos de Interesse foram utilizadas, sendo o Speeded Up Robust Feaure (SURF) a técnica utilizada para a detecção e descrição dos Pontos de Interesse das imagens analisadas. Para a classificação dos insetos, técnicas baseadas em casamento de modelos, em específico técnicas que utilizam os pontos de interesse para definir o casamento entre as imagens, foram utilizadas para definir a semelhança entre a imagem teste com as classes analisadas. Com essa informação três métricas foram utilizadas para definir a classe do inseto, a do ponto com distância mínima, a distância média mínima e o número de casamentos. Nos experimentos realizados foram variados os parâmetros do detector e descritor de pontos de interesse a fim de encontrar os melhores resultados para a classificação. O método proposto foi comparado com três classificadores baseados em Máquina de Vetores de Suporte, K vizinhos mais próximos e árvores de decisão. O método proposto obteve uma medida-F de 0.899 sendo estatisticamente melhor do que o classificador baseado em árvores de decisão e semelhante aos baseados em Máquina de Vetores de Suporte e K vizinhos mais próximos. O módulo de contagem foi comparado com a contagem de um especialista que marcou todas as imagens de teste. Através do teste de hipóteses ANOVA (Análise de variância) foi comprovado que a contagem do método proposto e do especialista não são divergentes, com um nível de significância de 5%, evidenciando o potencial da proposta na automação de avaliações de pragas em campo. |
| 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
|
| Coorientador(es) |
|
| 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) |
|
| Coorientador(es) |
|
| Orientando(s) |
|
| 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) |
|
| Coorientador(es) |
|
| 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. |
|