MCTA027-17 -- Teoria dos Grafos -- Estudo Dirigido -- 2022.2
Atualizado em 10/05
Página do curso entra no ar.
Expediente
- Professor: Aritanan Gruber
- Moodle: TG22.2-ED
- Atendimento: Ter 18–19h via Conferênciaweb da RNP
Ementa
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.
Avaliações e critérios
- 5 listas de exercícios ($L_1,\ldots,L_5$): enunciados, datas de entrega e correções no Moodle
Nota nominal: média aritmética das 4 melhores dentre as 5 listas $$ N = \frac{1}{4}\max\left\{\sum_{j\in S}L_j\,:\,S\in\binom{[5]}{4}\right\} $$
Conceito nominal ($C_N$): reflete o seu desempenho frente ao material apresentado e às avaliações realizadas; obtido pelo encaixe de $N$ em um dos intervalos: $$-\infty < \mathbf{F} < 5.0 \leq \mathbf{D} \leq 6.0 < \mathbf{C} \leq 7.0 < \mathbf{B} \leq 8.5 < \mathbf{A} < \infty.$$
Normalização
Sejam $\mu$ e $\sigma$ a média e o desvio padrão das notas $N$ atribuídas a todos os alunos. Cada aluno obterá uma nota normalizada: $$M = (N-\mu)/\sigma.$$
Conceito normalizado ($C_M$): reflete o seu desempenho perante os seus colegas; obtido pelo encaixe de $M$ em um dos intervalos: $$-\infty < \mathbf{F} < 0 \leq \mathbf{D} < \frac{1}{4}\sigma \leq \mathbf{C} < \frac{1}{2}\sigma \leq \mathbf{B} < \sigma \leq \mathbf{A} < \infty.$$
Considerando-se a ordenação $\mathbf{A} > \mathbf{B} > \mathbf{C} > \mathbf{D} > \mathbf{F}$, seu conceito efetivo (final / pré-recuperação) será maior ou igual ao seu conceito nominal: $$C_F = \max\{C_N,C_M\}.$$
Recuperação
Caso seu conceito $C_F$ seja $\mathbf{D}$ ou $\mathbf{F}$, você tem direito a uma prova online de recuperação $P_R$. Esta será única e contemplará toda a matéria do quadrimestre. Uma nova nota nominal $\overline{N}=(N+P_R)/2$ será utilizada para gerar um novo conceito (nominal) final pós-recuperação $\overline{C}_N$. Não haverá normalização na recuperação. Seu conceito final pós-recuperação pode ser menor que o pré-recuperação: uma vez feita, a recuperação é parte integrante da sua avaliação.
Bibliografia
- [BM] J.A. Bondy, U.S.R. Murty, Graph Theory, Springer-Verlag (2008)
Lista de tópicos por semana
Aulas | Tópicos | Leitura (Seções em [BM]) |
---|---|---|
A01 – A02 | Grafos e Digrafos: conceitos elementares | 1.1, 1.2, 1.4, 1.5 |
A03 – A05 | Subgrafos e Componentes | 2.1, 2.2, 2.4, 2.5, 3.1 – 3.4 |
A06 – A08 | Florestas e Árvores | 4.1, 4.2, 4.3, 5.1, 5.2, 6.2, 8.5 |
A09 – A10 | Traslados e Caminhos | 6.1, 6.3, 6.4 |
A11 – A13 | Fluxos | 7.1, 7.2, 7.3 |
A14 – A15 | Conectividade | 9.1, 9.2, 9.3, 9.6 |
A16 – A18 | Emparelhamentos e Coloração de Arestas | 16.1, 16.2, 17.1, 17.2 |
A19 – A20 | Ciclos Hamiltonianos | 18.1, 18.3 |
A21 – A22 | Conjuntos Estáveis, Cliques e Coloração | 12.1, 14.1 |
Estudando para esta disciplina
Este curso tem nível introdutório e contempla uma coleção de problemas elementares e fundamentais na área. Apesar disso, é normal fazer confusões e sentir-se perdido no início. O motivo é, em geral, a falta de familiaridade com formalismo matemático e raciocínio algorítmico -– algo que o curso pretende reverter.
- Refaça os exemplos fornecidos em sala de aula e re-prove os principais resultados.
- Preste atenção ao processo de solução e não foque somente no resultado final.
- Assista às aulas (vídeos) e resolva os exercícios propostos durante as mesmas e os contidos nas listas (não somente os para entrega).
- Estude a bibliografia indicada (monte grupos de estudo online) e faça um bom uso dos horários de atendimento.
- Tenha sempre em mente que aprendizado é uma tarefa ativa; não fique somente assistindo.
- Se ainda estiver se sentindo perdido, repita os passos acima. Mais cedo ou mais tarde, eles convergirão à compreensão.
Integridade acadêmica e transgressões
O Artigo 25 do Código de Ética da UFABC estabelece, à página 23: “Quanto aos trabalhos acadêmicos, é eticamente inaceitável que os discentes:
- I - fraudem avaliações;
- II - fabriquem ou falsifiquem dados;
- III - plageiem ou não creditem devidamente autoria;
- IV - aceitem autoria de material acadêmico sem participação na produção;
- V - vendam ou cedam autoria de material acadêmico próprio a pessoas que não participaram da produção.”
Trabalhos (listas, provas, programas) suspeitos de cópia ou de outra representação fraudulenta acarretarão aos envolvidos conceitos $\mathbf{F}$ (falha) no curso. A atividade será reportada à Comissão Disciplinar Discente da universidade para que sejam tomadas todas as providências disciplinares cabíveis.