Aula 01 Algoritmos e Computação

Prévia do material em texto

capa 
Algoritmos 
Um algoritmo pode ser expresso de diversas maneiras, dentre elas: 
• Linguagem Natural 
• Fluxograma 
• Pseudocódigo 
• Linguagem de Programação 
Algoritmos 
Método para resolver problemas. 
Algoritmos 
É a descrição de uma sequência de passos (ações/instruções) que 
devem ser seguidas para a solução de um problema. 
Algoritmos 
Um exemplo clássico para definir algoritmos é uma receita culinária. 
 
Problema: produção de refeições. 
Solução: repetir passos definidos (fazer iterações) e tomar decisões 
até que a refeição esteja pronta para ser servida. 
 
 
A solução é o algoritmo. 
Algoritmos 
Exemplo 1: receita de bolo simples 
Ingredientes 
• 2 xícaras de açúcar 
• 3 xícaras de farinha de trigo 
• 4 colheres de margarina bem cheias 
• 3 ovos 
• 1 e 1/2 xícara de leite aproximadamente 
• 1 colher (sopa) bem cheia de fermento em pó Dr. Oetker 
 
Fonte: http://www.tudogostoso.com.br/receita/29124-bolo-simples.html 
Algoritmos 
Exemplo 1: receita de bolo simples 
Modo de Preparo 
1. Bata as claras em neve 
2. Reserve 
3. Bata bem as gemas com a margarina e o açúcar 
4. Acrescente o leite e farinha aos poucos sem parar de bater 
5. Por último agregue as claras em neve e o fermento 
6. Coloque em forma grande de furo central untada e enfarinhada 
7. Asse em forno médio, preaquecido, por aproximadamente 40 minutos 
8. Quando espetar um palito e sair limpo estará assado 
Fonte: http://www.tudogostoso.com.br/receita/29124-bolo-simples.html 
 
Algoritmos 
Pergunta 1: de acordo com o exemplo, podemos observar que a 
execução do algoritmo do bolo é composta por: 
A. Ingredientes (Entrada | Estado Inicial). 
B. Sequência de passos (Processamento | Estado Intermediário). 
C. O Bolo (Saída | Estado Final). 
D. Todas as alternativas acima. 
Algoritmos 
Pergunta 1: de acordo com o exemplo, podemos observar que a 
execução do algoritmo do bolo é composta por: 
A. Ingredientes (Entrada | Estado Inicial). 
B. Sequência de passos (Processamento | Estado Intermediário). 
C. O Bolo (Saída | Estado Final). 
D. Todas as alternativas acima. 
 
R: Alternativa D. 
Algoritmos 
Pergunta 1 - Análise: 
Como pudemos observar, para a execução de um algoritmo (modo 
de preparo), foi necessário a presença de dados iniciais 
(ingredientes) a serem manipulados resultando em um estado final 
(o bolo). 
Algoritmos 
Exemplo 2: descobrir a hipotenusa de um triângulo retângulo dado 
dois catetos. 
Dados iniciais: 
• Cateto 1 
• Cateto 2 
 
C2 
C1 
H=? 
Algoritmos 
Exemplo 2: descobrir a hipotenusa de um triângulo retângulo dado 
dois catetos. 
Algoritmo: 
1. Eleve o cateto 1 ao quadrado. 
2. Escreva o resultado 1 da operação acima. 
3. Eleve o cateto 2 ao quadrado. 
4. Escreva o resultado 2 da operação acima. 
5. Some o resultado 1 com o resultado 2. 
6. Escreva o resultado 3 da operação acima. 
7. Tire a raiz quadrada do resultado 3. 
8. Escreva o resultado da operação acima que será a hipotenusa. 
 
Algoritmos 
Exemplo 2: descobrir a hipotenusa de um triângulo retângulo dado 
dois catetos. 
Dados finais: 
• Cateto 1 
• Cateto 2 
• Hipotenusa 
 
C2 
C1 
H=? 
Algoritmos 
• Variáveis: 
 
Conforme observamos, para executar um algoritmo é essencial 
a manipulação de dados, valores ou objetos. 
 
O mesmo vale para o computador. 
 
Algoritmos 
• Variáveis: 
 
Quando um computador executa um algoritmo, o mesmo 
precisa armazenar e manipular valores. 
Esses valores são armazenados e acessados da memória do 
computador. 
O acesso à memória é abstraído no conceito de variáveis. 
Algoritmos 
• Variáveis: 
• As variáveis podem ser entendidas como “caixas” que podem 
guardar um valor 
• Cada vez que guardamos um novo valor nela, apagamos o 
antigo 
• Para guardarmos um novo valor em uma variável usamos o 
comando de atribuição. 
Algoritmos 
• Variáveis: 
• Para a atribuição de valores iremos utilizar uma seta ( <- ) 
• A variável sempre irá se encontrar à esquerda 
• Na parte direita ficará uma expressão 
• O resultado da expressão será armazenado pela variável 
Algoritmos 
• Variáveis: 
• x <- 5 
 
• x <- 2+3*5 
 
• x <- (2+3)*5 
Algoritmos 
• Variáveis: 
• Exemplo: Determine o valor final da variável x ao final da 
sequência de passos: 
A. 4 
B. 7 
C. 10 
D. 25 
 
Algoritmos 
• Variáveis: 
• Exemplo: Determine o valor final da variável x ao final da 
sequência de passos: 
A. 4 
B. 7 
C. 10 
D. 25 
 R: Alternativa C. 
Algoritmos 
• Variáveis: 
• Exemplo: Determine o valor final da variável x ao final da 
sequência de passos: 
A. 20 
B. 22 
C. 16 
D. 24 
 
Algoritmos 
• Variáveis: 
• Exemplo: Determine o valor final da variável x ao final da 
sequência de passos: 
A. 20 
B. 22 
C. 16 
D. 24 
 R: Alternativa B. 
Algoritmos 
• Variáveis: 
• Exemplo: Determine o valor final da variável x ao final da 
sequência de passos: 
A. 3 
B. 6 
C. 9 
D. 21 
 
Algoritmos 
• Variáveis: 
• Exemplo: Determine o valor final da variável x ao final da 
sequência de passos: 
A. 3 
B. 6 
C. 9 
D. 21 
 R: Alternativa A. 
Algoritmos 
• Variáveis: 
• Exemplo: Determine o valor final da variável x ao final da 
sequência de passos: 
A. 143 
B. 105 
C. 215 
D. 47 
 
 
Algoritmos 
• Variáveis: 
• Exemplo: Determine o valor final da variável x ao final da 
sequência de passos: 
A. 143 
B. 105 
C. 215 
D. 47 
 
 R: Alternativa C. 
Algoritmos 
Um algoritmo pode ser constituído por 3 estruturas de fluxo: 
• Estruturas Sequenciais 
• Estruturas Condicionais 
• Estruturas de Repetição 
Algoritmos 
• Estruturas Sequenciais 
• Exemplo: Algoritmo para calcular média de três notas 
a <- leiaUmNumeroDoTeclado() 
b <- leiaUmNumeroDoTeclado() 
c <- leiaUmNumeroDoTeclado() 
media <- (a+b+c)/3 
exiba media 
 
Algoritmos 
• Estruturas Sequenciais 
• Exemplo: Dado o total de vendas de um vendedor, calcule 
a sua comissão. Suponha que a comissão do vendedor seja 
de 10% do total de vendas. 
totalvendas <- leiaUmNumeroDoTeclado() 
comissao <- totalvendas*0,1 
exiba comissao 
 
 
Algoritmos 
• Estruturas Sequenciais 
• Exemplo: Algoritmo que troca o valor de duas variáveis a e 
b 
auxiliar <- a 
 a <- b 
 b <- auxiliar 
 
 
 
Algoritmos 
Um algoritmo pode ser constituído por 4 estruturas de fluxo: 
• Estruturas Sequenciais [OK] 
• Estruturas Condicionais 
• Estruturas de Repetição 
Algoritmos 
• Estruturas Condicionais 
• Acontecem apenas quando alguma condição é verdadeira 
• Uma condição só pode ser verdade ou falsa 
• São usadas as palavras chave se-então-senão 
se(condição) então 
<instruções> 
senão 
<instruções> 
fim-se 
... 
<Condição> 
Instruções Instruções 
Verdade Falsa 
• Estruturas Condicionais 
• Exemplo: Algoritmo que imprime qual o menor entre dois numeros 
a <- leiaUmNumeroDoTeclado() 
b <- leiaUmNumeroDoTeclado() 
se(a < b)então 
menor <- a 
senão 
menor <- b 
fim-se 
exiba menor 
 
Algoritmos 
• Estruturas Condicionais 
• Exemplo: Algoritmo que imprima qual o menor entre dois numeros 
a <- leiaUmNumeroDoTeclado() 
b <- leiaUmNumeroDoTeclado() 
se(a < b)então 
menor <- a 
senão 
menor <- b 
fim-se 
exiba menor 
 
Algoritmos 
• EstruturasCondicionais 
• Exemplo: Algoritmo para calcular as raízes de uma 
equação do segundo grau: 
 
 
a*x² + b*x + c = 0 
Algoritmos 
• Estruturas Condicionais 
 a <- leiaUmNumeroDoTeclado() 
 b <- leiaUmNumeroDoTeclado() 
 c <- leiaUmNumeroDoTeclado() 
 delta <- 
 
 
 
Algoritmos 
Opções: 
A. delta 
B. a+b+c 
C. 4*a*c 
D. b*b - 4*a*c 
 
 
• Estruturas Condicionais 
 a <- leiaUmNumeroDoTeclado() 
 b <- leiaUmNumeroDoTeclado() 
 c <- leiaUmNumeroDoTeclado() 
 delta <- 
 
 
 
Algoritmos 
Opções: 
A. delta 
B. a+b+c 
C. 4*a*c 
D. b*b - 4*a*c 
 
 
b*b – 4*a*c 
• Estruturas Condicionais 
 a <- leiaUmNumeroDoTeclado() 
 b <- leiaUmNumeroDoTeclado() 
 c <- leiaUmNumeroDoTeclado() 
 delta <- b*b – 4*a*c 
 se ( delta >= 0 )então 
 x1 <- (raiz(delta) – b)/(2*a) 
 x2 <- (-1*raiz(delta) – b)/(2*a) 
 fim-se 
 
 
Algoritmos 
Opções: 
A. delta = 0 
B. delta > 0 
C. delta >= 0 
D. delta 
 
 
• Estruturas Condicionais 
 a <- leiaUmNumeroDoTeclado() 
 b <- leiaUmNumeroDoTeclado() 
 c <- leiaUmNumeroDoTeclado() 
 delta <- b*b – 4*a*c 
 se ( delta >= 0 )então 
 x1 <- (raiz(delta) – b)/(2*a) 
 x2 <- (-1*raiz(delta) – b)/(2*a) 
 fim-se 
 
 
Algoritmos 
Opções: 
A. delta = 0 
B. delta > 0 
C. delta >= 0 
D. delta 
 
 
• Estruturas Condicionais 
 a <- leiaUmNumeroDoTeclado() 
 b <- leiaUmNumeroDoTeclado() 
 c <- leiaUmNumeroDoTeclado() 
 delta <- b*b – 4*a*c 
 se (delta >= 0)então 
 x1 <- (raiz(delta) – b)/(2*a) 
 x2 <- (-1*raiz(delta) – b)/(2*a) 
 fim-se 
 
 
Algoritmos 
Algoritmos 
Um algoritmo pode ser constituído por 4 estruturas de fluxo: 
• Estruturas Sequenciais [OK] 
• Estruturas Condicionais [OK] 
• Estruturas de Repetição 
Algoritmos 
• Estruturas de Repetição 
• Irão repetir enquanto uma condição for satisfeita 
• São usadas as palavras chave enquanto-faça 
enquanto (<condição) faça 
 <instruções> 
fim-enquanto 
 
Instruções <Condição> 
Verdade 
Falsa 
• Estruturas de Repetição 
• Exemplo: Faça um algoritmo que imprima todos os 
números de 1 a 20 
num <- 1 
 enquanto(num <= 20) faça 
 exiba num 
 num <- num+1 
 fim-enquanto 
 
 
Algoritmos 
Algoritmos 
• Estruturas de Repetição 
• Exemplo: Faça um algoritmo que imprima todos os 
números de 1 a 20 
num <- 1 
 enquanto(num <= 20) faça 
 exiba num 
 num <- num+1 
 fim-enquanto 
 
 
• Estruturas de Repetição 
• Exemplo: Faça um algoritmo que some todos os números 
entre 200 e 400 
num <- 200 
soma <- 0 
enquanto(num <= 400) faça 
soma <- soma + num 
num <- num + 1 
fim-enquanto 
 
 
 
Algoritmos 
• Estruturas de Repetição 
• Exemplo: Faça um algoritmo que some todos os números 
entre 200 e 400 
num <- 200 
soma <- 0 
enquanto(num <= 400) faça 
soma <- soma + num 
num <- num + 1 
fim-enquanto 
 
 
 
Algoritmos 
Algoritmos 
Um algoritmo pode ser constituído por 4 estruturas de fluxo: 
• Estruturas Sequenciais [OK] 
• Estruturas Condicionais [OK] 
• Estruturas de Repetição [OK] 
Algoritmos 
• Por que estudar algoritmos? 
• O seu impacto é amplo e de longo alcance. 
Internet. Busca na web, roteamento de pacote, compartilhamento de arquivos,... 
Biologia. Projeto do genoma humano, enovelamento de proteínas,... 
 Computador. Layout de circuitos, sistema de arquivos, compiladores (fique ligado!)... 
 Computação gráfica. filmes, video games, realidade virtual... 
 Segurança. celular, e-commerce, urna eletrônica,... 
 Multimídia. MP3, JPG, DivX, HDTV, reconhecimento de face, .... 
 Redes Sociais. recomendações, feeds de notícia, propagandas,... 
 Física. simulação de partículas, simulação de colisão de partículas,... 
 
Linguagens de Programação 
• Computador X Pessoas 
• O que é conveniente 
para as pessoas às vezes 
não é conveniente para 
o computador 
 
• Pessoas querem fazer X, 
máquinas só fazem Y 
 
• Como proceder? 
Linguagens de Programação 
• Níveis de linguagens 
• Computador recebe 
instruções (ordens) 
• Instruções lógicas e 
padronizadas 
• Processa essas instruções 
e gera um resultado 
• Uma LP é uma forma 
padronizada de 
comunicação com o 
computador 
Linguagens de Programação 
• Níveis de linguagens 
• A maioria dos 
computadores utilizam 
lógica digital binária 
• A crescente 
complexidade dos 
programas 
• Novas formas de 
programar 
Linguagens de Programação 
• Máquina multinível 
• Solução para 
comunicação 
homem X 
máquina 
• Cada máquina 
possui sua 
linguagem 
 
Linguagens de Programação 
• Linguagem de baixo 
nível 
• Forte relação 
com o hardware 
• Restritas a 
linguagem de 
máquina 
• Codificação 
rígida com a 
arquitetura 
 
00111010100100100100001111010101
01110101010111110010010001111101
00100011010100101100000001010010
10101010101111110000010101010010
01111111111010101001001010010010
01000010100100100100101000101001
00100011010101010100000001010010
01000110101010101000000010100100
10001101010101010000000101001001
00011010101010100000001010010010
00110101010101000000010100100100
01101010101010000000101001001000
00000010100001010010010010101010
10101010101000000010101010101001
11010101101010100100100111010010
01001000100110101001110010010010
01000110101010101000000010100100
10001101010101010000011111011001 
 
Linguagens de Programação 
Dispositivos de 
entrada 
CPU 
Dispositivos de saída 
Unidade de memória 
Unidade de Controle 
ULA 
Arquitetura de Von Neumann 
Linguagens de Programação 
• Linguagem de 
montagem 
• É uma linguagem 
de baixo nível 
• Cada comando 
produz uma 
única instrução 
de máquina 
 
.data 
x1: .word 10 
x2: .word 5 
x3: .word -1 
 
.text 
lw $t0, x1 
lw $t1, x2 
add $t2, $t0, $t1 
sw $t2, x3 
 
li $v0, 1 
move $a0, $t2 
syscall 
 
li $v0, 10 
syscall 
Linguagens de Programação 
• Linguagem de alto 
nível 
• Se aproxima da 
linguagem 
utilizada por 
humanos 
• Cada comando 
produz várias 
instruções de 
máquina 
 
#include <stdio.h> 
 
int main() 
{ 
 int a = 10, b = 5; 
 printf (“%d\n”, 
a+b); 
return 0; 
} 
Linguagens de Programação 
• Linguagens de alto nível X Linguagens de baixo nível 
 
ALTO NÍVEL BAIXO NÍVEL 
Facilidade de manipulação, por tratar comandos com 
linguagens mais próximas do programador. 
Dificuldade de programação devido a forte proximidade com a 
sistemática de hardware. 
Facilidade em encontra erros Dificuldade em encontrar erros 
Possui portabilidade Totalmente dependente da arquitetura computacional utilizada 
Lenta, se comparada a linguagem de baixo nível Rápida, pois opera em um nível próximo do hardware 
Rotinas mais complexas, portanto utiliza mais memória Utiliza menos espaço de memória 
Linguagens de Programação 
• Processamento de Linguagens 
• O computador entende 
apenas a linguagem de 
máquina 
• Alternativas: Interpretação 
e tradução 
 
Linguagens de Programação 
• Interpretação 
• Comandos diretamente 
executados 
• Sequência: 
• Obter próximo comando 
• Converter o comando 
em instruções em 
linguagem de máquina 
• Executar as instruções 
 
Linguagens de Programação 
• Tradução 
• Traduz um programa de 
uma linguagem para outra 
de nível mais baixo 
• Ocorre com os programas 
escritos em linguagemde 
alto nível 
 
Linguagens de Programação 
• Compilador 
• Traduz linguagem de alto 
nível (código fonte) em 
linguagem de de baixo nível 
(código objeto) na forma de 
um executável 
• Exemplos: gcc, Turbo C, 
Visual C, Visual Basic, etc 
• C é uma linguagem 
compilada! 
 
Linguagens de Programação 
#include <stdio.h> 
 
int main() 
{ 
 int a = 10, b = 5; 
 printf (“%d\n”, 
a+b); 
return 0; 
} 
.data 
x1: .word 10 
x2: .word 5 
x3: .word -1 
 
.text 
lw $t0, x1 
lw $t1, x2 
add $t2, $t0, $t1 
sw $t2, x3 
 
li $v0, 1 
move $a0, $t2 
syscall 
 
li $v0, 10 
syscall 
capa