TDA Aula01b Programação de Computadores (rev 1)

Prévia do material em texto

<p>Apresentação do curso 1/34</p><p>Téc. de Desenvolv. de AlgoritmosTéc. de Desenvolv. de Algoritmos</p><p>Aula 01bAula 01b</p><p>Amilton Souza Martha</p><p>Luiz CD Gonçalves</p><p>Apresentação do curso 2/34</p><p>O que afinal é um programa?</p><p>● Um programa é uma sequência de comandos</p><p>correta que desencadeia uma determinada ação. Ex:</p><p>Um visualizador de imagens.</p><p>– Código fonte: o texto que digitamos, legível para</p><p>nós.</p><p>– Código executável: resulta num arquivo</p><p>executável, legível pela máquina</p><p>Apresentação do curso 3/34</p><p>O que é um algoritmo?</p><p>Definição de Algoritmo</p><p>● Algoritmo é a descrição de um conjunto de comandos</p><p>que, obedecidos, resultam numa sucessão finita de</p><p>ações.</p><p>● Etimologia da palavra</p><p>– Deriva do nome do matemático,</p><p>astrônomo e geógrafo da Pérsia</p><p>Mohammed Al-Khwārizmī (780 d.C.-</p><p>850 d.C.)</p><p>– Intelectual da Escola da Sabedoria de</p><p>Bagdá, território da Pérsia (atual Irã)</p><p>na época</p><p>Apresentação do curso 4/34</p><p>O que é um algoritmo?</p><p>Exemplo</p><p>● Um algoritmo é uma seqüência de instruções, que</p><p>resulta no cumprimento de uma determinada tarefa.</p><p>– Algoritmos não são necessariamente programas.</p><p>– Ex: uma receita de bolo, uma partitura musical, um</p><p>manual de utilização de um DVD. São algoritmos</p><p>que descrevem passo a passo o que fazer para</p><p>chegar a um resultado esperado.</p><p>Receita</p><p>•250g de farinha</p><p>•150g de margarina</p><p>•5 ovos</p><p>•2 colheres de fermento</p><p>•200 gramas de açúcar</p><p>1.Misturar os ingredientes</p><p>2.Cozinhar o bolo.</p><p>Apresentação do curso 5/34</p><p>O que é um algoritmo?</p><p>● Um algoritmo computacional deve contemplar 3</p><p>exigências:</p><p>– Instruções claras e sem ambiguidades, que não</p><p>impeçam as suas execuções pelo processador.</p><p>– A sequência de ações deve ser clara.</p><p>– Todas as instruções devem ser executadas num tempo</p><p>finito.</p><p>Apresentação do curso 6/34</p><p>O que é um algoritmo?</p><p>A representação</p><p>● Existem diversas formas de representação de algoritmos</p><p>(para escrever as receitas, no caso)</p><p>– Quanto maior o nível de detalhe menor a visão do todo do</p><p>algoritmo. Isso obscurece as idéias principais do</p><p>algoritmo.</p><p>– Geralmente é conveniente pensarmos apenas em nível</p><p>lógico, esquecendo da linguagem de programação</p><p>específica.</p><p>● Algumas formas de representação de algoritmos são</p><p>– Descrição Narrativa</p><p>– Fluxogramas</p><p>– Pseudo-código ou português estruturado</p><p>– A escrita diretamente na linguagem de programação</p><p>Apresentação do curso 7/34</p><p>O que é um algoritmo?</p><p>A representação - Descrição Narrativa</p><p>● Fornece a idéia geral do método</p><p>● Pouco rico em detalhes</p><p>● Geralmente é útil para fazer a descrição com um</p><p>pouco mais de detalhe do método</p><p>● Não intelegível pela máquina, claro.</p><p>● Ler 2 notas</p><p>● Calcular a média</p><p>● Imprimir aprovado se média maior ou igual a sete</p><p>● Se não tirou média, fazer exame</p><p>● Se média entre Média final e exame for maior ou igual a 5,</p><p>colocar aprovado, senão, colocar reprovado</p><p>● Ler 2 notas</p><p>● Calcular a média</p><p>● Imprimir aprovado se média maior ou igual a sete</p><p>● Se não tirou média, fazer exame</p><p>● Se média entre Média final e exame for maior ou igual a 5,</p><p>colocar aprovado, senão, colocar reprovado</p><p>Apresentação do curso 8/34</p><p>O que é um algoritmo?</p><p>A representação - Fluxogramas</p><p>● Fornece a idéia detalhada do</p><p>método</p><p>● Rico em detalhes</p><p>● Útil para fazer a descrição</p><p>com muito detalhe do método</p><p>● Intelegível pela máquina, com</p><p>softwares adequados</p><p>Apresentação do curso 9/34</p><p>O que é um algoritmo?</p><p>A representação - "Portugol"</p><p>● Fornece a idéia</p><p>geral do método</p><p>● Rico em detalhes</p><p>● Útil para fazer a</p><p>descrição com bom</p><p>de detalhe do</p><p>método</p><p>● Intelegível pela</p><p>máquina.</p><p>início</p><p>real media, nota1, nota2, exame, final;</p><p>escreva "Digite a 1ª nota: ";</p><p>leia nota1;</p><p>escreva "Digite a 2ª nota: ";</p><p>leia nota2;</p><p>media ← (nota1 + nota2)/2;</p><p>se (media >= 7)</p><p>escreva "Aprovado";</p><p>senão</p><p>escreva "Digite a nota de exame";</p><p>leia exame;</p><p>final ← (media + exame)/2;</p><p>se (final >= 5)</p><p>escreva "Aprovado";</p><p>senão</p><p>escreva "Reprovado";</p><p>fim se</p><p>fim se</p><p>fim</p><p>início</p><p>real media, nota1, nota2, exame, final;</p><p>escreva "Digite a 1ª nota: ";</p><p>leia nota1;</p><p>escreva "Digite a 2ª nota: ";</p><p>leia nota2;</p><p>media ← (nota1 + nota2)/2;</p><p>se (media >= 7)</p><p>escreva "Aprovado";</p><p>senão</p><p>escreva "Digite a nota de exame";</p><p>leia exame;</p><p>final ← (media + exame)/2;</p><p>se (final >= 5)</p><p>escreva "Aprovado";</p><p>senão</p><p>escreva "Reprovado";</p><p>fim se</p><p>fim se</p><p>fim</p><p>● Traduzível para</p><p>qualquer linguagem</p><p>● É o ideal.</p><p>● Praticamente igual ao</p><p>Algol/Pascal (daí a</p><p>designação Portugol)</p><p>Apresentação do curso 10/34</p><p>O que é um algoritmo?</p><p>A representação – Numa linguagem</p><p>● Fornece a idéia geral do método</p><p>● Pouco rico em detalhes</p><p>● Geralmente é útil para fazer a descrição com um</p><p>pouco mais de detalhe do método</p><p>● Não intelegível pela máquina, claro.</p><p>import javax.swing.*;</p><p>public class Algoritmo {</p><p>public static void main(String[] args) {</p><p>float media, nota1, nota2, exame, final;</p><p>nota1 = Float.parseFloat(JOptionPane.showInputDialog(</p><p>"Digite a 1ª nota:"));</p><p>nota2 = Float.parseFloat(JOptionPane.showInputDialog(</p><p>"Digite a 2ª nota:"));</p><p>media = (nota1 + nota2)/2;</p><p>if (media >= 7)</p><p>JOptionPane.showMessageDialog(null, "Aprovado");</p><p>else {</p><p>exame = Float.parseFloat(JoptionPane.showInputDialog(</p><p>"Digite a nota de exame"));</p><p>final = (media + exame)/2;</p><p>if (final >= 5)</p><p>JOptionPane.showMessageDialog(null, "Aprovado");</p><p>else</p><p>JOtionPane.showMessageDialog(null, "Reprovado");</p><p>}</p><p>}</p><p>}</p><p>import javax.swing.*;</p><p>public class Algoritmo {</p><p>public static void main(String[] args) {</p><p>float media, nota1, nota2, exame, final;</p><p>nota1 = Float.parseFloat(JOptionPane.showInputDialog(</p><p>"Digite a 1ª nota:"));</p><p>nota2 = Float.parseFloat(JOptionPane.showInputDialog(</p><p>"Digite a 2ª nota:"));</p><p>media = (nota1 + nota2)/2;</p><p>if (media >= 7)</p><p>JOptionPane.showMessageDialog(null, "Aprovado");</p><p>else {</p><p>exame = Float.parseFloat(JoptionPane.showInputDialog(</p><p>"Digite a nota de exame"));</p><p>final = (media + exame)/2;</p><p>if (final >= 5)</p><p>JOptionPane.showMessageDialog(null, "Aprovado");</p><p>else</p><p>JOtionPane.showMessageDialog(null, "Reprovado");</p><p>}</p><p>}</p><p>}</p><p>Apresentação do curso 11/34</p><p>O Java</p><p>Apresentação do curso 12/34</p><p>O JavaO Java</p><p>Características da Linguagem JavaCaracterísticas da Linguagem Java</p><p>● Possui uma coleção de APIs (Application</p><p>Programming Interfaces, bibliotecas) padrão que</p><p>auxiliam na construção de aplicativos</p><p>– Organizadas em pacotes (java.*, javax.* e extensões)</p><p>– Usadas pelos ambientes de execução (JRE) e de</p><p>desenvolvimento (SDK)</p><p>● As principais APIs são distribuídas juntamente com</p><p>os produtos para desenvolvimento de aplicações:</p><p>– Java 2 Standard Edition (J2SE): APIs essenciais para</p><p>qualquer aplicação Java (inclusive GUI)</p><p>– Java 2 Enterprise Edition (J2EE): APIs para o</p><p>desenvolvimento de aplicações distribuídas</p><p>– Java 2 Micro Edition (J2ME): APIs para o</p><p>desenvolvimento para aparelhos portáteis</p><p>Apresentação do curso 13/34</p><p>O JavaO Java</p><p>Plataformas para o desenvolvimentoPlataformas para o desenvolvimento</p><p>● Antes de qualquer instalação de</p><p>softwares é necessário instalar</p><p>– o JDK (link)</p><p>– o JRE (runtime que já deve estar</p><p>instalado na sua máquina) (link)</p><p>http://www.oracle.com/technetwork/java/javase/downloads/jdk-6u26-download-400750.html</p><p>http://www.java.com/pt_BR/download/</p><p>Apresentação do curso 14/34</p><p>O JavaO Java</p><p>Plataformas para o desenvolvimentoPlataformas para o desenvolvimento</p><p>● Comando de linha</p><p>– o básico</p><p>– programinhas como o do curso</p><p>● Dr. Java (http://www.drjava.org/)</p><p>– básico mas conveniente, rápido, mini-IDE, inglês</p><p>– programinhas como o do curso</p><p>● JCreator LE (http://www.jcreator.org)</p><p>– menos básico mas conveniente, rápido, IDE decente,</p><p>inglês</p><p>– programinhas como o do curso, projetos</p><p>● NetBeans/Eclipse</p><p>– complexo, lento, IDE sofisticada</p><p>– programinhas do outro curso, projetos gráficos</p><p>http://www.drjava.org/</p><p>http://www.jcreator.org/download.htm</p><p>Apresentação do curso 15/34</p><p>O Java</p><p>Comando de linha</p><p>Java Development Kit (JDK)</p><p>– Ferramentas para comando de linha: compilador,</p><p>depurador e outras. Necessário para a maior parte</p><p>das IDEs. (link)</p><p>– Para habilitar o ambiente via linha de comando é preciso</p><p>colocar o caminho $JAVA_HOME/bin</p><p>no PATH do</p><p>sistema</p><p>Java Runtime Environment (JRE)</p><p>– Tudo o que é necessário para executar aplicações Java</p><p>– JVM – Java Virtual Machine (Máquina Virtual Java)</p><p>– já deve estar instalado na sua máquina (link)</p><p>Um editor de texto ASCII (bloco de notas)</p><p>O prof dá todo o suporte</p><p>http://download.oracle.com/otn-pub/java/jdk/6u26-b03/jdk-6u26-windows-i586.exe</p><p>http://www.java.com/pt_BR/download/</p><p>Apresentação do curso 16/34</p><p>O JavaO Java</p><p>Comando de linhaComando de linha</p><p>$ javac Nome.java</p><p>Compilação: javac</p><p>A partir do diretório local</p><p>promove a compilação do</p><p>arquivo e resulta no arquivo</p><p>Nome.class</p><p>Execução: java</p><p>A partir do diretório local</p><p>onde Nome é o nome do</p><p>arquivo .class que</p><p>contém o main().</p><p>$ java Nome</p><p>Apresentação do curso 17/34</p><p>O JavaO Java</p><p>Dicas</p><p>● Convenciona-se que os identificadores (nomes) de</p><p>classes (programas) Java sempre possuem as iniciais</p><p>maiúsculas e por convenção também não usamos</p><p>acentuação</p><p>– MinhaClasseJava, Exercicio01,</p><p>TesteImpressao</p><p>• Um identificador com espaços é considerado pelo Java</p><p>como mais de um identificador.</p><p>Apresentação do curso 18/34</p><p>O JavaO Java</p><p>Comando de linhaComando de linha : : Dicas</p><p>● Para saber qual versão do java está instalada na</p><p>máquina executa-se o comando abaixo e resulta na saída</p><p>típica</p><p>● Erro comum: verifique sempre se o .class está no</p><p>diretório onde foi executado o java.</p><p>$ java -version</p><p>java version "1.6.0_22"</p><p>Java(TM) SE Runtime Environment (build 1.6.0_22-b04)</p><p>Java HotSpot(TM) Client VM (build 17.1-b03, mixed mode, sharing)</p><p>$</p><p>Apresentação do curso 19/34</p><p>• Algoritmo não computational</p><p>• Exemplos</p><p>• Receita</p><p>• Manual de instruções</p><p>• Depende da perícia do utilizador!</p><p>• Algoritmo computational</p><p> Manipular informação</p><p> Receber dados</p><p> Guardar dados</p><p> Devolver informação</p><p> Executar instruções</p><p> Fazer operações aritméticas</p><p> Fazer operações lógicas</p><p> Escolha entre várias instruções.</p><p> Repetir um conjunto de instruções</p><p>Um algoritmo</p><p>computacional é</p><p>uma sequencia de</p><p>passos tão bem</p><p>definida que até</p><p>um computador o</p><p>é capaz de a</p><p>executar</p><p>Algoritmos</p><p>Apresentação do curso 20/34</p><p> Problema</p><p> Conjunto das possíveis</p><p>entradas</p><p> Conjunto das saídas</p><p> Conjunto de operações</p><p>válidas</p><p> Solução Algorítmica</p><p> Conjunto ordenado</p><p>de operações válidas</p><p>que transformam o</p><p>conjunto de entradas</p><p>na saída desejada</p><p>Algoritmos</p><p>Componentes de um algoritmo</p><p>Apresentação do curso 21/34</p><p> Como se constroem algoritmos?</p><p> Trocar uma lâmpada queimada</p><p> Entrada</p><p> Lâmpada queimada</p><p> Lâmpada nova</p><p> Escada</p><p> Saída</p><p> Lâmpada nova funcionando</p><p> Operações válidas</p><p> Retirar a lâmpada</p><p> Colocar a lâmpada</p><p> Subir a escada</p><p> Descer a escada</p><p> Algoritmo 1</p><p> Subir a escada</p><p> Retirar a lâmpada</p><p>queimada</p><p> Colocar a lâmpada boa</p><p> Descer a escada</p><p>Algoritmos</p><p>Exemplo</p><p>Apresentação do curso 22/34</p><p> Como se constroem algoritmos?</p><p> Trocar uma lâmpada queimada</p><p> Entrada</p><p>– Lâmpada queimada</p><p>– Lâmpada nova</p><p>– Escada</p><p>– Lixo reciclado</p><p> Saída</p><p>– Lâmpada nova funcionando</p><p>– Lâmpada queimada no lixo</p><p> Operações válidas</p><p>– Retirar a lâmpada</p><p>– Colocar a lâmpada</p><p>– Subir a escada</p><p>– Descer a escada</p><p>– Jogarr a lâmpada no lixo</p><p> Descer a escada</p><p>Algoritmos</p><p>Exemplo</p><p> Algoritmo 2</p><p> Subir a escada</p><p> Retirar a lâmpada</p><p>fundida</p><p> Colocar a lâmpada boa</p><p> Descer a escada</p><p> Colocar a lâmpada</p><p>fundida no lixo</p><p>Apresentação do curso 23/34</p><p> Trocar uma lâmpada queimada</p><p> Entrada</p><p>– Lâmpada queimada</p><p>– Lâmpada nova</p><p>– Escada</p><p>– Lixo reciclado</p><p> Saída</p><p>– Lâmpada nova funcionando</p><p> Operações válidas</p><p> Retirar a lâmpada</p><p> Colocar a lâmpada</p><p> Subir a escada</p><p> Descer a escada</p><p> Deslocar a escada</p><p> Deitar a lâmpada no lixo</p><p> Algoritmo 3</p><p> Colocar a escada debaixo</p><p>da lâmpada</p><p> Colocar a lâmpada boa no</p><p>bolso</p><p> Subir a escada</p><p> Retirar a lâmpada fundida</p><p> Colocar a lâmpada boa</p><p> Descer a escada</p><p> Colocar a lâmpada fundida</p><p>na reciclagem</p><p> Arrumar a escada</p><p>É um bom algoritmo ?</p><p>Algoritmos</p><p>Exemplo</p><p>Apresentação do curso 24/34</p><p> Interagir com o utilizador</p><p> Realiza uma tarefa útil ao utilizador</p><p> Resolve o problema</p><p> Ser finito</p><p> Termina sempre e com o resultado previsto</p><p> Ser corretamente definido</p><p> Instruções claras que o utilizador consegue compreender e</p><p>seguir</p><p> Ser eficaz</p><p> Resolve sempre o problema mesmo nas situações mais</p><p>problemáticas</p><p> Ser eficiente</p><p> Utiliza o mínimo de recursos possível</p><p>Algoritmos</p><p>Características dos bons algoritmos</p><p>Apresentação do curso 25/34</p><p>1.1. InicioInicio</p><p>2.2. Suba um degrauSuba um degrau</p><p>3.3. Suba um degrauSuba um degrau</p><p>4.4. Suba um degrauSuba um degrau</p><p>5.5. Suba um degrauSuba um degrau</p><p>6.6. Suba um degrauSuba um degrau</p><p>7.7. Suba um degrauSuba um degrau</p><p>8.8. . . . .. . . .</p><p>9.9. FimFim</p><p>1.1. InicioInicio</p><p>2.2. Subir a escadaSubir a escada</p><p>3.3. FimFim</p><p>Algoritmos</p><p>Decomposição de algoritmos</p><p>Apresentação do curso 26/34</p><p>Algoritmos</p><p>Decomposição de algoritmos</p><p>1.1. InicioInicio</p><p>2.2. Suba um degrauSuba um degrau</p><p>3.3. Se não chegou ao topo vá para 2Se não chegou ao topo vá para 2</p><p>4.4. FimFim</p><p>1.1. InicioInicio</p><p>2.2. RepitaRepita</p><p>3.3. Suba um degrauSuba um degrau</p><p>4.4. Até chegar ao topoAté chegar ao topo</p><p>5.5. FimFim</p><p>1.1. InicioInicio</p><p>2.2. Enquanto não chegar ao topoEnquanto não chegar ao topo</p><p>3.3. Suba um degrauSuba um degrau</p><p>4.4. FimFim</p><p>Instruções válidas:Instruções válidas:</p><p>•Subir um degrauSubir um degrau</p><p>•Verificar se está no Verificar se está no</p><p>topotopo</p><p>Apresentação do curso 27/34</p><p>● O algoritmo não é a solução de um problema</p><p>– É uma forma de chegar-se à solução</p><p>● Não se aprende</p><p>– Copiando-se algoritmos</p><p>– Lendo-se algoritmos prontos</p><p>– Decorando-se algoritmos</p><p>● Aprende-se</p><p>– Construindo-se algoritmos</p><p>– Testando-se algoritmos</p><p>Conclusão</p><p>Apresentação do curso 28/34</p><p>● Qual é o problema.</p><p>– O que pretendemos do algoritmo</p><p>● Definir quais são os dados que entram</p><p>– Qual a situação inicial</p><p>– O que é necessário para resolver o problema</p><p>● Definir quais são os dados que saem</p><p>– Qual a situação final</p><p>– Que resultados devem ser apresentados</p><p>● Definir o Algoritmo</p><p>– Definir quais as instruções disponíveis/necessárias</p><p>– Organizar as instruções de forma a resolver o problema</p><p>● transformar as entradas em saídas</p><p>● Testar o algoritmo</p><p>– Verificar se resolve o problema</p><p>– Verificar se resolve todos os casos (ou quais)</p><p>● Otimizar o algoritmo</p><p>– Verificar se não utiliza recursos supérfluos</p><p>Conclusão</p><p>Apresentação do curso 29/34</p><p>Exercises</p><p>Apresentação do curso 30/34</p><p>● Uma pessoa vai de táxi a uma reunião de negócios.</p><p>Monte uma sequência de ações para que ela chegue ao</p><p>prédio onde vai ocorrer a reunião.</p><p>Ações</p><p>a)Entrar no prédio da reunião;</p><p>b)Sair do táxi;</p><p>c)Acenar para que o táxi pare;</p><p>d)Perguntar o preço da corrida;</p><p>e)Informar o destino ao motorista;</p><p>f)Esperar o táxi;</p><p>g)Pagar ao taxista;</p><p>h)Entrar no táxi.</p><p>Exercises</p><p>Esperar o táxi</p><p>Acenar para que o táxi pare</p><p>Entrar no táxi</p><p>Informar o destino ao motorista</p><p>Perguntar o preço da corrida</p><p>Pagar ao taxista;</p><p>Sair do táxi;</p><p>Entrar no prédio da reunião</p><p>Apresentação do curso 31/34</p><p>● Escreva um algoritmo para trocar o pneu de um</p><p>carro.</p><p>● Escreva um algoritmo para colocar gasolina num</p><p>posto de abastecimento Self-service.</p><p>● Escreva um algoritmo para telefonar de uma cabine</p><p>pública.</p><p>Exercises</p><p>Apresentação do curso 32/34</p><p>● Um barqueiro que possui uma lancha que leva 2</p><p>pessoas faz a travessia de um rio. Escreva um</p><p>algoritmo que resolva o problema da travessia de 3</p><p>pessoas.</p><p>– Resolva mesmo problema para a travessia de 10</p><p>pessoas</p><p>– Resolva o mesmo problema para a travessia de n</p><p>pessoas</p><p>● Para as n pessoas, resolva o</p><p>problema no qual a lancha leva</p><p>4 pessoas</p><p>Exercises</p><p>Apresentação do curso 33/34</p><p> Um homem, um lobo, um carneiro e um saco de alfaces</p><p>encontram-se do mesmo lado de um rio e querem</p><p>atravessá-lo. Para realizar a tarefa, existe uma canoa</p><p>que apenas transporta dois itens de cada vez. Como</p><p>fazer a travessia, tendo em conta que o lobo não pode</p><p>ficar sozinho com o carneiro e o carneiro não pode ficar</p><p>sozinho com o saco das alfaces .</p><p>E, claro, somente a homem dirige a canoa</p><p>Exercises</p><p>Apresentação do curso 34/34</p><p> Existem</p><p>duas jarras, uma de 3 litros e uma de 5 litros,</p><p>ambas vazias e nenhuma delas tem qualquer</p><p>marcação de medida. Existe uma fonte que pode ser</p><p>usada para encher ou despejar as jarras com água.</p><p> Como medir 4 litros de água?</p><p>3 5</p><p>Exercises</p><p>Slide 1</p><p>Slide 2</p><p>Slide 3</p><p>Slide 4</p><p>Slide 5</p><p>Slide 6</p><p>Slide 7</p><p>Slide 8</p><p>Slide 9</p><p>Slide 10</p><p>Slide 11</p><p>Slide 12</p><p>Slide 13</p><p>Slide 14</p><p>Slide 15</p><p>Slide 16</p><p>Slide 17</p><p>Slide 18</p><p>Slide 19</p><p>Slide 20</p><p>Slide 21</p><p>Slide 22</p><p>Slide 23</p><p>Slide 24</p><p>Slide 25</p><p>Slide 26</p><p>Slide 27</p><p>Slide 28</p><p>Slide 29</p><p>Slide 30</p><p>Slide 31</p><p>Slide 32</p><p>Slide 33</p><p>Slide 34</p>