CD102 — Fundamentos Matemáticos da Computação
Ementa, programa e bibliografia da disciplina CD102.
← Voltar para a lista de disciplinas
Ementa
Lógica proposicional e de predicados. Teoria dos conjuntos, relações e funções. Combinatória e princípios fundamentais de contagem. Noções de complexidade e análise assintótica de algoritmos. Estruturas discretas: grafos e árvores. Fundamentos matemáticos aplicados à modelagem em computação e ciência de dados.
Programa
1. Lógica proposicional
- Semântica e sintaxe do cálculo proposicional clássico
- Proposições e fórmulas bem formadas
- Conectivos lógicos: conjunção, disjunção, implicação e negação
- Tabelas-verdade
- Tautologias, contradições e contingências
- Noção de prova, axiomas, premissas e regras de inferência
- Teorema de correção e completude
2. Lógica de predicados
Lógica de primeira ordem
Quantificadores universal e existencial
Predicados e domínio de interpretação
Validade em lógica de predicados
Noções de decidibilidade e indecidibilidade
Regras inferenciais: instanciação universal, instanciação existencial, generalização universal e generalização
existencial
3. Tipos de demonstração
- Provas construtivas
- Provas por exaustão
- Provas diretas
- Provas por redução ao absurdo
- Provas por contrapositiva
4. Indução e recursão
- Provas por indução
- Hipótese indutiva
- Definições recursivas
- Sequências definidas recursivamente
- Conjuntos definidos recursivamente
- Operações definidas recursivamente
- Relações de recorrência
5. Conjuntos, relações e funções
- Formas de representação de conjuntos
- Relações entre conjuntos
- Inclusão, igualdade e diferença entre conjuntos
- Conjunto das partes
- Operações sobre conjuntos
- União, interseção, complemento e produto cartesiano
- Relações e funções
6. Técnicas de contagem e combinatória
- Princípios aditivo e multiplicativo
- Permutações
- Arranjos
- Combinações
7. Probabilidade
- Experimento aleatório
- Espaço amostral
- Eventos
- Propriedades básicas da probabilidade
- Probabilidade condicional
- Regra do produto
- Teorema de Bayes
8. Introdução à teoria dos grafos
- Definições e conceitos iniciais de grafos
- Vértices, arestas e adjacência
- Representação de grafos
- Grafos direcionados e não direcionados
- Uso de ferramentas computacionais para manipulação de grafos
Referências
- GERSTING, Judith L. Mathematical Structures for Computer Science. 7. ed. W. H. Freeman and Company, 2014.
- ROSEN, Kenneth H. Discrete Mathematics and its Applications. 7. ed. McGraw-Hill, 2007.
- SCHEINERMAN, Edward R. Matemática Discreta: uma introdução. Tradução da terceira edição norte-americana por Noverits do Brasil e revisão técnica de Flávio Soares Corrêa da Silva. Cengage Learning, 2017.