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
** Semana 4: Semiário 1: algoritmos de backtracking
** Semana 5: Seminário 2: Busca combinatorial 1
** Semana 6: Seminário 3: Busca combinatorial 2
** Semana 7: Seminário 4: Busca combinatorial 3
** Semana 8: Seminário 5: Busca combinatorial 4
** Semana 9: Seminário 6: Busca combinatorial 5
** Semana 10: Seminário 7: Satisfatibilidade 1
** Semana 11: Seminário 8: Satisfatibilidade 2
* 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.