Análise de Algoritmos Informações Gerais da Disciplina

AULA 1Profa. Sandra de Amo

Disciplina: Análise de Algoritmos Pós-graduação em CC - UFU

Apresentação Geral do Curso

Página web Bibliografia Material de Suporte Conteúdo Avaliação Aula 1: Qual o objetivo desta disciplina ?

TODAS AS INFORMAÇÕES:www.deamo.prof.ufu.br/CursoAA-POSGRAD-2015-1.html

Bibliografia Básica

1. S. Dasgupta, C. H. Papadimitriou, and U. V. Vazirani. Algorithms. McGraw-Hill Science/Engineering/Math; 1 edition (September 13, 2006). PDF Disponível online

2. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, MIT Press, 3ª Edição, 2009. (Edição em portugues : “Algoritmos-Teoria e Prática”, Editora Campus 2003) PDF disponível online.

3. Donald E. Knuth. The Art of Computer Programming, Volume 4A: Combinatorial Algorithms,Part 1. (Series in Computer Science & Information Processing) Addison-Wesley Professional, 2011.

4. Vijay V. Vazirani. Approximation Algorithms. Addison-Wesley 2001

Bibliografia Complementar

1. David Harel and Yishai Feldman. Algorithmics: The Spirit of Computing, 3a Edição, Addison Wesley, 2004.

2. Steven S. Skiena: The Algorithm Design Manual. Springer, 2a Edição., 2008.

3. Bernhard Korte, Jens Vygen. Combinatorial Optimization: Theory and Algorithms (Algorithmsand Combinatorics), 4a Edição, 2010.

Material de Suporte

Livro Texto Slides Artigos

Conteúdo do CursoParte I : Conceitos Básicos

Problemas e Algoritmos Notação Assintótica Complexidade de Algoritmos - Complexidade de Problemas Projeto e Análise de um Algoritmo Algoritmos Recursivos Algoritmo Randômicos (Probabilísticos) - uma introdução Algoritmos para as Operações Aritméticas

Parte II: Algoritmos de Ordenação: Tempo não linear: ocupação otimal de espaço Tempo linear : ocupação não otimal de espaço

Conteúdo do Curso (cont.)Parte IV: Algoritmos de Grafos

Algoritmos elementares de busca em largura e em profundidade Caminhos mais curtos - Algoritmo de Dijkstra Técnica Gulosa para projeto de algoritmos Árvores Espalhadas - Algoritmos de Kruskal e Prim

Parte V: Técnicas Avançadas de Projeto e Análise Programação Dinâmica (PD) Recursão versus PD Memoization

Parte VI : Tópicos Avançados Problemas NP-completos Algoritmos Aproximativos Algoritmos Probabilisticos

Critério de Avaliação Prova 1 : 15 de Abril 25 pontos

Prova 2: 13 de Maio 25 pontos

Prova 3: 17 de Julho 25 pontos

Seminários : A partir do dia 23 de Junho 17 pontos

Exercicios : 8 pontos

Sobre o que é esta disciplina ? Problemas e Algoritmos. Algoritmo = solução de um problema Antes de projetar um algoritmo para um problema:

Analisar se o problema em questão tem solução Determinar a classe de complexidade do problema

Projetar um algoritmo Analisar o algoritmo projetado Propor outras soluções mais eficientes Implementar a solução mais eficiente

Panorama Geral

Problema P Analisar se P temsolução (algorítmica)

Sim Determinar a dificuldade inerente do problema P (classe de complexidadede P)

Projetar um Algoritmo A para resolver P

Analisarcomplexidade de A

(A compativelcom a classe de complexidade de P)

Projetar soluçõesmais eficientes

Implementar a solução mais eficiente

= disciplina “Teoria da Computação”

= disciplina “Análise de Algoritmos”= disciplinas de programação

“Problemas” e “Algoritmos” O que é um problema ?

Função P: Input Output Instância do Problema = I ϵ Input

Tipos de Problemas Decisão, Otimização, ...

Decisão: Output = Sim ou Não, Otimização: existe uma função objetivo a otimizar (minimizar ou

maximizar). Output = valor que otimiza a função objetivo.

Solúveis e Insolúveis ... Tratáveis e Intratáveis ...

PI ϵ Input P(I)

Exemplos de Problemas

Busca de um elemento x em uma lista L ordenada Busca: (Listas X elementos) {Sim, Não} Busca(L,x) = Sim se x está em L; Não, caso contrário. Exemplo de instância do problema: L = [1, 3, 5, 10, 17], x = 12

Problema dos PrimosPrimos: N {Sim, Não} Exemplo de instância = 5Primos(n) = Sim, se n é primo; Não, caso contrário

Exemplos de Problemas

Problema do Circuito HamiltonianoHamilton: Grafos Dirigidos {Sim, Não}Instância = grafo dirigido GHamilton(G) = Sim, se G possui um caminho passando por todos os vértices

uma única vez; = Não, caso contrário

Problema da parada em um número determinado de passos Parada : (Programas, Inputs) {Sim, Não}

Instância: (P,w) onde P = código de um programa , w = input de P

Parada (P,w) = sim se P executado em w pára após 2^n passos, onde n = comprimento de w Parada (P,w) = não, em caso contrário.

Problema de Correspondência de Post (PCP)Post: Dominós {Sim,Não}

Instância= um conjunto de tipos de peças de dominós

Post(D) = Sim, se existe um pareamento de peças de tipos em D

= Não, caso contrário.

O problema PCPO problema PCP

…abc b c dg

f g eg efe f

c d e b c db

1 2 3 4 n

Input = um conjunto finito de tipos de peças de dominós

Pergunta : É possivel encontrar um pareamento, isto é,uma sequência de peças de tipos dados no input, tal que o string formado na parte de cima e idêntico ao string formado na parte de baixo ?

b c db

e f c d e

gf g

b c d e f g

b c d e f g

Sequência : 3 n 1

a b c a a a b c

Exemplos Exemplos

a b cbc a

a a b c

c a a

1 2 3 4

a a b a a b

bc a

c a a

a b cc

Sequência de peças= 2 1 3 2 4

a b c a a a b c

Exemplo Exemplo

a c cb a

c a a

1 2 3

a b ca b

Input

Resposta ?? Não

Justificativa : a parte de cima das peças é sempre maior que a parte de baixo !

Formalização do Problema Formalização do Problema Input genérico do Problema PCP

C = { t1b1 ,

t2b2 ,

t3b3 , … ,

tnbn }

t1, t2, …, tn são strings sobre um alfabeto S

b1, b2, …, bn são strings sobre um alfabeto S

Um pareamento (match) = uma sequência <i1, i2, …, ik> de números em {1,…,n}

tal que ti1 ti2 … tik = bi1 bi2 … bik= string do pareamento

Pergunta : Existe um Pergunta : Existe um pareamento pareamento para o input C ?para o input C ?

Hierarquia dos problemas dos exemplos (ordenados dos mais fáceis para mais difíceis) Problema Solúvel ? Complexidade

do problema ?Busca Sim Polinomial

Primos Sim Até 2003: Sabia-se que não era NP-completoEm 2003: Polinomial

Parada Sim Exponencial

Hamilton Sim NP-completo

Post Não

“Problemas” e “Algoritmos” Solução de um Problema

Conjunto finito de instruções cuja execução sobre o input termina depois de um tempo finito, produzindo no final o output.

Solução de um problema = algoritmo

Algoritmo : conjunto finito de instruções que transformam uma entrada em uma saída depois de um tempo finito.

Todo Algoritmo está associado a um Problema

Algoritmo que resolve o problema

Perguntas

Conjunto dos Algoritmos Conjunto dos Problemas

???

Função injetora ??

Não é função injetora: podem existir diferentes algoritmos para resolver um mesmo problema

Não é função sobrejetora: Existem problemas que não têm solução

Panorama Geral

Problema P Analisar se P temsolução (algoritmica)

Sim Determinar a dificuldade inerente do problema P (classe de complexidadede P)

Projetar um Algoritmo A para resolver P

Analisarcomplexidade de A

(A compativelcom a classe de complexidade de P)

Projetar soluçõesmais eficientes

Implementar a solução mais eficiente

= disciplina “Teoria da Computação”

= disciplina “Análise de Algoritmos”= disciplinas de programação

Solução quando existe, não é única Problema da OrdenaçãoOrdena : SeqNat SeqNat Ordena(<a1,...,an>) = <b1,...,bn>Onde: <b1,...,bn> é uma permutação de <a1,...,an>

b1 ≤ b2 ≤ ... ≤ bnAlgoritmos que o resolvem:

Insertion-SortSelection-SortBubble-SortHeap-SortMerge-SortQuick-Sort Radix-SortBucket-Sort

Insertion-SortSelection-SortBubble-SortHeap-SortMerge-SortQuick-Sort

Radix-SortBucket-Sort

Eficiência emTempo cresce

Eficiência emEspaço cresce

O que é um bom algoritmo ? Correto ?

Para cada input I, o resultado produzido pelo algoritmo A(I) é exatamente o que se espera (A(I) = P(I))

Eficiente em tempo ? O número de passos executado pelo algoritmo para

produzir o resultado A(I) é uma função polinomial do tamanho do input I

Eficiente em espaço ? O número de células de memória utilizadas pelo algoritmo

para produzir o resultado A(I) é uma função polinomial do tamanho do input I

O que é um bom algoritmo ?

Correto Eficiente em tempo

Eficiente em espaço

Critérios são “ortogonais” !

Soluções Aproximadas às vezes são mais interessantes do que as exatas ... Problema do Vertex Cover (problema de otimização)

Achar o menor subconjunto de vértices S tal que cada aresta tem pelo menos uma de suas extremidades no conjunto S ? Problema de Minimização de recursos

• Encontrar a solução ótima é difícil• Problema NP-hard• Encontrar solução aproximada é factível Existem algoritmos que encontram soluções aproximadas em tempo polinomial

Para cada input G, o algoritmo dá uma solução com custo C(G) tal que:

C(G) ≥ α Opt(G)

Soluções Aproximadas nem sempre sãofacilmente encontráveis

Problema do Caixeiro Viajante (problema de otimização)

Achar o circuito hamiltoniano mais curto (passando por todasas cidades uma única vez) ?

Problema de Minimização de recursos

• Encontrar a solução ótima é difícil• Problema NP-hard• Encontrar solução aproximada não é factível !

d1

d2

d3

d4 d5

d6