Condição de obtenção de frequência: entrega da versão definitiva da monografia até ao fim das aulas do segundo semestre.
Recomenda-se a entrega de uma versão inicial completa da monografia até ao fim das férias da Páscoa para recolha de comentários.
A nota final será a média pesada da nota do trabalho, com peso 75, e da nota da apresentação oral em exame, com peso 25.
Notar que cada orientador vai apenas orientar um trabalho.
Apesar de não existir uma forma normal mínima para as expressões regulares, existem diversas possíveis relações de ordem parcial que estabelecem quando duas espressões regulares equivalentes são simplificações (uma da outra). Pretende-se estudar o problema da simplificação automática, eventualmente utilizando álgebras de Kleene, e implementação de tal sistema.
Estudo dos protocolos de eleições electrónicas hoje propostos, e implementação de um sistema "automático" de eleições em que devem estar presentes, pelo menos, componentes que automatizem a votação, autenticação de votantes e boletins, contagem de votos e verificação de integridade.
A ideia é desenvolver uma aplicação gráfica que, dado um pequeno conjunto de regras gramaticais do Maya Clássico, e um vocabulário builtin, permita ao utilizador selecionar os diferentes hieroglifos que ocorrem no texto, enquanto a aplicação vai indicando a sua função sintática, traduções possíveis e dando pistas para quais os hieroglifos seguintes e a sua função na frase.
À partida a informação parece ser uma entidade de difícil quantificação visto tratar-se de um conceito qualitativo. Em 1948 Claude Shannon introduz a Teoria da Informação, onde a informação é tratada de forma quantitativa. De entre outros resultados, a teoria da informação mostra como medir de uma forma precisa a redundância. Só os dados que contêm redundância podem ser comprimidos.
Pretende-se um trabalho de síntese sobre teoria da informação, compressão de dados e a descrição/implementação de alguns algoritmos conhecidos de compressão de dados.
Com este trabalho pretende-se tirar partido da interface à linguagem C que a maioria dos sistemas Prolog possuem para desenvolver um módulo externo para implementar tabulação em Prolog. O trabalho requer o estudo da máquina abstracta de Prolog, o estudo da técnica de tabulação e tem uma componente de programação que envolve a implementação das primitivas de suporte à tabulação.
Notar que cada orientador vai apenas orientar um trabalho, sendo excepção Armando Matos e Luís Lopes que orientarão dois.
Algoritmos elementares e análise da sua eficiência. Algoritmos aleatorizados. Os testes de Miller-Rabin e Solovay-Strassen. Implementação dos algoritmos: geração de aleatórios, manipulação de inteiros de precisão arbitrária. Aplicação à determinação de primos grandes de determinada forma (por exemplo 2n-1).
Os algoritmos aleatorizados utilizam uma fonte de valores aleatórios com vista à tomada de decisões. A utilização de números (verdadeiramente) aleatórios permite em muitos casos a obtenção de algoritmos mais simples e eficientes do que qualquer algoritmo conhecido para o problema em causa. Estruturação do trabalho:
A importância da eficiência dos algoritmos de pesquisa de "strings". O algoritmo elementar de pesquisa de um "string" num texto e a sua eficiência. O algoritmo de Rabin-Karp. Pesquisa baseada em autómatos finitos: geração, representação e simulação do autómato finito. O algoritmo de Knuth-Morris-Pratt.
Em 1968, o biólogo Aristid Lindenmayer inventou uma forma de representar o algoritmo de crescimento de uma estrutura biológica. Essa representação a que foi dado o nome de "sistema L" é composta de um conjunto de regras e axiomas, constituindo o que em Ciência de Computadores é comum chamar uma gramática. A cada regra do sistema associarmos uma acção física, como por exemplo a bifurcação de um ramo numa árvore. A aplicação sucessiva das regras dessa gramática produz termos sucessivamente mais complexos da linguagem que, quando interpretados como acções dão origem ao crescimento de estruturas muitas delas com claras afinidades a estruturas biológicas.
O objectivo deste trabalho de monografia consiste em explorar estes sistemas em dimensão 1, 2 e eventualmente 3, vizualizando o tipo de estruturas obtido com diferentes sistemas L e tipos de acções associadas. Naturalmente, o trabalho tem uma componente de programação que envolve a implementação de uma aplicação gráfica (e.g., em Tcl/Tk, Java, Python) que possa ser utilizada como uma ferramenta didáctica na representação destas estruturas permitindo a vizualização do crescimento de estruturas em simultâneo com a selecção da regra a utilizar.
Este trabalho de monografia tem como objectivo o estudo sobre as diferentes implementações de cache usadas nos CPU actuais. Entre outros pontos deverão ser estudados as estratégias de: fetch da memória (demand e pre-fetch); localização na cache (mapeamento directo, fully associative e set-associative); substituição de linhas (LRU, FIFO e aleatória); actualização da memória (write through e write back).
Muitos dos problemas práticos que se estudam no mundo académico têm aplicação em situações distantes e pouco conhecidas pelos investigadores. O problema da elaboração de horários tem a enorme vantagem de permitir criar instâncias realistas sem recurso a fontes externas. Outro dos atractivos consiste na possibilidade de utilização prática imediata.
Neste trabalho pretende-se fazer um estudo das diferentes variantes do problema e das estratégias utilizadas para o abordar.
Tratando-se de um problema difícil, para a obtenção de soluções práticas é necessário recorrer a um algoritmo aproximado. Deve-se fazer uma pesquisa dos algoritmos mais eficientes, proceder à sua implementação, e analisar o seu desempenho.
O arredondamento de um número real a uma fracção tal que o denominador não possa exceder um determinado valor, por forma a minimizar a diferença entre a fracção e o número real seja mínima, é um problema que foi já estudado pelos gregos.
Neste trabalho pretende-se fazer um estudo histórico dos algoritmos existentes para este problema, e uma análise aprofundada da sua eficiência em termos de tempo computacional, qualidade da solução obtida, e estabilidade numérica.
Deverá ser feito também um apanhado das aplicações práticas deste algoritmo.
A Análise de Fluxo de Dados é usada para obter informação sobre um programa (normalmente em código intermédio) de modo a ser possível determinar quais as transformações a fazer ao programa para o tornar mais eficiente. Essas transformações terão de preservar o significado do programa. Exemplos de informações obtidas são: se uma variável num dado ponto do programa ainda virá a ser usada depois, ou quais as expressões cujos valores foram calculados e estão em memória quando se chega a um certo ponto do programa.
O trabalho incluirá o estudo desta matéria e a implementação de um conjunto ilustrativo destes algoritmos.
Um dos problemas em Processamento de Linguagem Natural (PLN) é o de se fazer a análise sintáctica de frases das línguas a tratar.
O trabalho incidirá sobre o estudo, implementação e comparação dos algoritmos mais habitualmente usados nestes sistemas.
A indicação BDCC significa que existe um exemplar na Biblioteca do DCC.
Pretende-se um trabalho de síntese sobre a computação quântica e uma análise detalhada de alguns algorítmos quânticos, por exemplo o problema de Deutsch que combina paralelismo quântico com interferência e o algorítmo de factorização proposto por Peter Shor.