5ALCM-Aula2-v2.1

Prévia do material em texto

Algoritmos	
  Computacionais	
  
Engenharias	
  
5ALCM	
   Prof.	
  Ivan	
  C.	
  Machado,	
  M.Sc.	
  
imachado@area1.edu.br	
  
Unidade	
  II	
  
06
/0
2/
20
14
	
  
5A
LC
M
	
  2
01
4.
1	
  
Unidade	
  2	
  
1.  Algoritmos	
  e	
  Resolução	
  de	
  Problemas	
  
1.  Noções	
  de	
  lógica	
  para	
  construção	
  de	
  algoritmos	
  
2.  Construção	
  de	
  algoritmos	
  sobre	
  problemas	
  do	
  cotidiano	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Algoritmos	
  e	
  Resoluções	
  de	
  Problemas	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Conceitos	
  Elementares	
  
Aplicação	
  no	
  cotidiano	
  
Relação	
  entre	
  lógica	
  e	
  algoritmos:	
  a	
  lógica	
  de	
  programação	
  
Noções	
  de	
  Lógica	
  
O	
  Que	
  é	
  um	
  Algoritmo?	
  
Utilidade	
  de	
  um	
  Algoritmo	
  
Representações	
  de	
  Algoritmos	
  
Noções	
  de	
  Algoritmo	
  
Resolução	
  de	
  Problemas	
  (Etapas)	
  
1.  Definir	
  o	
  problema	
  
2.  Estudar	
  a	
  situação	
  atual	
  e	
  verificar	
  as	
  possibilidades	
  de	
  
resolução	
  
3.  Utilizar	
  uma	
  linguagem	
  de	
  programação	
  para	
  escrever	
  o	
  
programa	
  que	
  objetiva	
  resolver	
  o	
  problema	
  
4.  Após	
  a	
  construção	
  do	
  programa,	
  validar	
  com	
  os	
  usuários	
  se	
  
o	
  problema	
  foi	
  resolvido	
  com	
  a	
  solução	
  computacional	
  
produzida	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Lógica	
  
Ê  Lógica	
  é	
  uma	
  parte	
  da	
  filosofia	
  que	
  estuda	
  o	
  fundamento,	
  a	
  
estrutura	
  e	
  as	
  expressões	
  humanas	
  do	
  conhecimento.	
  A	
  
lógica	
  foi	
  criada	
  por	
  Aristóteles	
  no	
  século	
  IV	
  a.C.	
  para	
  estudar	
  
o	
  pensamento	
  humano	
  e	
  distinguir	
  interferências	
  e	
  
argumentos	
  certos	
  e	
  errados.	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Lógica	
  
Ê  Lógica	
  é	
  a	
  arte	
  de	
  pensar	
  corretamente	
  e,	
  visto	
  que	
  a	
  forma	
  
mais	
  complexa	
  do	
  pensamento	
  é	
  o	
  raciocínio,	
  a	
  Lógica	
  
estuda	
  ou	
  tem	
  em	
  vista	
  a	
  "correção	
  do	
  raciocínio".	
  Assim,	
  a	
  
Lógica	
  ensina	
  a	
  colocar	
  Ordem	
  no	
  Pensamento.	
  	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Lógica	
  
Ê  Exemplos:	
  
Ê  Todo	
  mamifero	
  é	
  um	
  animal	
  
Todo	
  cavalo	
  é	
  um	
  mamífero	
  
Portanto,	
  todo	
  cavalo	
  é	
  um	
  animal	
  
Ê  Kaiton	
  é	
  país	
  do	
  planeta	
  Stix	
  
Todos	
  os	
  Xinpins	
  são	
  Kaiton	
  
Logo,	
  todos	
  os	
  Xinpins	
  são	
  Stixianos	
  
Ê  Baseados	
  em	
  silogismos.	
  Raciocínio	
  que	
  se	
  pauta	
  na	
  dedução,	
  
composto	
  basicamente	
  por	
  duas	
  premissas	
  ou	
  preposições	
  (maior	
  e	
  
menor),	
  a	
  partir	
  das	
  quais	
  se	
  alcança	
  uma	
  conclusão.	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Existe	
  lógica	
  no	
  dia-­‐a-­‐dia?	
  
Ê  As	
  pessoas	
  utilizam	
  lógica	
  no	
  cotidiano	
  sem	
  perceber	
  
Ê  Lógica	
  é	
  a	
  “coerência	
  raciocínios,	
  ideias”,	
  é	
  	
  a	
  “sequência	
  
coerente,	
  regular	
  e	
  necessária	
  de	
  acontecimentos,	
  de	
  coisas”	
  
Ê  Exemplos?	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Lógica	
  de	
  Programação	
  
Ê  Todo	
  e	
  qualquer	
  problema	
  de	
  programação,	
  em	
  que	
  se	
  vai	
  
executar	
  determinadas	
  operações,	
  dentro	
  de	
  certas	
  
condições	
  pré-­‐estabelecidas,	
  exige	
  que	
  se	
  estude	
  
previamente	
  uma	
  solução	
  em	
  que	
  se	
  emprega	
  a	
  Lógica.	
  
Ê  A	
  lógica	
  de	
  programação	
  permite	
  definir	
  a	
  sequência	
  lógica	
  
para	
  o	
  desenvolvimento	
  das	
  aplicações	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Lógica	
  de	
  Programação	
  
Ê  Significa	
  o	
  uso	
  correto	
  das	
  leis	
  do	
  pensamento,	
  da	
  “ordem	
  da	
  
razão”	
  e	
  de	
  processos	
  de	
  raciocínio	
  e	
  simbolização	
  formais	
  na	
  
programação	
  de	
  computadores,	
  objetivando	
  a	
  racionalidade	
  
e	
  o	
  desenvolvimento	
  de	
  técnicas	
  que	
  cooperem	
  para	
  a	
  
produção	
  de	
  soluções	
  logicamente	
  válidas	
  e	
  coerentes,	
  que	
  
resolvam	
  com	
  qualidade	
  os	
  problemas	
  que	
  se	
  deseja	
  
programar	
  	
  
(FORBELLONE,	
  2005)	
  
06/02/2014	
   5ALCM	
  2014.1	
  
O	
  Papel	
  da	
  Lógica	
  de	
  Programação	
  
Ê  Resolver	
  problemas	
  com	
  maior	
  rapidez	
  e	
  menor	
  esforço	
  
possíveis	
  
Ê  Automatizar	
  tarefas	
  rotineiras	
  
Ê  As	
  tarefas	
  que	
  devem	
  ser	
  realizadas	
  pelo	
  computador	
  de	
  
forma	
  automática	
  têm	
  de	
  ser	
  anteriormente	
  pensadas	
  e	
  
colocadas	
  em	
  uma	
  sequência	
  de	
  ações	
  para,	
  posteriormente,	
  
serem	
  inseridas	
  na	
  máquina	
  
06/02/2014	
   5ALCM	
  2014.1	
  
O	
  que	
  é	
  programação?	
  
5A
LC
M
	
  2
01
4.
1	
  
06
/0
2/
20
14
	
  
“Por	
  que/Para	
  que”	
  
Programar?	
  
5A
LC
M
	
  2
01
4.
1	
  
06
/0
2/
20
14
	
  
06/02/2014	
   5ALCM	
  2014.1	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Problemas	
  resolvidos	
  por	
  Algoritmos	
  
Ê  Projeto	
  Genoma	
  Humano	
  
Ê  Identificação	
  de	
  todos	
  os	
  100	
  mil	
  genes	
  no	
  DNA	
  humano,	
  
determinar	
  as	
  seqüências	
  dos	
  3	
  bilhões	
  de	
  pares	
  de	
  bases	
  
químicas	
  que	
  compõem	
  o	
  DNA	
  humano,	
  armazenar	
  essas	
  
informações	
  em	
  bancos	
  de	
  dados	
  e	
  desenvolvimento	
  de	
  
ferramentas	
  para	
  análise	
  de	
  dados.	
  
06/02/2014	
   5ALCM	
  2014.1	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Problemas	
  resolvidos	
  por	
  algoritmos	
  
Ê  Internet	
  
Ê  Permite	
  que	
  pessoas	
  de	
  todo	
  o	
  mundo	
  possam	
  acessar	
  e	
  
recuperar	
  grandes	
  quantidades	
  de	
  informação	
  rapidamente.	
  
Ê  Definir	
  melhor	
  rota	
  
Ê  Retornar	
  resultados	
  relevantes	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Como	
  a	
  busca	
  do	
  google	
  funciona?	
  
(Em	
  inglês)	
  
06/02/2014	
   5ALCM	
  2014.1	
  
06/02/2014	
   5ALCM	
  2014.1	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Self driving cars 
06/02/2014	
   5ALCM	
  2014.1	
  
06/02/2014	
   5ALCM	
  2014.1	
  
06/02/2014	
   5ALCM	
  2014.1	
  
06/02/2014	
   5ALCM	
  2014.1	
  
http://en.wikipedia.org/wiki/Timeline_of_computer_animation_in_film_and_television	
  
Problemas	
  resolvidos	
  por	
  algoritmos	
  
Ê  Diversas	
  outras	
  aplicações	
  
06/02/2014	
   5ALCM	
  2014.1	
  
06/02/2014	
   5ALCM	
  2014.1	
  
06/02/2014	
   5ALCM	
  2014.1	
  
O	
  que	
  é	
  um	
  algoritmo?	
  
06
/0
2/
20
14
	
  
5A
LC
M
	
  2
01
4.
1	
  
O conceito central da 
programação (e da c. 
computação) é o conceito 
de algoritmo! 
06/02/2014	
   5ALCM	
  2014.1	
  
Definição	
  
Ê  Um	
  conjunto	
  finito	
  de	
  regrasque	
  provê	
  uma	
  sequência	
  de	
  
operações	
  para	
  resolver	
  um	
  tipo	
  de	
  problema	
  específico	
  
[KNUTH]	
  
Ê  Uma	
  sequência	
  de	
  passos	
  que	
  visam	
  a	
  atingir	
  um	
  objetivo	
  
bem	
  definido	
  [FORBELLONE]	
  
Ê  Na	
  medida	
  em	
  que	
  precisamos	
  especificar	
  uma	
  sequência	
  de	
  
passos,	
  é	
  necessário	
  utilizar	
  ordem,	
  ou	
  seja,	
  “pensar	
  com	
  
ordem”,	
  portanto	
  precisamos	
  utilizar	
  lógica.	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Exemplos	
  de	
  algoritmos	
  
Ê  Uma	
  receita	
  de	
  bolo	
  
Ê  Instruções	
  para	
  se	
  instalar	
  um	
  equipamento	
  eletrônivo	
  
Ê  A	
  maneira	
  como	
  as	
  contas	
  de	
  serviços	
  básicos	
  (água,	
  luz,	
  
telefone	
  etc)	
  são	
  calculados	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Ainda	
  sobre	
  Algoritmos	
  
Ê  Um	
  algoritmo	
  é	
  qualquer	
  procedimento	
  computacional	
  bem	
  
definido	
  que	
  utiliza	
  como	
  entrada	
  um	
  valor	
  (ou	
  um	
  conjunto	
  
de	
  valores),	
  e	
  produz	
  como	
  saída	
  um	
  valor	
  (ou	
  um	
  conjunto	
  
de	
  valores).	
  
Ê  Um	
  algoritmo	
  é	
  então	
  uma	
  seqüência	
  de	
  passos	
  finitos	
  para	
  
atingir	
  um	
  objetivo	
  específico	
  (ou	
  seja,	
  transformar	
  entrada	
  
em	
  saída).	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Características	
  
Ê  Finito	
  
Ê  Não	
  ambíguo	
  
Ê  Gerar	
  saídas	
  
Ê  Efetivo	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Características	
  
06/02/2014	
   5ALCM	
  2014.1	
  
ALGORITMO	
  
LINGUAGEM	
  DE	
  
PROGRAMAÇÃO	
  
PROGRAMA	
  
Estrutura	
  de	
  um	
  algoritmo	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Entrada	
  
Processamento	
  
Saída	
  
Trocando	
  em	
  miúdos…	
  
Ê  Como	
  ordenar	
  uma	
  seqüência	
  qualquer	
  de	
  números	
  em	
  
ordem	
  crescente	
  ou	
  decrescente?	
  
06/02/2014	
   5ALCM	
  2014.1	
  
16	
   19	
   5	
   49	
   40	
  51	
   89	
  E:	
  
S:	
  
Algoritmos	
  de	
  ordenação	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Representação	
  de	
  Algoritmos	
  
Ê  Descrição	
  Narrativa	
  
Ê  Linguagem	
  natural	
  
Ê  Português	
  coloquial	
  
Ê  Fluxograma	
  
Ê  Representação	
  Gráfica	
  
Ê  Pseudocódigo	
  
Ê  Representação	
  textual	
  
Ê  Português	
  estruturado	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Descrição	
  Narrativa:	
  Troca	
  de	
  lâmpada	
  
1.  Pegar	
  uma	
  escada	
  
2.  Posicionar	
  a	
  escada	
  embaixo	
  da	
  lâmpada	
  
3.  Buscar	
  uma	
  lâmpada	
  nova	
  
4.  Subir	
  na	
  escada	
  
5.  Retirar	
  a	
  lâmpada	
  velha	
  
6.  Colocar	
  a	
  lâmpada	
  nova	
  
06/02/2014	
   5ALCM	
  2014.1	
  
E	
  se	
  a	
  lâmpada	
  não	
  estivesse	
  queimada?	
  
Troca	
  de	
  lâmpada	
  com	
  teste	
  
1.  Pegar	
  uma	
  escada	
  
2.  Posicionar	
  a	
  escada	
  embaixo	
  da	
  lâmpada	
  
3.  Buscar	
  uma	
  lâmpada	
  nova	
  
4.  Acionar	
  o	
  interruptor	
  
5.  Se	
  a	
  lâmpada	
  não	
  acender,	
  então	
  
1.  Subir	
  na	
  escada	
  
2.  Retirar	
  a	
  lâmpada	
  velha	
  
3.  Colocar	
  a	
  lâmpada	
  nova	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Troca	
  de	
  lâmpada	
  com	
  teste	
  no	
  início	
  
1.  Acionar	
  o	
  interruptor	
  
2.  Se	
  a	
  lâmpada	
  não	
  acender,	
  então	
  
1.  Pegar	
  uma	
  escada	
  
2.  Posicionar	
  a	
  escada	
  embaixo	
  da	
  lâmpada	
  
3.  Buscar	
  uma	
  lâmpada	
  nova	
  
4.  Subir	
  na	
  escada	
  
5.  Retirar	
  a	
  lâmpada	
  velha	
  
6.  Colocar	
  a	
  lâmpada	
  nova	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Troca	
  de	
  lâmpada	
  com	
  teste	
  e	
  repetição	
  
indefinida	
  
1.  Acionar	
  o	
  interruptor	
  
2.  Se	
  a	
  lâmpada	
  não	
  acender,	
  então	
  
1.  Pegar	
  uma	
  escada	
  
2.  Posicionar	
  a	
  escada	
  embaixo	
  da	
  lâmpada	
  
3.  Buscar	
  uma	
  lâmpada	
  nova	
  
4.  Subir	
  na	
  escada	
  
5.  Retirar	
  a	
  lâmpada	
  velha	
  
6.  Colocar	
  a	
  lâmpada	
  nova	
  
7.  Se	
  a	
  lâmpada	
  não	
  acender,	
  então	
  
1.  Retirar	
  a	
  lâmpada	
  queimada	
  
2.  Colocar	
  outra	
  lâmpada	
  nova	
  
3.  Se	
  a	
  lâmpada	
  não	
  acender,	
  então	
  
1.  …	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Até	
  quando?	
  
Troca	
  de	
  lâmpada	
  com	
  teste	
  e	
  condição	
  
de	
  parada	
  
1.  Acionar	
  o	
  interruptor	
  
2.  Se	
  a	
  lâmpada	
  não	
  acender,	
  então	
  
1.  Pegar	
  uma	
  escada	
  
2.  Posicionar	
  a	
  escada	
  embaixo	
  da	
  lâmpada	
  
3.  Buscar	
  uma	
  lâmpada	
  nova	
  
4.  Subir	
  na	
  escada	
  
5.  Retirar	
  a	
  lâmpada	
  velha	
  
6.  Colocar	
  a	
  lâmpada	
  nova	
  
7.  Enquanto	
  a	
  lâmpada	
  não	
  acender,	
  faça	
  
1.  Retirar	
  a	
  lâmpada	
  queimada	
  
2.  Colocar	
  outra	
  lâmpada	
  nova	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Estabelecemos	
  uma	
  	
  
condição	
  de	
  parada	
  
Exercício	
  1	
  
Ê  Descreva	
  com	
  detalhe	
  a	
  sequência	
  lógica	
  para	
  trocar	
  o	
  pneu	
  de	
  um	
  carro	
  
1.  Retirar	
  o	
  pneu	
  reserva	
  
2.  Retirar	
  o	
  macaco	
  
3.  Soltar	
  os	
  parafusos	
  do	
  pneu	
  
4.  Colocar	
  o	
  macaco	
  
5.  Elevar	
  o	
  carro	
  
6.  Retirar	
  os	
  parafusos	
  
7.  Retirar	
  o	
  pneu	
  
8.  Colocar	
  o	
  pneu	
  novo	
  
9.  Colocar	
  os	
  parafusos	
  
10.  Descer	
  o	
  carro	
  
11.  Guardar	
  o	
  pneu	
  velho	
  e	
  o	
  macaco	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Exercício	
  2	
  
Ê  Utilizando	
  linguagem	
  natural,	
  desenvolva	
  um	
  algoritmo	
  
para	
  somar	
  dois	
  números	
  e	
  multiplicar	
  o	
  resultado	
  pelo	
  
primeiro	
  número	
  
1.  Pedir	
  o	
  primeiro	
  número	
  ao	
  usuário	
  
2.  Pedir	
  o	
  segundo	
  número	
  ao	
  usuário	
  
3.  Somar	
  o	
  primeiro	
  e	
  segundo	
  número	
  
4.  Multiplicar	
  a	
  soma	
  pelo	
  primeiro	
  número	
  
5.  Exibir	
  o	
  resultado	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Exercício	
  3	
  
Ê  Um	
  homem	
  precisa	
  atravessar	
  um	
  rio	
  com	
  um	
  barco	
  que	
  
possui	
  capacidade	
  apenas	
  para	
  carregar	
  ele	
  mesmo	
  e	
  mais	
  
uma	
  de	
  suas	
  três	
  cargas,	
  que	
  são:	
  um	
  lobo,	
  um	
  bode	
  e	
  um	
  
maço	
  de	
  alfafa.	
  O	
  que	
  o	
  homem	
  deve	
  fazer	
  para	
  conseguir	
  
atravessar	
  o	
  rio	
  sem	
  perder	
  suas	
  cargas?	
  Escreva	
  um	
  
algoritmo	
  mostrando	
  a	
  resposta,	
  ou	
  seja,	
  indicando	
  todas	
  
as	
  ações	
  necessárias	
  para	
  efetuar	
  uma	
  travessia	
  segura.	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Linguagem	
  natural:	
  desvantagens	
  
Ê  Verbosidade	
  
Ê  Ambiguidade	
  
Ê  Ex:	
  “O	
  pregador	
  foi	
  grampeado	
  durante	
  o	
  conserto”	
  
06/02/2014	
   5ALCM	
  2014.1	
  
Fluxograma	
  
06/02/2014	
   5ALCM	
  2014.1	
  
06/02/2014	
   5ALCM	
  2014.1Fluxograma	
  –	
  Rep.	
  Gráfica	
  
06/02/2014	
   5ALCM	
  2014.1	
  
INÍCIO/FIM DECISÃO
PROCEDIMENTO CONECTOR
SAÍDA 
(IMPRESSÃO)ENTRADA MANUAL (TECLADO)