aula_1

Prévia do material em texto

í 
CIÊNCIA DA COMPUTAÇÃO 
CONSTRUÇÃO DE ALGORITMOS 
1º SEMESTRE – 2011-1 
PROFESSOR JORGE BARBOSA DE SOUZA NETO 
CENTRO UNIVERSITÁRIO ANHANGUERA DE CAMPO GRANDE 
 
 
TÓPICOS IMPORTANTES 
 
 Apresentação; 
 Plano de Ensino e Aprendizagem; 
 PLT – Construção de Algoritmos; 
 Bibliografias complementares 
o ASCÊNCIO, A.F.G.; CAMPOS, Edilene V.C. et al. Fundamentos da programação de 
computadores: algoritmos, Pascal, C/C++ e JAVA. 2ª ed. São Paulo: PEARSON, 2007. 
 Datas importantes 
o 05/04/2011 – Atividades de avaliação e entrega 1ª e 2ª etapas ATPS; 
o 31/05/2011 – Prova escrita oficial e entrega 3ª e 4ª etapas ATPS; 
o 21/06/2011 – Prova substitutiva. 
 ATPS – Atividade Prática Supervisionada; 
 Avaliação 
o MF = (N1 + ATPS * P1) + (N2 + ATPS * P2) / 10; 
o MF = (7 + 3 * 4) + (7 + 3 * 6) / 10. 
 
 
INTRODUÇÃO À CONSTRUÇÃO DE ALGORITMOS 
 
 Objetivo 
o Apresentar os conceitos elementares de lógica e sua aplicação no cotidiano. Definir algoritmo. 
Estabelecer uma relação entre lógica e algoritmos: a lógica de programação. Exemplificar a 
aplicação dos algoritmos utilizando situações do dia-a-dia. Comparar as principais formas de 
representação dos algoritmos. 
 Noções de lógica 
o O que é? 
 Uso corriqueiro da palavra lógica está normalmente relacionado à coerência e à 
racionalidade. Freqüentemente se associa a lógica apenas à matemática, não se 
percebendo sua aplicabilidade e sua relação com as demais ciências. 
 Podemos relacionar com correção do pensamento; 
 Sua preocupação é determinar quais operações são válidas e quais não são; 
 Estuda a correção do raciocínio; 
 Exemplos de lógica: 
 Todo mamífero é um animal. 
Todo cavalo é um mamífero. 
Portanto, todo cavalo é um animal 
 
 Kaiton é país do planeta Stix. 
 Todos os Xinpins são de Kaiton. 
 Logo, todos os Xinpins são Stixianos. 
o Existe lógica no dia-a-dia? 
 Ordem no pensamento; 
 Exemplos de lógica no dia-a-dia: 
 A gaveta está fechada. 
A caneta está dentro da gaveta. 
Precisamos primeiro abrir a gaveta para depois pegar a caneta. 
 Anacleto é mais velho que Felisberto. 
Felisberto é mais velho que Marivaldo. 
Portanto, Anacleto é mais velho que Marivaldo. 
o E a lógica de programação? 
 Significa o uso correto das leis do pensamento; 
 Ordem da razão; 
 Processos de raciocínio e simbolização formais na programação de computadores; 
 Desenvolvimento de técnicas para produção de soluções logicamente válidas e 
coerentes que resolva problemas que deseja programar; 
 Objetivo principal do estudo da Lógica de Programação é a construção de algoritmos 
coerentes e válidos. 
o O que é um algoritmo? 
 Pode ser definido como uma seqüência de passos que visam a atingir um objetivo 
definido; 
 À medida que precisamos especificar uma seqüência de passos, é necessário ordem, ou 
seja, pensar com ordem, portanto precisamos utilizar lógica; 
 Algoritmos são comuns em nosso cotidiano, exemplo de uma receita de bolo (explicar). 
 Algoritmizando a lógica 
o Por que é importante construir um algoritmo 
 Um algoritmo tem por objetivo representar mais fielmente o raciocínio envolvido na 
Lógica de Programação e, dessa forma, permite-nos abstrair de uma série de detalhes 
computacionais, nos focando na lógica de programação; 
 Outra importância da construção de algoritmos é que uma vez concebida uma solução 
algorítmica para um problema, esta pode ser traduzida para qualquer linguagem de 
programação, chamamos de processo de codificação. 
o Vejamos exemplos 
 Podemos utilizar o português coloquial para escrever um algoritmo; 
 Às vezes não nos damos conta ou não nos atentamos a detalhes de ações que 
executamos para atingir um determinado objetivo como o exemplo abaixo; 
 Exemplo de algoritmo para troca de lâmpada: 
 Pegar uma escada; 
 Posicionar a escada embaixo da lâmpada; 
 Buscar uma lâmpada nova; 
 Subir na escada; 
 Retirar a lâmpada velha; 
 Colocar a lâmpada nova. 
 
 Seguimos uma determinada seqüência de ações que, representada nesse algoritmo, 
fazem com que outra pessoa possa seguir, estabelecendo um padrão de 
comportamento, pois qualquer pessoa agiria da mesma maneira; 
 A seqüênciação é uma convenção com o objetivo de reger o fluxo de execução do 
algoritmo, determinando qual a primeira ação a ser executada e qual ação vem a seguir; 
 Seqüência linear da esquerda para a direita e de cima para baixo; 
 Reexaminando o algoritmo, notamos que ele tem um objetivo definido: trocar a 
lâmpada, porém e se a lâmpada estiver queimada? 
 No algoritmo anterior a execução das ações conduziria a uma troca, 
independentemente de a lâmpada estar ou não queimada, não foi prevista essa 
possibilidade em sua construção; 
 Para solucionar podemos efetuar um teste como abaixo: 
 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 
o Subir na escada; 
o Retirar a lâmpada velha; 
o Colocar a lâmpada nova. 
 Agora estamos ligando algumas ações à condição lâmpada não acender, ou seja, se esta 
condição for verdadeira (lâmpada queimada) efetuaremos a troca da lâmpada, 
seguindo as próximas ações: 
 Subir na escada; 
 Retirar a lâmpada velha; 
 Colocar a lâmpada nova. 
 Se a condição lâmpada não acender for falsa (a lâmpada está funcionando), as ações 
relativas à troca da lâmpada não serão executadas, e a lâmpada não será trocada; 
 Neste algoritmo aconteceu a inclusão de um teste seletivo, através de uma condição 
que determina qual ou quais ações serão executadas dependendo da verificação da 
condição resultar em verdadeiro ou falso, veja que no algoritmo anterior todas as ações 
eram executadas; 
 Este algoritmo está correto, uma vez que atinge seu objetivo, porém pode ser 
melhorado: 
 Acionar o interruptor; 
 Se a lâmpada não acender, então 
o Pegar uma escada; 
o Posicionar a escada embaixo da lâmpada; 
o Buscar uma lâmpada nova; 
o Acionar o interruptor; 
o Subir na escada; 
o Retirar a lâmpada velha; 
o Colocar a lâmpada nova. 
 Vejamos que da ação pegar uma escada até colocar a lâmpada nova todas dependem 
da lâmpada estar efetivamente queimada; 
 Há muitas formas de resolver um problema, uma vez que cada pessoa pensa e age de 
maneira diferente; 
 Poderíamos ter diversas soluções diferentes e corretas (se atingissem o resultado 
desejado), portanto predominam o bom senso e a prática da lógica de programação 
para indicar a forma mais adequada; 
 A solução apresentada aparentemente é a mais adequada, porém não prevê a 
possibilidade de a lâmpada não funcionar e, portanto, não atingir o objetivo nessa 
situação específica; 
 Podemos melhorar esta solução de tal modo que a lâmpada seja trocada diversas vezes, 
se necessário, até que funcione; 
 Troca de lâmpada com teste e repetição indefinida: 
 Acionar o interruptor; 
 Se a lâmpada não acender, então 
o Pegar uma escada; 
o Posicionar a escada embaixo da lâmpada; 
o Buscar uma lâmpada nova; 
o Acionar o interruptor; 
o Subir na escada; 
o Retirar a lâmpada queimada; 
o Colocar a lâmpada nova; 
o Se a lâmpada não acender, então 
 Retirar a lâmpada queimada; 
 Colocar a lâmpada nova; 
 Se a lâmpada não acender, então 
 Retirar a lâmpada queimada; 
 Colocar a lâmpada nova; 
 ... 
 Até quando??? 
 Assim não sabemos o número de testes necessários para efetuar a troca da lâmpada; 
 Portanto para não reescrevermos várias vezes esse conjunto de ações, precisamos 
expressar essa repetição da ação determinando um limite para tal repetição, como 
objetivo de garantir a condição de parada; 
 Troca de lâmpada com teste e condição de parada: 
 Acionar o interruptor; 
 Se a lâmpada não acender, então 
o Pegar uma escada; 
o Posicionar a escada embaixo da lâmpada; 
o Buscar uma lâmpada nova; 
o Acionar o interruptor; 
o Subir na escada; 
o Retirar a lâmpada queimada; 
o Colocar a lâmpada nova; 
o Enquanto a lâmpada não acender, faça 
 Retirar a lâmpada queimada; 
 Colocar a lâmpada nova; 
 Foi estabelecido um fluxo repetitivo que será finalizado assim que a condição de parada 
for falsa, ou seja, assim que a lâmpada acender. Percebemos que o número de 
repetições é indefinido, porém é finito, e que depende apenas da condição 
estabelecida, que leva a repetir as ações até alcançar o objetivo (trocar a lâmpada 
queimada por uma nova); 
 Até agora estamos efetuando a troca de uma única lâmpada, na verdade estamos 
testando um soque (acionado por um interruptor), trocando tantas lâmpadas quantas 
forem necessárias para assegurar que o conjunto funcione; 
 Se tivéssemos mais soquetes a testar, por exemplo dez soquetes? 
 A solução mais óbvia aparentemente seria repetir o algoritmo de uma única lâmpada 
para os dez soquetes, ficando mais ou menos assim: 
 Acionar o interruptor do primeiro soquete; 
 Se a lâmpada não acender, então 
o Pegar uma escada; 
o Posicionar a escada embaixo da lâmpada; 
o Buscar uma lâmpada nova; 
o Acionar o interruptor; 
o Subir na escada; 
o Retirar a lâmpada queimada; 
o Colocar a lâmpada nova; 
o Enquanto a lâmpada não acender, faça 
 Retirar a lâmpada queimada; 
 Colocar a lâmpada nova; 
 Acionar o interruptor do segundo soquete; 
 Se a lâmpada não acender, então 
o Pegar uma escada; 
o Posicionar a escada embaixo da lâmpada; 
o ... 
 Acionar o interruptor do terceiro soquete; 
 Se a lâmpada não acender, então 
 ... 
 Acionar o interruptor do quarto soquete; 
 ... 
 Acionar o interruptor do décimo soquete; 
 ... 
 Percebe-se que foram repetidas dez vezes a troca de lâmpada sendo para dez soquetes, 
e se fossem 100 soquetes? Teríamos que repetir 100 vezes a troca de lâmpada, 
portanto usando o bom senso e o melhor uso da lógica de programação o algoritmo 
seria: 
 
 
 
 
 
 
 
 Ir até o interruptor do primeiro soquete; 
 Enquanto a quantidade de soquetes testados for menor que dez, faça 
o Acionar o interruptor; 
o 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 a lâmpada queimada; 
 Colocar a lâmpada nova; 
 Enquanto a lâmpada não acender, faça 
 Retirar a lâmpada queimada; 
 Colocar a lâmpada nova; 
 Ir até o interruptor do próximo soquete; 
 Observe que quando a condição quantidade de soquetes testados for menor que dez 
for verdadeira, as ações serão executadas. Caso a condição de parada seja falsa, ou seja, 
todos os dez soquetes já tiverem sido testados, nada mais será executado; 
 Todo o exemplo foi desenvolvido a partir do problema de descrevermos os passos 
necessários para efetuar a troca de lâmpada, ou seja, construir um algoritmo para esse 
fim; 
 Inicialmente tínhamos um pequeno conjunto de ações que deveriam ser executadas 
todas passo a passo, uma após a outra, compondo uma ordem seqüencial de execução, 
a estrutura seqüencial; 
 Nota-se que nem sempre todas as ações são previstas e podemos sempre melhorar o 
algoritmo; 
 Qualquer pessoa, fundamentada de experiência poderia resolver este problema na 
prática, envolvendo inclusive circunstâncias inusitadas que pudessem surgir; 
 Um programa de computar não é dotado de experiências (não tem conhecimento 
prévio e nem adquire experiências), o que implica que devemos determinar em 
detalhes todas as ações que ele deve executar, prevendo todos os obstáculos, isto é 
descrever uma seqüência finita de passos que garantam a solução do problema. 
o De que maneira podemos representar um algortimo? 
 Até agora representamos o algoritmo de forma textual usando o português coloquial, 
podemos também representar de forma gráfica utilizando o fluxograma: 
 
 
 
 
 
 
 
 
 
 
 
 
início 
fim 
Ir para o primeiro soquete 
Soquetes 
testados < 10 
Acionar o interruptor 
Lâmpada não 
acendeu? 
Pegar uma escada 
Colocar a escada embaixo do soquete 
Buscar uma lâmpada nova 
Acionar o interruptor 
Subir na escada 
Retirar a lâmpada queimada 
Colocar a lâmpada nova 
Lâmpada não 
acendeu? 
Retirar a lâmpada queimada 
Colocar a lâmpada nova 
Ir para o próximo soquete 
F 
F 
F 
V 
V 
V