GAC024 Matemática Discreta

GAC024 é matemática discreta: a matemática de coisas que você pode contar e da lógica que os computadores executam. Cinco unidades cobrem conjuntos, sistemas de contagem, binário, algoritmos e grafos.

Ela combina naturalmente com os módulos de computação, e universidades que reconhecem GAC016 geralmente também reconhecem esta para um curso de fundamentos de ciência da computação. A avaliação segue o padrão habitual: um teste, uma prova e trabalho de campo.

• ⚠ Matemática discreta tem poucas fórmulas e muito raciocínio. Uma demonstração ou um algoritmo rastreado carrega os pontos, e uma resposta sem explicação rende quase nada.

• Um conjunto 集合 é uma coleção de objetos distintos. Ordem e repetição não importam.
• União 并集 $A \cup B$ é tudo em qualquer um; interseção 交集 $A \cap B$ é o que está em ambos; o complemento de conjunto 补集 é tudo fora.
• Um subconjunto 子集 tem todos seus elementos dentro de outro conjunto.
• Uma relação 关系 pares elementos de dois conjuntos. Uma função 函数 é uma relação onde cada entrada tem exatamente uma saída.
• Um diagrama de Venn 韦恩图 transforma um problema de conjunto em uma imagem, e desenhar um geralmente é mais rápido do que raciocinar sobre ele em palavras.

Exemplo resolvido. Em uma turma de 30 alunos, 18 estudam francês e 15 alemão; 7 estudam ambos. Quantos não estudam nenhum?

Subtrair a interseção uma vez é o princípio da inclusão-exclusão 容斥原理. Somar 18 e 15 sem isso conta os sete duas vezes, que é o erro padrão.

• Uma base numérica 进制 diz quantos dígitos usa. Decimal 十进制 usa dez, binário 二进制 dois, hexadecimal 十六进制 dezesseis.
• O valor de cada dígito é seu valor posicional 位值: no binário os lugares são 1, 2, 4, 8, 16 etc.
• Hexadecimal é atalho para binário: um dígito hexadecimal é exatamente quatro bits, é por isso que endereços de memória são escritos nele.

Exemplo resolvido. Converta 1101 em binário para decimal.

Escreva os valores posicionais acima dos dígitos antes de somar. Fazer isso de cabeça é onde os erros off-by-one vêm.

• Aritmética binária 二进制运算 soma como decimal, fazendo carry em 2 em vez de 10.
• Um bit 位 é um dígito binário; um byte 字节 é oito.
• Álgebra booleana 布尔代数 trabalha com verdadeiro e falso com AND, OR e NOT.
• Uma tabela-verdade 真值表 lista cada combinação de entrada e sua saída, e é a prova completa de que duas expressões lógicas são equivalentes.
• Portas lógicas 逻辑门 são a forma física dessas operações, e um circuito lógico 逻辑电路 é o que um processador é feito de.

• Um algoritmo 算法 é uma sequência finita de passos inequívocos que termina.
• Um fluxograma 流程图 desenha-o: uma decisão é um losango, um processo um retângulo.
• Pseudocódigo 伪代码 escreve-o em inglês estruturado, que é o que uma prova geralmente pede.
• Rastreamento 追踪 de um algoritmo — uma tabela com uma coluna por variável e uma linha por passo — é a técnica pontuada, e é assim que você encontra um bug sem executar nada.
• Eficiência 效率 importa: uma busca linear verifica cada item, uma busca binária divide a lista pela metade cada vez, e em um milhão de itens isso faz a diferença entre um milhão de passos e vinte.

Exemplo resolvido. Rastreie uma busca binária para 7 em [1, 3, 5, 7, 9, 11].

Meio é 5, que é menor que 7, então busque a metade direita. Meio de [7, 9, 11] é 9, que é maior, então busque a esquerda. Meio de [7] é 7. Encontrado, em três passos em vez de quatro.

A tabela de passos é a resposta. A palavra "encontrado" não é.

• Um grafo 图 é um conjunto de vértices 顶点 unidos por arestas 边. Modela qualquer coisa com conexões: estradas, amizades, dependências.
• O grau 度 de um vértice é quantas arestas se encontram nele.
• Uma árvore 树 é um grafo conectado sem ciclos, e é a forma de um sistema de arquivos, um organograma e um documento HTML.
• Um problema de caminho mais curto 最短路径 pergunta pela rota mais barata entre dois vértices, e é o que um app de navegação resolve toda vez que você o usa.