Matemática Discreta

Código:

EIC0011

Sigla:

MDIS

Áreas Científicas
Classificação	Área Científica
OFICIAL	Matemática

Ocorrência: 2008/2009 - 2S

Ativa?	Sim
Página Web:	http://moodle.fe.up.pt/0809/course/view.php?id=747
Unidade Responsável:	Departamento de Engenharia Informática
Curso/CE Responsável:	Mestrado Integrado em Engenharia Informática e Computação

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
MIEIC	162	Plano de estudos oficial a partir de 2006/07	1	-	5	56	135
		Plano de estudos de transição para 2006/07	1	-	5	56	135

Língua de trabalho

Português

Objetivos

O principal objectivo desta unidade curricular é a aprendizagem de novas ferramentas e técnicas para analisar e resolver problemas em diversas áreas.
Os estudantes devem ficar capazes de analisar problemas usando as metodologias da matemática, pensamento abstracto, inferência lógica a partir de premissas, e soluções rigorosas e concisas.

Programa

LÓGICA e DEMONSTRAÇÃO. Proposições e seus valores. Operações lógicas: conjunção, disjunção inclusiva e exclusiva, negação, suas tabelas de verdade. Tautologias e contradições. Proposições condicionais e equivalências suas tabelas de verdade. Álgebra das proposições. Fórmulas de De Morgan. Dualidade. Tipos de proposições condicionais. Argumentos. Resolução. Lógica dos predicados. Quantificadores. A natureza da prova. Utilização das proposições condicionais. Prova por contradição. Indução matemática,suas aplicações.

TEORIA dos CONJUNTOS. Definições, notações. Operações, suas propriedades. Diagramas de Venn. Cardinalidade e primeiros princípios de contagem. Dualidade. Família de conjuntos. Conjunto potência. Partição de um conjunto. Tipos ou categorias, conjuntos tipificados, operações. Pré-condições e pós-condições.

RELAÇÕES. Definição e sua representação. Representação matricial. Relacções e tipos, operações e suas propriedades. Relações de equivalência e partições. Utilização da aritmética modular, congruências, como exemplo. Relações de ordem. Representação por digrafos. Elementos maximais e minimais. Máximo e mínimo. Diagrama de Hasse. Aplicação ás bases de dados relacionais.

FUNÇÕES e OPERADORES. Definições e notações. Domínio, codominio e contradomínio. Composição. Injectividade, sobrejectividade, bijectividade e invertibilidade. Cardinalidade do conjunto de funções relacionada com a cardinalidade do domínio e codomínio. Utilização das bases de dados como aplicação da noção de dependência funcional. Formas normais.

ESTRUTURAS ALGÉBRICAS. Operações binárias e suas propriedades. Semi-grupos, monóides e grupos. Grupos cíclicos. Grupos diedrais e grupos de permutações. Sub-estruturas. Morfismos e isomorfismos. Grupos de código. Aplicações. Álgebra de Boole. Operações, propriedades. Funções booleanas. Mintermos e maxtermos. Aplicações. Simplificações de funções booleanas. Códigos de Gray e quadros de Karnaugh.

MÉTODOS de CONTAGEM. Princípios da adição e da multiplicação. Permutações e combinações, sua geração. Permutações e combinações generalizadas, sua geração. Princípio do pigeonhole ou das gavetas de Dirichlet. Princípio da inclusão-exclusão, sua fórmula geral. Desarranjos, sua definição e contagem. Funções geradoras e sua aplicação ás contagens. Relações de recorrência e sua aplicação ás contagens. Exemplos de aplicação.

TEORIA dos GRAFOS. Definição de grafo. Terminologia e exemplos. Digrafos. Grafos bipartidos.Casos particulares. Caminhos, circuitos e ciclos. Conectividade. Representação matricial dos grafos e suas propriedades.Isomorfismo entre grafos. Grafos Eulerianos. Grafos Hamiltonianos. Grafos planos. Teorema de Kuratowski. Fórmula de Euler para grafos planos. Grafos pesados.

ÁRVORES. Definições e notações.Terminologia e caracterização de árvores. Árvores geradas por grafos. Árvores binárias e tipos de atravessamento. Isomorfismo de árvores.

Bibliografia Obrigatória

Rosen, Kenneth H.; Discrete mathematics and its applications. ISBN: 0-07-289905-0
Garnier, Rowan; Discrete mathematics for new technology. ISBN: 0-7503-0652-1

Métodos de ensino e atividades de aprendizagem

Nas aulas teóricas aprende-se e discute-se a matéria da disciplina, e os exemplos de aplicação. Nas aulas práticas faz-se a análise e resolução de problemas, aplicando as ferramentas e os conhecimentos adquiridos nas aulas teóricas.

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Descrição	Tipo	Tempo (Horas)	Peso (%)	Data Conclusão
Participação presencial (estimativa)	Participação presencial	65,00
Exame final	Exame	2,00
Trabalho de avaliação individual	Exame	5,00
Estudo	Exame	63,00
	Total:	-	0,00

Obtenção de frequência

Haverá três mini-testes (a realizar nas aulas Teórico-Práticas) com a duração de 30 minutos e um trabalho individual, representando cada um dos elementos 4,5 valores da avaliação distribuída. A participação nas aulas é um dos elementos de avaliação representando 2 valores da avaliação distribuída.
Para obter frequência, o aluno deve ter pelo menos 6 valores na avaliação distribuída e não exceder o limite legal de faltas.

Fórmula de cálculo da classificação final

O exame final é uma prova escrita sem consulta, com a duração de 2 horas, constituída por uma parte prática, contendo 6 problemas, e uma parte teórica, contendo 3 perguntas, valendo respectivamente 75% e 25% da classificação (E).
A classificação da avaliação distribuída(D) contribui com D/4 valores para a classificação final, enquanto que a classificação do exame contribui com 20-D/4 valores. Assim, todos os alunos admitidos a exame final podem obter a classificação máxima.
A nota da classificação final (F) é calculada somando as duas componentes
F = D/4 + (20-D/4)/20*E

Avaliação especial (TE, DA, ...)

Nestes casos não será tomada em consideração a classificação da avaliação contínua.

Melhoria de classificação

Na melhoria de classificação, não será tomada em consideração a classificação da avaliação contínua.