Estruturas de Dados e Complexidade de Algoritmos

Prof. Dr. Lucídio dos Anjos Formiga CabralPPGI/UFPB

Março/2009

Descrição do curso

• Conteúdo– Introdução– Fundamentos de algoritmos– Análise da eficiência de algoritmos– Ordenação e estatísticas de ordem– Estruturas de dados avançadas– Técnicas avançadas de projeto e análise– Tópicos selecionados– Problemas NP-Completos

Bibliografia

• Básica:– CORMEN, T.; LEISERSON, C.; RIVEST, R.; STEIN, C.; Algoritmos:

Teoria e Prática, Editora Campus, Rio de Janeiro, 2002.

• Complementar– GOODRICH, M. T., TAMASSIA R., Projeto de Algoritmos, Editora

Bookman, Porto Alegre, 2004.– ZIVIANI, N., Projeto de Algoritmos, Editora Pioneira Thomson, Belo

Horizonte, 2004.– Knuth, D., The Art of Computer Programming, Volumes 1,2 e 3,

Addison-Wesley,1997.– TOSCANI, L. V.; VELOSO. PAULO A. S. Complexidade de

Algoritmos, Editora Sagra-Luzzatto, 2001.– SZWARCFITER, J.; Grafos e Algoritmos Computacionais, Editora

Campus, Rio de Janeiro, 1984.– TERADA, R.; Desenvolvimento de Algoritmos e Estrutura de Dados.

Editora Makron Books, 1991.

Organização do Curso

• Página do cursowww.di.ufpb.br/~lucidio/complexest.htm

• 3 provas escritas

Introdução

• O que é um algoritmo?– São as idéias implícitas nos programas de

computadores.– Corresponde a um conjunto bem definido de

regras que especificam uma seqüência de operações a serem aplicadas a um conjunto de dados, chamado entrada, produzindo após uma quantidade finita de tempo um conjunto de dados chamado saída.

– Também chamado de processo, procedimento computacional, etc.

– Pode ser implementado de diferentes formas.

O que será estudado?

• Objetivos principais:– Um conjunto de ferramentas práticas: uma

coleção de algoritmos fundamentais para uso em outros cursos, ou em seus trabalhos futuros.

– Estudo teórico: uma avaliação dos aspectos envolvidos no projeto, análise ou seleção de um algoritmo para um novo problema.

Exemplos de algoritmos

2 – Número Primo

Entrada: Uma número natural q.Saída: sim ou não, dependendo se q é primo.

NÓS BUSCAMOS ALGORITMOS QUE SEJAM CORRETOS E EFICIENTES !!!

1 - Ordenação

Entrada: Uma seqüência de n números ‹a1, a2, ..., an›.

Saída: Uma reordenação da seqûëncia de entrada ‹a'1, a'2, ...,a'n›,

onde a'1 ≤ a'2 ≤ ... ≤ a'n

Problemas

• Estudaremos os problemas computacionais, que consistem de uma descrição geral da questão a ser respondida, em geral, envolvendo algumas variáveis livres ou parâmetros.

• Uma instância de um problema computacional é uma questão específica obtida por associar valores aos parâmetros do problema.

Problema do Caixeiro Viajante

• Instância: Um conjunto de cidades X juntamente com a informação de distância d(x,y) entre qualquer par x, y pertencentes a X.

• Questão: Qual é a menor rota circular que inicia e termina em uma dada cidade e visita todas as cidades?

Problema Computacional

• Um instância de um problema computacional é um possível valor para a entrada.– ‹45, 7, 13, 23, 2› é uma instância para o problema da

ordenação.– 29 é uma instância para o problema dos números

primos.

• Um algoritmo está correto se, para qualquer instância, ele termina e retorna como saída o valor esperado.

Como expressar algoritmos?

• Aspectos como precisão e facilidade de expressão são importantes.

• Três formas– Linguagem natural– Pseudo-Código– Linguagem de Programação

• Infelizmente, quanto maior a facilidade de expressão menor é a precisão.

Corretude

• Para qualquer algoritmo, nós devemos provar que ele sempre retorna a saída desejada para todas as instâncias válidas do problema.

• Para a ordenação, isto deve ser válido ainda que a entrada já esteja ordenada, ou que contenha elementos repetidos

Quão bom é um dado algoritmo?

• Existem muitas considerações envolvendo esta questão?– Corretude

• Corretude teórica• Estabilidade númerica

– Eficiência• Complexidade• Velocidade• Uso de outros recursos

Corretude não é óbvia!

• O seguinte problema aparece em aplicações de manufatura e transporte.

• Suponha que você tenha um braço de robô equipado com um soldador. Para habilitar o braço do robô a soldar todos os pontos de contato, devemos construir uma ordem de visita aos pontos.

• Desde que robôs são caros, nós precisamos encontrar a ordem que minimiza o tempo (ou distância percorrida) que ele gasta para efetuar a solda nos pontos desejados.

Imagine um algoritmo para encontrar o melhor percurso!

Estratégia do vizinho mais próximo

• Uma solução muito popular inicia em algum ponto p0 e então caminha em direção ao vizinho mais próximo, digamos p1, e repete o procedimento.

• AlgoritmoVisite o ponto inicial p(0)

P = p(0)

i = 0

Enquanto existir ponto não visistado

i = i + 1

Seja p(i) o ponto não visitado, mais próximo de p(i-1)

Visite p(i)

Retorne para p(0) a partir de p(i)

• Este algoritmo é simples de entender e implementar e muito eficiente. Entretanto .............

Estratégia do vizinho mais próximo

• Entretanto, ele não é CORRETO!!!

Adotar a estratégia de sempre começar pelo ponto mais à esquerda ou a partir de qualquer outro ponto não corrige o problema.

Um algoritmo correto

• Nós podemos tentar todas as ordens possíveis dos pontos e então selecionar a ordem que minimiza o comprimento total.

• Algoritmod = INF

Para cada uma das n! Permutações Pi dos n pontos

Se (custo(Pi) <= d) então

d = custo(Pi)

Pmin = Pi

Retorne Pmin

• Desde que todas as ordens possíveis são consideradas, tem-se a garantia de terminar com o percurso (ciclo) de menor custo possível.

• Para valores ainda modestos de n este algoritmo se torna inviável.• Nenhum algoritmo correto eficiente existe para o problema do caixeiro

viajante.

O modelo RAM

• Algoritmos são a única parte durável, importante e original da ciência da computação porque podem ser estudados de modo independente da linguagem e da máquina.

• Assim sendo, faremos toda a nossa análise baseada no modelo de computação RAM (Máquina de Acesso Aleatório).

– Cada operação simples (+, -,=,if, call) toma exatamente um passo.– Laços e chamadas de procedimentos não são operações simples,

mas dependem sobre o tamanho da entrada e do conteúdo do procedimento.

– Cada acesso a memória toma exatamente um passo

• Nós medimos o tempo de execução de um algoritmo contando o número de passos.

Complexidade de melhor, médio e pior caso

• A complexidade de pior caso de um algoritmo é a função definida pelo número máximo de passos tomados sobre qualquer instância de tamanho n.

• A complexidade de melhor caso de um algoritmo é a função definida pelo número mínimo de passos tomados sobre qualquer instância de tamanho n.

• A complexidade de caso médio de um algoritmo é a função definida pelo número médio de passos tomados sobre qualquer instância de tamanho n.

Ordenação por Inserção

• Uma maneira de ordenar um vetor de n elementos é iniciar com uma lista vazia e sucessivamente inserir novos elementos na posição correta:

• Em cada estágio, o elemento inserido forma uma lista ordenada e após n inserções tem-se a lista totalmente ordenada.

• Quão eficiente é este algoritmo?• O tempo de execução muda para instâncias diferentes!!!!• Como esse algoritmo se comporta para uma lista já ordenada na

entrada?• E para uma lista ordenada em ordem inversa?

Análise exata da ordenação por inserção• Contaremos o número de vezes que cada linha do pseudo-código será

executada.

Análise exata da ordenação por inserção

• Para calcular T(n) do algortimo de ordenação, faremos:

Análise exata da ordenação por inserção• Melhor caso: lista ordenada de elementos• Avaliando o laço do enquanto podemos achar

T[ j ] <= x quando x tem valor inicial (i-1). E observamos que t(i)=1 para i=2,...,n. Portanto, o tempo de execução, neste caso é:

• O tempo de execução pode ser expresso então como:T(n) = an + b

Análise exata da ordenação por inserção• Pior caso: lista ordenada na ordem inversa

– Cada elemento T[ i ] deve ser comparado com todos os elementos da lista ordenada T[1...j –1] tal que t(i)=i para i=2,3,...,n.

– Observe que:

Análise exata da ordenação por inserção

• Portanto:

Análise exata da ordenação por inserção

• Que pode ser expresso como:

Análise do pior caso e do caso médio• Na análise do algoritmo de ordenação

consideramos o melhor e o pior caso. Vamos nos concentrar apenas no tempo de execução do pior caso, pois:– Seu tempo de execução corresponde a um limite

superior sobre o tempo de execução para qualquer instância.

– Ocorre com freqüência em alguns algoritmos.• Exemplo: pesquisa em um banco de dados por

informação não armazenada.

– Muitas vezes, o caso médio é quase tão ruim quanto o pior caso.

Ordem de Crescimento

• A função obtida na análise do pior caso do algoritmo de ordenação foi a função n2+bn+c. Esta função pode ser representada pelo termo n2 que tem crescimento muito superior aos demais termos.

• A ordem de crescimento é dada pelo termo mais significante da função. No algoritmo de ordenação nós dizemos que ele é de O(n2).

• Um algoritmo é mais eficiente que outro, se seu tempo de execução no pior caso tem uma ordem de crescimento menor.