Fundamentos de Modelagem Computacional de Conhecimento

Horário e Local da Disciplina

Quartas e Quintas das 10:20 as 12:00, na Sala do Mestrado/MMCC

Bibliografia:

  1. Introduction to Algorithms. 2ª ed., MIT Press, Cambridge, 2001. T. H. Cormen; C. E. Leiserson; R. L. Rivest; C. Stein
  2. Projeto de Algoritmos com implementações em Pascal e C. 3° Ed. Cengage Learning, 2010. Nivio Ziviani
  3. Matemática Discreta e Suas Aplicações. Kenneth H. Rosen, Mc-Graw Hill, tradução da 6a edição, 2009, ISBN-978-77260-36-2
  4. Artigos (indicados em aula)

Bibiografia adicional será indicada ao decorrer do curso

Material de apoio:

  1. Indrodução à disciplina
  2. Fundamentos de software, hardware e algoritmos
  3. Complexidade de algoritmos e notação assintótica
  4. Análise de algoritmos recursivos
  5. Teoria dos Grafos
  6. Teoria da Complexidade

Exercícios:

  • Lista de exercícios 1 (dia 18/09/2014) - Enviar para o email heitor <at> ic <dot> com <dot> br com o assunto "[LE1 - Fundamentos] - <NOME>"
  • Lista de exercícios 2 (dia 18/12). Entregar impressa.

Avaliações:

  • Prova 1 - (itens 1-4 da seção "material de apoio", caps 1-4 do cormen) - 08/10/2014

Datas Importantes

Seminários:

26/11 - equipes 8,3,1

27/11 - equipes 9, 2, 7

03/12 - equipes 10, 4, 6

04/12 - Evento (LCCV)

Trabalho Final

10/12 - equipes 8 e 3

11/12 - equipes 1 e 9

17/12 - equipes 10 e 7

18/12 - equipes 2, 4 e 6

Lista de Exercícios:

18/12 - Entregar a lista impressa

Seminários:

O ciclo de seminários se dará em torno dos seguintes artigos:

  1. The Great Principles of Computing (André e Wanderson)
  2. The Science in Computer Science (Zeferino, Antonio e Wilson)
  3. Is Computer Science Science? (Estela e Thiago)
  4. A New Framework for Computer Science and Engineering (Bruno e Fábio)
  5. Should Computer Scientists Experiment More?
  6. Computational Thinking (Vilker e Vitor)
  7. Five Deep Questions in Computing (Hugo e Paulo)
  8. Beyond Data and Analysis (Diego e Carlos)
  9. How Computers are Changing Biology (Helenilson e Renan)
  10. Life in Simulation (Pedro, Antonio e Juliana)

Trabalho Final

Observacões:

1. Comece a fazer este trabalho imediatamente. Você nunca terá tanto tempo para resolvê-lo quanto agora!

2. Este é um trabalho em grupo de no máximo 3 componentes.

3. Data de Entrega: de acordo com o cronograma apresentado no site da disciplina. O relatório deverá ser entregue impresso no dia da apresentação.

Problemas NP-completo e NP-difícil

Existem vários problemas que são NP-completo ou NP-difícil. O objetivo deste trabalho é identificar um algoritmo que sabidamente seja NP-completo ou NP-difícil e estuda-lo em detalhes. Os resultados devem ser apresentados na forma de uma revisão bibliográfica. Opcionalmente, valendo pontos extras, o grupo poderá apresentar uma heurística para a resolução desse problema. Nesse caso, a heurística deve ser implementada e avaliada para estimar o fator de aproximação.

O que deve ser feito

1. Escolha o seu problema e envie um email para heitor <at> ic <dot> ufal<dot>br. Aponte claramente a referência original onde o problema é proposto.

2. Escreva um relatório técnico de até cinco páginas (utilize preferencialmente o latex e escreva sobre o tema em português ou inglês no formato definido pela ACM. Para informações sobre a formatação veja a página http://www.acm.org/sigs/publications/proceedings-templates. O seu relatório deve conter claramente:

• A formulação do problema;

• A prova que o seu problema é NP-completo ou NP-difícil;

• As heurísticas utilizadas para resolver esse problema (revisão bibliográfica);

• A heurística que será implementada e avaliada (pode ser uma heurística nova, proposta pelo grupo, ou alguma das heurísticas encontradas na literatura).

• Avaliação experimental da heurística implementada, ou seja, este trabalho envolve obrigatoriamente a implementação e avaliação experimental;

• Análise do trabalho feito. Analisar significa que você deve ser capaz de entender os resultados e explicá-los de forma convincente. O grupo pode avaliar uma heurística já existente e reproduzir os resultados apresentados na literatura. Porém, deve acrescentar algo à avaliação existente.

• Caso seja necessário utilizar mais de cinco páginas, escreva essa parte extra como um apêndice de seu trabalho. Não há limite de páginas para o apêndice.

Composição da Nota

A nota será composta da seguinte maneira:

· 4 pontos para a apresentação individual (apesar do trabalho ser em grupo, todos devem apresentar)

· 4 pontos sobre a qualidade do relatório apresentado.

· 2 pontos sobre a qualidade da avaliação / implementação da heurística

· 2 pontos extras (porém somando máximo de 10 pontos) para quem propuser uma heurística diferente da que existe na literatura.

Equipes/Tema

Os temas serão atribuídos às equipes de acordo com a chegada dos e-mails.

  1. Helenilson/José Renan - Problema da Mochila 0-1 (Knapsack problem)
  2. Carlos Alberto/Diego Bezerra - Problema de Roteamento de Veículos (Vehicle Routing Problems (VRP))
  3. Fábio, Vilker e Victor - Problema do Clique em grafos
  4. Thiago Avila e Estela Mayra - Problema do Campo Minado

Composição da nota:

A nota será composta da seguinte maneira:

NF = (P1 + LE1 + LE2 + TF + SE)/5

onde:

NF - Nota final

P1 - Primeira prova

LE1 - Primeira lista de exercícios

LE2 - Segunda lista de exercícios

TF - Trabalho Final

SE - Seminário

Notas

Observação:

  • Os alunos Thiago, Estela e Zeferino estão com as notas pendentes pois não entregaram parte das avaliações. Pelo atraso, sofrerão uma penalização na nota.
  • Considerei as notas finais normalizadas
  • A tabela abaixo já contempla todo e qualquer tipo de ajuda, arredondamento, empurrões, etc. NENHUM outro tipo de ajuda será considerada.
  • Boas férias a todos!

Legenda:

  • LE1 - Lista de exercícios 1
  • P1 - Primeira Prova
  • SE - Seminário
  • TF - Trabalho Final
    • TFA - Apresentação
    • TFR - Relatório
    • TFH - Análise da Heurística
    • TFE - Pontos extras
  • NLE2 - Lista de exercícios 2 ( grafos)
    • PEN-LE2 - Penalização por ter copiado totalmente a lista ou por ter atrasado a entrega - nota original da lista