MCCC003-23 -- Algoritmos em Grafos -- 2025.3

Expediente

• Professor: Aritanan Gruber , sala S-539.2
• Aulas: Qua. 08–10h e Sex. 10–12h na S-108.0
• Atendimento: Qua. 10–12h (na S-539.2)
• Monitoria: (a definir)
• Moodle: AG-Q24.3-DA1
  andamento do curso, links úteis, material, avaliações, notas, mensagens, etc.

Ementa

Revisão da terminologia básica de Teoria dos Grafos. Noções de análise de algoritmos. Estruturas de dados para representação de grafos. Buscas em largura e profundidade e suas aplicações: caminhos mínimos sem pesos, componentes conexas. Grafos ponderados. Árvores geradoras mínimas: algoritmos de Prim e Kruskal. Grafos Eulerianos e Hamiltonianos. O Problema do Caixeiro Viajante. Digrafos: definições básicas, componentes fortemente conexas e ordenação topológica. Caminhos mínimos em digrafos ponderados: algoritmos de Dijkstra, Bellman-Ford e Floyd–Warshall. Fluxo máximo: algoritmo de Ford-Fulkerson e suas aplicações.

Objetivos

Mostrar como representar um grafo computacionalmente (Matriz de Adjacências e Lista de Adjacências), discutir as vantagens e desvantagens de cada abordagem e discutir como adaptar tais estruturas para representar grafos nos quais os vértices e/ou arestas possuam atributos (por exemplo, grafos orientados, grafos ponderados, grafos com os vértices coloridos). Apresentar algoritmos eficientes para problemas clássicos em grafos e discutir, sem a necessidade de muito rigor formal, os tempos de execução dos algoritmos estudados. Discutir o impacto das estruturas de dados escolhidas para a implementação dos algoritmos sobre o tempo de execução desses. Espera-se que ao final do curso o aluno seja capaz de modelar problemas em grafos. Espera-se que este conheça os principais problemas em grafos e os algoritmos eficientes que os resolvem. Espera-se também que o aluno tenha demonstrado capacidade de implementar tais algoritmos em uma linguagem de alto nível. Por fim, espera-se que o aluno tenha noções da complexidade de tempo de execução dos algoritmos cobertos ao longo do curso. Este curso tem como objetivo desenvolver tanto habilidades teóricas (algoritmos) como práticas (implementações eficientes de tais algoritmos).

Recomendação

Natureza da Informação, Funções de Uma Variável, Algoritmos e Estruturas de Dados I e II, Programação Estruturada, Matemática Discreta I e II.

Avaliações e critérios

• listas de exercícios serão disponibilizadas no Moodle no decorrer do quadrimestre (em geral, a cada 4 aulas);
  devem ser feitas (fazem parte do seu estudo), mas não valem nota;
  
• três exercícios programas $E_1$, $E_2$ e $E_3$; datas de entrega a serem definidas ao longo do quadrimestre;
  
• três provas regulares $P_1$, $P_2$ e $P_3$ e uma prova substitutiva $P_4$ aberta;
  
  • $P_1$ : Sex. 10/10 @ 10h
  • $P_2$ : Sex. 07/11 @ 10h
  • $P_3$ : Sex. 05/12 @ 10h
  • $P_4$ : Sex. 12/12 @ 10h

Nota nominal ($N$): com $$ \begin{align*} P &= \frac{1}{3}\max\left\{\sum_{j\in S}P_j\,:\,S\in\binom{[4]}{3}\right\} \\ &= \frac{1}{3}\max\big(P_1 + P_2 + P_3,\ P_1 + P_2 + P_4,\ P_1 + P_3 + P_4,\ P_2 + P_3 + P_4\big), & P_j\in[0,10] \end{align*} $$ i.é, $P$ é a média das três melhores dentre quatro notas ($P_j=0$ em caso de ausência) e $$ E =\frac{1}{3}\big(E_1 + E_2 + E_3\big), \quad\quad E_i\in[0,10] $$ tem-se que $$ N = \frac{4}{5}P + \frac{1}{5}E. $$

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.$$

Recuperação

Caso seu conceito $C_N$ seja $\mathbf{D}$ ou $\mathbf{F}$, você tem direito a uma prova 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$. Note que 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

Primária

• [CLRS] T. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT University Press (2009)
  Versão em Português: Algoritmos: Teoria e Prática, 3a ed., Elsevier (2012)
• [KT] J. Kleinberg, E. Tardos, Algorithm Design, Pearson Education, Inc. (2006)

Secundária

• [AMO] R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows: Theory, Algorithms, and Applications, Prentice Hall (1993)
• [BM] J.A. Bondy, U.S.R. Murty, Graph Theory, Springer-Verlag (2008)
• [Eri] J. Erickson, Algorithms, self-published on the web (2019)
• [Feo] P. Feofiloff, Algoritmos para Grafos via Sedgewick, self-published on the web (2020)
• [Sed] R. Sedgewick, Algorithms in C, Part 5: Graph Algorithms, 3rd ed., Addison-Wesley (2002)
• [SW] R. Sedgewick, K. Wayne, Algorithms, 4th ed., Addison-Wesley (2011)

Requisitos

• [LLM] E. Lehman, F. Leighton, A. Meyer, Mathematics for Computer Science, MIT CC3.0 (2018)
• [Fle] M.M. Fleck, Building Blocks for Theoretical Computer Science , self-published on the web
• [DPV] S. Dasgupta, C. Papadimitriou, U. Vazirani, Algorithms, McGraw-Hill (2006)
  Versão em Português: Algoritmos, AMGH (2009)

Lista de tópicos (tentativa)

Detalhes de cada tópico (coberto nas aulas) serão atualizados no Moodle ao longo do quadrimestre.

[*] se o tempo permitir; em caso contrário, as aulas serão usadas para terminar os tópicos das aulas anteriores.

Estudando para esta disciplina

A natureza do tópico, o posicionamento do curso na grade, e a lista de pré-requisitos indicam que esta é uma disciplina de nível intermediário; e será tratada como tal. Você deve assistir às aulas, estudar a bibliografia indicada, e dedicar-se às listas de exercícios.

Caso seus pré-requisitos não estejam tão sólidos quanto desejável (falta de familiaridade com formalismo matemático e raciocínio algorítmico, atitude passiva com relação ao aprendizado, tempo dedicado insuficiente, etc.), será possível fazer confusões e sentir-se perdido no início.

Alguns procedimentos que costumam funcionar em cursos introdutórios para mitigar os motivos relacionados também costumam funcionar por aqui:

• Refaça os exemplos e re-prove os resultados fornecidos em sala de aula.
• Preste atenção aos processos de solução (aprenda-os!) e não foque somente nos resultados finais.
• Assista ativamente às aulas; resolva os exercícios nelas propostos e os contidos nas listas.
• Estude a bibliografia indicada, monte grupos de estudo, 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. “Ouvir” às aulas e “ler” os livros tem pouco ou nenhum efeito neste curso – e em qualquer disciplina matemática/algorítmica que o valha.
• Se ainda assim, sentir-se perdido, repita os passos acima. Mais cedo ou mais tarde, eles convergirão à compreensão.

Note que você não será convidado a regurgitar respostas fornecidas em aula ou presente nos livros. As questões em listas e provas testarão sua capacidade de entender os problemas e apresentar uma solução para eles. Às vezes, serão uma adaptação simples ou uma extensão direta do que foi visto. Outras, será necessário relacionar dois ou mais métodos ou conceitos apresentados. Outras ainda, irão requerer análise e raciocínio mais profundo (o que leva tempo, então não deixe nada para a última hora!).

Tenha em mente: além do escrito acima, para aproveitar bem este curso, você deve familiarizar-se com o material na leitura sugerida correspondentes antes da aula, e estudá-los com afinco depois.

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.

LLMs

Representam um grande avanço da inteligência artificial generativa. O uso para estudo é encorajado, mas cuidado com alucinações e respostas incorretas. Note que o uso de tais ferramentas durante avaliações enquadram-se no Artigo 25 acima.

Para pensar ao longo do curso: Do que adianta as máquinas aprenderem e os alunos não?