É estudado o problema de tratamento de exceções, com vistas a ambientes modulares. É feita uma caracterização inicial do problema, sendo identificados os requisitos que um mecanismo de tratamento de exceções em ambientes modulares deve possuir. A seguir, são discutidas e analisadas as propostas recentemente feitas para resolver o problema, sendo, cada uma delas, confrontada com os requisitos antes mencionados. É proposto, então, um mecanismo que assegura tais requisitos. A ênfase principal dada ao mecanismo proposto e a sua aplicabilidade a ambientes modulares e sua capacidade de verificação. / The exception handling problem is studied, especially in the case of modular environments. The problem is characterized, and the requirements that a mechanism for handling exceptions in such environments must have are identified. Current approaches for dealing with the problem are analized and evaluated with respect to those requirements. A mechanism for handling exceptional conditions in modular environments that fits the requirements is proposed. The main characteristics of the mechanism are its applicability in modular environments and the enforcement of verifiability.

É estudado o problema de tratamento de exceções, com vistas a ambientes modulares. É feita uma caracterização inicial do problema, sendo identificados os requisitos que um mecanismo de tratamento de exceções em ambientes modulares deve possuir. A seguir, são discutidas e analisadas as propostas recentemente feitas para resolver o problema, sendo, cada uma delas, confrontada com os requisitos antes mencionados. É proposto, então, um mecanismo que assegura tais requisitos. A ênfase principal dada ao mecanismo proposto e a sua aplicabilidade a ambientes modulares e sua capacidade de verificação. / The exception handling problem is studied, especially in the case of modular environments. The problem is characterized, and the requirements that a mechanism for handling exceptions in such environments must have are identified. Current approaches for dealing with the problem are analized and evaluated with respect to those requirements. A mechanism for handling exceptional conditions in modular environments that fits the requirements is proposed. The main characteristics of the mechanism are its applicability in modular environments and the enforcement of verifiability.

[pt] Consideramos o Problema Quadrático da Mochila 0-1 (QKP), que consiste em maximizar uma função booleana quadrática sujeito a uma restrição de capacidade linear. O problema possui aplicações em várias áreas, como por exemplo, telecomunicações. engenharia financeira, problemas de localização e teoria dos grafos (clique máximo). Propomos um algoritmo de Branch-and-Bound para resolver exatamente QKP, baseado em Relaxação Lagrangeana. Inicialmente, linearizamos a formulação do problema acima, e em seguida, aplicamos a técnica de relax-and-cut dinamicamente à relaxação contínua do problema, utilizando algumas classes de desigualdades válidas. O método do subgradiente é usado neste processo. Propomos também uma nova heurística primal para QKP, que obtém soluções melhores do que heurísticas propostas anteriormente, encontrando a solução ótima em todas as instâncias que consideramos. A boa qualidade dos limites superior e inferior é traduzida em gap`s pequenos no nó raiz da árvore de enumeração (em geral, menor do que 1%, inclusive para instâncias difíceis). Isto, aliado a testes de fixação de variáveis, permite resolver exatamente QKP em poucos nós da árvore de enumeração. Introduzimos uma maneira de gerar instâncias aleatórias mais difíceis do que as instâncias na literatura. Apresentamos resultados computacionais para instâncias geradas aleatoriamente (instâncias da literatura, e as novas instâncias mais difíceis) para QKP de tamanhos e densidades diferentes; e também para instâncias conhecidas do problema de clique máxima. / [en] We consider the 0-1 Quadratic Knapsack Problem (QKP), which consists of maximizing a quadratic Boolean function subject to a linear capacity constraint. The problem has applications in several areas such as telecommunications, financial engineering, location problems, graph theory (Max Clique). We propose a Branch-and-Bound algorithm to solve the QKP to optimality based on lagrangian Relaxation. Initially, we linearize the formulation of the problem given above and then we relax-and-cut dinamicaly its continous relaxation using a few classes of valid inequalities. In the process the Subgradient Method is applied. We also propose a new primal heuristic for the QKP that has improved upon previous approaches, and finds an optimal solution for all of the instances we considered. The good quality of our upper and lower bounds is translated into small gaps at the root node of the enumeration tree (usually below 1%, even for difficult instances). That, coupled with tests for fixing variables, allowed optimality to be proven within only a few nodes of the enumeration tree. We provide a way to randomly generate instances of the QKP harder than those in the literature. We report computational results for randomly generated instances (the ones in the literature and the new harder ones) of QKP with different densities and sizes; and also for Known instances of Max Clique problems.

[pt] Problemas de Programação de Horários (PPHs) tem sido amplamente estudados, dada a sua importância prática e teórica. A maioria das variações do problema pertence µa classe NP-Difícil. Em geral, trata-se da alocação de recursos materiais e humanos no espaço e no tempo, visando a otimização de um conjunto de objetivos definidos. Na Programação de Horários de Cursos Universitários, por exemplo, o objetivo pode ser a satisfação do corpo docente e o desempenho acadêmico dos alunos. Nos últimos anos, as formulações de PPHs propostas pela International Timetabling Competition (ITC) tem sido bastante utilizadas, sendo notável a predominância de métodos baseados em busca local e metaeurísticas entre as abordagens propostas recentemente. Este trabalho tem como objetivo propor algoritmos para o Problema de Programação de Horários Pós-Matrícula da ITC, focando principalmente em métodos heurísticos baseados em Programação Matemática. Entre os modelos de Programação Linear Inteira Mista que propomos para este problema, destaca-se o modelo baseado na Formulação de Representantes Assimétricos para o Problema de Coloração de Grafos. Abordamos a aplicação da heurística de Local Branching e propomos um esquema de resolução por Geração de Colunas, como forma de viabilizar o tratamento dos modelos propostos, uma vez que a complexidade de tais modelos representa um desafio para os resolvedores de Programação Linear Inteira Mista atualmente disponíveis. / [en] Timetabling Problems have been widely studied, given its practical and theorical relevance. Most of its variations belong to the NP-Hard class of problems. In general, it is about allocation of material and human resources in time and space, aiming to optimize some set of defined objetives. In University Course Timetabling, for example, the objective might be the satisfaction of professors and the academic performance of students. In the last years, the formulations for timetabling problems proposed by the In- ternational Timetabling Competition (ITC) have been widely adopted. The predominance of meta-heuristics and local search-based methods is remark- able among the recently proposed approaches. The objetive of this thesis is to propose algorithms for the Post Enrolment-based Course Timetabling Problem of the ITC, focusing on Mathematical Programming-based heuris- tic methods. Among the Mixed Integer Linear Programming models that we propose for this problem, we highlight the one based on the Asymetric Representatives Formulation for the Graph Coloring Problem. We explore the application of the Local Branching heuristic and we propose a Column Generation solution procedure, as an attempt to handle the proposed models, given that the complexity of such models poses a challenge for currently available Mixed Integer Linear Programming solvers.

[pt] Esta dissertação apresenta uma integração entre a programação funcional e a programação em lógica, obtida pela definição e implementação da Linguagem LispLog. Nesta nova linguagem, o resultado de uma resolução pode ser utilizado como argumento de uma função (pelo operador metalisp) e o resultado da avaliação de uma função pode ser ligado a uma variável lógica (pelo operador avalia). A construção desta linguagem foi realizada a partir da simulação, em microcomputador similar ao IBM-PC, de uma máquina com arquitetura de pilhas, chamada Máquina LispLog, e de seu compilador. A utilização desta linguagem é possível através do Sistema LispLog, que fornece um ambiente de programação orientado por menus. / [en] This dissertation shows an integration between the function programming and logic programming, achieved through LispLog Language’s definition and implementation. In this new language the resultant of a resolution may be used as an argument of a function (through metalisp operator) and the result of a function’s avaliation may be linked to a logic variable (through avalia operator). The LispLog Language was constructed by a simulation of stack architecture machine, named LispLog Machine, and its compiler, in a microcomputer similar similar to IBM-PC. The LispLog System provides a programming environment oriented by menus, wich makes possible the use of this language

[pt] O transporte de materiais perigosos tem recebido atenção considerável nos últimos anos, despertando assim o interesse de pesquisadores em se aprofundar e desenvolver modelos matemáticos de roteirização que minimizem o risco associado a esta operação. O presente trabalho baseia-se em estudos focados em encontrar rotas que minimizam a distância total, a probabilidade de acidentes, a população potencialmente exposta, as conseqüências associadas aos acidentes ou uma combinação desses fatores. No entanto, ainda que uma rota possa ter uma probabilidade muito baixa de acidente, ou estar associada a uma baixa conseqüência esperada (custo), pode não ser correto escolher essa rota se a conseqüência potencial ao ocorrer um acidente seja alta. Percebe-se então, que os diferentes interesses ligados à otimização do transporte de Materiais Perigosos (MP) podem ser conflitantes entre si, obtendo assim um problema com múltiplos objetivos, no qual nem sempre é possível identificar a melhor solução, ou seja, uma alternativa que se desempenha melhor que outras, em todos os critérios. Nesse contexto, o estudo que segue apresenta um modelo multiobjetivo para a roteirização de MP, além de uma metodologia específica de resolução que permita determinar rotas que minimizam o risco de acidentes com baixas probabilidades de ocorrência, mas com altas conseqüências, que podem dar lugar a altos custos, tanto ao meio ambiente como à população exposta. Ao final do trabalho são feitas indicações de questões e extensões para futuras pesquisas. / [en] Hazardous materials transportation has received considerable attention in the last years. Many researchers have been developing mathematical models that minimize the risk associated to this operation. The present work is based on studies that focus routing techniques that minimize either the total distance, the expected number of accidents (fatal or not fatal), the accident probability, the residential population within a given distance from a route, or a mixture of these parameters. They work with the assumption that a route should not be chosen if the potential consequence incurred given that an accident occurs is high, even if the route has a very low probability of an accident, or a low associated expected consequence. For this reason, it is possible to observe that an important characteristic of the hazardous materials routing problem is the existence of multiple conflicting objectives. This means that a route that minimizes risk may not coincide with a route that minimizes the truck operating cost, or with a route that minimizes the risk imposed to special population categories. In this context, this research presents a multiobjective model to the Hazardous Materials Routing and also a specific solution methodology that determines routes that minimize the accident risk with low probabilities, but with high consequences, including the high cost affecting the environment and the population exposed. A number of extensions and open issues are indicated for future research.

[pt] No nosso quotidiano ouvimos com frequência falar da importância das Tecnologias de Informação e Comunicação (TIC) pelos diversos atores sociais. A influência das TIC atravessa as diversas áreas da sociedade como: agricultura, serviços, comércio, indústria, investigação, entre outros. Se fizermos um raciocínio inverso será difícil nomearmos campos sociais que não sejam influenciados direta ou indiretamente pelas TIC. Além disso a demanda de trabalhadores em Computer Science e áreas relacionadas a STEM (Science, Technology, Engineering and Mathematics) está em aumento. É por isso mesmo que é importante que as crianças desde tenra idade se interessem pela tecnologia (Programação de computadores) e participem dela de uma forma divertida e lúdica. O presente trabalho propõe a criação de uma ferramenta de Realidade Virtual que permite que os estudantes aprendem conceitos básicos da programação e pensamento computacional tendo como finalidade que eles desfrutem da tecnologia e se sintam motivados em aprender mais. A ferramenta é uma Linguagem Visual de Programação. Os algoritmos são formados mediante a montagem de blocos-, resolvendo com isso um dos principais problemas dos estudantes que são os erros de sintaxe. Além disso a ferramenta traz consigo um conjunto de desafios ordenados por níveis, que têm como finalidade ensinar aos estudantes princípios básicos da programação e a lógica (programação sequencial, estrutura de dados repetitiva e condicional), onde em cada nível o aluno aprenderá as diferentes conceitos e comportamentos do pensamento computacional. Para as avaliações com os usuários se contou com a participação de 18 alunos com idades entre 12 e 15 anos provenientes de duas instituições públicas do Rio de Janeiro. Nestas avaliações considerou-se também medir a sensação de imersão mediante a Telepresença, Presença Social e Usabilidade. / [en] Nowadays, we often hear about the importance of Information and Communication Technologies (ICT) by various social actors. The influence of ICT crosses the various areas of society as agriculture, services, trade, industry, research, among others. If we do an inverse reasoning, it will be difficult to name social fields that are not directly or indirectly influenced by ICTs. In addition, the demand for workers in Computer Science and areas related to the STEM (Science, Technology, Engineering, and Mathematics) is on the rise. That is why it is important to make the young person interested in technology (Computer programming) and participate in it in a fun and playful way. The present work proposes the creation of a Virtual Reality tool that allows students to learn basic concepts of programming and computational thinking with the purpose that they enjoy the technology and feel motivated to learn more. The tool is a Visual Programming Language; the algorithms are formed by block-assembly, thereby solving one of the students main problems, which are syntax errors. In addition, the tool brings with it a set of level-ordered challenges aimed at teaching students basic principles of programming and logic (sequential programming, repetitive and conditional data structure), where at each level the student will learn the different concepts and behaviors of computational thinking. For the evaluations with the users we counted on the participation of 18 students between 12 and 15 years old coming from two public institutions of Rio de Janeiro. In these evaluations it was also considered to measure the sensation of immersion through Telepresence, Social Presence and Usability.

Este trabalho descreve a aplicação da Programação Genética, uma técnica de Computação Evolucionária, ao problema da Síntese de Fala automática. A Programação Genética utiliza as técnicas da evolução humana para descobrir programas bem adaptados a um problema específico. Estes programas, compostos de instruções, variáveis, constantes e outros elementos que compõe uma linguagem de programação, são evoluídos ao longo de um conjunto de gerações. A Síntese de Fala, consiste na geração automática das formas de ondas sonoras a partir de um texto escrito. Uma das atividades mais importantes, é realizada através da conversão de palavras e letras para os sons da fala elementares (fonemas). Muitos sistemas de síntese são implementados através de regras fixas, escritas por programadores humanos. Um dos mais conhecidos sistemas de síntese é o FESTIVAL, desenvolvido pela Universidade de Edimburgh, usando a linguagem de programação funcional LISP e um número fixo de regras. Neste trabalho, nós exploramos a possibilidade da aplicação do paradigma da Programação Genética, para evoluir automaticamente regras que serão adotadas para implementação do idioma Português na ferramenta FESTIVAL, desenvolvido no projeto SPOLTECH (CNPq – NSF cooperação entre UFRGS e Universidade do Colorado). A modelagem do problema, consiste na definição das regras de pronúncia do Português Brasileiro, que a implementação do sistema FESTIVAL pronuncia erradamente, já que o mesmo foi implementado primariamente para o idioma Inglês. A partir destas regras, o sistema de Programação Genética, desenvolvido neste trabalho, evolui programas que constituem boas soluções para a conversão de letras para fonemas. A descrição dos resultados obtidos, cobre detalhes sobre a evolução das soluções, complexidade e regras implementadas, representadas pelas soluções mais bem adaptadas; mostrando que a Programação Genética, apesar de ser complexa, é bastante promissora.

A dificuldade dos estudantes em relação à aprendizagem de Algoritmos é um assunto que se renova, devido à grande demanda de mercado em relação a profissionais da área de Tecnologia da Informação. A complexidade na construção do raciocínio lógico e do Pensamento Computacional leva a altos índices de evasão e reprovação em disciplinas introdutórias de programação. A concepção tradicional no ensino de Algoritmos possui grandes desafios, da elaboração de materiais interessantes, que estimulem o aluno a resolver problemas, até o uso de novas tecnologias, a fim de motivar o discente em um ambiente dinâmico. Entendendo essas circunstâncias, esta tese tem como foco propor uma concepção diferenciada para o processo de ensino de Algoritmos, caracterizada por uma prática pedagógica baseada na integração de ambientes imersivos a paradigmas de programação, diferentes dos comumente utilizados em sala de aula. Os resultados alcançados com esta proposta mostraram que as características de interação e imersão, proporcionadas pelo mundo virtual, aliadas a ferramentas de programação em blocos visuais, motivam e estimulam a atenção dos alunos, tornando-os protagonistas no desenvolvimento de seus saberes sobre algoritmos e programação. Estas afirmações estão calcadas na observação dos experimentos realizados, com base na metodologia de ensino proposta, consolidados a partir de uma inferência estatística apurada sobre os resultados dos alunos na disciplina de Algoritmos e programação nos três semestres avaliados e, por uma análise detalhada sobre a evolução destes estudantes durante todas as atividades da última etapa do estudo. Estas análises mostraram efetivamente a evolução dos estudantes, tanto na construção do raciocínio lógico, quanto na melhoria do seu desempenho acadêmico. / Difficulties of students towards learning algorithms are a topic that is being renewed constantly, due to the large market demand in relation to professionals in the field of Information Technology. The complexity in the construction of logical reasoning and Computational Thinking leads to high rates of evasion and failure in introductory programming courses. Traditional concept in teaching algorithms has great challenges, since the development of interesting materials that encourage students to solve problems, until to the use of new technologies in order to motivate the students in a dynamic environment. Understanding these circumstances, this thesis focuses on proposing a different design to the process of teaching algorithms, characterized by a pedagogical practice based on the integration of immersive environments with programming paradigms, different from those commonly used in the classroom. The results obtained with this proposal showed that the interaction and immersion features offered by the virtual world, combined with programming tools in visual blocks, motivate and stimulate student's attention, making them protagonists in developing their knowledge about algorithms and programming. These statements are justified by the observation of experiments conducted, based on the proposed teaching methodology, consolidated from a statistical inference calculated on the results of the students in the discipline of algorithms and programming in three semesters evaluated, and, for a detailed analysis of the evolution of these students during all activities of the last stage of the study. These analyzes showed effectively the progress of students, both in the construction of logical reasoning and in improving their academic performance.

Modelos BDI (ou seja, modelos Beliefs-Desires-Intentions models) de agentes têm sido utilizados já há algum tempo. O objetivo destes modelos é permitir a caracterização de agentes utilizando noções antropomórficas, tais como estados mentais e ações. Usualmente, estas noções e suas propriedades são formalmente definidas utilizandos formalismos lógicos que permitem aos teóricos analisar, especificar e verificar agentes racionais. No entanto, apesar de diversos sistemas já terem sido desenvolvidos baseados nestes modelos, é geralmente aceito que existe uma distância significativa entre esta lógicas BDI poderosas e sistemas reais. Este trabalho defende que a principal razão para a existência desta distância é que os formalismos lógicos utilizados para definir os modelos de agentes não possuem uma semântica operacional que os suporte. Por “semântica operacional” entende-se tanto procedimentos de prova que sejam corretos e completos em relação à semântica da lógica, bem como mecanismos que realizem os diferentes tipos de raciocínio necessários para se modelar agentes. Há, pelo menos, duas abordagens que podem ser utilizadas para superar esta limitação dos modelos BDI. Uma é estender as lógicas BDI existentes com a semântica operacional apropriada de maneira que as teorias de agentes se tornem computacionais. Isto pode ser alcançado através da definição daqueles procedimentos de prova para as lógicas usadas na definição dos estados mentais. A outra abordagem é definir os modelos BDI utilizando formalismos lógicos apropriados que sejam, ao mesmo tempo, suficientemente poderosos para representar estados mentais e que possuam procedimentos operacionais que permitam a utilizaçao da lógica como um formalismo para representação do conhecimento, ao se construir os agentes. Esta é a abordagem seguida neste trabalho. Assim, o propósito deste trabalho é apresentar um modelo BDI que, além de ser um modelo formal de agente, seja também adequado para ser utilizado para implementar agentes. Ao invés de definir um novo formalismo lógico, ou de estender um formalismo existente com uma semântica operacional, define-se as noções de crenças, desejos e intenções utilizando um formalismo lógico que seja, ao mesmo tempo, formalmente bem-definido e computacional. O formalismo escolhido é a Programação em Lógica Estendida com Negação Explícita (ELP) com a semântica dada pelaWFSX (Well-Founded Semantics with Explicit Negation - Semântica Bem-Fundada com Negação Explícita). ELP com a WFSX (referida apenas por ELP daqui para frente) estende programas em lógica ditos normais com uma segunda negação, a negação explícita1. Esta extensão permite que informação negativa seja explicitamente representada (como uma crença que uma propriedade P não se verifica, que uma intenção I não deva se verificar) e aumenta a expressividade da linguagem. No entanto, quando se introduz informação negativa, pode ser necessário ter que se lidar com programas contraditórios. A ELP, além de fornecer os procedimentos de prova necessários para as teorias expressas na sua linguagem, também fornece um mecanismo para determinar como alterar minimamente o programa em lógica de forma a remover as possíveis contradições. O modelo aqui proposto se beneficia destas características fornecidas pelo formalismo lógico. Como é usual neste tipo de contexto, este trabalho foca na definição formal dos estados mentais em como o agente se comporta, dados tais estados mentais. Mas, constrastando com as abordagens até hoje utilizadas, o modelo apresentanto não é apenas uma especificação de agente, mas pode tanto ser executado de forma a verificar o comportamento de um agente real, como ser utilizado como mecanismo de raciocínio pelo agente durante sua execução. Para construir este modelo, parte-se da análise tradicional realizada na psicologia de senso comum, onde além de crenças e desejos, intenções também é considerada como um estado mental fundamental. Assim, inicialmente define-se estes três estados mentais e as relações estáticas entre eles, notadamente restrições sobre a consistência entre estes estados mentais. Em seguida, parte-se para a definição de aspectos dinâmicos dos estados mentais, especificamente como um agente escolhe estas intenções, e quando e como ele revisa estas intenções. Em resumo, o modelo resultante possui duas características fundamentais:(1) ele pode ser usado como um ambiente para a especificação de agentes, onde é possível definir formalmente agentes utilizando estados mentais, definir formalmente propriedades para os agentes e verificar se estas propriedades são satifeitas pelos agentes; e (2) também como ambientes para implementar agentes.