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.
|
Nossa principal referência bibliográfica será o livro premiado:
Teoria Computacional de Grafos 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. |
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 |
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.
Serão cobertos os Capítulos 1-8 do livro-texto, que resumidamente correspondem aos seguintes tópicos:
Teremos duas provas e quatro listas de exercício.
A prova P1 será entregue a vocês no dia 11 de agosto por meio deste link (que estará funcionando a partir do horário da aula), e as soluções deverão ser devolvidas até 17 de agosto, por email enviado para Franklin com cópia para Celina. Mantenham o mesmo padrão de organização e clareza utilizado nas listas de exercícios (escrever de forma legível ou em LaTeX, preparar um único arquivo PDF com todas as soluções etc). Será permitida consulta a livros, artigos, notas e vídeos das aulas e anotações pessoais. Para que vocês possam se concentrar totalmente na prova, não teremos aula nos dias 11 e 13 de agosto.
O gabarito está disponível neste link. Por favor, confiram as soluções do gabarito e as suas notas. Se restar alguma dúvida ou se acharem que algo está errado na correção, por favor compareçam à vista de prova na quinta-feira 10/9 de 15h às 16h, na mesma sala Google Meet usada para a monitoria.
A prova P2 será entregue a vocês no dia 18 de setembro por meio deste link (que estará funcionando a partir do horário da aula), e as soluções deverão ser devolvidas até 27 de setembro, por email enviado para Celina com cópia para Franklin. Mantenham o mesmo padrão de organização e clareza utilizado nas listas de exercícios (escrever de forma legível ou em LaTeX, preparar um único arquivo PDF com todas as soluções etc). Será permitida consulta a livros, artigos, notas e vídeos das aulas e anotações pessoais. Para que vocês possam se concentrar totalmente na prova, não teremos aulas a partir do dia 22 de setembro.
O gabarito está disponível neste link. A vista de prova será na na quinta-feira dia 1/10 de 8h às 9h na mesma sala Google Meet das aulas.
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 |