Estruturas Discretas

Código:

CC1001

Sigla:

CC1001

Nível:

100

Áreas Científicas
Classificação	Área Científica
OFICIAL	Ciência de Computadores

Ocorrência: 2014/2015 - 1S

Ativa?	Sim
Página Web:	http://www.dcc.fc.up.pt/~sandra/Home/ED1415.html
Unidade Responsável:	Departamento de Ciência de Computadores
Curso/CE Responsável:	Licenciatura em Ciência de Computadores

Ciclos de Estudo/Cursos

Sigla	Nº de Estudantes	Plano de Estudos	Anos Curriculares	Créditos UCN	Créditos ECTS	Horas de Contacto	Horas Totais
L:CC	77	Plano de estudos a partir de 2014	1	-	6	56	162
MI:ERS	124	Plano Oficial desde ano letivo 2014	1	-	6	56	162

Língua de trabalho

Português

Objetivos

Estudo das estruturas discretas fundamentais que estão na base formal da área de Ciência de Computadores/Informática.

Resultados de aprendizagem e competências

A frequência desta disciplina deve desenvolver as seguintes aptidões:

• Capacidade de trabalhar com notação matemática e com os principais conceitos de matemática discreta;

 

• Construir e compreender provas matemáticas;

 

• Utilizar conceitos matemáticos para formalisar e resolver problemas comuns em Ciência de Computadores/Informática.

 

Modo de trabalho

Presencial

Programa

 

1. Tópicos elementares de lógica: cálculo proposicional, equivalência lógica, regras de inferência, breve introdução ao cálculo de predicados.

 

1. Teoria de conjuntos: conjuntos e subconjuntos, operações de conjuntos, diagramas de Venn.

 

1. Indução matemática: indução matemática, definições por recursão.

 

1. Relações: Produtos cartesianos e relações, propriedades de relações, funções, representações computacionais de relações, ordens parciais, relações de equivalência e partições.

 

1. Grafos: definições e exemplos, subgrafos, grafos complementares e grafos isomorfos, graus de vérices, grafos planares, caminhos e ciclos hamiltonianos.

 

1. Tópicos elementares de álgebra: aneis e aritmética modular, algebra booleana.

 

1. Números inteiros: o algoritmo da divisão, números primos, máximos divisor comum e algoritmo de euclides, o teorema fundamental da aritmética.

 

1. Contagem: somas e productos, permutações, combinações, coeficientes binomiais.

 

Bibliografia Obrigatória

Makinson David 1941-; Sets, logic and maths for computing. ISBN: 978-1-84628-844-9
Grimaldi Ralph P.; Discrete and combinatorial mathematics. ISBN: 978-0-201-54983-6 hbk
Kenneth H. Rosen; Discrete Mathematics and its Applications, McGraw-Hill, Inc.

Métodos de ensino e atividades de aprendizagem

Aulas teóricas de exposição dos conteúdos programático assim como de exemplos e casos de estudo. Aulas práticas de resolução de exercícios propostos semanalmente.

Palavras Chave

Ciências Tecnológicas

Tipo de avaliação

Avaliação distribuída sem exame final

Componentes de Avaliação

Designação	Peso (%)
Exame	50,00
Participação presencial	0,00
Teste	50,00
Total:	100,00

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

Teste intercalar (50% de peso na nota final).
Exame final (50% de peso na nota final).
Sendo TI a classificação obtida  no teste intercalar e EF a
classificação obtida no exame final, então a nota final é dada por:
F = TI*(0.5) + EF*(0.5)
TI,EF >= 6 e F >= 9.5
Não obterão aprovação na avaliação distribuída, os alunos que não obtiverem um mínimo de 6 valores (em 20), em ambos os testes e um mínimo de 9.5 valores de nota final.
Para os alunos que não obtiverem aprovação, haverá um exame de recurso. O exame de recurso terá duas componentes (claramente indicadas) correspondendo aos tópicos avaliados no teste e no exame final respectivamente, permitindo dois cenários possíveis de determinação da nota final:

• os alunos podem responder às duas componentes do exame, sendo nesse caso a nota final determinada exclusivamente pela nota do exame (opção obrigatória para os alunos a realizar melhoria de nota e alunos que não tenham obtido uma nota mínima no primeiro teste);

 

• os alunos podem responder apenas à componente do exame correspondente à matéria avaliada no segundo teste, sendo a nota determinada pela fórmula indicada para a avaliação distribuída.

 

Melhoria de classificação

Exame de melhoria cotado para 20.