Plano de Ensino

IDENTIFICAÇÃO

EMENTA

Estruturas básicas: Conjuntos, Funções, Sequências e Matrizes; Algoritmos: Função de crescimento e Complexidade; Teoria dos Números e Criptografia; Indução e Recursão; Contagem e o Princípio da Casa do Pombo; Relações, Fechamento de Relações, Relações de Equivalência, Estruturas Algébricas, Reticulados e Ordem Parcial; Grafos, Modelos de Grafos, Representação de Grafos, Conectividade; Árvores, Aplicações de Árvores, Buscas em Árvores.

JUSTIFICATIVA

O pensamento lógico, o poder da notação matemática e a utilidade de abstrações constituem princípios básicos na formação do Engenheiro de Computação. Os estudantes precisam entender as estruturas matemáticas discretas e o raciocínio matemático a fim de ler, compreender e construir abstrações computacionais corretas e eficientes.

OBJETIVO

PROGRAMA

1. Estruturas básicas

   1. Conjuntos e Operações em Conjuntos

   2. Funções

   3. Sequências e Somatório

   4. Cardinalidade de Conjuntos

   5. Matrizes

2. Algoritmos

   1. Função de Crescimento

   2. Complexidade de Algoritmos

3. Teoria dos Números e Criptografia

   1. Aritmética Modular e Divisibilidade

   2. Primos e Máximo Divisor Comum

   3. Resolução de Congruências

   4. Criptografia

4. Indução e Recursão

   1. Indução Matemática

   2. Indução Forte e o Princípio da Boa Ordenação

   3. Definições Recursivas e Indução Estrutural

   4. Algoritmos Recursivos

   5. Correção de Programas

5. Contagem

   1. Fundamentos básicos de contagem

   2. Princípio da Casa do Pombo

   3. Permutações e Combinações

   4. Coeficientes Binomiais e Identidades

   5. Aplicações de Relações de Recorrência

   6. Resolução de Relações de Recorrência

   7. Algoritmos com a técnica Dividir para Conquistar

   8. Inclusão-exclusão

6. Relações

   1. Propriedades das Relações

   2. Representação de Relações

   3. Fechamento de Relações

   4. Relações de Equivalência

   5. Estruturas algébricas

   6. Reticulado e Ordem Parcial

7. Grafos

   1. Modelos de Grafos

   2. Terminologia e Tipos Especiais de Grafos

   3. Representação de Grafos e Isomorfismo em Grafos

   4. Conectividade

   5. Caminhos Eulerianos e Hamiltonianos

   6. Problemas de Caminho Mínimo

8. Árvores

   1. Aplicações de Árvores

   2. Buscas em Árvores

   3. Árvores Geradoras e Árvores Geradoras Mínimas (Minimum Spanning Trees)

METODOLOGIA

Técnicas de ensino que serão utilizadas: Aulas expositivas (síncronas - 25 horas) , vídeos expositivos e estudos dirigidos (assíncronos 20 horas - sendo 15 horas práticas).

Recursos didáticos: Software Microsoft Teams para aulas expositivas, Vídeos temáticos e Estudos dirigidos orientados.

Horário de Atendimento aos estudantes:

Segunda-feira 8:00 - 9:00 (Software Microsoft Teams)

Cronograma previsto para desenvolvimento do conteúdo:

1. Estruturas básicas (1a semana)

   1. Conjuntos e Operações em Conjuntos

   2. Funções

   3. Sequências e Somatório

   4. Cardinalidade de Conjuntos

   5. Matrizes

2. Algoritmos (2a e 3a semanas)

   1. Função de Crescimento

   2. Complexidade de Algoritmos

3. Teoria dos Números e Criptografia (4a e 5a semanas)

   1. Aritmética Modular e Divisibilidade

   2. Primos e Máximo Divisor Comum

   3. Resolução de Congruências

   4. Criptografia

4. Indução e Recursão (5a, 6a e 7a semanas)

   1. Indução Matemática

   2. Indução Forte e o Princípio da Boa Ordenação

   3. Definições Recursivas e Indução Estrutural

   4. Algoritmos Recursivos

   5. Correção de Programas

5. Contagem (8a e 9a semanas)

   1. Fundamentos básicos de contagem

   2. Princípio da Casa do Pombo

   3. Permutações e Combinações

   4. Coeficientes Binomiais e Identidades

   5. Aplicações de Relações de Recorrência

   6. Resolução de Relações de Recorrência

   7. Algoritmos com a técnica Dividir para Conquistar

   8. Inclusão-exclusão

6. Relações (10a e 11 semanas)

   1. Propriedades das Relações

   2. Representação de Relações

   3. Fechamento de Relações

   4. Relações de Equivalência

   5. Estruturas algébricas

   6. Reticulado e Ordem Parcial

7. Grafos (12a e 13a semanas)

   1. Modelos de Grafos

   2. Terminologia e Tipos Especiais de Grafos

   3. Representação de Grafos e Isomorfismo em Grafos

   4. Conectividade

   5. Caminhos Eulerianos e Hamiltonianos

   6. Problemas de Caminho Mínimo

8. Árvores (14a e 15a semanas)

   1. Aplicações de Árvores

   2. Buscas em Árvores

   3. Árvores Geradoras e Árvores Geradoras Mínimas (Minimum Spanning Trees)

AVALIAÇÃO

As avaliações serão constituídas de 8 (oito) trabalhos, sendo sete deles com valor de 10 (dez) pontos e um trabalho final com valor 30 pontos, que serão realizados nas seguintes datas correspondentes às semanas:

• 2ª semana: PRIMEIRA AVALIAÇÃO 

• 3ª semana: SEGUNDA AVALIAÇÃO

• 5ª semana: TERCEIRA AVALIAÇÃO

• 7ª semana: QUARTA AVALIAÇÃO

• 9ª semana: QUINTA AVALIAÇÃO

• 11ª semana: SEXTA AVALIAÇÃO

• 13ª semana: SÉTIMA AVALIAÇÃO

• 14ª e 15ª semanda: OITAVA AVALIAÇÃO (trabalho final) (30 pontos)

BIBLIOGRAFIA

Básica

1. Kenneth H. Rosen, Matemática discreta e suas aplicações. 6ª Edição, São Paulo: McGraw-Hill, 2009. ISBN: 9788577260362.

2. GERSTING, Judith L. Fundamentos matemáticos para a ciência da computação: um tratamento moderno de matemática discreta. 5ª ed. Rio de Janeiro: LTC - Livros Técnicos e Científicos, 2004. ISBN 9788521614227.

3. Szwarcfiter, J. L., Grafos e Algoritmos Computacionais. Ed. Campus, 1986.

Complementar

1. MENEZES, Paulo Blauth. Matemática discreta para computação e informática. 2. ed. Porto Alegre: Sagra Luzzatto, 2008. ISBN 8524106913.

2. GRAHAM, Ronald L.; KMUTH, Donald E.; PATASHNIK, Oren. Matemática concreta: fundamentos para a ciência da computação. Rio de Janeiro: LTC, c1995. 475 p. ISBN 9788521610403.

3. SCHEINERMAN, Edward R. Matemática discreta: uma introdução. São Paulo, SP: Thomson, 2003. ISBN 8522102910.

4. MENEZES, P. B.; TOSCANI, L. V.; LOPEZ, J. G. Aprendendo Matemática Discreta com Exercícios. Porto Alegre: Bookman, 2009. Série Livros Didáticos – Informática UFRGS.

5. HUNTER, David J. Fundamentos da Matemática Discreta. Rio de Janeiro: LTC, 2011.

APROVAÇÃO

Aprovado em reunião do Colegiado realizada em: ____/____/______

Coordenação do Curso de Graduação: _________________________

---

Documento assinado eletronicamente por Marcelo Rodrigues de Sousa, Professor(a) do Magistério Superior, em 11/07/2021, às 19:48, conforme horário oficial de Brasília, com fundamento no art. 6º, § 1º, do Decreto nº 8.539, de 8 de outubro de 2015.

---

A autenticidade deste documento pode ser conferida no site https://www.sei.ufu.br/sei/controlador_externo.php?acao=documento_conferir&id_orgao_acesso_externo=0, informando o código verificador 2897753 e o código CRC AF493578.

---