CPS740 Algoritmos e Grafos / COS242 Teoria de Grafos - 2020

PESC - Programa de Engenharia de Sistemas e Computação
COPPE - Instituto Alberto Luiz Coimbra de Pós-Graduação e Pesquisa de Engenharia
UFRJ - Universidade Federal do Rio de Janeiro


Ir para:
Professores - Monitoria - Aulas - Ementa - Avaliações - Listas

AVISO: Vejam o comunicado do Prof. Daniel Ratton Figueiredo, Coordenador Acadêmico do PESC.

Esta página contém as principais informações sobre o curso de Algoritmos e Grafos (CPS740), que em 2020 será oferecido juntamente com Teoria dos Grafos (COS242) em uma parceria PESC-ECI. A página será alterada com frequência, então fiquem atentos. Também é útil consultar o FAQ sobre o retorno às atividades acadêmicas do PESC. Observem que existe um formulário provisório de inscrição do PESC, e um código para inscrição no Moodle anunciado na grade de disciplinas (no nosso caso, codigo16). O número de vagas da turma pode ser limitado.

Capa do livro

Nossa principal referência bibliográfica será o livro premiado:

Teoria Computacional de Grafos
Jayme Luiz Szwarcfiter
Rio de Janeiro, Elsevier, 2018.

Google Books - Prêmio Elon Lages Lima - Errata - Implementações

O livro está atualmente indisponível em versão impressa, mas pode ser adquirido em versão eletrônica a partir do site do Grupo Gen ou em outras livrarias de e-books.

PROFESSORES

Voltar ao topo

MONITORIA

Neste período contaremos com os seguintes monitores:

A monitoria será realizada por Google Meet nos horários indicados pela escala dos monitores. Os alunos também podem utilizar o Discord para troca de mensagens e para tirar dúvidas. (Pode ser acessado diretamente pelo browser e não é necessário abrir conta).

A escala dos monitores será a seguinte:

Data Horário Monitor
08/Julho 15h-16h Luiz
15/Julho 15h-16h Edinelço e Vitor
21/Julho 17h-18h Guilherme
28/Julho 14h-15h Bruno e Luiz
29/Julho 15h-16h Sobre L1
03/Agosto 14h-15h Bruno
10/Agosto 15h-16h Sobre L2
20/Agosto 17h-18h Luiz e Guilherme
26/Agosto 13h-14h Bruno e Vitor
31/Agosto 15h-16h Guilherme, Luiz e Bruno
09/Setembro 13h-14h Vítor
14/Setembro 15h-16h Sobre L4
16/Setembro 15h-16h Vista L3
28/Setembro 15h-16h Vista L4

Voltar ao topo

AULAS

As aulas serão ministradas de forma remota pelo Google Meet. Entrem de preferência com email @cos, caso possuam. Fiquem atentos também ao Moodle.
Horários: 3as- e 5as-feiras, de 8h às 10h.
Início do período: 06 de julho de 2020. Nossa primeira aula será 3a-feira dia 7 de julho.
Término do período: 03 de outubro de 2020.

Data Tópicos previstos Livro-texto Recursos Comentários
07/Julho Apresentação do curso; história sobre grafos e algoritmos; estruturas de dados; Python Cap. 1 Notas
Vídeo
Apresentação de Prof. Celina sobre o problema das quatro cores está disponível neste link. Artigo de Euler, de interesse histórico, está disponível neste link para quem tiver curiosidade; tradução em português disponível neste link.
09/Julho Complexidade de algoritmos; notação assintótica; algumas definições em Teoria de Grafos Cap. 1, Cap. 2 Notas
Vídeo
Uma exposição bem útil sobre caminhos Eulerianos (com direito a implementação em várias linguagens!) está disponível neste link. Uma reportagem interessante sobre o problema do isomorfismo de grafos e o resultado recente de Babai: neste link. Quem tiver curiosidade sobre notação assintótica, pode também ler este artigo de Donald Knuth.
14/Julho Mais definições em Teoria de Grafos; árvores; grafos direcionados; Representações de grafos Cap. 2 Notas
Vídeo
16/Julho Conectividade; planaridade; ciclos Hamiltonianos; coloração Cap. 2 Notas
Vídeo
21/Julho Implementações em Python Notas
Vídeo
Palesta do convidado Prof. Fabiano S. Oliveira (UERJ). Façam download das implementações neste link. Vejam também o projeto EMA.
23/Julho Técnicas básicas; coloração aproximada; ordenação topológica Cap. 3 Notas
Vídeo
Não percam o painel temático Ciência de Redes x Teoria dos Grafos: Uma Nova Esperança, com participação de Daniel Ratton Figueiredo e Fábio Happ Botler e moderação de Jayme Swarcfiter, no site do Festival do Conhecimento UFRJ 2020. Acessem pela Sala 17 a partir das 17h do dia 24/07.
28/Julho Recusão; dividir e conquistar; árvores de decisão; limite inferior para ordenação; programação dinâmica Cap. 3, Cap. 5 Notas
Vídeo
30/Julho Algoritmos gulosos Cap. 5 Notas
Vídeo
Vejam essa animação sobre o algoritmo de Kruskal.
04/Agosto Alteração estrutural; algoritmo para cálculo de número cromático; backtracking Cap. 5 Notas
Vídeo
06/Agosto Mais exemplos de dividir e conquistar e de programação dinâmica Cap. 5 Notas
Vídeo
Última aula antes da prova. Informem se quiserem revisar algum tópico específico. Não esqueçam de entrar neste site no dia 11 de agosto pela manhã para baixar a prova P1. Como vocês estarão fazendo prova, não teremos aula nos dias 11 e 13 de agosto.
18/Agosto Busca em grafos Cap. 4 Notas
Vídeo
20/Agosto Busca em profundidade - digrafos Cap. 4 Notas
Vídeo
25/Agosto Fluxo máximo em redes Cap. 6 Notas
Vídeo
27/Agosto Algoritmos para fluxo máximo Cap. 6 Notas
Vídeo
01/Setembro Caminhos mínimos Cap. 7 Notas
Vídeo
03/Setembro Alguns problemas ligados a grafos em maratonas da SBC Notas
Vídeo
Palestra com o convidado Prof. Paulo Eustáquio (UERJ)
08/Setembro Algoritmo de Floyd-Warshall Cap. 7 Notas
Vídeo
10/Setembro Emparelhamentos Cap. 8 Notas
Vídeo
15/Setembro Emparelhamentos Cap. 8 Notas
Vídeo
17/Setembro Emparelhamentos - continuação Cap. 8 Notas
Vídeo

* Prévia sujeita a modificações. Por favor avise se encontrar erros.
** Será disponibilizado.

Voltar ao topo

EMENTA

Serão cobertos os Capítulos 1-8 do livro-texto, que resumidamente correspondem aos seguintes tópicos:

Voltar ao topo

AVALIAÇÕES

Teremos duas provas e quatro listas de exercício.

Voltar ao topo

LISTAS

As listas resolvidas devem ser enviadas por email aos monitores indicados até a data limite. Não é necessário digitar as soluções em LaTeX, mas pedimos que escrevam de modo legível e bem organizado para evitar atrasos na correção.

Organizem todas as questões em um único arquivo PDF. Há muitas opções de aplicativos gratuitos para escanear documentos por meio de câmera de celular; vocês podem utilizá-los para preparar um PDF de soluções manuscritas caso não possuam um scanner convencional. Nesse caso, verifiquem se as páginas foram salvas na orientação correta e, se necessário, rotacionem as páginas. Recomendamos ainda que iniciem cada questão em uma nova página, incluindo também o nome completo, o número da lista e o número da questão.

Lista Data limite Enviar para
01 21/Julho Edinelço e Vitor
02 05/Agosto Luiz, Guilherme e Bruno
03 01/Setembro Luiz, Guilherme e Bruno
04 15/Setembro Vitor e Bruno

Voltar ao topo