01_Apresentacao do Curso e Introducao

Prévia do material em texto

1
Estrutura de Dados e 
Algoritmos
1
Apresentação do Curso e Introdução
Prof. Cláudio Campelo, PhD
Departamento de Sistemas & Computação / UFCG
Apresentação do curso
� Créditos: 4
� Carga-horária: 60h
� Pré-requisitos: Programação II, Laboratório de 
Programação II, Teoria dos Grafos
� Dependências: OAC, LOAC, PLP, ATAL
� Linhas gerais: estudo preliminar sobre algoritmos e 
avançado sobre estruturas de dados.
� Página do professor: 
www.claudiocampelo.com
2
2
Apresentação do curso
3
� Página do curso de EDA: 
https://sites.google.com/a/computacao.ufcg.edu.br/e
daufcg
� Página do curso de LEDA: 
https://sites.google.com/a/computacao.ufcg.edu.br/le
daufcg/
� Para cada disciplina existe um grupo associado
(acessível através da página da disciplina)
� Solicitem para serem adicionados nos grupos
URGENTE!
Dicas para a Disciplina (EDA)
4
� Acompanhar os avisos no grupo da disciplina e 
acompanhar o site da disciplina
constantemente.
� Não deixar o assunto acumular.
� Fazer os exercícios recomendados.
� Estudar também pelas referências.
� Fazer uso da monitoria (aulas e horários de 
atendimento aos alunos).
� Revisar a matemática necessária.
� Evitar fazer reposições.
� Conversar com a turma anterior.
3
Dicas para a Disciplina (LEDA)
5
� Acompanhar os avisos no grupo da disciplina e 
acompanhar o site da disciplina constantemente.
� Não deixar o assunto acumular.
� Fazer os exercícios recomendados.
� Estudar também pelas referências.
� Fazer uso da monitoria (aulas e horários de 
atendimento aos alunos).
� Revisar a matemática necessária.
� Evitar fazer reposições.
� Conversar com a turma anterior.
� Crie suas implementações! Não as pegue pronta
com alguém do semestre anterior.
Avaliação (informação no site)
6
� EDA
� 3 provas teóricas
� LEDA
� 3 provas práticas
� 16 roteiros
� Bonificação na média (critérios a definir)
� Nota combinada
4
Iniciando a conversa…
7
� O que é um algoritmo?
� Como podemos descrever algoritmos?
� Como devemos avaliar algoritmos?
� O que é análise de algoritmos?
O que é um algoritmo?
8
� Procedimento que recebe valores a serem
manipulados (entradas) e produz algum valor 
(ou valores) como saída.
� Uma sequência finita de passos/instruções que
transformam um conjunto de valores em uma
dada situação inicial em uma situação final
que satisfaz condições específicas.
5
Exemplos de Algoritmos
9
� Receita de bolo
� Descrição de como trocar o pneu de um carro
� Algoritmo para resolver equações quadráticas
� Algoritmo para calcular o MDC, MMC, raiz quadrada
� Métodos ensinados a crianças para somar, subtrair, 
multiplicar e dividir inteiros
� …
Programas x Algoritmos
10
� Algoritmo
� Idéia usada para computar alguma coisa
� Expresso em diversas linguagens naturais
� Programa
� Texto que descreve um sistema computacional
� Expresso em notações projetadas para computadores
6
Escrita de Algoritmos
11
� Linguagem natural?
� Linguagem de Programação (código) ?
� Pseudo-código?
Linguagem
Humana Código
pseudo-código
Exemplo
12
� Faça um programa que calcula as médias
acumuladas de um vetor V com n inteiros. A média
deve ser armazenada em um vetor M de n reais.
7
Exemplo
13
double[] calculaMedia(int[] v){
1: for i = 1..n 
2: soma = 0
3: for j = 1..i 
4: soma = soma + V[j]
5: M[i] = soma/i
6: return M
}
Como avaliar o algoritmo?
Critérios de avaliação
14
� Corretude
� Se para toda entrada especficada a saída correta é 
produzida
� Simplicidade
� Facilmente entendido, implementado e mantido
� Eficiência
� Inversa da quantidade de recursos requeridos para seu
funcionamento
8
De volta ao Exemplo
15
double [1..n] calculaMedia(int V[1..n]){
1: for i = 1..n 
2: soma = 0
3: for j = 1..i 
4: soma = soma + V[j]
5: M[i] = soma/i
6: return M
}
É correto? É simples? É eficiente?
Corretude
16
� Garantir que em qualquer possível execução, cada
bloco faz exatamente o que esperamos que faça
� Ações relacionadas a corretude:
� Identificar o que deve ser feito por cada bloco
� Identificar o estado antes do bloco executar
� Avaliar o efeito do bloco sobre o estado
� Caracterizar o estado após a execução do bloco
� Provar corretude de algoritmos não é fácil !
9
Simplicidade
17
� Você teria dificuldade em implementá-lo?
� Você teria dificuldades em encontrar erros em uma
implementação de outra pessoa?
Eficiência
18
� Não basta dizer apenas se é eficiente mas quão
eficiente!
� Como algoritmo é idéia, como avaliar os recursos
que uma idéia consome?
� Abstrair detalhes de implementação.
� Refletir apenas o que é intrínseco de cada algoritmo.
� Comparação com algoritmos que resolvem o mesmo
problema ajudam muito na prática.
10
Eficiência
19
� A eficiência de um algoritmo é relevante?
Eficiência
20
� Por que estudar eficiência?
� Os algoritmos ajudam a estudar a escalabilidade
� A eficiência geralmente descreve a linha entre:
� Tratável, intratável, insolúvel
� É a “moeda” da computação
� Qual é o melhor algoritmo para a solução de um 
problema?
Complexidade x Eficiência
11
Eficiência
21
� Método experimental
� várias implementações completas 
� um grande número de execuções controladas 
� medição cautelosa das variáveis de interesse 
� análise (estatística) dos resultados 
� Método analítico
� idéia: construir um modelo matemático do algoritmo. 
� comparar algoritmos com base nos modelos 
Abordagem Experimental
22
� Executar os dois algoritmos
� Medir o tempo
public static int arrayMax(int[] A) { .. }
long antes = System.nanoTime();
int x = arrayMax(new int [] {4,5,6,1});
long depois = System.nanoTime();
long tempo = depois – antes;
12
Abordagem Experimental 
23
1
1
1
1
1
11111111
t (ms)
n
Algoritmo
Tamanho 
da entrada
+- 50 
medições
Quais fatores 
influenciam?
Quais fatores 
influenciam?
24
13
Abordagem Experimental
25
� Fatores que influenciam
� Tamanho da entrada (n)
� Hardware
� Processador
� Memória
� Software
� Sistema Operacional
� Linguagem de Programação
� Compilador
C/C++
Abordagem Experimental
26
� Limitações:
� Os experimentos são realizados em um número 
limitado de testes.
� Os dados podem não indicar a tendência dos valores 
não testados
� Os dois algoritmos devem ser testados no mesmo 
ambiente (hardware e software)
� Para analisar o tempo de execução, precisamos 
executar o algoritmo
14
Qual o desafio 
para comparar 
algoritmos sem 
executá-los?
Qual o desafio 
para comparar 
algoritmos sem 
executá-los?
27
Propor uma metodologia
para analisar o tempo de 
execução dos algoritmos
Propor uma metodologia
para analisar o tempo de 
execução dos algoritmos
28
15
Objetivos
29
� Considerar todas as entradas
� Abstrair detalhes: analisar algoritmos 
independentemente de hardware e software
� Análise feita em alto nível (pseudo-código)
� Avaliar sem precisar rodar experimentos
public boolean XYZ(int n, …) { 
…
…
}
f(n)
Algoritmos
MatemáticaAnálises
Considerações
30
� O tempo de execução de cada operação primitiva
depende do hardware e software, mas de todo modo 
é constante
� Hipótese
O tempo de cada operação 
primitiva é praticamente o mesmo
16
Operações Primitivas
31
� Atribuição: a = x
� Operação aritmética: a+1
� Comparação de números: a>b
� Indexar array: a[i]
� Retorno de método: return x;
Custo unitário: custo(primitiva) = 1
Custo constante: custo(primitiva) = c
ou
Custo das Operações
32
� Instruções Consecutivas
� If then else
Cmd1;
Cmd2; custo(Cmd1) + custo(Cmd2)
if (teste) {
...// CustoIf
} else {
... // CustoElse
}
custo(teste) + 
max[custo(if),custo(else)]
17
Custo de outras Operações
33
� Laço
� Aninhamento de Laços
� tempo do laço interno x tempo do laço externo
� Recursão
� Mais complexo
� Veremos dois métodos (iterativo e mestre)
for (...) {
... // CustoFor
}
n * custoFor
Número de Iterações
Exercício 1
34
� Quais as primitivas do algoritmo a seguir?
public int max(int x, int y) {
if (x > y)
return x;
else return y;
}
18
Exercício 1
35
� Quais as primitivas do algoritmo a seguir?
public int max(int x, int y) {
if (x > y)
return x;
else return y;
}
Exercício 2
36
� Quais as primitivas do algoritmo a seguir?
long potencia(int n) { 
long r = 1;
for (int i=1; i<=n; i++) 
r=2*r;
return r;
}
19
Exercício 2
37
� Quais as primitivas do algoritmo a seguir?
long potencia(int n) { 
long r = 1;
for (int i=1; i<=n; i++) 
r =2*r;
return r;
}
Exercício 2
38
� Quais as primitivas do algoritmo a seguir?
long potencia(int n) { 
long r = 1;
for (int i=1; i<=n; i++) 
r=2*r;
return r;
}
custo (
)
20
Exercício 2
39
� Quais as primitivas do algoritmo a seguir?
long potencia(int n) { 
long r = 1;
for (int i=1; i<=n; i++) 
r=2*r;
return r;
}
)
custo (
Exercício 2
40
� Quais as primitivas do algoritmo a seguir?
long potencia(int n) { 
long r = 1;
for (int i=1; i<=n; i++) 
r=2*r;
return r;
}
)
custo ( ) +
custo (
) +
custo (
21
Exercício 2
41
� Quais as primitivas do algoritmo a seguir?
long potencia(int n) { 
for (int i=1; i<=n; i++) 
r=2*r;
return r;
}
)
c1 +
custo (
) +
custo (
Exercício 2
42
� Quais as primitivas do algoritmo a seguir?
long potencia(int n) { 
for (int i=1; i<=n; i++) +
r=2*r;
return r;
}
)
c1 +
n*custo ( ) +
custo (
22
Exercício 2
43
� Quais as primitivas do algoritmo a seguir?
long potencia(int n) { 
for ( c1 ; i<=n; i++) +
r=2*r;
return r;
}
)
c1 +
n*custo ( ) +
custo (
Exercício 2
44
� Quais as primitivas do algoritmo a seguir?
long potencia(int n) { 
for ( c1 ; c2*(n+1); i++) +
r=2*r;
return r;
}
)
c1 +
n*custo ( ) +
custo (
23
Exercício 2
45
� Quais as primitivas do algoritmo a seguir?
long potencia(int n) { 
for ( c1 ; c2*(n+1); c3*(n)) +
r=2*r;
return r;
}
)
c1 +
n*custo ( ) +
custo (
Exercício 2
46
� Quais as primitivas do algoritmo a seguir?
long potencia(int n) { 
c1 + c2*(n+1) + c3*(n) +
r=2*r;
return r;
}
)
c1 +
n*custo ( ) +
custo (
24
Exercício 2
47
� Quais as primitivas do algoritmo a seguir?
long potencia(int n) { 
c1 + c2*(n+1) + c3*(n)
+
return r;
}
)
c1 +
n*c4 +
custo (
Exercício 2
48
� Quais as primitivas do algoritmo a seguir?
long potencia(int n) { 
c1 + c2*(n+1) + c3*(n)
+
}
c1 +
n*c4 +
c5
25
Exercício 2
49
� Quais as primitivas do algoritmo a seguir?
long potencia(int n) { 
c1 + c2*(n+1) + c3*n +
}
c1 +
n*c4 +
c5
custo = 2*c1 + c2*(n+1) + c3*n + n*c4 + c5
Tipos de Análises
50
0
1
2
3
4
5
6
1 2 3 4 5 6 7
tamanho da entrada
te
m
po
 
de
 
ex
ec
u
çã
o 
(m
s)
Pior caso
Melhor casoTempo médio
26
Melhor, Pior e Caso Médio
51
� Pior Caso 
� Mais comum
� T(n) = tempo máximo para um algoritmo com qualquer entrada de 
tamanho n
� Fácil de calcular (sem probabilidade)
� Caso Médio
� T(n) = tempo esperado sobre todas as entradas de tamanho n
� Precisa de uma hipótese da distribuição estatística das entradas
� Melhor Caso
� Não acrescenta muita informação
� Raramente ocorre na prática
� Logo, não é uma boa medida
Exercício 4
52
� Qual a expressão 
do tempo de 
execução de cada 
algoritmo?
boolean primo(int n) { 
if (n==2) return true;
for (int i=2; i<n; i++) 
if (n%i==0) 
return false; 
return true;
}boolean primo(int n) { if (n==2) return true; 
for (int i=2; i<=n/2; i++) 
if (n%i==0) 
return false; 
return true;
}
27
Complexidade x Hardware
53
Supercomputador
109 instruções/seg
2n2
Computador
107 instruções/seg
50nlog10(n) Algoritmo de Ordenação
Análise
54
� Quem ordenará mais rápido com n=106?
50.106.log10106/107 ≈ 30 segundos
2.1012/109 = 2000 segundos10
9 instr/s
2n2
107 instr/s
50nlog10(n)
28
Análise
55
É importante não só ter uma 
máquina boa, mas também um 
algoritmo (tecnologia) eficiente!
É importante não só ter uma 
máquina boa, mas também um 
algoritmo (tecnologia) eficiente!
56