Buscar

aula10_Algoritmos

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 3, do total de 36 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 6, do total de 36 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Você viu 9, do total de 36 páginas

Faça como milhares de estudantes: teste grátis o Passei Direto

Esse e outros conteúdos desbloqueados

16 milhões de materiais de várias disciplinas

Impressão de materiais

Agora você pode testar o

Passei Direto grátis

Prévia do material em texto

PROGRAMA DE INFORMÁTICA BÁSICA 
Algoritmos 
Prof. João Dallyson 
 
Aula passada... 
• Introdução 
• Evolução do Software 
• Classificação do Software 
• Sistema Operacional (SO) 
• Evolução do SO 
• Funções do SO 
• Componentes do SO 
 
 
 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 2 
Sumário 
• Introdução à Lógica de Programação 
• Conceito de Algoritmo 
• Representação de Algoritmos 
• Descoberta de Algoritmos 
• Exemplos 
 
 
 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 3 
Noções de Lógica 
• Lógica: Ciência que estuda as formas do pensamento; 
• Sempre que pensamos a lógica nos acompanha: 
– Um bebê sabe que precisa chorar para receber atenção; 
– A gaveta está fechada. A caneta está dentro da gaveta. 
Precisamos primeiro abrir a gaveta para depois pegar a 
caneta. 
• O pensamento (e a lógica) pode ser expresso 
através da palavra falada ou da palavra escrita; 
• Um mesmo pensamento pode ser expresso em 
inúmeros idiomas, tanto oralmente quanto por 
escrito; 
 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 4 
Algoritmo 
• Qual sua importância na programação? 
– Representar o raciocínio, independentemente de 
detalhes computacionais, que podem ser 
acrescentados mais tarde 
– Focalizar primeiro na resolução algorítmica do 
problema, possibilitando depois codificá-la em 
qualquer linguagem 
 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 5 
Conceito de Algoritmo 
• Definição Informal: 
– É o pensamento descrito como uma sequência de 
passos que visam atingir um objetivo; 
– Conjunto de passos que definem como uma tarefa é 
realizada. (BROOKSHEAR, 2013); 
• Ex: ciclo de máquina realizado pela CPU: 
Enquanto a instrução parar não for executada 
Continue a executar os seguintes passos: 
a) Obtenha uma instrução. 
b) Decodifique a instrução. 
c) Execute a instrução. 
• Exemplos de Algoritmos no cotidiano? 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 6 
Conceito de Algoritmo 
• Definição Formal: 
– É um conjunto ordenado de passos executáveis, não 
ambíguos, que define um processo finalizável. 
(BROOKSHEAR, 2013) 
 
• Ex: algoritmo infinito 
– Crie uma lista de todos os inteiros positivos. 
• Obs: 
– Existem aplicações importantes para processos que 
não terminam: 
• Monitoramento de sinais vitais de um paciente 
 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 7 
Natureza abstrata dos algoritmos 
• Diferença: algoritmo x representação 
– Analogia: Uma história X um livro 
– Uma história: abstrata, conceitual, em sua natureza 
– Um livro: representação física de uma história 
• Livro em vários idiomas, a história continua imutável 
 
– Um algoritmo é abstrato e distinto de sua 
representação. 
• Ex: F = (9/5)C + 32, ou, 
 Multiplique o valor da temperatura em Celsius por 9/5 e 
adicione 32 ao produto. 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 8 
Natureza abstrata dos algoritmos 
• Programas X Processos X Algoritmos ? 
– Entidades distintas, porém relacionadas. 
– Programa: Representação de um algoritmo 
– Processo: Atividade de executar um algoritmo 
 
• Importância dos algoritmos na programação? 
– Representar o raciocínio, independentemente de 
detalhes computacionais, que podem ser acrescentados 
mais tarde 
– Focalizar primeiro na resolução algorítmica do problema, 
possibilitando depois codificá-la em qualquer linguagem 
 30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 9 
Exercício 
• Em que sentido os passos descritos pela seguinte 
lista de instruções falham em constituir um 
algoritmo? 
– Passo 1: Pegue um moeda de seu bolso e coloque 
sobre a mesa. 
– Passo 2: Retorne ao Passo 1. 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 10 
Dois pontos: 
 
1º) As instruções definem um processo que não termina. 
2º) Ambiguidade: O processo alcançara um estado no qual não haverá 
mais moedas em seu bolso. O algoritmo não descreve o que deve ser feito 
nesta situação 
Representação de Algoritmos 
• Humanos: linguagem natural tradicional, linguagem de 
figuras. 
– Problemas da linguagem natural: 
• Mal entendimento: algumas vezes possui mais de um 
significado. 
• Ex: “Visitar os netos pode ser irritante” 
– Ou os netos causam problemas quando você os visita 
– Ou ir visitá-los é problemático 
 
• Problemas de comunicação surgem quando a 
linguagem usada para a representação de um algoritmo 
não é precisamente definida ou quando a informação 
não é dada com o detalhamento adequado. 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 11 
Representação de Algoritmos 
• Requer primitivas bem definidas (evita ambiguidade) 
– Primitivas: conjunto bem definidos de blocos de construção a 
partir dos quais representações de algoritmos podem ser 
construídas. 
• Sintaxe: representação simbólica da primitiva 
• Semântica: significado da primitiva 
• Ex: água (sintaxe: 5 símbolos, semântica: líquido natural, 
transparente, incolor, indispensável para a sobrevivência da maioria 
dos seres vivos) 
• linguagem de programação: 
– Coleção de primitivas 
 + 
– Coleção de regras 
• definem como as primitivas podem ser combinadas para representar 
ideias mais complexas 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 12 
Pássaro de origami - primitivas 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 13 
Primitivas de origamis Algoritmo 
Primitivas - Pseudocódigo 
• Pseudocódigo: 
– É um sistema notacional no qual ideias podem ser 
expressas informalmente durante o processo de 
desenvolvimento do algoritmo (BROOKSHEAR, 2013); 
– Objetivo de fornecer meios para representar algoritmos 
de uma maneira legível e informal. 
• Exemplos: 
– Sentença de Atribuição: 
• Nome  expressão 
• Atribua a nome o valor de expressão. 
• Saldo  SaldoContaCorrente + SaldoPoupanca 
– Sentença de Condição 
se (condição) então (atividade) 
 senão 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 14 
Primitivas - pseudocódigo 
– Sentença de repetição: 
 enquanto (condição) faça (atividade) 
 repita (atividade) até (condição) 
 Ex: enquanto (existem ingressos a serem vendidos) faça 
(venda um ingresso) 
 
• Indentação: 
 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 15 
Descoberta de Algoritmos 
• Matemático G. Polya (1945) apresentou fases para 
guiar o processo de resolução de problemas: 
 
 Fase 1. Entender o problema. 
 Fase 2. Bolar um plano para resolver o problema. 
 Fase 3. Executar o plano. 
 Fase 4. Avaliar a solução em termos de precisão e 
de seu potencial como uma ferramenta para solucionar 
outros problemas. 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 16 
Exemplos 
• Problemas das Torres de Hanói 
– Mover os discos de uma haste para outra sem que o 
disco maior fique sobre o disco menor 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 17 
Solução? 
Dando o primeiro passo 
• Tentar trabalhar o problema de trás para frente 
– Se um problema for encontrar uma maneira de produzir uma saída 
a partir de uma dada entrada, poderíamos iniciar com a saída e 
voltar até a entrada. 
– Ex: Pássaro origami, tentar desdobrar para descobrir como foi feito. 
 
• Resolver um problema relacionado mais fácil 
– Relaxar algumas das restrições do problema 
– Resolver partes do problema primeiro (metodologia bottomup) 
 
• Refinamento passo a passo: 
– Divide o problema em problemas menores (metodologia top-
down) 
– Ex: Componentes pré-fabricados de grandes sistemas 
coorporativos 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 18 
Resolução de Problemas 
• Partimos do problema geral para atingir níveis 
específicos. 
• Ex: Considere uma escola cujo cálculo da média é realizado com 
utilização de quatro notas bimestrais que determinam a 
aprovação ou reprovação dos alunos. Considere que o valor da 
média dever ser maior ou igual a 7 para que haja aprovação. 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 19 
Resolução de Problemas 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 20 
Resolução de Problemas 
 Programa média 
 
 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 21 
Exemplos 
• Trocar uma lâmpada (v1.1) 
– sequencial 
 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 22 
 pegar uma escada; 
 posicionar a escada embaixo da lâmpada; 
 buscar uma lâmpada nova; 
 subir na escada; 
 retirar lâmpada velha; 
 colocar lâmpada nova. 
Exemplos 
• Trocar uma lâmpada SE estiver queimada (v1.2) 
– Seleção (Decisão) 
 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 23 
 pegar uma escada; 
 posicionar a escada embaixo da lâmpada; 
 buscar uma lâmpada nova; 
 acionar o interruptor; 
 se a lâmpada não acender, então 
 subir na escada; 
 retirar lâmpada queimada; 
 colocar lâmpada nova. 
Exemplos 
• Trocar uma lâmpada SE estiver queimada (v1.3) 
– Seleção (Decisão) 
– Evita buscar a escada e lâmpada 
 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 24 
 acionar o interruptor; 
 se a lâmpada não acender, então 
 pegar uma escada; 
 posicionar a escada embaixo da lâmpada; 
 buscar uma lâmpada nova; 
 acionar o interruptor; 
 subir na escada; 
 retirar lâmpada queimada; 
 colocar lâmpada nova. 
Exemplos 
• Trocar uma lâmpada SE estiver queimada (v1.4) 
– Seleção (Decisão) 
– Re-teste depois da troca 
 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 25 
 acionar o interruptor; 
 se a lâmpada não acender, então 
 pegar uma escada; 
 posicionar a escada embaixo da lâmpada; 
 buscar uma lâmpada nova; 
 acionar o interruptor; 
 subir na escada; 
 retirar lâmpada queimada; 
 colocar lâmpada nova; 
 se a lâmpada não acender, então 
 retirar lâmpada queimada; 
 colocar lâmpada nova; 
 se a lâmpada não acender, então 
 . . . 
Exemplos 
• Trocar uma lâmpada SE estiver queimada (v1.5) 
– Repetição 
– Re-teste depois da troca (por repetição) 
 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 26 
 acionar o interruptor; 
 se a lâmpada não acender, então 
 pegar uma escada; 
 posicionar a escada embaixo da lâmpada; 
 buscar uma lâmpada nova; 
 acionar o interruptor; 
 subir na escada; 
 retirar lâmpada queimada; 
 colocar lâmpada nova; 
 enquanto a lâmpada não acender, faça 
 retirar lâmpada queimada; 
 colocar lâmpada nova; 
Problemas e Soluções 
• Não existe, em geral, uma única solução para o mesmo 
problema; 
 
• Algumas soluções são melhores do que outras, sob 
algum critério; 
 
• Alguns problemas são casos particulares de outros 
similares; 
 
• As vezes, é melhor resolver o problema mais genérico, 
assim, resolve-se uma classe de problemas, e não 
apenas um. 
 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 27 
Formas de Representação 
• Gráficas (Fluxograma) 
– Vantagens 
• Maior clareza no fluxo de execução 
• Linguagem visual 
– Desvantagens 
• Requer conhecimento de convenções gráficas 
• Mais trabalhoso em decorrência de seus desenhos 
• Dificuldade para fazer correções 
• Textuais (Linguagem Natural e Pseudo-código ) 
– Apresenta mais vantagens, desde que se tomem alguns cuidados: 
• Riqueza gramatical de nossa língua pode levar a 
ambiguidades 
• Para resolver, utilizaremos um conjunto restrito de regras, 
conhecido como Português Estruturado 
 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 28 
Calcular raiz de uma equação do 1º grau? 
• Linguagem natural 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 29 
Calcular raiz de uma equação do 1º grau? 
• Fluxograma 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 30 
Calcular raiz de uma equação do 1º grau? 
• Pseudo-código 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 31 
Exercícios 
1) Descreva a diferenças entre um processo, um 
algoritmo e um programa. 
2) Cite exemplos de algoritmos com os quais você esteja 
familiarizado. Eles são realmente algoritmos segundo 
a definição formal? 
3) Escreva um algoritmo para realizar a troca de um pneu 
de uma bicicleta. 
4) Escreva um algoritmo para realizar a troca de um 
único pneu de um carro. 
5) Construa um algoritmo que, dado o valor de um 
compra, sejam aplicados 10% de desconto na venda à 
vista e exiba o valor a ser pago. 
 
 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 32 
Links 
Metropole Digital – Lógica e Algorimos 
http://www.metropoledigital.ufrn.br/aulas/disciplinas/logic
a/ 
 
Web Portugol 
http://siaiacad17.univali.br/webportugol 
login: bctfc senha:bctfc 
 
Jogo Light Bot 
http://www.jogosjogos.com/jogar-jogo/Light-Bot.html 
 
Scratch 
http://scratch.mit.edu/ 
 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 33 
Agradecimentos 
 
 
• Ao Prof. Dr. Bruno Feres, do BCT/UFMA 
• Ao Prof. Dr. Sergio Souza Costa, do BCT/UFMA 
• Ao Prof. Me. Geraldo Braz, DEINF/UFMA 
• Ao Prof. Me. Osvaldo Silva Sousa Junior, NTI/UFMA 
 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 34 
Referências 
• BROOKSHEAR, J. G. Ciência da Computação: Uma visão 
abrangente. 11ª Ed. Porto Alegre, 2013. 
• MANZANO, J. A. N. G; OLIVEIRA, J. F. Algoritmos: Lógica 
para Desenvolvimento de Programação de 
Computadores. 26ª Ed. São Paulo: Érica, 2013; 
• MANZANO, J. A. N. G; OLIVEIRA, J. F. Algoritmos: 
Estudo Dirigido. 15ª Ed. São Paulo: Érica, 2013; 
 
 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 35 
Perguntas.... 
30/10/2013 Prof. João Dallyson (BCT – UFMA) Fundamentos da Computação 36

Materiais relacionados

Perguntas relacionadas

Materiais recentes

Perguntas Recentes