Repositório RCAAP

Esta dissertação tem como objetivo estudar a combinação de duas técnicas de planejamento em inteligência artificial: planejamento hierárquico e planejamento sob incerteza Knightiana. Cada uma delas possui vantagens distintas, mas que podem ser combinadas, permitindo um ganho de eficiência para o planejamento sob incerteza e maior robustez a planos gerados por planejadores hierárquicos. Primeiramente, estudamos um meio de efetuar uma transformação, de modo sistemático, que permite habilitar algoritmos de planejamento determinístico com busca progressiva no espaço de estados a tratar problemas com ações não-determinísticas, sem considerar a distribuição de probabilidades de efeitos das ações (incerteza Knightiana). Em seguida, esta transformação é aplicada a um algoritmo de planejamento hierárquico que efetua decomposição a partir das tarefas sem predecessoras, de modo progressivo. O planejador obtido é competitivo com planejadores que representam o estado-da-arte em planejamento sob incerteza, devido à informação adicional que pode ser fornecida ao planejador, na forma de métodos de decomposição de tarefas.

Coreografias de serviços Web representam uma forma mais escalável e flexível de compor serviços do que uma abordagem centralizada como a orquestração, e seu papel na integração e comunicação de sistemas de larga escala é vital para os objetivos da SOC (Computação Orientada a Serviços) e da Internet do Futuro. Atualmente coreografias de serviços Web possuem vários desafios de pesquisa, dos quais a qualidade de serviço (QoS) e o monitoramento de coreografias de serviçosWeb são linhas importantes. O objetivo deste trabalho é propor e implementar um mecanismo de monitoramento não intrusivo de coreografias de serviços Web baseado em SLAs (Acordos de Nível de Serviço) que especificam as restrições de atributos de QoS de maneira probabilística. Esta dissertação propõe um mecanismo para coreografias de serviços Web que: (1) define requisitos de QoS; (2) especifica contratos probabilísticos sobre parâmetros de QoS usando SLA; e (3) realiza um monitoramento não intrusivo de coreografias de serviços Web para detectar violações de SLA.

Os Métodos Ágeis surgiram no final da década passada como uma alternativa aos métodos tradicionais de desenvolvimento de software. Eles propõem uma nova abordagem para o desenvolvimento, eliminando gastos com documentação excessiva e burocrática, enfatizando a comunicação, colaboração com o cliente e as atividades que trazem valor imediato na produção de software com qualidade. Por meio de um processo empírico, com ciclos constantes de inspeção e adaptação, a equipe trabalha sempre num ambiente de melhoria contínua. Uma das atividades propostas pela Programação Extrema (XP) para guiar a equipe em direção à melhoria é conhecida como tracking. O papel do tracker é coletar métricas para auxiliar a equipe a entender o andamento do projeto. Encontrar maneiras eficazes de avaliar o processo e a equipe de desenvolvimento não é uma tarefa simples. Além disso, alguns dos possíveis problemas não são facilmente reconhecidos a partir de dados quantitativos. Este trabalho investiga o uso de métricas no acompanhamento de projetos utilizando Métodos Ágeis de desenvolvimento de software. Um estudo de caso da aplicação de XP em sete projetos acadêmicos e governamentais foi conduzido para validar algumas dessas métricas e para avaliar o nível de aderência às práticas propostas, com o objetivo de auxiliar o tracker de uma equipe ágil.

O objetivo deste trabalho é desenvolver uma plataforma para anotação e classificação automática de entidades nomeadas para notícias escritas em português do Brasil. Para restringir um pouco o escopo do treinamento e análise foram utilizadas notícias esportivas do Campeonato Paulista de 2011 do portal UOL (Universo Online). O primeiro artefato desenvolvido desta plataforma foi a ferramenta WebCorpus. Esta tem como principal intuito facilitar o processo de adição de metainformações a palavras através do uso de uma interface rica web, elaborada para deixar o trabalho ágil e simples. Desta forma as entidades nomeadas das notícias são anotadas e classificadas manualmente. A base de dados foi alimentada pela ferramenta de aquisição e extração de conteúdo desenvolvida também para esta plataforma. O segundo artefato desenvolvido foi o córpus UOLCP2011 (UOL Campeonato Paulista 2011). Este córpus foi anotado e classificado manualmente através do uso da ferramenta WebCorpus utilizando sete tipos de entidades: pessoa, lugar, organização, time, campeonato, estádio e torcida. Para o desenvolvimento do motor de anotação e classificação automática de entidades nomeadas foram utilizadas três diferentes técnicas: maximização de entropia, índices invertidos e métodos de mesclagem das duas técnicas anteriores. Para cada uma destas foram executados três passos: desenvolvimento do algoritmo, treinamento utilizando técnicas de aprendizado de máquina e análise dos melhores resultados.

Um problema importante na área de Biologia Sistêmica é o de inferência de redes de regulação gênica. Os avanços científicos e tecnológicos nos permitem analisar a expressão gênica de milhares de genes simultaneamente. Por \"expressão gênica\'\', estamos nos referindo ao nível de mRNA dentro de uma célula. Devido a esta grande quantidade de dados, métodos matemáticos, estatísticos e computacionais têm sido desenvolvidos com o objetivo de elucidar os mecanismos de regulação gênica presentes nos organismos vivos. Para isso, modelos matemáticos de redes de regulação gênica têm sido propostos, assim como algoritmos para inferir estas redes. Neste trabalho, focamos nestes dois aspectos: modelagem e inferência. Com relação à modelagem, estudamos modelos existentes para o ciclo celular da levedura (Saccharomyces cerevisiae). Após este estudo, propomos um modelo baseado em redes Booleanas probabilísticas sensíveis ao contexto, e em seguida, um aprimoramento deste modelo, utilizando cadeias de Markov não homogêneas. Mostramos os resultados, comparando os nossos modelos com os modelos estudados. Com relação à inferência, propomos um novo algoritmo utilizando o paradigma de crescimento de semente de genes. Neste contexto, uma semente é um pequeno subconjunto de genes de interesse. Nosso algoritmo é baseado em dois passos: passo de crescimento de semente e passo de amostragem. No primeiro passo, o algoritmo adiciona outros genes à esta semente, seguindo algum critério. No segundo, o algoritmo realiza uma amostragem de redes, definindo como saída um conjunto de redes potencialmente interessantes. Aplicamos o algoritmo em dados artificiais e dados biológicos de células HeLa, mostrando resultados satisfatórios.

Uma decomposição de um grafo G é um conjunto D = {H_1,... , H_k } de subgrafos de G dois-a-dois aresta-disjuntos que cobre o conjunto das arestas de G. Se H_i é isomorfo a um grafo fixo H, para 1<=i<=k, então dizemos que D é uma H-decomposição de G. Neste trabalho, estudamos o caso em que H é um caminho de comprimento fixo. Para isso, primeiramente decompomos o grafo dado em trilhas, e depois fazemos uso de um lema de desemaranhamento, que nos permite transformar essa decomposição em trilhas numa decomposição somente em caminhos. Com isso, obtemos resultados para três conjecturas sobre H-decomposição de grafos no caso em que H=P_\\ell é o caminho de comprimento \\ell. Dois desses resultados resolvem versões fracas das Conjecturas de Kouider e Lonc (1999) e de Favaron, Genest e Kouider (2010), ambas para grafos regulares. Provamos que, para todo inteiro positivo \\ell, (i) existe um inteiro positivo m_0 tal que se G é um grafo 2m\\ell-regular com m>=m_0, então G admite uma P_\\ell-decomposição; (ii) se \\ell é ímpar, existe um inteiro positivo m_0 tal que se G é um grafo m\\ell-regular com m>=m_0, e G contém um m-fator, então G admite uma P_\\ell-decomposição. O terceiro resultado diz respeito a grafos altamente aresta- conexos: existe um inteiro positivo k_\\ell tal que se G é um grafo k_\\ell-aresta-conexo cujo número de arestas é divisível por \\ell, então G admite uma P_\\ell-decomposição. Esse resultado prova que a Decomposition Conjecture de Barát e Thomassen (2006), formulada para árvores, é verdadeira para caminhos.

O estudo do comportamento assintótico de densidades de algumas subestruturas é uma das principais áreas de estudos em combinatória. Na Teoria das Permutações, fixadas permutações ?1 e ?2 e um inteiro n > 0, estamos interessados em estudar o comportamento das densidades de ?1 e ?2 na família de permutações de tamanho n. Assim, existem duas direções naturais que podemos seguir. Na primeira direção, estamos interessados em achar a permutação de tamanho n que maximiza a densidade das permutações ?1 e ?2 simultaneamente. Para n suficientemente grande, explicitamos a densidade máxima que uma família de permutações podem assumir dentre todas as permutações de tamanho n. Na segunda direção, estamos interessados em achar a permutação de tamanho n que minimiza a densidade de ?1 e ?2 simultaneamente. Quando ?1 é a permutação identidade com k elementos e ?2 é a permutação reversa com l elementos, Myers conjecturou que o mínimo é atingido quando tomamos o mínimo dentre as permutações que não possuem a ocorrência de ?1 ou ?2. Mostramos que se restringirmos o espaço de busca somente ao conjunto de permutações em camadas, então a Conjectura de Myers é verdadeira. Por outro lado, na Teoria dos Grafos, o problema de encontrar um circuito Hamiltoniano é um problema NP-completo clássico e está entre os 21 problemas Karp. Dessa forma, uma abordagem comum na literatura para atacar esse problema é encontrar condições que um grafo deve satisfazer e que garantem a existência de um circuito Hamiltoniano em tal grafo. O célebre resultado de Dirac afirma que se um grafo G de ordem n possui grau mínimo pelo menos n/2, então G possui um circuito Hamiltoniano. Seguindo a linha de Dirac, mostramos que, dados inteiros 1 6 l 6 k/2 e ? > 0 existe um inteiro n0 > 0 tal que, se um hipergrafo k-uniforme H de ordem n satisfaz ?k-2(H) > ((4(k - l) - 1)/(4(k - l)2) + ?) (n 2), então H possui um l-circuito Hamiltoniano.

The parallel and distributed platforms of High Performance Computing available today have became more and more heterogeneous (CPUs, GPUs, FPGAs, etc). Graphics Processing Units (GPU) are specialized co-processor to accelerate and improve the performance of parallel vector operations. GPUs have a high degree of parallelism and can execute thousands or millions of threads concurrently and hide the latency of the scheduler. GPUs have a deep hierarchical memory of different types as well as different configurations of these memories. Performance prediction of applications executed on these devices is a great challenge and is essential for the efficient use of resources in machines with these co-processors. There are different approaches for these predictions, such as analytical modeling and machine learning techniques. In this thesis, we present an analysis and characterization of the performance of applications executed on GPUs. We propose a simple and intuitive BSP-based model for predicting the CUDA application execution times on different GPUs. The model is based on the number of computations and memory accesses of the GPU, with additional information on cache usage obtained from profiling. We also compare three different Machine Learning (ML) approaches: Linear Regression, Support Vector Machines and Random Forests with BSP-based analytical model. This comparison is made in two contexts, first, data input or features for ML techniques were the same than analytical model, and, second, using a process of feature extraction, using correlation analysis and hierarchical clustering. We show that GPU applications that scale regularly can be predicted with simple analytical models, and an adjusting parameter. This parameter can be used to predict these applications in other GPUs. We also demonstrate that ML approaches provide reasonable predictions for different cases and ML techniques required no detailed knowledge of application code, hardware characteristics or explicit modeling. Consequently, whenever a large data set with information about similar applications are available or it can be created, ML techniques can be useful for deploying automated on-line performance prediction for scheduling applications on heterogeneous architectures with GPUs.

Existem várias linguagens e plataformas que permitem a programação baseada no modelo de atores, uma solução elegante para a programação concorrente proposta há algumas décadas. Segundo esse modelo, implementa-se o programa na forma de uma série de agentes que são executados em paralelo e se comunicam entre si somente por meio da troca de mensagens, sem a necessidade de memória compartilhada ou estruturas tradicionais de sincronização como semáforos e mutexes. Uma das áreas nas quais esse modelo seria particularmente adequado é a programação de aplicações web, isto é, aplicações cujas lógicas de negócios e de dados residem num servidor e que são acessadas pelo usuário por intermédio de um navegador. Porém, existem muitos obstáculos ao desenvolvimento de aplicações desse tipo, entre eles a falta de linguagens e ferramentas que permitam integrar tanto o servidor quanto o cliente (navegador) no modelo de atores, as dificuldades de conversões de dados que se fazem necessárias quando o servidor e o cliente são desenvolvidos em linguagens diferentes, e a necessidade de contornar as dificuldades inerentes aos detalhes do protocolo de comunicação (HTTP). O PAWEB é uma proposta de uma plataforma para o desenvolvimento e execução de aplicações web que fornece a infraestrutura necessária para que tanto o lado cliente quanto o lado servidor do aplicativo hospedado possam ser escritos numa mesma linguagem (Python), e possam criar e gerenciar atores que trocam mensagens entre si,tanto local quanto remotamente, de maneira transparente e sem a necessidade de implementar conversões de dados ou outros detalhes de baixo nível.

Em Aprendizagem Colaborativa com Suporte Computacional (ACSC), o planejamento instrucional consiste em obter uma sequência de interações instrucionais que definem o conteúdo instrucional como a representação do que deve ser ensinado e da forma em que os participantes devem interagir, denominada informação de planejamento instrucional. O desenvolvimento, adaptação e personalização de unidades concisas de estudo compostas por recursos instrucionais e informação de planejamento instrucional, denominadas unidades de aprendizagem, envolve um processo de planejamento instrucional complexo que consome muito tempo e apresenta um conjunto de tarefas repetitivas a serem efetuadas pelos projetistas instrucionais. Neste trabalho, o planejamento instrucional em ACSC é modelado como um problema de planejamento hierárquico para dar suporte ao desenvolvimento, adaptação e personalização das unidades de aprendizagem de forma automática. A modelagem consiste na representação do domínio a ser ensinado, das caraterísticas dos estudantes e das estratégias de planejamento instrucional na linguagem do sistema JSHOP2ip, um sistema de planejamento hierárquico desenvolvido para dar solução aos problemas específicos de planejamento instrucional. Para avaliar a modelagem proposta, efetuamos o desenvolvimento de um gerador de cursos colaborativos como um serviço Web usando a modelagem proposta e o sistema JSHOP2ip, no qual foram avaliados o desempenho, a modelagem das estratégias e a saída do planejador. Além disso, para demonstrar a viabilidade do modelo proposto em situações reais, efetuamos o desenvolvimento de uma ferramenta de autoria de unidades de aprendizagem que emprega o gerador de cursos colaborativos.

A Web 2.0 alterou o desenvolvimento de aplicações para internet. Contudo, os pesquisadores e desenvolvedores ainda replicam as ideias uns dos outros com pouco reuso. Esse cenário ilustra a necessidade de uma engenharia de domínio, na qual as similaridades e as variabilidades de uma família de aplicações são identificadas e documentadas, com a finalidade de obter o reuso dos componentes desenvolvidos. Neste trabalho, e feita uma engenharia de domínio para Redes Sociais na Web 2.0, com o foco nas funcionalidades colaborativas relativas ao compartilhamento de conteúdo. Como método, e utilizado o FODA (Feature Oriented Domain Analysis) adaptado com o modelo 3C de colaboração para classificar e padrões para interação mediada por computador para descrever as funcionalidades colaborativas. No modelo 3C, a colaboração e analisada a partir da comunicação, coordenação e cooperacao, e padroes descrevem e detalham o contexto de uso das funcionalidades levantadas. Para a implementação das funcionalidades colaborativas comuns nessas aplicações, são desenvolvidos componentes de software compatíveis com a plataforma Groupware Workbench. Um experimento foi realizado para avaliar os artefatos gerados na engenharia de domínio e um estudo de caso para avaliar a aplicabilidade e abrangência dos componentes desenvolvidos em um contexto real, a rede social para compartilhamento de imagens de arquitetura, chamada Arquigrafia Brasil. Os experimentos e o estudo de caso indicaram que os artefatos gerados são reusáveis, uteis e abrangem boa parte das funcionalidades presentes nas redes sociais atuais.

A técnica de Análise de Componentes Principais (PCA) tem como objetivo principal a descrição da variância e covariância entre um conjunto de variáveis. Essa técnica é utilizada para mitigar redundâncias no conjunto de variáveis e para redução de dimensionalidade em várias aplicações nas áreas científica, tecnológica e administrativa. Por outro lado, o modelo de dados multidimensionais é composto por relações de fato e dimensões (tabelas) que descrevem um evento usando métricas e a relação entre suas dimensões. No entanto, o volume de dados armazenados e a complexidade de suas dimensões geralmente envolvidas neste modelo, especialmente no ambiente de data warehouse, tornam a tarefa de interpretar a correlação entre dimensões muito difícil e às vezes impraticável. Neste trabalho, propomos o desenvolvimento de uma Interface de Programação de Aplicação (API) para a aplicação da PCA no modelo de dados multidimensionais para facilitar a tarefa de caracterização e redução de dimensionalidade, integrando essa técnica com ambientes de Data Warehouses. Para verificar a eficácia desta API, um estudo de caso foi realizado utilizando dados de produção científica e suas citações obtidas das Plataformas Lattes, Web of Science, Google Scholar e Scopus, fornecidas pela Superintendência de Tecnologia da Informação da Universidade de São Paulo.

O QC-MDPC McEliece foi considerado um dos mais promissores esquemas criptográficos de chave pública que oferecem segurança contra ataques por computadores quânticos. O tamanho das chaves públicas do QC-MDPC McEliece é competitivo com o das chaves do RSA, e o esquema tem uma redução de segurança aparentemente forte. Por três anos, o esquema não sofreu ataques críticos, até que na Asiacrypt de 2016 Guo, Johansson, e Stankovski mostraram um ataque de reação contra o QC-MDPC McEliece que explora um aspecto não considerado em sua redução de segurança: a probabilidade de o algoritmo de decriptação falhar é menor quando a chave secreta e o vetor usado para encriptar a mensagem compartilham certas propriedades, chamadas de espectros. Dessa forma, um atacante pode, ao detectar falhas de decriptação, obter informação sobre o espectro, que será usada para reconstruir a chave secreta. Guo et al. apresentaram um algoritmo para a reconstrução da chave a partir do espectro recuperado, para o qual é possível apontar três problemas. O primeiro é que seu algoritmo não é eficiente quando o espectro da chave não foi recuperado quase completamente, o que resulta em o atacante ter que enviar um grande número de testes de decriptação à portadora da chave secreta. O segundo problema é que o desempenho de seu algoritmo não escala bem para níveis de segurança mais altos. O terceiro e último problema é que, por ser baseado numa busca em profundidade, seu algoritmo não pode ser paralelizado trivialmente. Para aumentar a eficiência do ataque, dois novos algoritmos de reconstrução são propostos neste trabalho. Estes algoritmos são mais eficientes, usam menos informação sobre a chave secreta, e podem ser paralelizados trivialmente. O primeiro algoritmo é probabilístico e tem complexidade assintótica ligeiramente melhor do que a do original. Entretanto, o desempenho do algoritmo probabilístico piora rapidamente, embora mais lentamente do que o algoritmo de Guo et al., conforme a quantidade de informação sobre o espectro diminui. O segundo algoritmo explora uma relação linear entre os blocos da chave secreta. Este é mais eficiente, tanto assintoticamente quanto na prática, que os dois outros algoritmos, e é eficiente mesmo com 50% menos informação sobre o espectro do que o necessário para o algoritmo original. Isso permite que o atacante encontre a chave secreta fazendo apenas em torno de 20% do número de testes necessários pelo algoritmo de Guo\'s et al., considerando-se o nível de segurança de 80 bits. O desempenho de ambos os algoritmos são analisados e comparados com o do algoritmo original, e as análises são feitas tanto para a complexidade teórica quanto para o desempenho na prática, considerando a implementação dos algoritmos em linguagem C.

A computação em nuvem tem recebido um grande destaque, ao propor um novo e eficiente mecanismo para disponibilizar recursos computacionais. Dos investimentos cada vez maiores nessa plataforma, inclusive pela academia, surge a oportunidade de compartilhar estes recursos computacionais entre diferentes instituições. As grades computacionais são um mecanismo bem estabelecido para o compartilhamento de alguns tipos de recursos computacionais. Através do entendimento de como isso é feito nestas estruturas, esse trabalho avalia as soluções existentes e propõe um arquitetura alternativa que permite a criação das federações de nuvens computacionais.

Recentemente estudiosos como Benkler, Lessig, Boyle, Hess e Ostrom retomaram o uso do conceito de commons, mas agora relacionado à informação em geral ou à informação científica. Nesse trabalho, nós lançamos mão desse termo para destacar o caráter cooperativo da pesquisa científica, a importância da transparência e neutralidade no acesso ao commons da Ciência e a natureza anti-rival da informação científica. O conceito de commons nos é muito útil para focar todo o conjunto dos artigos científicos já publicados, quer estejam na forma impressa ou na digital. Ainda permite um estudo através de prismas multidisciplinares e, finalmente, enfatiza a dinâmica das comunidades científicos como um todo. Em qualquer commons de informação, quanto maior a distribuição do conhecimento, mais dinâmico e eficiente é o processo de evolução do conhecimento. A tecnologia da imprensa tem desempenhado um papel fundamental na divulgação de informação e o seu surgimento marcou uma revolução no conhecimento e na cultura da nossa civilização. A tecnologia digital tem se mostrado mais eficiente ainda, uma vez que a natureza da sua implementação em bits se aproxima mais da natureza anti-rival das idéias do que qualquer outra tecnologia hoje empregada para preservação e distribuição de informação. Em nosso estudo, constatamos que o commons da Ciência pode ser enormemente enriquecido através de práticas cooperativas e de acesso aberto na publicação da academia. Percebemos também que o uso da tecnologia digital no commons científico, especialmente na publicação dos resultados da pesquisa, aumenta grandemente a distribuição do conhecimento acadêmico, suas oportunidades de escrutínio e validação, a dinâmica de amadurecimento das idéias científicas e, conseqüentemente, pode tornar o desenvolvimento da Ciência mais veloz e eficiente. No entanto, o meio digital tem sido utilizado tanto para criar um ambiente de livre circulação de idéias quanto para controlá-las. Por um lado, código computacional tem sido implementado para garantir o acesso apenas aos que pagam pelos altos preços das revistas científicas. Por outro lado, a publicação de revistas on-line de acesso aberto e outras formas alternativas de disseminação de conteúdo científico têm se proliferado. Ainda, o decrescente orçamento das bibliotecas, o crescente preço das assinaturas de revistas científicas e as crescentes restrições aplicadas pelas leis de propriedade intelectual têm minado a natureza livre das idéias científicas e colocado a Comunicação Científica numa crise. Estamos no meio de uma transição de paradigmas quanto à publicação dos resultados de pesquisa científica, onde aspectos legais, tecnológicos e sócio-econômicos estão em renegociação. À luz das oportunidades da tecnologia digital e da publicação em acesso aberto, as formas de disseminação dos resultados da pesquisa científica presentemente estabelecidas tem sido repensadas. Inserimos essa análise num contexto maior, o paradigma da Comunicação Científica. Isso nos auxilia a fazer um estudo mais abrangente das complexas questões envolvendo nosso tema, analisando os aspectos tecnológicos, legais e sócio-econômicos de uma possível transição para o modelo de publicação de acesso aberto. Tão grandes são as oportunidades desse novo modelo que ele tem agregado em torno de si iniciativas sócio-acadêmicas conhecidas por Movimento de Acesso Aberto à literatura científica. Atualmente, há muitos testes e modelos de publicação dessa literatura. Em especial, nesse trabalho focamos o modelo de acesso aberto aos resultados científicos, suas vantagens, as dificuldades para seu estabelecimento e como ele tem se desenvolvido. Analisamos a viabilidade de criação de um ecossistema de bibliotecas digitais de acesso aberto, especializadas em cada ramo da Ciência. Nossos modelos de partida baseiam-se em alguns aspectos de serviços como arXiv, CiteSeer e Google Scholar. Entre as muitas conclusões desse estudo, constatamos que bibliotecas desse tipo aumentam sobremaneira a dinâmica de circulação, geração, transformação e renovação do conhecimento científico. Assim, o processo de produção de recursos no commons científico pode se tornar muito mais eficiente.

Uma representação retangular de um grafo plano G é uma representação de G, onde cada vértice é desenhado como um retângulo de modo que dois retângulos devem compartilhar algum segmento de seus lados se e somente se existe uma aresta em G entre os vértices correspondentes aos retângulos. Ainda, a representação de G deve formar um retângulo e não deve existir buracos, ou seja, toda região interna deve corresponder a algum vértice de G. Um desenho retangular de um grafo plano H é um desenho de H, onde todas as arestas são desenhadas como segmentos horizontais ou verticais. Ainda, todas as faces internas são retângulos e as arestas que incidem na face externa também formam um retângulo. Nesta dissertação, apresentamos os principais trabalhos existentes na literatura para problemas associados à representação retangular. Também apresentamos resultados para problemas associados ao desenho retangular. Por fim, apresentamos o algoritmo que desenvolvemos para determinar as coordenadas dos vértices de um desenho retangular quando a orientação das arestas já foram determinadas.

No Brasil e em vários outros países, decisões de tribunais superiores criam jurisprudência e podem ser utilizadas na resolução de casos semelhantes. Os acórdãos, textos que registram tais decisões, contam com uma classificação multicategoria e multirrótulo chamada de verbetação, realizada manualmente com a intenção de que tais documentos possam ser facilmente buscados e recuperados. A literatura da área já identificou vários problemas na elaboração dessas verbetações; concomitantemente, algoritmos neurais de linguística computacional baseados em atenção, como o Transformer e o BERT, têm ganhado destaque ao permitir que a resolução automática de problemas linguísticos atinja patamares nunca antes alcançados, lançando questões sobre seus limites, potencial e aplicabilidade. O trabalho de pesquisa aqui apresentado consiste num estudo inicial do uso de algoritmos baseados em atenção para a automação da verbetação de acórdãos em português, com o intuito de lançar caminhos para a resolução dos problemas listados na literatura e de agregar conhecimento do escopo e funcionalidade dessa família de métodos. Para tal, utilizamos dados do Projeto Kollemata como base para implementar e treinar versões multicategoria e multirrótulo de diversos modelos BERT, com o intuito de realizar a verbetação de acórdãos de maneira automática. Esse processo constituiu-se de três etapas: a construção de um córpus processável a partir dos dados do Kollemata e a consequente análise exploratória desse córpus com o intuito de mapear as propriedades dos dados a serem utilizados; a adequação ontológica e taxonômica do sistema de classes do córpus com base nos resultados obtidos dessa análise, de maneira a tornar a classificação computacionalmente viável; a implementação de uma versão multicategoria e multirrótulo do BERT e seu treinamento com o córpus adequado, sob diversos parâmetros e usando diferentes modelos BERT de interesse, de maneira a avaliar o comportamento e limites das médias da Medida-F1 e outros índices de performance. Obtivemos, no melhor caso, 72% para a micro-média da medida-F1 e 71% para sua macro-média, constituindo ganhos da ordem de 30% ou mais em relação aos baselines estatísticos utilizados. Além disso, encontramos uma família ótima de parâmetros para essa tarefa, condizente com valores ótimos obtidos para tarefas distintas e observamos uma série de propriedades interessantes da evolução das métricas de performance em função de diferentes parâmetros. Registramos, também, melhor performance dos modelos maiores e pré-treinados com dados em português, em comparação com modelos menores e multilinguais. Entretanto, essa vantagem é pequena, o que indica a possibilidade da utilização de modelos menores e multilinguais para essa tarefa em específico, sem perda significativa de qualidade. Uma análise cuidadosa desse e de outros resultados auxiliares aqui apresentados, também nos levou a concluir que a principal barreira na obtenção de melhores resultados de performance é a forma como os dados foram classificados e organizados, indicando esse como principal aspecto de melhora a ser implementado em trabalhos futuros.

Homomorfismos de grafos são funções do conjunto de vértices de um grafo no conjunto de vértices de outro grafo que preservam adjacências. O estudo de homomorfismos de grafos é bastante abrangente, existindo muitas linhas de pesquisa sobre esse tópico. Nesta dissertação, apresentaremos resultados sobre homomorfismos de grafos relacionados a pseudo-aleatoriedade, convergência de seqüência de grafos e matrizes de conexão de invariantes de grafos. Esta linha tem se mostrado muito rica, não apenas pelos seus resultados, como também pelas técnicas utilizadas nas demonstrações. Em especial, destacamos a diversidade das ferramentas matemáticas que são usadas, que incluem resultados clássicos de álgebra, probabilidade e análise.

O Job Shop Scheduling Problem é um problema NP-Difícil que chama a atenção de muitos pesquisadores devido seu desafio matemático e sua aplicabilidade em contextos reais. Geralmente, principalmente em cenários próximos aos de fábricas e indústrias, obter um escalonamento ótimo por meio de métodos computacionais exatos implica em um alto desprendimento de tempo. Em contrapartida, devido às exigências de um mercado cada vez mais competitivo, as decisões de onde, como, quando e com o que produzir devem ser tomadas rapidamente. O presente trabalho propõe o desenvolvimento de um método heurístico Beam Search para solucionar o Job Shop Scheduling Problem e o Flexible Job Shop Scheduling Problem. Para isso, inicialmente um algoritmo do tipo list scheduling é definido e então o método Beam Search é construído baseado neste algoritmo. Os métodos propostos foram avaliados em diferentes níveis de complexidade utilizando instâncias da literatura que retratam diferentes cenários de planejamento. Em linhas gerais, as soluções encontradas se mostraram bastante competitivas quando comparadas a outras soluções da literatura.

The popularity and consolidation of many Free/Libre Open-Source Software (FLOSS) projects in the information technology (IT) market keep industry and academia interested in identifying practices that can be beneficial to the software development process. Two decades ago, a set of practices observed in the Linux kernel development was used to characterize the FLOSS development model as a noisy bazaar. However, since then, the FLOSS ecosystem diversified its forms of development. The Linux kernel project has also undergone notable transformations in its community and development processes toward professionalism and civility. FLOSS projects usually have a community supporting its development and organically producing plentiful information to describe how, when, and why a particular change occurred in the source code or the development flow. Although the existence of several studies on the FLOSS phenomenon and its development, these essential sources of information have been overlooked due to the informality and socio-technical challenges for data collection and analysis. Neglect of these resources may have led some studies to outdated and shallow results regarding FLOSS development practices. Bearing this in mind, we considered the great wealth of open-access materials and the Linux project relevance and protagonism on FLOSS phenomenon to mitigate the distance between what is investigated by academia and what is observed in practice on the development of the Linux kernel. We designed a multi-method investigation to cover academics and practitioners perspectives on the projects socio- technical aspects. We used a multivocal literature review, examining peer-reviewed papers and grey literature, to accurately map the Linux kernel development communitys current characteristics. We included the participant observation on the development community as a third perspective to discuss our findings and nuances involved in community-based development. We also synthesized a set of research strategies to review FLOSS community publications. As a result, this research summarizes the state-of-the-art and state-of-the- practice of the Linux kernels contemporary development model. As an adjoining outcome of this work, we present a combination of research methods that could boost and guide future FLOSS ecosystems research.