MAB 368, Algoritmos e Grafos - 2019/2

Bacharelado em Ciência da Computação, Professora Márcia R. Cerioli
Instituto de Matemática - UFRJ

Aulas:

  • 6 ago - terça Descrição do conteúdo da disciplina. Indicação de ítens a serem revisados. Revisão do vocabulário de teoria dos grafos.
    Representação de grafos e digrafos. Tamanho da entrada de um algoritmo sobre grafos: O(n+m).
  • 8 ago - quinta Matriz de adjacência x Lista de Adjacências. Complexidade das operações básicas em cada uma.
    Algoritmo ótimo. Cota inferior igual ao tamanho da entrada. Cota inferior do problema. Problema da ordenação topológica. Grafos com ciclos não tem ot. Como exibir uma ot. Para casa: Teorema de caracterização dos grafos que possuem o.t.
    Primeira lista de exercícios.
  • 13 ago - terça Descrição de um primeiro algoritmo. Graus de entrada. Prova de corretude e análise da complexidade de tempo e espaço.
    Algoritmo para ot de digrafos acíclicos: descrição, corretude e complexidade de tempo e espaço (para casa e discussão no grupo). Algoritmo ótimo para o problema da Ordenação Topológica. Subrotinas na descrição de algoritmos.
  • 15 ago - quinta Busca em Grafos.
    Algoritmo Geral de busca. Descrição, exemplos. Busca em Largura e em Profundidade.
    Corretude. Obs. Este conteúdo não está nos livros, de maneira tão explícita.
  • 20 ago - terça Busca em Grafos.
    Complexidade do Algoritmo Geral de Busca. Árvores de busca. Propriedades do Algoritmo Geral de busca. Floresta geradora. Teste de conexidade de grafo. Número de componentes conexos.
  • 22 ago - quinta Nível de vértices na árvore de busca. Ordem do processamento dos vértices em uma busca: L, PE, PS
    Busca em Largura. Classificação das arestas em uma BL. Teste
  • 27 ago - terça Inscrições na Semana de Computação e Programação
  • 29 ago - quinta Semana de Computação Em especial, teremos Meia-maratona de Programação neste dia! ♥♥
  • 3 set - terça Distância e cálculo da distância de um vértice a raiz da busca.
    Ciclos ímpares em uma BL e Reconhecimento de grafos bipartidos. Segunda lista de exercícios.
  • 5 set - quinta Busca em Profundidade em grafos não direcionados.
    Propriedade das arestas da co-árvore em uma BL. Biconectividade e articulações. Função lowpt e demarcadores.
  • 10 set - terça Busca em Profundidade em grafos direcionados.
    Classificação das arestas em uma BP. Componentes fortemente conexos. Grafo dos cfc.
  • 17 set - terça Conceitos de BP para determinar componentes fortemente conexos. Terceira lista de exercícios
    Algoritmos de Kosaraju-Sharir para cfc (livro do Cormen)). Prova de corretude. Análise da Complexidade.
  • 19 set - quinta Alteração Estrutural Número cromático e o problema da coloração de vértices.
    Coloração de vértices - algoritmo de Zykov (Jayme, seção 5.6 e 5.7) Corretude e complexidade do algoritmo de Zykov.
  • 24 set - terça - Primeira Prova ❀
  • 26 set - quinta Problemas de Otimização Combinatória.
    Método Guloso. Algoritmo guloso para coloração (não necessariamente ótima) de grafos de complexidade O(n+m). (livro do Jayme).
    Problema Árvore geradora mínima
  • 1 out - terça Critérios gulosos para resolver o problema da Árvore Geradora Mínima.
    Algoritmo de Kruskal (mantém acíclico). Corretude e Complexidade.
  • 3 out - quinta Árvore geradora mínima. Critério guloso do Algoritmo de Prim (mantém conexo).
    Problema da Seleção de Atividades Critérios gulosos que não estão corretos.
    Critério guloso que leva a um algoritmo correto. Algoritmo e complexidade. Quarta lista de exercícios.
  • 8 out - terça Problemas dos Caminhos mais curtos e suas relações. Algoritmo de Dijkstra
    Programação Dinâmica: Técnica geral.
  • 10 out - quinta Técnica geral e subestrutura ótima (livro do Cormen e pg 130-131 do livro do Jayme).
    Algoritmo de Floyd-Warshall (livro do Cormen, seção 25.2). Corretude e complexidade de Floyd-Warshall.
    Teste
  • 15 out - terça Programação Dinâmica. Execução, complexidade de espaço e recuperação dos caminhos em Floyd-Warshall.
    Problema da Maior Subsequência Comum (MSC) (Cormen, seção 15.4). Solução sem PD.
  • 17 out - quinta Algoritmo para a MSC por PD. Complexidade de tempo e espaço.
  • 22 out - terça Semana de Integração Acadêmica
  • 24 out - quinta Semana de Integração Acadêmica
  • 29 out - terça Fluxo em grafos. (Jayme, Cap 6)
    Rede, fluxo, o problema do fluxo máximo, valor de um fluxo, fluxo maximal. Corte em uma rede, capacidade do corte, fluxo em um corte.
  • 31 out - quinta Cortes e fluxo
    fluxo em um corte, fluxo na rede, cota superior para o valor de um fluxo máximo. Redes residuais. Caminho aumentante.
  • 5 nov - terça Caminho aumentante de fato, aumenta o valor do fluxo. Teorema do Fluxo máximo-Corte Mínimo. Algoritmo de Ford e Fulkerson.
    Teorema do fluxo inteiro (Se as capacidades são números inteiros, então o fluxo obtido pelo algoritmo de FF terá um valor inteiro em cada aresta da rede) e, portanto, um valor inteiro a cada iteração. Análise do Algoritmo de Ford e Fulkerson. (Jayme, Seção 6.3 e 6.4)
  • 7 nov - quinta Algoritmo de Edmonds-Karp para fluxo máximo (Jayme, Seção 6.5)
    Algoritmo de Dinic (Jayme, Seção 6.6)
    Corretude e exercício comparativo.
  • 12 nov - terça
    Algoritmo de Edmonds-Karp e Algoritmo de Dinic Análise das Complexidades.
    Aplicação de fluxo máximo (emparelhamento em grafos bipartidos).
  • 14 nov - quinta Um filme (menos de 5 min)
    Não haverá aula presencial.
  • 19 nov - terça Segunda Prova ❀
    (a confirmar até 15 de novembro)

    Página criada em 4 ago 2019 e última atualização 12 out 2019 por Márcia R. Cerioli