EDA_IMPA

Prévia do material em texto

Estrutura de Dados 
e Algoritmos em C
Roberto de Beauclair Seixas
tron@impa.br
2
Porque usar computador ?
“É indigno de homens eminentes perder 
horas como escravos na tarefa desgastante 
de calcular. Esse trabalho bem poderia ser 
confiado a pessoas sem qualquer 
qualificação especial, se máquinas 
pudessem ser utilizadas.”
Gottfried Wilhelm Leibniz
3
Engenharia de Software
“Engenharia de software é a área 
interdisciplinar que engloba vertentes 
tecnológicas e gerencial visando a 
abordar, de modo sistemático, os 
processos de construção, implantação e 
manutenção de produtos de software com 
qualidade assegurada por construção, 
segundo cronogramas e custos 
previamente definidos.”
4
Engenharia de Software
Interdisciplinar baseada nos seguintes áreas:
z Ciência da Computação
z Sistemas e Modelos
z Avaliação de Complexidade de Problemas
z Álgebra Linear
z Cálculo
z Administração de Projetos
z Comunicação
5
Estrutura de Dados
z Em linguagens de programação o Tipo de Dado de uma 
variável define o conjunto de valores que a variável pode 
assumir.
z Tipo Abstrato de Dados é o Tipo de Dado em termos 
do que os usuários podem fazer e não ao computador.
z Estrutura de Dados é um método particular de se 
implementar um Tipo Abstrato de Dados.
z A implementação de um Tipo Abstrato de Dados
escolhe uma Estrutura de Dados para representá-lo. 
z Cada Estrutura de Dados é construída dos tipos básicos 
(int, real, char) ou dos tipos estruturados (array, record) 
de uma linguagem de programação. 
6
Abu Abd-Allah ibn Musa 
al'Khwarizmi
z Seu trabalho mais importante escrito 
em 830 nos dá a palavra álgebra. 
Æ classifica a solução de equações quadráticas 
e dá métodos geométricos para completar o quadrado. 
z Al'Khwarizmi também escreveu números Hindu-árabe. 
Æ Este texto de árabe está perdido mas uma tradução latina 
“Algoritmi de numero Indorum”, em inglês “Al-Khwarizmi on the
Hindu Art of Reckoning”, deu origem a palavra algoritmo que 
deriva do nome dele no título. 
z O primeiro uso do zero com lugar posicional na anotação 
básica provavelmente foi devida a al'Khwarizmi. 
7
z Dicionário Webster:
“Any special method of solving a certain kind of problem.”
Algoritmo
8
z Dicionário Webster:
“Any special method of solving a certain kind of problem.”
( parece coisa do McGuiver! )
Algoritmo
9
z Fundamentals of Computer Algorithms; 
E.Horowitz, S.Sahni; 1978:
“A precise method useable by a computer for the
solution of a problem.”
Algoritmo
10
z Fundamentals of Computer Algorithms; 
E.Horowitz, S.Sahni; 1978:
“A precise method useable by a computer for the
solution of a problem.”
Algoritmo
11
Linguagem C
Desenvolvida pelo Bell Lab no início dos anos 70, 
visando a implementação do UNIX. Possui um 
padrão feito por Kernighan e Ritchie em 1978.
Tem facilidades para a programação em “alto” e 
“baixo” níveis e gera código eficiente. 
Possui um grande conjunto de operadores, o que 
permite um código compacto, porém de baixa 
legibilidade. 
É excelente para construir programas portáveis. 
12
Oops!
#include <stdio.h>
main(){char *b=" .:-;!/>)|&IH%*#"; float
i,j,k,r,x,y=-16; while (puts(""),y++<15) 
for(x=0;x++<84; putchar(b[(int)k&15])) 
for(i=k=r=0; j=r*r-i*i-2+x/25, i=2*r*i+y/10, 
j*j+i*i<11&&k++<111; r=j);}
Motivação:
Presente
14
Engenharia de Software:
What the Hell is this?
z Engenheiros Civis fazem Plantas antes de 
construírem prédios;
z Engenheiros Eletrônicos fazem Esquemas antes 
de montarem aparelhos; 
z Engenheiros Mecânicos fazem Desenhos antes 
de produzirem máquinas; 
z Engenheiros de Software são superdotados pela 
Mãe Natureza, e não precisam de nada disso!
Æ “Se prédios fossem construídos da mesma forma que fazemos 
sistemas, o primeiro pica-pau que aparecesse no planeta destruiria
a humanidade” - Weinberg
15
A Engenharia de Software é 
uma área MUITO NOVA!
z O ser humano faz casas e abrigos há 
milhões de anos;
z O ser humano lida com eletricidade há 
milhares de anos;
z O ser humano produz máquinas e 
ferramentas há outros milhares de anos;
z O ser humano faz software há 40 anos.
Æ Estamos nos primórdios da computação...
16
Conclusão
“A formulação de um problema é 
freqüentemente mais essencial do que sua 
solução, a qual pode ser meramente uma 
questão de habilidade matemática ou 
experimental.”
Einstein e Infeld, 
“A Evolução da Física” - 1938
17
Aderência da Linguagem
Motivação:
Passado e Futuro(?)
19
Alan M. Turing 
(1912-1954)
z Computing Machinery and Intelligence. 
Mind, Vol. LIX. 433-460, 1950.
Æ Os computadores terão inteligência.
z Debate: Então, e agora ?
Æ Será uma relação simbiótica ?
(computador como uma ferramenta)
Æ Os computadores terão “consciência”?
20
53 anos depois
z Previsão de tecnologia de Turing foi fantástica! 
Æ Armazenamento de Gb de memória são comuns. 
z Previsão de inteligência foi otimista. 
Æ Vários locais da Internet oferecem “chatterbots” do Teste de Turing. 
Æ Ninguém passou (ainda) 
` http://www.loebner.net/Prizef/loebner-prize.html
z Os testes de Turing ainda se apresentam como desafios de 
longo prazo.
z Mas acredita-se que não demorará 
Æ menos de 50 anos, mais de 10 anos. 
21
Mas, houve progresso ...
z Computadores solucionaram alguns problemas: 
“Mapa de 4 cores”
Æ K. Appel and W. Haken, “The solution of the four-color-map problem,” 
Scientific American, Oct 1977, 108-121
e uma prova “manual” http://www.math.gatech.edu/~thomas/FC/fourcolor.html
(1995)
z Os computadores venceram o campeão mundial de xadrez
Æ com alguma ajuda dos programadores, mas … venceu!
z Os computadores estão presentes no dia-a-dia
z Ajudam a projetar e idealizar novas coisas
z Estas são relações simbióticas.
z Aprendizado e formação de conhecimento ainda são ilusórios.
22
Armadilha dos números
z Os seres humanos possuem 100 Tb de informação (1012) e podem 
processar 100 T ops.
Æ ROBOT, Hans Moravec, Oxford, 1998, page 58
z Então, um supercomputador “tem” um poder comparável.
z O Genoma humano tem 109 bits:
Æ 90% não possuem informação alguma (proteínas de ligação)
Æ 90% em comum com os chimpanzés 
Æ 90% comum entre os indivíduos
Æ Então, realmente só 106 bytes são relevantes (huh?!)
z Estamos perdendo algo ...
Æ Um excelente algoritmo de compressão ? 
Æ Uma melhor linguagem de programação ?
Æ Técnicas de aprendizado ?
23
Charles Babbage 
(1791-1871)
z Os objetivo de Babbage foram 
alcançados
Æ mas ainda precisamos de melhores algoritmos e máquinas 
mais rápidas.
z O que acontecerá quando:
Æ A capacidade de processamento for infinita ? 
Æ A capacidade de armazenamento for infinita ?
z Limites remanescentes:
Æ Conteúdo: A capacidade de informação do Cyberspace
Æ Software: Bugs, >100$ por linha de código (!)
Æ Processamento: > 1,000 $/cpu/ano
24
Benefícios
z Hoje os computadores podem:
Æ Ler para os cegos (OCR & Texto → Fala)
Æ Ouvir para os surdos (Fala → Texto)
Æ Escrever para os deficientes (Fala → Texto)
z Logo:
Æ Substituir deficiências: 
` melhor memória, melhor visão, …
Æ Novas formas de comunicação 
` Tradução automática de telefonemas
Æ Revolucionar a interface homem-computador
25
Vannevar Bush 
(1890-1974)
z “As We May Think” The Atlantic Monthly, 1945
http://www.theatlantic.com/unbound/flashbks/computer/bushf.htm
z Memex
Æ Todo conhecimento humano 
… “a billion books” hyper-linked together ...
Æ Registrando tudo o que se vê
` filmes e fotos 
` ... “a machine which types when talked to” ...
Æ Navigate by
` … text search following links associations ...
z Conexões diretas ao sistema nervoso ?
26
Memex Individual
Memex: “Lembrar o que é visto e ouvido e rapidamente 
devolver qualquer informação solicitada”
27
Quanto de Informação Existe 
?
z Logo, tudo poderá ser gravado e 
catalogado.
z A maioria da informação nunca será 
vista.
z Fundamentos tecnológicos:
Æ Atenção humana
Æ “Sumarização” automática
Æ Busca automática
http://www.lesk.com/mlesk/ksg97/ksg.html
28
Resumo
z Pense seriamente sobre Algoritmosz Qual o melhor algoritmo para um problema? 
→ “aderência”
z Oito paradigmas para projetar um bom algoritmo:
1. reduzir a um problema conhecido (ex: ordenação); 
2. recursão; 
3. criar ou expandir uma estrutura de dados; 
4. dividir e conquistar; 
5. guloso; 
6. programação dinâmica; 
7. probabilidade; 
8. aproximação.
29
Cuidado com os efeitos 
colaterais!
30
Estruturas de Dados 
e Algoritmos em C
z Proposta de Curso – Nível Iniciação Científica
Æ A finalidade deste curso é ensinar ao aluno as técnicas básicas 
de estruturação de dados em linguagens convencionais e 
capacitá-lo a empregar essas técnicas, na construção de 
pequenos programas.
z Descrição do Curso
Æ Familiarizar os alunos com a linguagem de programação C, 
enfocando os elementos essenciais para a construção de 
programas confiáveis, seguros, corretos, eficientes e baratos. 
Para tanto, as estruturas de dados básicas serão estudadas e 
implementadas em C, bem como algoritmos para manipulá-las.
31
Ementa
z Linguagem C
Æ Conceitos fundamentais
Æ Expressões
Æ Controle de fluxo
Æ Funções
z Estruturas de dados básicas
Æ Vetores
Æ Matrizes
Æ Cadeia de caracteres
Æ Tipos estruturados
z Estruturas de dados dinâmicas
Æ Alocação dinâmica
Æ Listas encadeadas
Æ Pilhas
Æ Filas
Æ Árvores
z Ordenação e busca
Æ Arquivos
Æ Ordenação
Æ Busca 
Æ Hashing
z Aplicações
Æ Grafos e árvores
Æ Buscas
Æ Árvore geradora mínima
Æ Caminho mínimo
Æ Redes de fluxo
32
Problema Algorítmico
z Problema
E ⇒ conjunto das possíveis entradas
S ⇒ conjunto das saídas desejadas
R(E,S) ⇒ relação entre entradas e saídas desejadas
O ⇒ operações válidas
z Solução
A ⇒ algoritmo correto
e sA
∀e ∈ E (e,s) ∈ R(E,S)
33
Solução de Problemas
modelo matemático
algoritmo informal
modelo matemático
algoritmo informal
tipo abstrato de dados
pseudo código
tipo abstrato de dados
pseudo código
estrutura de dados
programa
estrutura de dados
programa
código de máquinacódigo de máquina
...
34
Algoritmos e 
Complexidade
z Problema, Instância e Algoritmo.
z Dado um problema:
Æ Como encontrar um algoritmo eficiente para 
solucioná-lo ?
Æ Uma vez encontrado, como compará-lo a outros 
algoritmos que também resolvem o problema ?
Æ Como determinar se o algoritmo está correto ?
Æ Como determinar se o algoritmo é eficiente ?
35
Algoritmo
Conjunto finito de instruções, composta de uma ou 
mais operações válidas, com o objetivo de 
resolver um problema específico.
z Operações válidas
Æ definidas 5 ÷ 0
Æ efetivas √ π
z Término em tempo finito (procedimento computacional)
z Entrada (opcional)
z Saída (uma ou mais)
36
Alguns Exemplos Iniciais
Para qualquer algoritmo, temos que provar que ele sempre 
retornará o resultado desejado para todas as instâncias 
possíveis do problema.
⌦ Correção (Correctness)
⌦ Eficiência
37
Critérios de Análise
z Eficácia
Æ Correção
z Eficiência
Æ Tempo
Æ Espaço
Æ Simplicidade / Clareza
Æ Otimalidade
z Limitações
Æ Computabilidade
Æ Tratabilidade
z Parcialmente Correto
Æ entrada válida → saída 
desejada
Æ pode ser tempo infinito
z Totalmente Correto
Æ tempo finito
Æ saída desejada
especificação
requisitos
código
verificação NÃO
erros
problema
algoritmo
SIM
solução
38
Correção não é óbvio!
⌦ Você recebeu a tarefa de programa um braço de robô de 
soldagem. 
⌦ O robô deve soldar (visitar) o primeiro ponto de solda, 
depois o segundo, terceiro e assim por diante.
⌦ Determine um algoritmo para achar o melhor caminho. 
39
Vizinho Mais Próximo
⌦ Inicie em algum ponto p0 e então vá para o ponto mais 
próximo p1. Repita o processo a partir de p1, etc. até que 
todos os pontos sejam visitados.
Escolha e visite um ponto inicial p0
p = p0; i = 0;
enquanto existirem pontos não visitados
i = i + 1
escolha e visite o ponto pi, mais próximo de pi-1
retorne ao ponto inicial
⌦ Este algoritmo é simples de entender, simples de 
entender e muito eficiente. Está correto ?
40
Vizinho Mais Próximo
⌦Algoritmo não é correto!
⌦Escolher sempre o ponto mais próximo é muito 
restritivo, pois pode nos levar a fazer movimentos 
desnecessários.
41
Par Mais Próximo
⌦ Conectar ao par mais próximo de pontos cuja conexão 
não irá causar um ciclo ou bifurcações, até se formar 
uma única cadeia de pontos com todos os pontos.
faça n ser o número de pontos do conjunto e d = ∞
para i = 1 até n - 1 faça
para cada par de pontos (x,y) de caminhos parciais
if (dist(x,y) <= d) então 
xm = x; ym = y; d = dist(x,y);
conecte (xm, ym) por uma aresta
conecte os dois pontos por uma aresta
⌦ Este algoritmo está correto para o contra-exemplo 
anterior. Então agora estará correto ?
42
Par Mais Próximo
⌦Algoritmo não é correto! 
⌦Existe algoritmo correto ?!
43
Um algoritmo correto
z Podemos tentar todas as ordenações de pontos 
possíveis e então selecionar a ordenação que 
minimiza o comprimento total.
z Uma vez que todas as possíveis ordenações são 
consideradas, podemos garantir que teremos o melhor 
caminho possível.
z Mas, isso significa testar n! permutações, que é 
extremamente lento. Tão lento que é inviável quanto 
se tem mais de 10 ou 20 pontos.
z Conclusão: Não existe um algoritmo correto eficiente!
� Traveling Salesman Problem�
44
Eficiência
“Porque (simplesmente) não usar um supercomputador?”
z Supercomputadores são para pessoas muito ricas e 
muito estúpidas para escrever algoritmos eficientes! 
(S.Skiena)
z Um algoritmo rápido rodando em um computador lento 
irá sempre ganhar de um supercomputador com um 
algoritmo ruim para instâncias suficientemente grandes.
z Normalmente, os problemas não chegam a ficar tão 
grandes antes do algoritmo rápido ganhar.
45
Problema: Ponto em Polígono
Dado em polígono plano simples, ou seja, os 
lados não se cruzam, P e um ponto p do 
plano, decidir se p é interior ou não ao 
polígono P.
P
•p
46
Complexidade Assintótica
z Existe algum algoritmo que resolve o problema?
Æ Isso requer que o algoritmo pare após um número finito de 
passos para qualquer instância do problema.
z Dado um certo algoritmo A, quão eficiente é este 
algoritmo? Dado dois algoritmos A e B, qual deles é 
superior?
z Dentre todos os algoritmos que resolvem o problema, qual 
deles é melhor?
z Medir a complexidade (ou eficiência) de um algoritmo pelo 
tempo necessário à sua execução em função do tamanho 
da instância. (Complexidade Assintótica O(f (n)))
47
Análise de Algoritmos
z Recursos Computacionais
Æ Tempo de execução e quantidade de memória
z Implementação do Algoritmo
Æ Linguagem e arquitetura
z Tamanho da entrada (N)
Æ Número de elementos ou número de nós da expressão
z Complexidade (tempo) de Pior Caso
Æ T(N): Maior tempo de execução do algoritmo com todos os 
problemas possíveis de tamanho N.
Æ T(N) é proporcional ao número total de instruções t (N) 
executadas para o pior caso de tamanho N⇒ T(N) = c t (N)
48
Definição 1
Um algoritmo A para resolver P tem 
complexidade O(f (n)) se existe uma 
constante k > 0 e um natural N tais que, 
para qualquer instância de P de tamanho n
> N, o número de passos de A necessários 
para resolver esta instância é, no máximo, k 
f (n).
ex. 1000 n2 “ambiente computacional”` “natureza do método”
49
Ordens de Magnitude
x ← x + y
1
for i ← 1 to n
begin
x ← x + y
end
n
for i ← 1 to n
begin
for j ← 1 to n
begin
x ← x + y
end
end
n2
50
Complexidade
z Se um algoritmo processa problemas de tamanho 
n em tempo cn2 para alguma constante c, então 
dizemos que a complexidade (time complexity) do 
algoritmo é O(n2), lendo-se “ordem n2”.
algoritmo complexidade 1 s 1 m 1 h
A1 n 1000 6x104 3.6x106
A2 n log n 140 4893 2.0x105
A3 n2 31 244 1897
A4 n3 10 39 153
A5 2n 9 15 21
51
Tempo de Execução
20 50 100 200 500 1000
1000 n 0.02 s 0.05 s 0.1 s 0.2 s 0.5 s 1 s
1000 n log n 0.09 s 0.3 s 0.6 s 1.5 s 4.5 s 10 s
100 n2 0.04 s 0.25 s 1 s 4 s 25 s 2 m
10 n3 0.02 s 1 s 10 s 1 m 21 n 2.7 h
nlog n 0.4 s 1.1 h 220 d 125 s 5E8 s -
2n 1 s 35 a 3E4 s
Tamanho
ComplexidadeObs.: Supondo que 1 operação leva 1 µs.
52
Curiosidades
z Explosão Combinatorial
Æ 100! → número com 158 dígitos
Æ 120! → número com 200 dígitos
Æ número de prótons no universo → 126 dígitos
Æ número de µ segundos desde o Big-Bang→ 24 dígitos
z Impacto da Evolução Tecnológica
algoritmo atuais 100 x 1000 x
n N1 100 N1 1000 N1
n2 N2 10 N2 31.6 N2
n3 N3 4.64 N3 10 N3
2n N4 N4 + 6.64 N4 + 9.97
53
z Dada a função f abaixo, calcule o seu valor 
para x = 40545 e y = 70226.
f (x,y) = 9 x4 - y4 + 2 y2
dígitos: 3 7 11 15 19 21
1010 -10-13 1.3 107 82152 2
Oops! O valor correto é 1
Outra Curiosidade (sic!)
54
Outra Curiosidade (sic!)
z Dada a função f abaixo, calcule o seu valor para:
x = 77617 y = 33096.
f (x,y) = 333.75 y6 + x2 (11 x2 y2 - y6 - 121 y4 - 2) + 5.5 y8 + x/2y
Precisão simples: 1.172603…
Precisão dupla: 1.1726039400531…
Precisão extendida: 1.172603940053178… 
Oops! O valor correto é -0.8273960599… ( - 54767 / 66192 )
55
Moral da História
“Computers do not solve problems,
People do!”
E.R.Davidson