Disciplina Curricular

Matemática Discreta MD

Licenciatura Bolonha em Engenharia Informática e de Computadores - Alameda - LEIC-A 2006

Contextos

Grupo: LEIC-A 2006 > 1º Ciclo > Ciências de Engenharia

Período:

Peso

7.5 (para cálculo da média)

Objectivos

Desenvolver o raciocínio matemático rigoroso. Dominar os conceitos e instrumentos matemáticos necessários para a análise de procedimentos e algoritmos, quer quanto à sua correcção, quer quanto à sua eficiência.

Programa

Algoritmia Introdução à linguagem de programação Mathematica. Procedimento versus algoritmo. Análise da eficiência de programas imperativos no pior caso e no caso médio. Notação assintótica. Somatórios, produtórios. Princípio de inclusão-exclusão. Demonstração por indução finita de formas fechadas. Fórmula da soma de Euler. Motivação: análise de algoritmos sobre matrizes, pesquisa e ordenação. Teoria de números elementar Aritmética modular. Divisibilidade, máximo divisor comum, algoritmo de Euclides. Factorização e primalidade, teorema de Euler. Teorema chinês dos restos. Relações de equivalência e de congruência. Corpos finitos. Polinómios sobre corpos finitos. Transformada de Fourier discreta, seu cálculo eficiente e correcção. Motivação: criptografia (RSA), teoria algorítmica de números. Funções geradoras Função geradora de uma sucessão. Propriedades. Coeficientes binomiais. Função geradora de uma variável aleatória discreta, momentos. Análise de recorrências. Teorema da expansão racional. Resolução de equações lineares às diferenças. Motivação: problemas de contagem, análise de algoritmos recursivos, tabelas de dispersão (hashing). Correcção de programas Correcção parcial de programas, condições invariantes. Terminação de programas, expressões variantes. Pré-condição e pós-condição. Cálculo de Hoare para correcção parcial de programas imperativos. Ordens parciais, bem fundadas e indução. Cálculo de Hoare para correcção total de programas imperativos. Motivação: correcção total de algoritmos de pesquisa e ordenação. Grafos Grafos, caminhos e ciclos. Árvores. Problema do percurso mínimo, algoritmo de Dijkstra e sua análise, soluções distribuídas (Chandy-Misra). Grafos dirigidos, fluxos e cortes. Teorema do fluxo máximo, algoritmo de Ford-Fulkerson. Motivação: optimização, problemas de encaminhamento em redes. Linguagens e autómatos Autómatos finitos determinísticos e não determinísticos. Expressões regulares, gramáticas regulares. Linguagens regulares. Lema da bombagem. Autómatos de pilha e linguagens livres de contexto, hierarquia de Chomsky. Motivação: reconhecimento de padrões, algoritmo de Knuth-Morris-Pratt.