Português English
Contato

Lista de Disciplinas | CMP605

Tópicos Especiais em Computação DCV – Tópicos selecionados em Otimização Combinatória

Professor responsável: Marcus Ritt
Carga Horária: 30 horas
2 créditos
Oferecimento: Segundo Semestre
Matrícula de Graduandos: INF05504

* Súmula
Tópicos selecionados em otimização combinatória focando no volume 4B do livro “The Art of Computer Programming” incluindo algoritmos de backtracking, estruturas de dados eficientes para backtracking, busca combinatorial para problemas de cobertura simples, e com cores e multiplicidade, técnicas de pré-processamente, e técnicas para resolver de satisfatibilidade. (Mais informações em http://www.inf.ufrgs.br/~mrpritt/doku.php?id=inf5504:homepage ).

* Objetivos
Ao final da disciplina espera-se que o aluno
– conheça métodos e algoritmos de estado de arte em tópicos selecionados em busca combinatória em otimização combinatória.
– saiba aplicar as técnicas a problemas práticos.
* Conteúdo Programático

** Semana 1: Introdução: Contextualização e visão geral de métodos e algoritmos de estado de arte em otimização combinatória.

** Semanas 2 e 3: Contextualização

  1. Revisão de conceitos matemáticos: variáveis aleatórias, probabilidades, probabilidades condicionais, desigualdades de Markov, Chernoff, Jensen, martingales, coeficientes binomiais, números harmônicas de Fibonacci.
  1. Revisão de conceitos de análise e projeto de algoritmos: técnicas de análise, solução de recorrências e funções geradoras, notação assintótica, programação dinâmica.
  1. Revisão de conceitos de otimização combinatória: programação linear e inteira, dualidade.

** Semana 4: Semiário 1: algoritmos de backtracking

  1. O algoritmo básico de backtracking.
  2. Estruturas de dados.
  3. Algoritmo para gerar pares de Langford.
  4. Códigos “commafree”.
  5. Estimar o tempo de execução.

** Semana 5: Seminário 2: Busca combinatorial 1

  1. Operação elementar de ligações dançantes.
  2. Problemas de cobertura exata.
  3. Algoritmo para resolver problemas de cobertura exata com ligações dançantes.

** Semana 6: Seminário 3: Busca combinatorial 2

  1. Itens secundários em problemas de cobertura exata.
  2. Solução de Sudokus.
  3. Probemas com polyominoes.
  4. A fatoração de um problema de cobertura exata.

** Semana 7: Seminário 4: Busca combinatorial 3

  1. Cobertura exata com cores.
  2. Multiplicidade em problemas de cobertura.
  3. Cobertura exata com cores e multiplicidades.

** Semana 8: Seminário 5: Busca combinatorial 4

  1. Análise de algoritmo para problemas de cobertura exata com cores e multiplicidades.
  2. Técnicas para focar em problemas de busca.
  3. Técnicas para aproveitar equivalências locais.
  4. Técnicas de pré-processamento.

** Semana 9: Seminário 6: Busca combinatorial 5

  1. Métodos para encontrar soluções de menor custo.
  2. Implementação de cortes de menor custo.
  3. Ligações dançantes com ZDDs (zero-suppressed decision diagram).

** Semana 10: Seminário 7: Satisfatibilidade 1

  1. Introdução à satisfatibilidade.
  2. Problemas de cobertura e coloração.
  3. Aplicações: fatoração, teste, aprendizagem de funções booleanas, verificação de modelos (model checking), tomografia digital.

** Semana 11: Seminário 8: Satisfatibilidade 2

  1. Solução de SAT bom backtracking.
  2. Estuturas de dados preguiçosas.
  3. Satisfatibilidade por observação.
  4. Satisfatibilidade com DPLL.

* Metodologia

Aulas teóricas-expositivas, exercícios individuais e em classe, trabalhos individuais com apresentação e discussão em aula.

Carga Horária
– Teórica: 25 horas
– Prática: 5 horas
* Experiências de Aprendizagem

Aulas teóricas-expositivas, exercícios individuais e em classe, trabalhos individuais com apresentação e discussão em aula. Estão previstas Atividades Autônomas do Aluno com uma carga horária de 5 (cinco) horas-aula a serem desenvolvidas ao longo do semestre. As atividades previstas podem incluir: realização de temas e trabalhos, leitura de texto (capítulos de livros ou artigos), resolução de listas de exercícios entre outras.

* Critérios de Avaliação
Os estudantes serão avaliados pela apresentação de um tópico selecionado em um dos seminários (nota S) e a solução de uma lista de exercícios correspondentes ao tópico (nota T).
A média final é M=(S+T)/2.
O conceito final corresponde com a nota final e a frequência f como segue:
Conceito final=
A, caso 9<=m<=10 e f>=75%
B, caso 7.5<=m<9 e f>=75%
C, caso 6<=m<7.5 e f>=75%
D, caso m<6 e f>=75%
FF, caso f<75%
Para ser aprovado é necessário obter um conceito final de A,B ou C.

* Atividades de Recuperação Previstas
Alunos que receberam um conceito D podem recuperar a nota através de uma prova oral sobre o conteúdo do tópico selecionado.
Um aluno com conceito final D pode realizar uma única prova oral de recuperação sobre a matéria do tópico selecionado. Pré-requisito para realização da prova de recuperação é uma frequência de 75% ou maior e ter apresentando o tópico selecionado em aula.
Não há recuperação das provas e nem dos trabalhos por não comparecimento/entrega, exceto nos casos previstos na legislação (saúde, parto, serviço militar, convocação judicial, luto, etc.), sendo necessária a devida comprovação por parte do aluno e a aprovação pela instância responsável dentro da universidade.
* Prazo para Divulgação dos Resultados das Avaliações
O resultado de cada avaliação será disponibilizado 15 dias úteis após do prazo de entrega.