Matemática Discreta

Código:

EIC0011

Sigla:

MDIS

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

Ocorrência: 2006/2007 - 2S

Ativa?	Sim
Página Web:	http://paginas.fe.up.pt/~fjr/ensino/20062007/md.html
Unidade Responsável:	Ciências Fundamentais e da Electrotecnia
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
LEIC	0	Plano de estudos de transição para 2006/07	1	5	5	56	135
MIEIC	159	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 disciplina é a aprendizagem de novas ferramentas e técnicas para analisar e resolver problemas em diversas áreas.
Os alunos 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

R. Garnier and J. Taylor; Discrete Mathematics for New Technology, IoP, 2002. ISBN: 0-7503-0652-1 (www.iop.org)
Kenneth H. Rosen; Discrete Mathematics and Its Applications, McGraw-Hill, 1999. ISBN: 0-07-289905-0

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.

Palavras Chave

Ciências Físicas > Matemática > Matemática discreta

Tipo de avaliação

Avaliação distribuída com exame final

Componentes de Avaliação

Descrição	Tipo	Tempo (Horas)	Peso (%)	Data Conclusão
Aulas da disciplina (estimativa)	Participação presencial	70,00
Mini-testes (4 vezes)	Exame	4,00		2007-06-08
Exame final	Exame	3,00		2007-07-20
	Total:	-	0,00

Componentes de Ocupação

Descrição	Tipo	Tempo (Horas)	Data Conclusão
Acompanhamento das aulas	Estudo autónomo	42	2007-06-08
Preparação para o exame final	Estudo autónomo	28	2007-07-20
	Total:	70,00

Obtenção de frequência

Haverá quatro mini-testes, com a duração de 30 minutos cada, ao longo do semestre.
Para obter frequência, o aluno deve ter pelo menos 6 valores na média dos mini-testes 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, constituida 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 contínua (C) contribui com C/4 valores para a classificação final, enquanto que a classificação do exame contribui com 20-C/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 = C/4 + (20-C/4)*E/20 = E + (1-E/20)*C/4

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.