Agosto
Conjuntos
MonitoriaReunião com a monitoria
Relações e funções
MP 1Conjuntos
Conjuntos infinitos e enumerabilidade
MP 2Relações e funções
CIN0132 · 2026.2 · Sistemas de Informação
Matemática Discreta para Computação
Cinco unidades: conjuntos, relações e funções; princípios de contagem; sequências e relações de recorrência; lógica e técnicas de demonstração; grafos e árvores.
- Terças
- 18:50–20:30
- Quintas
- 17:00–18:50
- Sala
- E233 · Centro de Informática
Ao fundo, um grafo de disco unitário: dois vértices se ligam quando estão a menos de 160 px um do outro. Animação adaptada do Constellation Field, do ThreeUI.
Agenda 2026.2
Calendário
Aulas, miniprovas (MP), exercícios escolares (EE) e momentos de projeto, conforme a proposta pedagógica da disciplina. Ajustes são avisados no Classroom.
Setembro
Funções especiais
MP 3Conjuntos infinitos e enumerabilidade
Endorrelações
MP 4Funções especiais (offline, em vídeo)
Elementos de aritmética modular
ProjetoEncontro com a monitoria (cancelado)
EE1Primeiro exercício escolar (conteúdo até elementos de aritmética modular)
MP 5Endorrelações (offline, gabarito da turma); em sala, resolução do EE1
Princípio aditivo, princípio multiplicativo da contagem, princípio da inclusão-exclusão e complementar
Outubro
MP 6Elementos de aritmética modular (offline, em vídeo); em sala, apresentação do projeto pela monitoria
Permutações, arranjos, combinação, binômio de Newton
MP 7Princípio aditivo, princípio multiplicativo da contagem, princípio da inclusão-exclusão e complementar (offline, em vídeo); sem aula, por causa da Expo UFPE 2026
Somatórios, PA e PG, somatório de polinômios
MP 8Princípio da inclusão-exclusão, permutações, arranjos, combinação, binômio de Newton
Técnicas de Newton para sequências polinomiais, relações de recorrência
MP 9Somatórios, PA e PG, somatório de polinômios
Lógica proposicional e tabelas-verdade
MP 10Técnicas de Newton para sequências polinomiais, relações de recorrência
Novembro
Técnicas básicas de demonstração
MP 11Lógica proposicional e tabelas-verdade
ProjetoDesenvolvimento de projeto e orientação
ProjetoDesenvolvimento de projeto e orientação
Grafos e árvores I
Grafos e árvores II
Grafos e árvores III
MP 12Técnicas básicas de demonstração
PrazoEntrega do projeto no Classroom
Dezembro
EE2Segundo exercício escolar
ProjetoApresentação dos projetos
Feriado (Nossa Senhora da Conceição, Recife)
FinalProva final
MPminiprovaEEexercício escolarProjetoprojeto e monitoriaFinalprova final
Já liberadas
Listas de exercícios
Cada lista traz afirmações para marcar V ou F, com a dificuldade estimada de cada item, de baixa a alta. O gabarito objetivo aparece logo abaixo do link de cada lista. As listas novas saem no Classroom às terças, depois da aula.
Lista 0111/08
Conjuntos
Abrir PDF
| Questão | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I | F | V | V | F | F |
| II | V | F | F | F | F |
| III | V | F | V | V | V |
| IV | F | V | F | V | V |
Lista 0218/08
Relações e funções
Abrir PDF
| Questão | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I | V | V | V | F | F |
| II | F | V | V | F | F |
| III | F | F | V | F | V |
| IV | V | V | V | F | F |
Lista 0325/08
Conjuntos infinitos e enumerabilidade
Abrir PDF
| Questão | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I | F | F | V | V | F |
| II | V | F | V | F | F |
| III | F | V | V | F | V |
| IV | V | F | F | V | V |
Lista 0401/09
Funções especiais
Abrir PDF
| Questão | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I | V | F | V | V | F |
| II | V | V | V | F | F |
| III | V | V | F | F | F |
| IV | V | F | V | F | F |
Lista 0508/09
Endorrelações
Abrir PDF
| Questão | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I | V | F | F | V | F |
| II | V | F | V | F | F |
| III | V | V | V | V | F |
| IV | F | V | V | F | F |
Lista 0615/09
Elementos de aritmética modular
Abrir PDF
| Questão | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I | V | F | V | F | V |
| II | F | V | F | V | F |
| III | V | F | F | V | V |
| IV | F | V | V | F | F |
Lista 0729/09
Princípios aditivo e multiplicativo, inclusão-exclusão e complementar
Abrir PDF
| Questão | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I | V | F | V | F | F |
| II | V | V | F | V | F |
| III | V | F | V | F | V |
| IV | F | V | F | V | F |
Lista 0806/10
Permutações, arranjos, combinações e binômio de Newton
Abrir PDF
| Questão | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I | V | V | V | F | F |
| II | F | F | F | F | V |
| III | F | V | V | V | V |
| IV | V | V | F | F | F |
Lista 0913/10
Somatórios, PA e PG, somatório de polinômios
Abrir PDF
| Questão | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I | F | V | V | F | F |
| II | F | F | V | V | V |
| III | V | F | V | V | F |
| IV | F | F | V | F | V |
Lista 1020/10
Técnicas de Newton para sequências polinomiais e relações de recorrência
Abrir PDF
Gabarito ainda não divulgado.
Os PDFs ficam no Google Drive da turma e abrem com a conta @cin.ufpe.br de quem está matriculado no Classroom.
Notas e provas
Avaliação
Dois exercícios escolares, doze miniprovas e um projeto bônus, especificado pela monitoria.
Média
0,7 EE + 0,3 MP + Bônus
Prova final em 10/12.
- EE
- Média dos dois exercícios escolares, (EE1 + EE2)/2.EE1 em 22/09 · EE2 em 01/12
- MP
- Média das 12 miniprovas.Em geral às quintas-feiras; veja o calendário
- Bônus
- Nota do projeto, valendo até 2 pontos na média.Jogo de Voronoi em grafos; entrega em 30/11 e apresentação em 03/12
Provas aplicadas
Enunciados em PDF, com o mesmo acesso das listas, e o gabarito objetivo de cada asserção. As próximas miniprovas entram aqui depois de aplicadas.
| Questão | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I | V | F | V | F | V |
| II | V | F | V | F | F |
| III | F | V | V | F | V |
| IV | V | F | F | V | F |
MP 120/08
Conjuntos
Enunciado (PDF)
| Questão | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I | V | F | V | V | V |
| II | V | F | V | F | V |
| III | V | F | V | F | F |
| IV | F | F | F | V | V |
MP 227/08
Relações e funções
Enunciado (PDF)
| Questão | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I | F | F | F | V | V |
| II | V | F | V | V | F |
| III | V | F | F | F | V |
| IV | F | F | V | F | F |
MP 303/09
Conjuntos infinitos e enumerabilidade
Enunciado (PDF)
| Questão | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I | V | F | F | V | F |
| II | V | F | V | F | F |
| III | V | F | V | F | F |
| IV | F | F | F | V | F |
MP 410/09
Funções especiais
Enunciado (PDF)
| Questão | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I | V | F | V | V | F |
| II | V | F | V | V | F |
| III | F | V | V | V | F |
| IV | V | F | V | V | F |
MP 524/09
Endorrelações
Enunciado (PDF)
| Questão | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I | V | F | F | V | V |
| II | V | F | V | F | F |
| III | V | F | F | V | F |
| IV | V | F | F | V | F |
MP 601/10
Elementos de aritmética modular
Enunciado (PDF)
| Questão | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I | V | V | F | V | V |
| II | V | F | V | V | F |
| III | V | V | V | F | V |
| IV | V | F | V | F | F |
MP 708/10
Princípios aditivo e multiplicativo, inclusão-exclusão e complementar
Enunciado (PDF)
| Questão | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I | V | F | V | F | V |
| II | V | V | F | V | F |
| III | V | F | V | F | V |
| IV | V | V | F | F | F |
MP 815/10
Inclusão-exclusão, permutações, arranjos, combinações e binômio de Newton
Enunciado (PDF)
| Questão | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I | V | F | F | F | V |
| II | F | V | F | F | V |
| III | F | V | F | V | F |
| IV | F | F | V | F | F |
MP 922/10
Somatórios, PA e PG, somatório de polinômios
Enunciado (PDF)
| Questão | 1 | 2 | 3 | 4 | 5 |
|---|---|---|---|---|---|
| I | V | F | V | V | F |
| II | V | F | V | V | F |
| III | F | V | V | V | V |
| IV | V | V | F | F | V |
Bônus de até 2 pontos
Projeto: Jogo de Voronoi em grafos
Cada grupo escreve, em Python, uma estratégia para escolher vértices de um grafo numa competição entre as equipes da turma. A especificação é da monitoria.
Abrir a demonstração interativaTreze grafos e cinco estratégias com pseudocódigo. Cada lance vem explicado, e dá para jogar contra uma estratégia ou contra um colega.
Como funciona
- Em cada partida, as duas equipes alternam jogadas até posicionar 3 centros cada uma. Cada confronto tem duas partidas, e cada equipe começa uma delas.
- Cada vértice fica com a equipe do centro mais próximo, pela distância de menor caminho no grafo, e soma o seu peso para ela. Em caso de empate, o peso se divide entre as duas.
- A entrega é um arquivo
resposta.pycom uma função, com o nome da estratégia do grupo, que recebe o grafo da partida (um objetoGraphda networkx) e devolve o vértice escolhido. A competição usa grafos regulares e não regulares. - A classificação define a nota do projeto, de 0 a 10: o primeiro lugar recebe 10, e o último, 0. A nota só vale se o grupo explicar presencialmente a estratégia e o código.
Regras
- Até 12 grupos, com 6 alunos em cada.
- Python, com a networkx como única biblioteca externa.
- Código de autoria do grupo, sem código gerado por IA nem copiado de fontes externas. Código não autoral zera a nota do grupo.
Entradas oficiais
Pendente O professor vai elaborar as entradas oficiais da competição e publicar aqui, em novembro, o SHA-256 de cada uma. Assim a turma pode conferir, depois das partidas, que as entradas usadas são exatamente as que foram fixadas antes.
Grupos
O prazo de inscrição já passou. Quem não se inscreveu até 15/10 só pode pedir a liberação diretamente ao monitor bolsista, Gabriel Nobrega da Silva Barros (gnsb@cin.ufpe.br).
Datas
- SHA-256 das entradas oficiais (pendente)
- Desenvolvimento e orientação com a monitoria, em sala
- Entrega do
resposta.pyno Classroom; nada é aceito depois do prazo - Apresentação dos projetos
Material da monitoria
Abrem com a conta @cin.ufpe.br da turma. Dúvidas no canal #dúvidas do Discord da monitoria ou por e-mail aos monitores.
Ementa, unidades e módulos
Material digital
São cinco unidades, cada uma dividida em módulos, um por aula expositiva. Cada módulo leva à sua lista de exercícios e, nas unidades 1 a 4, à sua miniprova.
Ementa: conjuntos, relações, funções, princípios de contagem, elementos de lógica, técnica de demonstração matemática, elementos de teoria dos grafos, número e suas representações.
- Conjuntos, relações e funções6 módulos · 11/08 a 15/09
- Princípios de contagem2 módulos · 29/09 e 06/10
- Sequências e relações de recorrência2 módulos · 13/10 e 20/10
- Lógica e técnicas de demonstração2 módulos · 27/10 e 03/11
- Grafos e árvores3 módulos · 17/11 a 24/11
Leituras: tradução e readaptação, pelo Prof. Sérgio Queiroz, dos textos livres de Levin, Aspnes e Hefferon (veja a Bibliografia); os PDFs abrem com a conta @cin.ufpe.br. Vídeos: públicos no YouTube.
Unidade 1 · 6 módulos
Conjuntos, relações e funções
- 1.1Conjuntosaula de 11/08Lista 01MP 1
- 1.2Relações e funçõesaula de 18/08Lista 02MP 2
- 1.3Conjuntos infinitos e enumerabilidadeaula de 25/08Lista 03MP 3
- 1.4Funções especiaisaula de 01/09Lista 04MP 4
- 1.5Endorrelaçõesaula de 08/09Lista 05MP 5
- 1.6Elementos de aritmética modularaula de 15/09Lista 06MP 6
Tópicos da ementa
Operações de união, interseção, diferença, complemento, produto cartesiano de conjuntos, diferença de conjunto para vetores e tuplas; conjuntos especiais; comutatividade, distributividade e associatividade da união e da interseção, leis de Morgan; subconjuntos, continência estrita e não estrita e subconjunto próprio; conjunto das partes e partições; endorrelação, reflexividade, simetria, antissimetria, transitividade, ordens parciais e posets, relações de equivalência, fecho reflexivo, fecho simétrico, fecho transitivo, aritmética; funções, funções injetoras, sobrejetoras e bijetoras, plano cartesiano, função piso, teto, sinal, parte fracionária, valor absoluto; enumerabilidade; divisibilidade, fatoração, primos e fatoriais, elementos de teoria dos números.
Vídeos
Os três abrem a playlist Pré-Cálculo.
Unidade 2 · 2 módulos
Princípios de contagem
- 2.1Princípios aditivo e multiplicativo, inclusão-exclusão e complementaraula de 29/09Lista 07MP 7
- 2.2Permutações, arranjos, combinações e binômio de Newtonaula de 06/10Lista 08MP 8
Tópicos da ementa
O Teorema Fundamental da Contagem; permutações, arranjos, permutações com repetição; combinações, coeficientes binomiais, binômio de Newton; técnicas de agrupamento, técnicas de asterisco e barra; Princípio da Inclusão-Exclusão.
Unidade 3 · 2 módulos
Sequências e relações de recorrência
- 3.1Somatórios, PA e PG, somatório de polinômiosaula de 13/10Lista 09MP 9
- 3.2Técnicas de Newton para sequências polinomiais e relações de recorrênciaaula de 20/10Lista 10MP 10 · 29/10
Tópicos da ementa
Definição e notação de sequências; progressão aritmética, números triangulares, progressão geométrica; diferenças finitas, ajuste polinomial de sequências; definição e notação de funções recursivas; resolução por telescopagem; a técnica da raiz característica; indução matemática, indução forte.
Unidade 4 · 2 módulos
Lógica e técnicas de demonstração
- 4.1Lógica proposicional e tabelas-verdadeaula de 27/10Lista 11 · 27/10MP 11 · 05/11Tabela-verdade
- 4.2Técnicas básicas de demonstraçãoaula de 03/11Lista 12 · 03/11MP 12 · 26/11
Tópicos da ementa
Conectivos lógicos; implicações; recíprocas e contrapositivas, “se e somente se”, condições necessárias e suficientes; predicados e quantificadores universais e existenciais, negação e quantificadores; lógica proposicional, tabelas-verdade, tautologia; equivalência lógica, leis de Morgan, disjunção e implicação, dupla negação, negação de uma implicação; demonstrações matemáticas; prova direta por implicações; prova por contrapositiva; prova por contradição; prova por invariante; prova por exemplo; prova por contraexemplo; prova por casos; negação do implica; prova em cascata; prova por indução, indução forte; princípio da casa dos pombos.
Vídeos
Os três formam a playlist Demonstrações matemáticas.
Ferramenta da unidade 4
Tabela-verdade
Escreva uma fórmula da lógica proposicional para ver a tabela, coluna por coluna, e saber se ela é tautologia, contradição ou contingência. Preencha a segunda fórmula para testar se as duas são equivalentes.
Use os botões ou o teclado: ~ para ¬, & para ∧, | para ∨, -> para → e <-> para ↔. As constantes são V e F, e colchetes valem como parênteses.
Todas as formas de digitar e a ordem de precedência
- ¬
~!notnão- ∧
&/\ande- ∨
|\/orou- ⊕
^xor- →
->=>implica- ↔
<-><=>iffsse- V
V1Ttrue- F
F0false
Sem parênteses, o ¬ vale primeiro; depois vêm o ∧, o ∨ e o ⊕, o → e, por último, o ↔. O → associa à direita: p → q → r é lido como p → (q → r). As variáveis são letras ou palavras, que podem terminar em número, como p, r1 ou chove; só não use como variável as letras e palavras da tabela acima.
Exemplos da aula
Comutatividade e associatividade · compara F₁ com F₂
Equivalências notáveis · compara F₁ com F₂
Tautologias e contradições · uma fórmula só
A ideia vem da Truth Table Tool do CS103, de Stanford.
Unidade 5 · 3 módulos · só listas
Grafos e árvores
- 5.1Grafos e árvores Iaula de 17/11Lista 13 · 17/11
- 5.2Grafos e árvores IIaula de 19/11Lista 14 · 19/11
- 5.3Grafos e árvores IIIaula de 24/11Lista 15 · 24/11
LaboratórioGrafosGraus, listas e matriz de adjacência, caminhos e circuitos, conectividade, direção e DAGs, grafos especiais e desenho no plano e as travessias, passo a passo.
LaboratórioÁrvoresNotações, níveis e altura, percursos, árvores binárias estritas, completas e perfeitas e árvores de busca binária, com o balanceamento.
Tópicos da ementa
Definição de grafo, vértice, aresta, caminho, direcionamento de arestas, pesos, vértices adjacentes, conectividade, grau (de saída/entrada), ciclo, DAGs, posicionamento espacial (mergulho), grafo para representar relação; busca em largura e profundidade em grafos; definição de árvore, árvores livres e enraizadas, raiz, pai, filho, irmão, ancestral, folha, descendente, nó interno, profundidade, altura, nível, subárvore, árvores binárias; percurso pré-ordem, pós-ordem e in-ordem; árvore binária estrita, completa e perfeita; árvores de busca binária, busca, adição e remoção de nó, elementos de balanceamento de árvore binária.
Leituras
Referências
Bibliografia
Os três primeiros textos são livres e estão em inglês. Para os livros, o catálogo da UFPE mostra em que biblioteca estão os exemplares e se estão disponíveis para empréstimo.
Livres, online
Discrete Mathematics: An Open Introduction
Livro aberto, em inglês
Notes on Discrete Mathematics
Notas de aula da Yale University, em inglês
Theory of Computation: Making Connections
Livro aberto, em inglês
Livros no acervo da UFPE
Discrete Mathematics and Its Applications
2011 · em português: Matemática Discreta e suas Aplicações
Na UFPE: Biblioteca do CCEN, com a 6ª edição em português (2009) e a 4ª, a 5ª e a 6ª em inglês.
Fundamentos Matemáticos para a Ciência da Computação
7ª edição · LTC · 2016
Na UFPE: Biblioteca do CCEN, com a 3ª edição (1993).
Matemática Concreta: Fundamentos para a Ciência da Computação
2ª edição · LTC · 1995
Na UFPE: Biblioteca do CCEN, com a 2ª edição (1995).
Com login no catálogo da UFPE, a aba E-books reúne os livros digitais disponíveis para a comunidade da universidade.
Equipe 2026.2
Monitoria
Os monitores acompanham as listas, as miniprovas e o projeto; Gabriel Nobrega da Silva Barros é o monitor bolsista. Escreva para o e-mail institucional de cada um.
Edisio Uchoa Cavalcanti Neto
eucn@cin.ufpe.br
Gabriel Freitas de Albuquerque
gfa3@cin.ufpe.br
Isabelle Tenorio Vaz Bezerra
itvb@cin.ufpe.br
Victor Lemos de Freitas
vlf2@cin.ufpe.br
Wallyson Rodrigues da Silva
wrs4@cin.ufpe.brDúvidas: canal #dúvidas no Discord da monitoria. O convite está no Classroom.
Projeto com a monitoria: orientação em sala em 10/11 e 12/11; veja a seção Projeto.