Conceitos de matemática discreta e de lógica para computação (lógica formal e lógica de predicados). Noção de complexidade. Técnicas de demonstração direta, demonstração por contraposição e demonstração por absurdo. Relaçaõ de recorrência, provas, indução matemática. Uso da lógica formal em programação declarativa e na demonstração de correção de um algoritmo. Relações e conceitos de teoria de grafos. Modelagem de problemas usando grafos.
Relacionei os exercícios realizados no 4º bimestre/2020 durante as aulas da disciplina COM150 do Curso de Bacharel de Ciência de Dados da Univesp. Abaixo segue uma breve descrição do problema de negócios e da solução em Python (o link direciona para o código):
- Relação de recorrência 1: Judith L Gersting (Seção 3.1). Exercícios diversos para estabelecer definições e obter soluções para relações recorrentes com uso de algoritmos recursivos.
- Relação de recorrência 2: Judith L Gersting (Seção 3.2). Criando uma seguência com 4 casos básicos. Fórmula fechada de segunda ordem.
- Relação binária com matrizes: criação da classe Matrix e implementação de operadores lógicos e aritméticos, diagonal principal e secundária, características (ordem, identidade, triangular superior, triangular inferior). Cálculo da matriz de acessibilidade para grafos a partir da matriz boolena de adjacência.
- Conversor polonês ou "pré-ordem": dada uma equação algébrica "em ordem" transformá-la em ordem polonesa ou "pré-ordem".
- Conversor polonês inverso ou "pós-ordem": dada uma equação algébrica "em ordem" transformá-la em ordem polonesa inversa ou "pós-ordem".
- Conversor de expressão: conversor gráfico de expressão para operadores booleandos entre "pré-ordem" e "pós-ordem" - infixToPostfix.
- Circuitos e caminhos em grafos: obter a mínima distância entre a origem e destino em um grafo direcionado com pesos em seus vértices.
- Algoritmo de Dijkstra: obter o menor caminho entre dois vértices ponderados de um grafo, usando o algoritmo de Dijkstra.
- Caminho Hamiltonioano: obter todos os possíveis caminhos Hamiltonianos para um grafo a partir de um determinado vértice. Checar se existe um ciclo. Num caminho Hamiltoniano todos os vértices de um grafo devem ser visitados apenas uma única vez.
- Caminho de Euler: verificar se um grafo possui um caminho de Euler. Obter o caminho de Euler. Num caminho de Euler todas as arestas de um grafo devem ser visitados apenas uma única vez.
- Algoritmo de Warshall: dado um grafo G com n nós, o algoritmo de Warshall deve calcular uma sequência de n + 1 matrizes de acessibilidades M0, M1, M2, …, Mn.