Disciplina Curricular

Elementos de Matemática Discreta EMD

Licenciatura Bolonha em Engenharia de Telecomunicações e Informática - LERC 2006

Contextos

Grupo: LERC 2006 > 1º Ciclo > Ciências da Engenharia

Período:

Peso

4.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

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. Motivação: criptografia (RSA), teoria algorítmica de números. Algoritmia e correcção de programas Introdução à linguagem de programação Mathematica. Procedimento versus algoritmo. Análise da eficiência de programas imperativos no pior caso. Notação assintótica. Somatórios, formas fechadas, perturbação da soma, indução finita. Correcção parcial e total de programas, condições invariantes, expressões variantes. Pré-condição e pós-condição. Cálculo de Hoare para correcção de programas imperativos. Motivação: análise e verificação de algoritmos sobre matrizes, 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. 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.

Metodologia de avaliação

Avaliação contínua. Média dos 3 melhores de entre 4 testes.

Disciplinas Execução

2016/2017 - 1ºSemestre

2015/2016 - 1º Semestre

2014/2015 - 1º Semestre

2013/2014 - 1 Semestre