Algoritmos e

Estruturas de Dados

Introdução a Algoritmos e

Estrutura de Dados (Aula 1)

Prof. Jeane Cecília

Roteiro

Apresentação do Plano de Ensino

Ementa, Objetivos, Conteúdo Programático,

Critérios de Avaliação, Referências

Algoritmos Computacionais

Definição, Exemplo, Complexidade, Formas

de Descrição

Ementa

Análise de Algoritmos: Notação O e

Análise Assintótica. Estruturas de Dados:

Listas, Árvores e Grafos. Pesquisa de

Dados. NP-Completude. Projeto:

desenvolvimento de programa com

estruturas de dados avançadas.

Objetivos

Apresentar aos alunos conceitos e

questões relativas ao desenvolvimento e

análise de algoritmos, bem como sua

relação com estruturas de dados.

Desenvolver o raciocínio algorítmico para

resolução de problemas computacionais.

Conteúdo Programático

Análise de Algoritmos

Análise do Pior Caso;

Notação Assintótica;

Conteúdo Programático Estruturas de Dados.

Listas ligadas: simples, duplas, circulares;

Alocação dinâmica de memória;

Pilhas, Filas: alocação estática e dinâmica;

Árvores: binárias;

Construção recursiva de árvores

Passeio em árvores: préfixo, pósfixo e central

Grafos: orientados e não-orientados;

Aplicações.

Conteúdo Programático

Pesquisas de Dados

Seqüencial e Binária;

Árvores: busca (largura e profundidade),

inserção e remoção; balanceamento;

Grafos: busca, árvore geradora;

Aplicações.

Conteúdo Programático

Conceitos Básicos de NP-Completude

Problemas NP-completos;

Redutibilidade;

Aplicações.

Projeto de Desenvolvimento com

Estruturas de Dados Avançadas

Critérios de Avaliação Exemplo de avaliação:

Primeira verificação: [Lista de Exercícios] (peso

3) + Prova Teórica (peso 6) + Participação (peso

1)

Segunda verificação: Prova Teórica (peso 4) +

Projeto (peso 5) + Participação (peso 1)

Terceira Verificação: Prova Escrita (todo o

assunto)

Exame Final: Prova Escrita (todo o assunto)

Referências

BÁSICA:

Cormen, Thomas H. et. al. Algoritmos: Teoria e Prática. Editora Campus, 2002.

COMPLEMENTAR:

Ziviani, Nivio. Projeto de Algoritmos. Editora Nova Fronteira, 2004.

Sedgewick, Robert. Algorithms in C++. Addison Wesley, 2000.

Manber, Udi. Introduction to Algorithms: A Creative Approach. Addison Wesley, 1989.

Sedgewick, Robert. and Flajolet, Philippe. An Introduction to the Analysis of Algorithms. Addison Wesley, 1996.

Algoritmos Computacionais

Definição (Cormen)

“Qualquer procedimento computacional bem

definido que toma algum valor ou conjunto de

valores como entrada e produz algum valor

ou conjunto de valores como saída.”

Algoritmos Computacionais

Entrada

Informações fornecidas inicialmente que

permitem encontrar a solução do problema.

Instância

Uma entrada específica para o problema

Saída

Resultado obtido após o processamento de uma

instância do problema.

Exemplo

O problema de ordenação:

Entrada: <a1, a2, ..., an>

Saída: <a’1, a’2, ..., a’n>

permutação da entrada tal que:

a’1 ≤ a’2 ≤ ... ≤ a’n

Exemplo

O problema de ordenação

< 10, 8, 5> (Instância do problema)

Algoritmo correto: Para cada instância de

entrada, ele pára com a saída correta

(resolve o problema)

Exemplo

Calcular 1+2 +...+n

Algoritmo1

Algoritmo2

Número de operações

O(n) O(n2) O(1)

Número de Operações

Exemplo

Sejam 5 algoritmos A1 a A5 para resolver um mesmo problema, de complexidades diferentes. (Supomos que uma operação leva 1 ms para ser efetuada.)

Tk(n) é a complexidade ou seja o número de operações que o algoritmo efetua para n entradas

nA1

T1(n)= nA2

T2(n)=nlog n

A3

T3(n)=n2A4

T4(n)=n3A5

T5(n)=2n

16 0.016s 0.064s 0.256s 4s 1m4s

32 0.032s 0.16s 1s 33s 46 Dias

512 0.512s 9s 4m22s 1 Dia 13h 10137 Séculos

Complexidade

Avaliação independente da máquina

Avaliação da eficiência do algoritmo em

termos de recursos computacionais

(tempo de execução, memória ocupada,

número de nós se processamento

distribuído).

Formas de descrição

Pseudo-código

Linguagem de programação

Fluxograma

Linguagem natural (ambigüidade!)

Desenvolvimento

Identificação de etapas

Detalhamento de cada etapa

Seqüência de operações básicas sobre os dados considerados

Exemplos:

Projeto genoma humano

Internet (rotas e localização de páginas)

Comércio eletrônico (criptografia, assinaturas)

Estruturas de dados

Meio para organizar e armazenar dados

com o objetivo de facilitar o acesso e as

modificações

Conhecer pontos fortes e limitações de

várias delas

A escolha da estrutura de dados podem

ser decisivos na eficiência do algoritmo

Estruturas de dados

Tipos de dados

Interger, real, boolean, etc.

Tipos abstratos de dados

Filas, pilhas, listas, etc.

Estruturas de dados: Método particular de

se implementar um TAD

Problemas NP-Completos

Classe de problemas para os quais não se

conhece uma solução eficiente.

É possível existir um algoritmos eficiente

para um problema NP?

Se existe para um, então existe para

todos!

Exemplo

Efetuar entregas através de caminhão a

partir de um armazém central. Qual a

menor distância percorrida pelo

caminhão?

Problema do caixeiro viajante

Referências

Referência básica para esta aula:

Capítulo 1 do Cormen

Exercício

Estudar o Capítulo 1 do Cormen