Disciplina de Algoritmos e Estruturas de Dados III

Conteúdo:

• análise de algoritmos e classes de complexidade de algoritmos;
• estratégias de projeto de algoritmos:
• divisão e conquista;
• programação dinâmica;
• algoritmos gulosos;
• backtracking.
• aplicações das diversas estratégias de desenvolvimento de algoritmos;
• algoritmos em grafos
• determinação de caminhos e ciclos;
• árvore geradora mínima;
• algoritmos de busca;
• ordenação topológica.

Transparências utilizadas em aula:

O conteúdo disponibilizado abaixo tem como objetivo auxiliar o aluno em alguns tópicos. Deve-se ressaltar que o estudo deve ser complementado com assuntos discutidos em aula e consultas bibliográficas.

Assunto	Arquivo com transparências	Arquivo com transparências e espaço para anotações
Crescimento de funções e notação assintótica.	aedsiii_01.pdf	aedsiii_01_annotations.pdf
Técnica de Divisão e Conquista.	aedsiii_02.pdf	aedsiii_02_annotations.pdf
Técnica de Programação Dinâmica.	aedsiii_03.pdf	aedsiii_03_annotations.pdf
Algoritmos em Grafos: Introdução.	aedsiii_04.pdf	aedsiii_04_annotations.pdf
Algoritmos em Grafos: Busca em Grafos.	aedsiii_05.pdf	aedsiii_05_annotations.pdf
Branch and Bound.	bnb.pdf

Códigos de Exemplo

• Problema da Mochila (com repetição de itens):
• knap_recursive.c
• knap_table.c

Trabalhos:

O material entregue para trabalhos deverá consistir em:

• Código: a implementação computacional pode ser feita em qualquer ferramenta, desde que o código entregue compile/execute com algum dos seguintes programas:
• GNU Compiler Collection (GCC) versão 3.x ou superior
• Free Pascal 2.x ou superior
• Java 1.4 ou superior
• Relatório Técnico
• O relatório técnico deve descrever o algoritmo e as estruturas de dados utilizadas, com o acompanhamento de experimentos computacionais que mostrem o desempenho do algoritmo com dados de diferentes dimensões. A visualização dos resultados deve ser facilitada com a inclusão de gráficos.

Trabalho - Branch-and-Bound:

• instruções e dicas;
• instâncias (em formato texto para dos/windows ou unix/linux);
• lucros ótimos pré-calculados para avaliação do seu algoritmo.

Exercícios:

Lista 1