PT | EN

MINISTÉRIO DA EDUCAÇÃO

UNIVERSIDADE FEDERAL DE SANTA CATARINA

CENTRO TECNOLÓGICO

DEPARTAMENTO DE INFORMÁTICA E ESTATÍSTICA

PROGRAMA DE ENSINO

1. Identificação

Disciplina:INE5403 - Fundamentos de Matemática Discreta para Computação
Nível:Graduação
Carga Horária:108 horas-aula (Teórica: 108)
Vigência:De 2010-2 até 2019-2

2. Ementa

Conjuntos, Seqüências e Somas. Lógica Proposicional, Lógica de Primeira Ordem, Lógica Matemática (Prova de Teoremas), Indução e Recursão. Análise Combinatória: Permutações e Combinações, O Princípio do Pombal, Relações de Recorrência. Relações: Propriedades de Relações, Relações de Equivalência, Fecho de Relações. Funções: Definição e Tipos. Composição de Funções, Crescimento de Funções. Relações de Ordenamento: Reticulados, Álgebras Booleanas. Estruturas Algébricas: Semigrupos e Grupos. Elementos de Teoria de Números. Aplicações da Matemática Discreta.

3. Cursos Relacionados

4. Objetivos

4.1 Objetivo Geral:

Desenvolver capacidade de raciocínio formal rigoroso e habilidades analíticas e de abstração, ao longo do estudo de conceitos fundamentais da Matemática Discreta que são relevantes para o aprendizado da Ciência da Computação.

4.2 Objetivos Específicos:

  1. Compreender princípios e conceitos básicos da Teoria dos Conjuntos
  2. Compreender princípios e conceitos básicos de Lógica Proposicional, Lógica de Primeira Ordem e Provas de Teoremas
  3. Compreender e aplicar o princípio da Indução Matemática
  4. Compreender e aplicar a abordagem recursiva para a solução de problemas computacionais
  5. Compreender princípios e conceitos básicos dos problemas combinatoriais
  6. Descrever e manipular Relações e tipos especiais de relações
  7. Descrever as principais Estruturas Algébricas
  8. Compreender e aplicar os fundamentos da Teoria de Números

5. Conteúdo Programático

  1. Introdução [4 horas-aula]
    1. Apresentação do curso
    2. Tipos de dados básicos e padrões de notação
  2. Provas (Demonstrações) [10 horas-aula]
    1. Proposições
    2. Predicados e Quantificadores
    3. Provas de Teoremas
  3. Coleções [4 horas-aula]
    1. Conjuntos
    2. Sequências e somas
  4. Indução Matemática [10 horas-aula]
    1. Provas indutivas
    2. Indução Forte
  5. Recursão [6 horas-aula]
    1. Definições Recursivas
    2. Algoritmos Recursivos
  6. Relações [12 horas-aula]
    1. Definição e representação
    2. Caminhos em relações
    3. Propriedades de relações
    4. Manipulação e fecho de Relações
    5. Relações de equivalência
  7. Funções [8 horas-aula]
    1. Definições e tipos
    2. Crescimento de funções
  8. Contagem I [10 horas-aula]
    1. O Princípio do Pombal
    2. Contagem de Conjuntos
    3. Arranjos e Combinações
    4. Coeficientes Binomiais
  9. Contagem II [8 horas-aula]
    1. Resolução de Relações de Recorrência
  10. Relações de ordenamento [8 horas-aula]
    1. Conjuntos Parcialmente Ordenados (Conjuntos PO)
    2. Extremos de Conjuntos PO
    3. Reticulados
    4. Álgebras Booleanas Finitas
  11. Tópicos em Estruturas Algébricas [6 horas-aula]
    1. Operações Binárias
    2. Semigrupos
    3. Grupos
  12. Números Inteiros [14 horas-aula]
    1. Noções Elementares
    2. MDCs e algoritmos de Euclides
    3. Aritmética Modular
  13. Aplicações da Matemática Discreta [8 horas-aula]

6. Bibliografia Básica

  1. KOLMAN, B., BUSBY, R. C., ROSS, S.. Discrete mathematical structures. 3rd ed. Prentice Hall, 1996 (2 exemplares na biblioteca)
  2. TREMBLAY, J.P. Discrete mathematical structures with applications to computer science.. McGraw-Hill, 1975. (1 exemplar na biblioteca)
  3. ROSEN, K.H.. Discrete mathematics and its applications. 5th ed. McGrall-Hill, 2003. (2 exemplares na biblioteca)
  4. SCHEINERMAN, E.R.. Matemática Discreta - Uma introdução, tradução da 2a edição norte-americana, Cengage Learning, São Paulo, 2011
  5. CORMEN, T., LEISERSON, C., RIVEST, R., STEIN, C.. Introduction to Algorithms. MIT Press, 2001.
  6. Curso MIT 6042, http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/

7. Bibliografia Complementar

  1. GERSTING, Judith L. Fundamentos Matemáticos para a Ciência da Computação. 5a. Edição. LTC Editora, 2004. 616p. (15 exemplares na biblioteca)
  2. SINGH, S.. O último teorema de Fermat. 9. ed. Record, 2002. (1 exemplar na biblioteca)
  3. BERLINSKI, D. O advento do algoritmo: a idéia que governa o mundo. Globo, 2002. (1 exemplar na biblioteca)