Aula+1+-+ACA

Prévia do material em texto

Análise de Computabilidade e Complexidade de 
Algoritmos
Aula Zero
Prof. MSc. Roberth Silva
roberth410@gmail.com
13/02/2017 Análise de Computabilidade e Complexidade de Algoritmos - Prof. MSc. Roberth Silva 1
Roteiro
• Introdução
• Algoritmo
• Problemas Computacionais
• Descrevendo Algoritmos
• Estrutura de Dados
• Representação dos Dados
• Programas
13/02/2017 2Análise de Computabilidade e Complexidade de Algoritmos - Prof. MSc. Roberth Silva
Introdução - Algoritmo
• O que é um algoritmo?
– Procedimento computacional que toma algum valor (conjunto) como entrada e
produz um valor (conjunto) como saída.
• Qual a diferença entre algoritmos e programas?
– Idéia x texto descritivo
– Humanos x computadores
13/02/2017 3Análise de Computabilidade e Complexidade de Algoritmos - Prof. MSc. Roberth Silva
Introdução - Algoritmo
• Os algoritmos fazem parte do dia-a-dia das pessoas. Exemplos de
algoritmos:
– instruções para o uso de medicamentos,
– indicações de como montar um aparelho,
– uma receita de culinária
• Def. de Dijkstra:
– Um algoritmo corresponde a uma descrição de um padrão de
comportamento, expresso em termos de um conj
finito de ações.
13/02/2017 4Análise de Computabilidade e Complexidade de Algoritmos - Prof. MSc. Roberth Silva
Introdução - Algoritmo
• Exemplo de algoritmo
13/02/2017 5Análise de Computabilidade e Complexidade de Algoritmos - Prof. MSc. Roberth Silva
Problemas Computacionais
• Especifica a relação entre a entrada e a saída desejada
13/02/2017 6Análise de Computabilidade e Complexidade de Algoritmos - Prof. MSc. Roberth Silva
Problemas Computacionais
• Uma 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
13/02/2017 7Análise de Computabilidade e Complexidade de Algoritmos - Prof. MSc. Roberth Silva
Descrevendo Algoritmos
Como descrever um algoritmo?
• Utilizar uma linguagem. Qual?
– Linguagem natural (português ou inglês).
– Linguagem de programação.
• Problemas:
– Ambiguidade
– Estruturação
– Prolixidade (demasiadamente longo, extenso ou demorado, enfadonho, 
fastidioso; que usa mais palavras e frases do que o necessário)
– Inadequação para programação
13/02/2017 8Análise de Computabilidade e Complexidade de Algoritmos - Prof. MSc. Roberth Silva
Descrevendo Algoritmos
13/02/2017 9Análise de Computabilidade e Complexidade de Algoritmos - Prof. MSc. Roberth Silva
Estrutura de Dados
• Estruturas de dados e algoritmos estão intimamente ligados:
– Não se pode estudar estruturas de dados sem considerar os algoritmos 
associados a elas
– Assim como a escolha dos algoritmos em geral depende da representação e da 
estrutura dos dados.
• Para resolver um problema é necessário escolher uma abstração da 
realidade, em geral mediante a definição de um conjunto de dados que 
representa a situação real.
• A seguir, deve ser escolhida a forma de representar esses dados
13/02/2017 10Análise de Computabilidade e Complexidade de Algoritmos - Prof. MSc. Roberth Silva
Escolha da Representação dos Dados
• A escolha da representação dos dados é determinada, entre outras, 
pelas operações a serem realizadas sobre os dados.
• Considere a operação de adição:
– Para pequenos números, uma boa representação é por meio de barras verticais 
(caso em que a operação de adição é bastante simples).
– Já a representação por dígitos decimais requer regras relativamente complicadas, 
as quais devem ser memorizadas.
– Entretanto, quando consideramos a adição de grandes números é mais fácil a 
representação por dígitos decimais (devido ao princípio baseado no peso relativo 
da posição de cada dígito).
13/02/2017 11Análise de Computabilidade e Complexidade de Algoritmos - Prof. MSc. Roberth Silva
Programas
• Programar é basicamente estruturar dados e construir algoritmos.
• Programas são formulações concretas de algoritmos abstratos,
baseados em representações e estruturas específicas de dados.
• Programas representam uma classe especial de algoritmos capazes de
serem seguidos por computadores.
• Um computador só é capaz de seguir programas em linguagem de
máquina.
• É necessário construir linguagens mais adequadas, que facilitem a tarefa
de programar um computador.
13/02/2017 12Análise de Computabilidade e Complexidade de Algoritmos - Prof. MSc. Roberth Silva
Programas
13/02/2017 13Análise de Computabilidade e Complexidade de Algoritmos - Prof. MSc. Roberth Silva
SQL Server
Visual Studio
Tipos de Dados
• Caracteriza o conjunto de valores a que uma constante pertence, ou que
podem ser assumidos por uma variável ou expressão, ou que podem ser
gerados por uma função.
• Tipos simples de dados são grupos de valores indivisíveis (como os tipos
básicos int, boolean, char e float de Java).
– Exemplo: uma variável do tipo boolean pode assumir o valor verdadeiro ou o
valor falso, e nenhum outro valor.
• Os tipos estruturados em geral definem uma coleção de valores simples,
ou um agregado de valores de tipos diferentes.
13/02/2017 14Análise de Computabilidade e Complexidade de Algoritmos - Prof. MSc. Roberth Silva
Tipos Abstrados de Dados (TAD’s)
• TAD’s ...
13/02/2017 15Análise de Computabilidade e Complexidade de Algoritmos - Prof. MSc. Roberth Silva
Dúvidas?
13/02/2017 16Análise de Computabilidade e Complexidade de Algoritmos - Prof. MSc. Roberth Silva