Sistemas de Reescrita
Código
8417
Unidade Orgânica
Faculdade de Ciências e Tecnologia
Departamento
Departamento de Matemática
Créditos
6.0
Professor responsável
António José Mesquita da Cunha Machado Malheiro
Horas semanais
5
Total de horas
15
Língua de ensino
Português
Objectivos
Pretende-se apresentar os conceitos básicos da Teoria dos Sistemas de Reescrita, os quais estão na base de muitas aplicações computacionais, incluindo a computação algébrica simbólica, a prova automática de teoremas, a especificação e verificação de programas e a programação de linguagens de ordens superiores. Assim, os alunos obterão as valências necessárias para identificar nos mais variados campos da Teoria da Computação os conceitos aqui apresentados e os que lhes estão subjacentes.
Conteúdo
1. Sistemas abstractos de redução: reduções e equivalências; indução transfinita; Relações de ordem.
2. Sistemas de reescrita de termos: termos, substituições e identidades; álgebras livres; álgebras de termos; classes equacionais; problemas equacionais; modularidade.
3. Sistemas de reescrita de palavras: congruências de Church-Rosser; o problema da palavra; semigrupos e apresentações; sistemas de reescrita monádicos; sistemas de reescrita especiais.
4. Terminação: o problema de decisão; ordens de redução; ordens de simplificação.
5. Confluência: confluência e confluência local; o problema de decisão; pares críticos; ortogonalidade.
6. Completude: o procedimento de Knuth-Bendix; teoremas sobre sistemas de reescrita completos.
7. Bases de Grobner: redução de polinómios; bases de Grobner; algoritmo de Buchberger.
Bibliografia
Método de ensino
Uma vez que a disciplina decorre, este ano, com poucos alunos funcionará em regime tutorial. Nestas horas de trabalho conjunto serão apresentados os principais tópicos e resultados, devendo estes ser complementados com a leitura do livro de referência. Serão propostos exercícios de modo a consolidar o estudo. Os alunos são convidados a apresentar o seu trabalho e as suas dificuldades ao professor durante o horário de dúvidas e também por e-mail.
Método de avaliação
A avaliação de conhecimentos à disciplina de sistemas de reescrita compreende dois modelos. Uma avaliação contínua ou um exame final.
A avaliação contínua tem quatro momentos. Dois serão provas escrita e outros dois trabalhos realizados pelos alunos individualmente. A cada uma destas provas corresponde uma percentagem de 25% da nota final à disciplina. Cada prova escrita tem a duração de 120 minutos. Os trabalhos serão apresentados e discutidos em seminário. Cada uma destas provas será cotada de 0 a 20 valores, com precisão à décima. O resultado final será a média das quatro provas com arredondamento às unidades.
A avaliação em exame final tem a duração de três horas.
Em qualquer das situações, se a nota final for superior a 16 valores, o aluno pode optar por ficar com nota final de 16 valores ou realizar uma prova complementar/oral para defender a nota.