aula1-intro

Prévia do material em texto

Algoritmos e Estruturas de Dados I
Introdução
Curso de Engenharia de Computação
CEFET-MG
2013/2
Cristina Duarte Murta
 Tópicos da aula
 Conceitos
 Algoritmo, Estrutura de dados, Programa
 Problema
 Limites da computação
 Computabilidade 
 Complexidade de algoritmos
 Introdução à Análise de Complexidade de Algoritmos
Algoritmos e Estruturas de dados
 Algoritmo
 Seqüência de ações executáveis para a obtenção de uma solução para 
um determinado tipo de problema
 Exemplos: receitas médicas, receitas culinárias, procedimentos para 
montagem de um equipamento
 Estrutura de dados 
 representação de um conjunto de dados (abstração)
 Algoritmos + estruturas de dados = programas 
 Nome de um livro do cientista N. Wirth
 
Definições de algoritmo dadas por especialistas
 Aho, Hopcroft, Ullman
 algoritmo é uma seqüência finita de instruções, cada uma com um significado claro, 
que pode ser desempenhada com uma quantidade finita de esforço em um tempo 
finito 
 Knuth
 um algoritmo é um conjunto finito de regras que forma uma seqüência de operações 
para resolver um determinado problema e tem quatro características importantes:
 finitude: sempre termina após um número finito de passos
 definição: cada passo é definido precisamente, de forma rigorosa e sem ambigüidade
 entrada: um algoritmo tem 0 ou mais entradas, tomadas de um conjunto específico de 
objetos
 saída: um algoritmo tem uma ou mais saídas
 Cormen, Leiserson, Rivest
 seqüência de passos computacionais que transformam uma entrada em uma saída
 conceito de função matemática
Algoritmos e Estruturas de Dados
PROBLEMA!
Pensando 
uma solução
ALGORITMO
ESTRUTURA
DE DADOS
PROGRAMAPROGRAMA
 
Diferença entre Algoritmo e Problema
 Problema
 especificação de uma relação entre uma entrada e uma saída; especifica 
o que fazer.
 Algoritmo: solução para um problema
 um procedimento computacional bem definido que toma a entrada e 
produz um conjunto de valores como saída; especifica como fazer. 
 Algoritmos são utilizados para resolver problemas. 
Programas
 programas são implementações de algoritmos e 
estrutura de dados
 programar é projetar a estrutura de dados e construir 
algoritmos
 os computadores só entendem programas em 
linguagem de máquina
 uma linguagem de programação é uma notação para 
expressão de programas, com dois objetivos:
 é um meio para o programador expressar o raciocínio 
algorítmico
 compiladores traduzem o algoritmo para a linguagem de 
máquina 
ALGORITMO
ESTRUTURA
DE DADOS
PROGRAMAPROGRAMA
Algoritmos e Estruturas de dados
 Algoritmos + estruturas de dados = programas
 Há interdependência entre os algoritmos e as estruturas de dados
 Estruturas de dados e algoritmos são partes essenciais de um 
programa
 a escolha da estrutura de dados limita ou define os algoritmos 
associados a elas
 a escolha dos algoritmos depende de como os dados estão 
representados, i.é, da estrutura dos dados
 
Formalização do conceito de algoritmo
 A definição formal de procedimento computacional é feita através de uma 
formalismo matemático denominado Máquina de Turing (MT)
 MT: é um modelo de computação abstrato
• MT são aceitas como formalização do conceito de algoritmos
• há vários formalismos equivalentes
 Sistemas de Post, algoritmos de Markov, lambda calculus, etc. 
 Tese de Church-Turing 
• nada será considerado algoritmo se não puder ser apresentado por uma 
máquina de Turing
• todos os problemas que podem ser resolvidos por qualquer modelo de 
computação podem ser expressos por uma máquina de Turing
 Todas as formalizações apresentadas até hoje para o conceito de algoritmo 
foram transcritas para uma MT
 
Máquina de Turing: 
o computador é uma máquina que processa sequências de bits
 
 Computação e Algoritmos
 
• Estudo dos algoritmos e suas implementações
– Propriedades matemáticas e formais: estudo do comportamento dos 
algoritmos para determinar sua correção e eficiência
– Implementações em hardware: projeto e construção de sistemas de 
computação que executam algoritmos => foco importante da Engenharia 
de Computação
– Implementações lingüísticas: projeto de linguagens de programação e 
algoritmos de tradução destas linguagens de modo que possam ser 
executadas pelo hardware
– Aplicações: identificação de problemas importantes e escrita de software 
correto e eficiente para resolvê-los 
Em computação, tudo é algoritmo!
Computabilidade e complexidade
 Áreas de estudo de algoritmos
 COMPUTABILIDADE
 se existe uma solução algorítmica para um problema
 se o problema é computável
 ou decidível ou recursivo (notação matemática)
 COMPLEXIDADE
 qual é a complexidade da solução
 quão difícil é resolver o problema
 qual é o custo da solução
Computabilidade e complexidade
 Questões
 é possível projetar um algoritmo para resolver um problema?
 é possível projetar um algoritmo eficiente para resolver um problema?
 é possível afirmar que um determinado algoritmo é o melhor possível 
para resolver um determinado problema?
Computabilidade
 Dois conjuntos de problemas
 computáveis: para os quais existe uma solução algorítmica
 um problema matemático é computável se pode ser resolvido por um 
computador, isto é, se podemos expressar sua solução na forma 
algorítmica
 sinônimos: solucionável, decidível, recursivo
 não computáveis: problemas que não podem ser resolvidos 
algoritmicamente
 Indecidíveis: problemas de decisão
 A teoria da computabilidade prova que há inúmeros problemas não 
computáveis (indecidíveis)
 A teoria não ajuda a especificar quais são estes problemas
Computabilidade
 Um problema indecidível – não computável
 Problema da parada (the halting problem)
 Entrada: um programa P e uma entrada de dados w
 Saída: decidir se o programa P será finalizado para a entrada w
 P pode entrar em loop infinito e nunca parar!
 O problema da parada é indecidível
 Não é possível escrever um algoritmo que resolve o problema da parada
Algoritmo para o 
problema da parada
Entradas: P,w Saída: sim/não
Computabilidade
 Um problema indecidível – não computável
 Problema da parada (the halting problem)
 Entrada: um programa P e uma entrada de dados w
 Saída: decidir se o programa P será finalizado para a entrada w
 P pode entrar em loop infinito e nunca parar!
 O problema da parada é indecidível
 Não é possível escrever um algoritmo que resolve o problema da parada
Algoritmo para o 
problema da parada
Entradas: P,w Saída: sim/não
 
Áreas de estudo dos algoritmos
• Computabilidade
 trata da existência ou não de algoritmos para resolver determinados 
problemas
• Teoria de algoritmos
 trata da existência ou não de algoritmos eficientes para resolver 
determinados problemas
• Projeto de algoritmos
 trata do estudo das técnicas de projeto que geralmente produzem 
algoritmos efetivos para classes de problemas
• Análise de algoritmos – análise de complexidade
 dado um algoritmo, determinar suas características de desempenho, isto 
é, determinar seu comportamento frente às entradas possíveis
 
Algoritmos na prática 
 um algoritmo útil deve requerer não apenas um número finito de 
passos, mas um número finito e razoavelmente pequeno de 
passos. 
 Há algoritmos que podem demorar milênios para serem 
executados
 veremos a seguir...
 
Características desejáveis nos algoritmos
 correção
 o algoritmo para com a saída correta para qualquer instância válida da 
entrada
 prova de correção: verificação formal
 eficiência
 o algoritmo deve fazer uso eficiente dos recursoscomputacionais
 elegância
 código correto, eficiente, simples, claro, fácil de implementar
 robustez
 provê respostas para qualquer entrada de dados
 generalidade
 adaptabilidade do algoritmo a diversos tipos de dados e sistemas
Complexidade computacional
 Para os problemas computáveis
 Precisamos conhecer sua complexidade
 Quanto custa uma determinada solução?
 Qual é a melhor solução possível?
 Qualquer solução inclui obrigatoriamente o custo inerente ao 
problema
 Complexidade de algoritmos
 Recursos gastos para resolver um problema computacional
 Todo tipo de recurso
 Principais: tempo de CPU e espaço em memória 
 
Análise de Complexidade de Algoritmos
 Análise de complexidade
 parte da computação que avalia a eficiência (o custo) dos 
algoritmos em termos de 
 tempo de execução - uso de CPU
 espaço ocupado - uso de memória
 estuda o comportamento dos algoritmos frente às entradas que ele 
pode receber
 o custo dos algoritmos depende do tamanho da entrada de dados
 
Análise de Complexidade de Algoritmos
 Porque é importante
 para auxiliar o projeto e a implementação dos programas
 para melhorar a eficiência dos programas
 programas com entradas de dados muito grandes
 programas executados milhares ou milhões de vezes
 para avaliar o tempo de execução dos algoritmos
 para comparar diversos algoritmos que resolvem o mesmo 
problema
 porque nos diz qual é o maior problema que pode ser resolvido 
por um ou mais computadores!
 
Análise de Complexidade de Algoritmos
Três perspectivas da análise de complexidade:
• Análise de um algoritmo particular
– Quanto custa a execução de um dado algoritmo?
• Análise de uma classe de algoritmos
– Dada uma coleção de algoritmos que resolvem um mesmo problema, qual 
é o melhor algoritmo do conjunto?
• Análise de um problema
– Qual é o menor custo possível para resolver um dado problema?
– Quais são os limites mínimos de tempo e espaço necessários para 
resolver um problema computável? O custo inerente ao problema...
 
Análise de complexidade de algoritmos
 Quanto a
 tempo de execução 
 uso de CPU: 
 medida do número de operações que um programa executa
 espaço ocupado 
 uso de memória: 
 medida do espaço ocupado durante a execução do programa
 Custos de tempo e de espaço são dados em função do tamanho da entrada
complexidade de 
tempo e de espaço
 
Análise do espaço ocupado: como fazer
 Cálculo da quantidade de dados que um algoritmo deve armazenar na memória 
do computador para fazer sua tarefa mais os dados iniciais
 Como fazer: avaliar a quantidade de variáveis e o espaço ocupado por elas
 Dois casos básicos
 uso eficiente do espaço
 o algoritmo utiliza o espaço correspondente aos dados de entrada mais uma 
fração deste valor
 uso pouco eficiente do espaço
 o algoritmo utiliza o espaço correspondente aos dados de entrada mais uma 
quantidade igual ou maior do que este valor
 
Análise do tempo de execução
Há duas maneiras de avaliar o tempo de execução
1- Medição empírica ou experimental
– medir o tempo de execução do algoritmo para diversas entradas
– este tempo é influenciado por diversos fatores
• ambiente: hardware, sistema operacional, compiladores
• condições de processamento no momento da execução
• o algoritmo
• a entrada de dados
– esta medida é válida em situações particulares
• vantagem: dá a medida de tempo real de uma execução
• desvantagem: esta medida só é válida para o ambiente em que foi 
executada
 
Análise do tempo de execução
Duas maneiras de avaliar o tempo de execução (continuação)
2 - Análise ou medida analítica
 determina a quantidade de trabalho requerida pelo algoritmo, que 
depende 
 da natureza do problema
 do algoritmo utilizado para sua solução
 da entrada de dados (tamanho e formato)
 o custo é determinado por uma expressão matemática que representa a 
ordem da grandeza de tempo de execução 
 esta expressão representa ou “traduz” o comportamento do algoritmo 
quanto ao seu tempo de execução
 
Funções de complexidade
 
Medida analítica do tempo de execução
Como analisar a complexidade de tempo de um algoritmo
 um algoritmo é uma seqüência de operações ou passos ou 
comandos dos tipos
 instruções básicas: 
 comandos de atribuição, operações matemáticas e lógicas, comandos 
de leitura e escrita, trocas, etc.
 comandos condicionais (comandos de decisão, testes)
 iterações ou loops ou laços
 chamadas de função/método/procedimento/rotina/subrotina
 combinação das anteriores
 
Medida analítica do tempo de execução
Medida analítica
 Princípio: o custo do algoritmo é dado pelo número de operações 
executado pelo algoritmo
 o tempo de execução é proporcional ao custo calculado 
 Consiste em contar o número de operações ou passos ou comandos 
que um algoritmo executa para uma dada entrada de dados
 Este resultado é apresentado como uma função matemática com 
parâmetro n (tamanho da entrada) => o custo é uma função do 
tamanho da entrada n
 
Medida analítica do tempo de execução
Exemplo: contar o número de instruções executadas no 
seguinte comando:
 for (i = 1; i <= n; i++) 
a[i] = 0;
 
Medida analítica do tempo de execução
Exemplo: contar o número de instruções executadas no seguinte 
comando:
 for (i = 1; i <= n; i++) 
 a[i] = 0;
Operações e número de execuções
• Atribuição i = 1 1 execução
• Atribuição a[i] = 0 n execuções
• Incremento i = i + 1 n execuções
• Teste i <= n ? n + 1 execuções 
 TOTAL 3n +2 comandos executados
 
Medida analítica do tempo de execução
Exemplo: contar o número de instruções executadas no 
seguinte comando:
 for (i = 1; i <= n; i++) 
a[i] = 0; 
f(n): função que expressa o custo da linha acima de acordo com o 
tamanho da entrada n 
 f(n) = 3n + 2 
 f(n) cresce proporcionalmente a n
 
Medida analítica do tempo de execução
 Como analisar um algoritmo particular
 contar o número de operações realizadas pelo algoritmo para uma 
dada entrada
 expressar este número em função do tamanho da entrada
 exemplos: 
 f(n) = 5n
 g(n) = 2n2 + 10
 h(n) = nlogn
 como calcular o tempo (aproximação)
 medir o tempo médio para uma operação
 multiplicar o tempo pela função de complexidade
 
Como calcular o tempo
 considere um computador de 1 GHz
 suponha que este computador execute 109 operações por segundo 
(aproximação)
 custo médio de uma operação: 1 ns
 para um algoritmo com f(n) = n e n= 109
 o computador gastará 1 segundo
 para um algoritmo com f(n) = 100 n e n= 109 
 o computador gastará 100 s 
• para um algoritmo com f(n) = n2 e n= 109 
– o computador gastará 31,7 anos
 
 Medida analítica: premissas
 a análise é sempre realizada em relação a um modelo computacional: 
computador genérico com um processador 
 máquina RAM (Random Access Memory)
 todos os acessos à memória tem o mesmo custo
 instruções são executadas sequencialmente (uma após a outra)
 não há instruções nem operações paralelas
 todas as instruções simples têm custo similar (uma unidade de tempo)
 +,-,*,/, =, ==, >, <, if, etc.
 chamadas de função e laços não são operações simples
 são composições de operações simples
 algoritmos com operações mais caras também podem ser analisados sem perda 
de precisão
 por exemplo, algoritmos que incluem operações matemáticas complexas ou 
acesso à memória secundária
 
Análise de Complexidade de Algoritmos
 Algoritmo ótimo
 é o algoritmo cujo custode execução é igual ao custo mínimo 
para a classe de problemas que ele resolve.
 Exemplo:
 Problema P de tamanho n com custo mínimo f(n) = 50n
 3 algoritmos A, B e C que resolvem o problema P com custos de, 
respectivamente, 2n2, 50n e nlogn
 B é um algoritmo ótimo. 
 
Análise de complexidade
 Ordem de crescimento e constantes
 as funções de complexidade são descritas por funções matemáticas
 exemplos
 2n, 3n + 2, 2n2 , 3 log n , 5 n log n , 19n3 + 100, 2n + 32, etc. 
 informação mais importante para análise da complexidade é a ordem de 
crescimento => classe de complexidade
 se a função é logarítmica, linear, quadrática, cúbica, exponencial, etc.
 para obter a classe de complexidade, constantes aditivas e multiplicativas 
são desprezadas
 constantes são importantes somente se 
 são muito grandes
 para comparação mais refinada (detalhada) da eficiência
 
Ordens de Grandeza e seus prefixos
 padrão internacional – obrigatório saber
Sistema 
internacional 
de unidades
SI
Bibliografia
 Projeto de Algoritmos
 Nivio Ziviani
 Edições em Pascal/C, Java/C++
 Algoritmos: Teoria e Prática
 T.H. Cormen, C.E. Leiserson, 
R.L. Rivest, C. Stein
 tradução da 2a. edição 
americana
 Editora Campus, 2002. 
Avaliação
 2 provas de 40 pontos cada
 Prova 1 em dezembro: dia 17 ou 19
 Prova 2 data a ser definida
 Várias listas de exercícios = 20 pontos
 
 Exercício 1
 Individual
 Fazer um resumo de EXATAMENTE uma página do Capítulo 1 
do livro do Ziviani.
 Papel a4, espaço 1, 50 linhas 
 Resumos iguais terão notas iguais a zero.
 Para o dia 14 de novembro
	Computabilidade
	Slide 2
	Slide 3
	Definições dos Cientistas da Computação
	Slide 5
	Diferença entre Algoritmo e Problema
	Slide 7
	Slide 8
	Formalização do conceito de algoritmo
	Slide 10
	Ciência da Computação e Algoritmos Definição de ciência da computação (Gibbs e Tucker)
	Computabilidade e complexidade
	Slide 13
	Slide 14
	Slide 15
	Slide 16
	Áreas de estudo dos algoritmos
	Algoritmos na prática 
	Características desejáveis nos algoritmos
	Complexidade
	Análise de Complexidade de Algoritmos
	Slide 22
	Slide 23
	Análise de complexidade de algoritmos
	Análise do espaço ocupado
	Análise do tempo de execução
	Slide 27
	Funções de complexidade
	Medida analítica do tempo de execução
	Slide 30
	Slide 31
	Slide 32
	Slide 33
	Slide 34
	Como calcular o tempo
	Medida analítica: premissas
	Slide 37
	Análise de complexidade
	Ordens de Grandeza e seus prefixos
	Slide 40
	Slide 41
	Slide 42