MCTA027-17 - Teoria dos Grafos (2019 Q3)
Professora: Carla Negri Lintzmayer, Sala 508-2, carla.negri@ufabc.edu.br
Avisos importantes (fique atento sempre!)
[25/02] Notas da prova de recuperação. Entre em contato por e-mail em caso de qualquer dúvida.―― novos ↑ ――
[03/02] Avisos sobre a prova de recuperação:
- Plantão de atendimento profa. Carla: dia 10/02/2020, das 18h às 22h (sala 508-2).
- Plantão de atendimento prof. Maycon: dia 12/02/2020, das 18h às 22h (sala 518-2).
- A prova de recuperação será na sala S-301-2, a partir das 9h, no dia 15/02/2020 (sábado).
- Por favor, me envie um e-mail se você for realizar a prova, para que eu possa imprimir uma quantidade correta de provas.
- Tenha certeza de que leu o e-mail sobre detalhes da prova (enviado ano passado).
- Mande um e-mail em caso de qualquer dúvida.
- Confiram seus e-mails para uma versão não resumida das informações a seguir (ele tem mais informações).
- As notas finais (antes da REC) estão disponíveis.
- Plantão de atendimento sobre as notas: dia 16/12, das 18h às 21h (mande um e-mail para outros horários).
- Por favor, preencha o formulário anônimo de avaliação da disciplina.
- Plantão de atendimento para a REC: dia 10/02/2020, das 18h às 22h (mande e-mail durante o recesso sempre que precisar).
- O local da REC será avisado próximo à data da mesma.
[08/12] O atendimento do prof. Maycon dessa segunda (9/12) será realizado pelo prof. Guilherme Mota (sala 530-2).
[01/12] Atenção para mudança nas datas das provas. Havendo qualquer problema, entrem em contato por e-mail o quanto antes. A lista 4 pode ser entregue até o dia 05/12 às 19h, sem penalidade na nota.
[29/11] Formulário de consulta sobre as datas da P2 e da REC.
[26/11] As notas da lista 2 e da parte teórica da lista 3 estão disponíveis. Anotações nos pdfs foram enviadas para seus e-mails.
[20/11] Lista 4 disponível.
[20/11] A lista 3 pode ser entregue até o dia 24/11 às 23h, sem penalidade na nota.
[16/11] A lista 3 pode ser entregue até o dia 21/11 às 19h, sem penalidade na nota.
[08/11] As notas da prova 1 estão disponíveis. Dúvidas podem ser tiradas no horário de atendimento ou em outro horário melhor, marcado por e-mail. Não deixem de me procurar!
[04/11] Lista 3 disponível.
[30/10] Material (extra) disponível sobre indução e solução dos exercícios de indução das listas 1 e 2.
[28/10] A lista 2 pode ser entregue até amanhã, 29/10, às 20h, sem penalidade na nota.
[28/10] As notas da parte teórica da lista 1 está disponível. Anotações no pdfs foram enviadas para seus e-mails.
[15/10] Lista 2 disponível.
[12/10] Data de entrega da Lista 1 adiada. Feliz dia das crianças!
[01/10] Lista 1 disponível.
[19/09] Página da disciplina no ar.
Conteúdo dessa página
 |
Dias, horários e local das aulas (voltar ao topo)
Terças-feiras, das 21h às 23h, sala S-302-2.Quintas-feiras, das 19h às 21h, sala S-311-2.
Dias, horários e local de atendimento (voltar ao topo)
Neste quadrimestre o conteúdo da disciplina será unificado com as turmas dos Profs. Guilherme Mota e Maycon Sambinelli.
|
Assim, alunos de todas as turmas podem escolher livremente entre os horários abaixo:
Nesse horários não é preciso confirmar ou marcar, apenas apareça!
Se não puder, me mande um e-mail para combinarmos algo. Algumas dúvidas (mais simples) podem ser tiradas por e-mail. |
Ementa da disciplina (voltar ao topo)
Conceitos básicos de grafos dirigidos e não dirigidos. Passeios, caminhos, circuitos. Grafos bipartidos e multipartidos. 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.
Objetivos: (i) Apresentar os conceitos e resultados básicos da Teoria dos Grafos; (ii) Permitir o uso de grafos e suas propriedades para modelar problemas computacionais; (iii) Apresentar algoritmos eficientes para problemas recorrentes em computação; (iv) Tornar familiares certos padrões de soluções que ocorrem frequentemente em problemas envolvendo grafos.
(Disponível na pg. 79 do projeto pedagógico.)
Recomendação (voltar ao topo)
Disciplinas: Matemática Discreta; Processamento da Informação; Algoritmos e Estruturas de Dados IPara facilitar o acompanhamento do curso, é recomendado que você já possua:
- conhecimentos de programação (em linguagem C), com boas noções de algoritmos,
- familiaridade com estruturas de dados básicas (vetores, listas, 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, conjuntos, somatórios e manipulação de funções).
- Livro "Velleman, D. J.. How to Prove It: A Structured Approach. Second Edition. Cambridge University Press. 2006."
- O que é uma prova matemática, do prof. Paulo Feofiloff, da USP.
- Matemática discreta para computação, dos profs. Anamaria Gomide e Jorge Stolfi, da Unicamp.
- Indução matemática, do prof. Cid Carvalho de Souza, da Unicamp.
- Portal da Matemática da OBMEP.
- Indução e contagem, do prof. Rogério Steffenon e Felipe Guarnieri, da Unisinos.
- Projeto de algoritmos (em C), do prof. Paulo Feofiloff, da USP.
- Estruturas de dados (em C), do prof. Paulo Feofiloff, da USP.
- Notas de aula, da disciplina de Programação Estruturada, da prof. Carla Lintzmayer (introdução à programação em C, recursão, vetores e listas).
Bibliografia e outros materiais (voltar ao topo)
- [BM] Bondy, J. A.; Murty, U. S. R. Graph theory. Graduate Texts in Mathematics. Springer. New York. 2008.
- [V] Velleman, D. J.. How to Prove It: A Structured Approach. Second Edition. Cambridge University Press. 2006.
- [S] Sedgewick, R.. Algorithms in C, part 5: graph algorithms. 3rd edition. Addison-Wesley. 2002.
- [BMwa] Bondy, J. A.; Murty, U. S. R.. Graph theory with applications. Elsevier. 1976.
- [D] Diestel, R.. Graph Theory. 5th edition. Springer-Verlag, Heidelberg Graduate Texts in Mathematics, Volume 173. 2016.
- [W] West, D. B.. Introduction to Graph Theory. 2nd edition. Pearson Education. New Jersey. 2001.
- [CLRS3] Cormen, T. H.; Leiserson, C. E.; Rivest, R. L.; Stein, C.. Introduction to Algorithms. 3rd ed. MIT Press. 2009.
- [M] Mota, G. O.. Notas de aulas - Teoria dos grafos. Em constante atualização.
- [LM] Lintzmayer, C. N.; Mota, G. O.. Notas de aulas - Análise de algoritmos e estruturas de dados. Em constante atualização.
- Grupo de Whatsapp criado e mantido pelos alunos.
Cronograma e notas de aula (voltar ao topo)
As referências utilizadas nas aulas serão atualizadas durante o curso.Sobre qualquer material feito por mim, participe do banco de informantes.
| Aula | Data | Tópicos |
|---|---|---|
| 1 | 24/9 | Apresentação da disciplina. Introdução à teoria dos grafos. Métodos de demonstração.
Referências: Cap. 3, 6 [V], Cap. 4, 5 Matemática discreta para computação. Extras: slides usados na aula. |
| 26/9 | Sem atividades acadêmicas: UFABC para todos
Dica de leitura: capítulos 3 e 6 do livro "Velleman, D. J.. How to Prove It: A Structured Approach. Second Edition. Cambridge University Press. 2006." |
|
| 2 | 1/10 | Conceitos básicos.
Referências: Cap. 1.1 [BM]. Extras: Notas da aula, Cap. 1 [M], exemplos de implementação. |
| 3 | 3/10 | Representações. Subgrafos e passeios. Grafos bipartidos.
Referências: Cap. 2.1, 2.2 [BM]. Extras: Notas da aula, Cap. 1, 2 [M]. |
| 4 | 8/10 | Caracterização de bipartidos. Teorema de Mantel.
Extras: Notas da aula, Cap. 1, 2 [M]. |
| 5 | 10/10 | Minimalidade e maximalidade. Cintura e diâmetro. Componentes.
Referências: Cap. 2.1 [BM]. Extras: Notas da aula, Cap. 1 [M]. |
| 6 | 15/10 | Arestas e vértices de corte. Grafos Eulerianos e caracterizações. Decomposição em ciclos.
Referências: Cap. 3.1, 3.2, 3.3, 2.4 [BM]. Extras: Notas da aula, Cap. 3 [M]. |
| 7 | 17/10 | Algoritmo de Fleury. Árvores e caracterizações.
Referências: Cap. 3.3, 4.1 [BM]. Extras: Notas da aula, Cap. 22 [LM], Cap. 4 [M]. |
| 8 | 22/10 | Caracterizações de árvores.
Referências: Cap. 4.1 [BM]. Extras: Notas da aula, Cap. 4 [M]. |
| 9 | 24/10 | Busca em largura (com corretude).
Referências: Cap. 6.1 [BM], Cap. 22.1, 22.2 [CLRS3]. Extras: Notas da aula, Cap. 20 [LM]. |
| 10 | 29/10 | Revisão e solução de exercícios.
Referências: listas. Extras: sobre indução e solução dos exercícios de indução das listas 1 e 2. |
| 11 | 31/10 | Prova 1 |
| 12 | 5/11 | Solução da P1. Algoritmo de Dijkstra e corretude.
Referências: Cap. 6.3 [BM], Cap. 24.3 [CLRS3]. Extras: Notas da aula, Cap. 23 [LM], animação do Dijkstra. |
| 13 | 7/11 | Emparelhamentos. Teorema de Berge. Cobertura por vértices.
Referências: Cap. 16.1, 16.2 [BM]. Extras: Notas da aula, Cap. 6 [M]. |
| 14 | 12/11 | Teorema de Konig. Teorema de Hall.
Referências: Cap. 16.2 [BM]. Extras: Notas da aula, Cap. 6 [M]. |
| 15 | 14/11 | Corolário do Teorema de Hall. Caminhos e ciclos Hamiltonianos. Teorema de Dirac.
Referências: Cap. 18.1, 18.3 [BM]. Extras: Notas da aula, Cap. 8 [M]. |
| 16 | 19/11 | Coloração de vértices. Limitantes.
Referências: Cap. 14.1, 14.3 [BM]. Extras: Notas da aula, Cap. 9 [M]. |
| 17 | 21/11 | Coloração de vértices. Coloração de arestas. Limitantes.
Referências: Cap. 17.1, 17.2 [BM]. Extras: Notas da aula, Cap. 10 [M]. |
| 18 | 26/11 | Coloração de arestas. Limitantes. Grafos planares.
Referências: Cap. 17.1, 17.2 [BM]. Extras: Notas da aula, Cap. 10 [M], vídeo sobre grafos planares, por uma das melhores grafeiras que existem. |
| 19 | 28/11 | Grafos planares e não-planares. Teorema de Kuratowski.
Referências: Cap. 10.1, 10.3, 10.5, 15.1, 15.2 [BM]. Extras: Notas da aula, Cap. 12 [M], vídeo sobre grafos planares, por uma das melhores grafeiras que existem. |
| 20 | 3/12 | Revisão e solução de exercícios.
Referências: listas. |
| 21 | 5/12 | Revisão e solução de exercícios.
Referências: listas. |
| 22 | 10/12 | Prova 2 |
| 23 | 12/12 | Atendimento na sala da professora. |
| 24 | 15/02/2020 | Prova de recuperação, 9h, sala S-301-2. |
Plágio (voltar ao topo)
- Entre outros, o código de ética da UFABC estabelece em seu artigo 25 que é eticamente inaceitável que os discentes:
- fraudem avaliações,
- fabriquem ou falsifiquem dados,
- plagiem ou não creditem devidamente autoria,
- aceitem autoria de material acadêmico sem participação na produção,
- 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.
- Sempre consulte o documento completo ou converse com o seu professor em caso de dúvidas!
- 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.
Listas de exercícios (voltar ao topo)
- Ao todo teremos 4 listas, cujos enunciados serão disponibilizados aqui, nas datas indicadas abaixo.
- As listas conterão exercícios teóricos e práticos.
- As soluções dos exercícios teóricos deverão ser feitas à mão (capriche na letra!), escaneadas e um único arquivo em formato PDF deve ser entregue (sugestão de aplicativo: CamScanner).
- As soluções dos exercícios práticos deverão ser feitas em linguagem C e um único arquivo em formato c deve ser entregue.
- A entrega deverá ser feita apenas pelo tidia (a menos que haja problemas no tidia nas datas em questão, caso em que elas podem ser entregues por e-mail).
- Todos os prazos de entrega já estão definidos (marque na sua agenda!).
- Soluções entregues em no máximo 12h após o prazo serão aceitas em casos bem justificados.
- O critério de correção de uma lista será indicado na mesma.
- Qualquer detecção de plágio nas listas 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 (vide Seção plágio).
Critérios de avaliação regular (voltar ao topo)
- A avaliação da disciplina constituirá da nota de duas provas, respectivamente denotadas por P1 e P2, e da média simples das notas das listas de exercícios, denotada por L, onde 0 ≤ P1,P2,L ≤ 10.
- A prova 1 vale 40% da nota.
- A prova 2 vale 40% da nota.
- As listas valem 20% da nota.
- Sua média final (MF) antes da recuperação, portanto, será
MF = 0.4 x P1 + 0.4 x P2 + 0.2 x L - 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
O, se ausência total exceder 25%
Mecanismo de recuperação (voltar ao topo)
- A recuperação será aplicada apenas aos alunos que tiverem conceito final D ou F e cujas ausências não excederem 25% da quantidade de aulas.
- Consistirá numa prova, em formato similar às aplicadas ao longo do curso.
- 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 + 2 x NR) / 3}
- 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
Mecanismos de avaliação substitutivos (voltar ao topo)
A prova substitutiva será aplicada ao aluno que possuir justificativa de ausência em uma das provas. A listagem dos documentos aceitos como justificativa consta na resolução ConsEPE n° 181.A nota obtida na prova substitutiva necessariamente substituirá a prova para a qual o aluno tem justificativa.
A data para realização da prova substitutiva deverá ser combinada com a professora por e-mail o quanto antes, assim que o aluno estiver em condições de realizá-la.
Carla Negri Lintzmayer - carla.negri@ufabc.edu.br