---

2023 Q3

MCTA027-17 - Teoria dos Grafos - Diurno

Professora: Carla Negri Lintzmayer, carla.negri@ufabc.edu.br

🚨 Avisos importantes (fique atento sempre!)

[21/dez] 🔥🔥🔥🔥🔥 As notas finais, pós-rec, estão disponíveis na planilha. Cheque seu e-mail para mais informações!

[15/dez] 🔥🔥🔥 Médias e conceitos atualizados para os valores finais antes da REC.
Não esqueça de confirmar o interesse em fazer a prova de recuperação!!! Eu preciso saber para imprimir o número de provas correto.
Também observe que há aula/atendimento no dia 19.

[10/dez] Atenção para os avisos semi-finais (leia todos!!!):

• Terminei de corrigir a P2 e as notas estão na planilha. Note que ainda falta uma atividade prática, e por isso há duas médias e conceitos na planilha!!!
• A aula do dia 19 é de atendimento voltado à prova de recuperação. Todos estão convidados a participar, mas não será cobrada presença.
• Não esqueça de confirmar o interesse em fazer a prova de recuperação!!!
• Dias e horários para vista de prova (tanto da P1 quanto da P2):
  • Dia 11/dez, 10h às 11h, na sala da professora.
  • Dia 11/dez, 14h às 15h, na sala da professora.
  • Dia 13/dez, 8h30 às 9h45, na sala da professora.
  • Dia 14/dez, 17h às 18h30, na sala da professora.
• Dias e horários para os atendimentos (dúvidas) até o final do quadrimestre:
  • Dia 11/dez, 13h a 14h, na sala da professora.
  • Dia 12/dez, 9h a 10h, na sala da professora.
  • Dia 13/dez, 12h a 13h, na sala da professora.
  • Dia 19/dez, 8h a 10h, na sala de aula.

[29/nov] Correção: o horário de atendimento do dia 5/dez da professora será entre 8h e 9h (fiz confusão na agenda)!!
[27/nov] Atenção para mudança nos horários de atendimento!!

• Dia 4/dez não haverá atendimento da professora.
• Dia 5/dez haverá atendimento da professora das 9h às 10h 8h às 9h.
• Dia 5/dez haverá atendimento do monitor das 17h às 19h.
• Dia 6/dez não haverá atendimento da professora após a prova.
• Dia 7/dez não haverá atendimento do monitor.

[24/out] O atendimento do dia 29/out será até 10h40 apenas. Note que a aula do dia 29/out inteira é um grande atendimento.
[23/out] Veja no moodle as soluções dos exercícios práticos.
[19/out] Veja no moodle mais detalhes sobre a quarta e última entrega de exercícios.
[19/nov] A lista 6 (última 🙏) está disponível, sobre outros problemas interessantes. Divirta-se!
[16/nov] As notas da P1, faltas até o momento e vale moral até o momento estão disponíveis!!! Os exercícios práticos da entrega 2 também foram corrigidos. Vejam a seção de Notas.
Vista de prova/exercícios teóricos/exercícios práticos: podem ser feitas em qualquer horário de atendimento!
Particularmente no dia 22/nov ficarei das 10h às 12h30 na minha sala para isso.
[14/nov] O PDF das aulas 16 e 17 foi atualizado!!!
[11/nov] A lista 5 está disponível, sobre caminhos mínimos. Divirta-se!
[6/nov] Excepcionalmente, não haverá atendimento hoje entre 13h e 14h. Atenderei por mais tempo logo após a aula e na quarta até meio dia.
[2/nov] Veja no moodle mais detalhes sobre a terceira entrega de exercícios.
[1/nov] A lista 4 está disponível, sobre digrafos. Divirta-se!
[31/out] Modifiquei levemente algumas coisas no cronograma: a entrega 3, antes prevista para 20/11, agora está em 22/11. A entrega 4, antes prevista para 29/11, foi dividida em duas partes, teórica e prática, e agora está em 4/12 e 13/12, respectivamente.
[25/out] Atenção! O prazo para entrega dos exercícios práticos foi aumentado. Além disso, alguns programas que antes foram detectados como corretos, podem ter mudado de status. Veja recado no Moodle!
[25/out] Solução dos exercícios que fiquei devendo na aula de hoje.
[19/out] A primeira entrega de exercícios pode ser feita também na aula do dia 25/out.
[16/out] As notas da lista 1 bem como as explicações dos símbolos usados na correção estão na planilha, na seção de Notas.
[11/out] Veja no moodle mais detalhes sobre a segunda entrega de exercícios.
[5/out] A primeira entrega de exercícios pode ser feita também na aula do dia 11/out.
[24/set] Veja no moodle mais detalhes sobre a primeira entrega de exercícios.
[24/set] Corrigi dois pequenos errinhos na lista 1. Baixe o pdf novamente.
[24/set] Foram definidos os horários de atendimento! Veja a seção "Dias, horários e locais de atendimentos".
[10/set] Verifique a seção Recomendação!!!
[10/set] Responda a esse formulário até o dia 21/set para que eu possa definir os melhores horários de atendimento extra-classe.
[10/set] Site no ar. Estude-o como se o seu conteúdo fosse ser cobrado em avaliação.

📝 Dias, horários e locais das aulas

🙋 Dias, horários e locais dos atendimentos

🧐 Ementa da disciplina

MCTA027-17 - Teoria dos Grafos (pg. 80)

Objetivos:

• Apresentar os conceitos e resultados básicos da Teoria dos Grafos;
• Permitir o uso de grafos e suas propriedades para modelar problemas computacionais;
• Apresentar algoritmos eficientes para problemas recorrentes em computação;
• Tornar familiares certos padrões de soluções que ocorrem frequentemente em problemas envolvendo grafos.

Conteúdo programático: Conceitos básicos de grafos dirigidos e não dirigidos. Passeios, caminhos, circuitos. Grafos bipartidos e multi-partidos. Subgrafos. Isomorfismo. Conexidade. Florestas e árvores. Exemplos de problemas de interesse: coloração de vértices; clique máximo; caixeiro viajante; problemas de fluxo. Estruturas de dados para a representação de grafos. Percursos em grafos: em largura, em profundidade. Ordenação topológica. Árvores geradoras mínimas. Algoritmo de Kruskal. Caminhos mínimos em grafos: algoritmo de Dijkstra, algoritmo de Floyd-Warshall. Emparelhamentos: Teorema de Hall.

🖖 Recomendação

Para facilitar o acompanhamento do curso, é recomendado que você possua:

• conhecimentos de programação (em qualquer linguagem imperativa), com boas noções de algoritmos recursivos,
• familiaridade com estruturas de dados básicas (vetores, listas ligadas, pilhas, filas e árvores),
• capacidade para reconhecer argumentos lógicos em uma prova matemática (por indução, contradição, construção),
• familiaridade com linguagem matemática (como quantificadores lógicos, somatórios e manipulação de funções).

Materiais de apoio para esses tópicos:

• Livro de Bases Matemáticas, dos profs. Armando Caputi e Daniel Miranda, da UFABC.
• Meus vídeos com definição e exemplos de indução.
• Projeto de algoritmos (em C), do prof. Paulo Feofiloff, da USP.
• Estruturas de dados (em C), do prof. Paulo Feofiloff, da USP.
• Videoaulas de Algoritmos e Estruturas de Dados I, do prof. Mário San Felice, da UFSCar.
• Notas de aula da disciplina de Estruturas de Dados do prof. Rafael Schouery, da Unicamp (introdução à programação em C, recursão, listas, pilhas e filas, árvores).

📚 Bibliografia e outros materiais

1. [SED] Sedgewick, R.. Algorithms in C, part 5: graph algorithms. 3rd ed. Addison-Wesley. 2002.
2. [B&M] Bondy, J. A.; Murty, U. S. R.. Graph Theory. Graduate Texts in Mathematics. Springer. New York. 2008.
3. [LM] Lintzmayer, C. N.; Mota, G. O.. Notas de aulas - Análise de algoritmos e estruturas de dados
4. [CLRS3] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.. Introduction to Algorithms. 3rd ed. MIT Press. 2009.

⏰ Datas importantes

Resumo das datas importantes:

• Entrega 1 de atividades: 11/out ✅
• Entrega 2 de atividades: 25/out ✅
• Prova 1: 30/out ✅
• Entrega 3 de atividades: 22/nov ✅
• Entrega 4 de atividades teóricas: 4/dez ou 6/dez
• Prova 2: 6/dez
• Entrega 4 de atividades práticas: 13/dez
• Provas substitutivas (para quem tiver justificativa - veja seção Avaliações substitutivas): 13/dez, das 10h às 12h
• Prova de recuperação (para quem enviar e-mail confirmando - veja seção Recuperação): 20/dez

📆 Cronograma

ATENÇÃO! O conteúdo exato e materiais de apoio de cada aula são atualizados durante o quadrimestre.
As aulas que já foram ministradas estão coloridas.

Aula 1 - 18/set Conteúdo: Sobre o curso. Material complementar: slides da aula; vídeos sobre indução:

Aula 2 - 20/set Conteúdo: Definições básicas e teorema do aperto de mãos. Referências: Cap. 23 [LM], Sec. 1.1, 1.2, 2.1, 2.2 [B&M]. Material complementar: notas da aula 2.

Aula 3 - 25/set Conteúdo: Mais definições básicas e outros resultados elementares. Referências: Cap. 23 [LM], Sec. 3.1, 3.2 [B&M]. Material complementar: notas da aula 3.

Aula 4 - 27/set Conteúdo: Término de definições básicas e resultados elementares. Grafos bipartidos. Conteúdo: Mais definições básicas e outros resultados elementares. Referências: Cap. 23 [LM], Sec. 3.1, 3.2 [B&M]. Material complementar: notas da aula 3 (término) e notas da aula 4.

Aula 5 - 2/out Conteúdo: Término de grafos bipartidos. Árvores. Referências: Cap. 23 [LM], Sec. 4.1 [B&M]. Material complementar: notas da aula 5.

Aula 6 - 4/out Conteúdo: Término de árvores. Breve introdução à análise de algoritmos. Referências: Cap. 2, 4 e 5 [LM]. Material complementar: notas da aula 5 (término) e notas da aula 6.

Aula 7 - 9/out Conteúdo: Representação de grafos como estruturas de dados. Referências: Cap. 17 [SED]. Material complementar: notas da aula 7, e arquivos fonte.

Aula 8 - 11/out Conteúdo: Busca em grafos. Busca em largura. Referências: Cap. 18 [SED]. Material complementar: notas da aula 8.

Aula 9 - 16/out Conteúdo: Término de busca em largura. Busca em profundidade. Referências: Cap. 18 [SED]. Material complementar: notas da aula 8 (término) e notas da aula 9.

Aula 10 - 18/out Conteúdo: Árvore geradora mínima. Algoritmos de Prim e Kruskal. Referências: Cap. 20 [SED]. Material complementar: notas da aula 10.

Aula 11 - 23/out Conteúdo: Algoritmos de Prim e Kruskal. Referências: Cap. 20 [SED], Cap. 21 [CLRS3]. Material complementar: material sobre Heap, material sobre Union-Find, notas da aula 11.

Aula 12 - 25/out Conteúdo: Revisão para a prova. Solução dos exercícios que fiquei devendo durante a aula.

Aula 13 - 30/out Prova 1. Conteúdo: tudo o que foi visto entre as aulas 1 e 12. Atenção! Não haverá atendimento neste dia!

Aula 14 - 1/nov Conteúdo: Digrafos: introdução e resultados básicos. DAGs. Cap. 19, até 19.5 [SED]. Material complementar: notas da aula 14.

Aula 15 - 6/nov Conteúdo: Ordenação topológica. Componentes fortemente conexas e algoritmo de Kosajaru. Sec. 19.8 [SED]. Material complementar: notas da aula 15 (algoritmo de Tarjan não foi dado, está como extra).

Aula 16 - 8/nov Conteúdo: Caminhos Mínimos. Algoritmo para DAGs. Algoritmo de Dijkstra. Cap. 21 [SED]. Material complementar: notas da aula 16.

Aula 17 - 13/nov Conteúdo: Algoritmo de Bellman-Ford. Algoritmo de Floyd-Warshall. Cap. 21 [SED]. Material complementar: notas da aula 17.

15/nov (Feriado Proclamação da República) Reposição em 19/dez (terça-feira).

20/nov (Feriado Dia da Consciência Negra) Reposição em 20/dez (quarta-feira).

Aula 18 - 22/nov Conteúdo: Grafos Eulerianos e Hamiltonianos. Material complementar: notas da aula 18.

Aula 19 - 27/nov Conteúdo: Emparelhamentos e conjuntos independentes. Comentário: uso em coloração de vértices e arestas. Material complementar: notas da aula 19. Extra: notas da aula 19 com material extra.

Aula 20 - 29/nov Conteúdo: Revisão para a prova.

Aula 21 - 4/dez Conteúdo: Fluxo.

Aula 22 - 6/dez Prova 2. Conteúdo: tudo o que foi visto entre as aulas 14 e 20. Atenção! Não haverá atendimento neste dia!

13/dez Provas substitutivas. Veja detalhes na seção Avaliações substitutivas.

Aula 23 - 19/dez (⚠ Em uma terça-feira, às 8h, por ser reposição de uma aula de quarta-feira!) Conteúdo: Resolução das provas e atendimento para a REC.

Aula 24 - 20/dez (⚠ Em uma quarta-feira, às 10h, por ser reposição de uma aula de segunda-feira!) Prova de recuperação para os alunos que ficaram com conceito D ou F ** E QUE ** enviarem e-mail indicando interesse em realizá-la. Veja detalhes na seção Mecanismo de recuperação.

👎 Plágio

• Entre outros, o código de ética da UFABC estabelece em seu artigo 25 que é eticamente inaceitável que os discentes:
  1. fraudem avaliações,
  2. fabriquem ou falsifiquem dados,
  3. plagiem ou não creditem devidamente autoria,
  4. aceitem autoria de material acadêmico sem participação na produção,
  5. vendam ou cedam autoria de material acadêmico próprio a pessoas que não participaram da produção.
  
  
• Muitos ainda têm dúvidas sobre a interpretação das regras definidas pelo Código de Ética da UFABC.
• Por esta razão, diversos professores elaboraram um documento (disponível aqui) com vários exemplos e esclarecendo a interpretação das regras acima.
• Abaixo uma versão resumida, que não substitui de modo algum sua leitura:
• Regra 1: Você não pode enviar para avaliação um trabalho que não seja de sua própria autoria ou que seja derivado/baseado em soluções elaboradas por outros.
• Regra 2: Você não pode compartilhar a sua solução com outros alunos nem pedir aos seus colegas que compartilhem as soluções deles com você.
• Regra 3: Nos trabalhos enviados para avaliação você deve indicar eventuais assistências que você tenha recebido.
• Nós encorajamos fortemente que você procure outras pessoas quando houver a necessidade. Discuta o problema e possíveis ideias para soluções, mas elabore sua própria solução, por conta própria.
• Qualquer violação às regras descritas acima implicará em descarte dos conceitos atribuídos a TODAS as tarefas avaliativas regulares de TODOS os envolvidos, causando assim suas reprovações automáticas com conceito F.
• Possível denúncia à Comissão de Transgressões Disciplinares Discentes da Graduação, a qual decidirá sobre a punição adequada à violação que pode resultar em advertência, suspensão ou desligamento, de acordo com os artigos 78-82 do Regimento Geral da UFABC.
• Sempre consulte o documento completo ou converse com o seu professor em caso de dúvidas!

🏋 Listas de exercícios

• Sobre gabaritos das listas de exercícios:
  eu acredito que o objetivo de um exercício teórico não é a resolução do problema em si, mas sim praticar a resolução de problemas;
  você precisa chegar nas soluções por conta própria (com algumas dicas da minha parte) ao invés de apenas ler um gabarito (que mostrará uma única solução possível);
  por isso, eu não disponibilizo gabaritos das minhas listas;
  a melhor forma para você saber se resolveu o exercício corretamente é me procurar em horários de atendimento e me mostrar a sua solução.



• Ao todo teremos 6 listas de exercícios teóricas, divididas de acordo com os principais temas vistos e cujos enunciados estão disponibilizados abaixo.
• O objetivo principal é prover problemas representativos dos conceitos vistos, equivalentes aos que serão cobrados nas avaliações.
• Procure atendimento sempre que tiver dúvidas nos exercícios.
• Faça o maior número de exercícios que puder, sempre.
  • Vale moral!!
    Qualquer exercício extra que for feito pode ser entregue nos dias das provas para serem considerados como evidência do seu esforço.
    Participar das aulas, dos atendimentos/monitorias, também vale moral.
    Alunos com moral terão direito a pedir arredondamento de conceitos e notas ou abono de alguma falta ao final do curso.
    Em nenhuma hipótese será feito o arredondamento de conceitos ou abono de faltas para alunos sem moral.



• Finalmente:
  • Lista 1 (Conceitos básicos em grafos)
  • Lista 2 (Introdução a algoritmos em grafos e buscas)
  • Lista 3 (Árvores geradoras mínimas)
  • Lista 4 (Conceitos básicos em digrafos)
  • Lista 5 (Caminhos mínimos)
  • Lista 6 (Outros problemas interessantes)

✍ Entregas de exercícios

• Farão parte da avaliação da disciplina a entrega de alguns exercícios teóricos e práticos.
• Os exercícios teóricos devem ser feitos à mão (capriche na letra!), em papel, e entregues durante as aulas, nas datas previstas.
  • Se algo te impossibilita de fazer as listas à mão, converse comigo antes de fazer em outro formato, pois caso contrário sua nota naquela lista será zero.
  • Capriche na letra e não entregue sua primeira solução! Passe a limpo antes.
  • As listas corrigidas serão devolvidas aos alunos, para que possam aprender com os erros.
  • Até o final do quadrimestre, devem ser devolvidas à professora, pois são itens de avaliação.
  • Os enunciados dos exercícios estão disponíveis na seção Listas de exercícios. Os exercícios a serem entregues estão descritos apenas no Moodle da turma.
• Os exercícios práticos devem ser feitos em linguagem C e entregues via Moodle, nas datas previstas.
  • As implementações serão avaliadas tanto com relação à corretude (devem passar em todos os casos de teste) quanto com relação à eficiência (devem ser usadas as estruturas de dados vistas em aula e/ou exigidas pelo enunciado).
  • Os enunciados dos exercícios estão disponíveis apenas no Moodle da turma.
• Ao todo serão 4 entregas, cujas datas encontram-se no Moodle e também resumidas na seção Datas importantes.

🎓 Critérios de avaliação

• A avaliação da disciplina constituirá da nota de duas provas, denotadas P₁ e P₂, da média ponderada das notas dos exercícios teóricos entregues, denotada ET, e da média ponderada das notas dos exercícios práticos entregues, denotada EP.
• A prova 1 vale 34% da nota e 0 ≤ P₁ ≤ 10.
• A prova 2 vale 34% da nota e 0 ≤ P₂ ≤ 10.
• Os exercícios teóricos valem 16% da nota e 0 ≤ ET ≤ 10, com ET = 10 × (soma das notas obtidas nos exercícios entregues) / (número de exercícios exigidos).
• Os exercícios práticos valem 16% da nota e 0 ≤ EP ≤ 10, com EP = 10 × (soma das notas obtidas nos exercícios entregues) / (número de exercícios exigidos).
• O conteúdo das provas englobará todos os temas vistos até a data das mesmas.


• Sua média final (MF) antes da recuperação, portanto, será
  
  MF = 0.34 × P₁ + 0.34 × P₂ + 0.16 × ET + 0.16 × EP


• Se você teve presença em 75% ou mais das aulas, seu conceito final será
  
  A, se MF ≥ 8.5
  B, se 7.0 ≤ MF < 8.5
  C, se 6.0 ≤ MF < 7.0
  D, se 5.0 ≤ MF < 6.0
  F, se MF < 5.0
  
• Se você faltou em 25% ou mais das aulas, seu conceito final será O.
  
• Não esqueça do vale moral!

💯 Notas

Confira aqui as notas das entregas dos exercícios teóricos!

Confira aqui as notas das entregas dos exercícios práticos!

Confira aqui as notas de todas as atividades, inclusive contagem de faltas e do vale moral!

Lembre-se sempre que a intenção das listas de exercício é reforçar seu aprendizado.
Não deixe de procurar atendimento para entender o motivo de ter errado algum exercício!

🤒 Mecanismos de avaliação substitutivos

• Uma prova substitutiva será aplicada ao aluno que possuir justificativa de ausência em uma das provas.
• Envie por e-mail a sua justificativa o quanto antes, para informar à professora que irá realizar a prova substitutiva.
• A listagem dos documentos aceitos como justificativa consta na resolução ConsEPE n° 227.
• A nota obtida na prova substitutiva necessariamente substituirá a prova para a qual o aluno tem justificativa.
• A data para realização de avaliações substitutivas da Prova 1 ou da Prova 2 será 13/dez, das 10h às 12h, em sala a ser informada por e-mail aos realizadores.

💪 Mecanismo de recuperação

• A recuperação constituirá uma prova teórica que será aplicada apenas aos alunos que tiverem conceito final D ou F e que enviarem e-mail confirmando interesse.
• O conteúdo da prova englobará todos os temas vistos durante o quadrimestre.
• A nota obtida na prova de recuperação (NR) será usada obter a nota final com recuperação (NFR), que consiste na média a seguir:
  NFR = max {MF, (MF + NR) / 2}
• O conceito final obtido na recuperação substituirá o conceito original e será
  C, se NFR ≥ 6.0
  D, se 5.0 ≤ NFR < 6.0
  F, se 0.0 ≤ NFR < 5.0
  

---