Baixe o app para aproveitar ainda mais
Prévia do material em texto
Linguagens de Programação Profa. Amanda Rocha Chaves amanda.chaves@ufvjm.edu.br http://sites.google.com.br/site/lpufvjmbct ALGORITMOALGORITMO Introdução Algoritmo Qual o significado dessa palavra? Significado desconhecido... Utilizamos algoritmos no nosso dia-a-dia constantemente. Como fazer um computador resolver um problema? Resolução de problemas Ao nos deparamos com um problema e desejamos utilizar um computador para resolvê-lo, devemos seguir os seguintes passos: 1. Descrever o problema de forma clara e precisa. 2. Encontrar um sequência de passos que permitam que o problema possa ser resolvido de maneira automática e repetitiva. 3. Definir como os dados que serão processados serão armazenados no computador. Como fazer um computador resolver um problema? Resolução de problemas Ao nos deparamos com um problema e desejamos utilizar um computador para resolvê-lo, devemos seguir os seguintes passos: 4. Utilizar uma linguagem de programação para escrever o programa que deverá, a princípio, resolver o problema. 5. Verificar se o problema foi resolvido. Solução de um problema via computador: Resolução de problemas Baseia-se, portanto, em dois pontos: 1. Forma como os dados são armazenados. 2. Sequência de passos. Algoritmo Definições de algoritmo 1. Um procedimento passo a passo para a solução de um problema. 2. Uma seqüência detalhada de ações a serem executadas para realizar alguma tarefa. Exemplos de algoritmo 1. Uma receita de bolo. 2. Instruções para se utilizar um microondas. 3. A maneira como as contas de água, luz e telefone são calculadas mensalmente. Exemplo de algoritmo Receita para se preparar um bolo: Ingredientes: Modo de preparo: • 2 xícaras (chá) de farinha de trigo. • 1 xícara (chá) de açúcar cristal. • 1 colher (sopa) de fermento em pó. • 1 pitada de sal. • 3 ovos. • 2 colheres de manteiga. • 1 xícaras (chá) de leite. • Óleo para untar. • Farinha de trigo para polvilhar. 1. Numa vasilha, misture 2 xícaras (chá) de farinha de trigo, 1 xícara (chá) de açúcar cristal, 1 colher (sopa) de fermento em pó, 2 colheres de manteiga e 1 pitada de sal. Junte 3 ovos e 1 xícara (chá) de leite. Misture bem. 2. Unte uma forma retangular de 25 cm x 37 cm com óleo. 3. Polvilhe farinha de trigo e despeje a massa. 4. Asse em temperatura média (de 170°C a 180°C) por 30 minutos. Algoritmo Um algoritmo opera sobre um conjunto de entradas (no caso do bolo, farinha ovos, fermento, etc.) de modo a gerar uma saída que seja útil (ou agradável) para o usuário (o bolo pronto). Entrada Sequência detalhada de passos Saída Tarefa: Fazer um bolo Algoritmo: características 1. Finitude: Um algoritmo deve sempre terminar após um número finito de passos. 2. Definição: Cada passo de um algoritmo deve ser precisamente definido. As ações devem ser definidas rigorosamente e sem ambiguidades, ou seja, não devem dar margem à dupla interpretação. 3. Entradas: Um algoritmo deve ter zero ou mais entradas, isto é, dados que lhe são fornecidos antes de iniciar. Algoritmo: características 4. Saídas: Um algoritmo deve gerar uma ou mais saídas. 5. Efetividade: Um algoritmo deve ser efetivo. Isto significa que todas as operações devem ser suficientemente básicas de modo que possam ser em princípio executadas com precisão em um tempo finito por um humano usando papel e lápis. Algoritmo Todos sabemos construir algoritmos. COMO? Pode haver mais de um algoritmo para resolver um determinado problema. Algoritmos Problema 1: Dispomos de duas vasilhas com capacidades de 9 e 4 litros respectivamente. As vasilhas não tem nenhum tipo de marcação, de modo que não é possível ter medidas como metade ou um terço. Mostre uma sequência de passos, que usando as vasilhas de 9 e 4 litros encha uma terceira vasilha de medida desconhecida com seis litros de água. Algoritmos Possível solução do problema 1: 1. Encha a vasilha de 9 litros; 2. Usando a vasilha de 9 litros, encha a vasilha de 4 litros; 3. Despeje o que sobrou na vasilha de 9 litros (5 litros) na terceira vasilha. Observe que falta um litro para completar os seis litros; 4. Esvazie a vasilha de 4 litros; 5. Torne a encher a vasilha de 9 litros; 6. Usando a vasilha de 9 litros encha a vasilha de 4 litros; 7. Esvazie a de 4 litros; 8. Usando o que restou na vasilha de 9 litros (5 litros), encha novamente a vasilha de quatro litros; 9. Despeje o que sobrou na vasilha de 9 litros (1 litro) na terceira vasilha, que agora tem 6 litros. Algoritmos Problema 2: As torres de Hanoi Algoritmos Problema 2: As torres de Hanoi Inicialmente têmse três hastes A, B e C, e na haste A repousam três anéis de diâmetros diferentes, em ordem decrescente por diâmetro. Objetivo: Transferir os três aneis da haste A para B, usando C , se necessário, obedecendo às seguintes regras: a) Devese mover um único anel por vez. b) Um anel de diâmetro maior nunca pode repousar sobre algum outro de diâmetro menor. Algoritmo Início 1. Mover um anel da haste A para a haste B. 2. Mover um anel da haste A para a haste C. 3. Mover um anel da haste B para a haste C. 4. Mover um anel da haste A para a haste B. 5. Mover um anel da haste C para a haste A. 6. Mover um anel da haste C para a haste B. 7. Mover um anel da haste A para a haste B. Fim Possível solução do problema 2: Algoritmos Problema 2: As torres de Hanoi Movimentação mínima: 2n-1 Onde n representa o número de discos Algoritmo e Computação Por que a palavra ALGORITMO ficou tão associada à computação? Para responder essa pergunta devemos entender um pouco sobre o funcionamento dos computadores Algoritmo e Computação Como criar um programa de computador? Como executá-lo? Como um programa é visto pelo computador? Funcionamento de um computador Contém um conjunto relativamente pequeno de instruções que é capaz de executar. Programa de computador Conjunto de instruções que será executado pelo processador em uma determinada sequência. Esse programa leva o computador a executar alguma tarefa. Um programa nada mais é que um tipo de Algoritmo Algoritmo x programa Particularidade de um programa: As operações de um programa são específicas para o computador e restritas ao conjunto de instruções que o processador pode executar. Podemos considerar esse conjunto de instruções como a primeira linguagem de programação do computador, também chamada de linguagem de máquina. 0101010101110101011010111010101010101011101010110101110101001010101011101010110101110101010 1010111010101101011101010010101010010111010111101010110101110101001010101011101010110101110 1010010101010111010101101011101010010101010111010101111101010110101110101001010101011101010 Linguagens de programação Classificação segundo sua proximidade com a linguagem de máquina • Linguagens de baixo nível o Linguagem de montagem (assembly): possui uma instrução alfanumérica para cada instrução numérica em linguagem de máquina. • Linguagens de alto nível: se aproximam da linguagem natural o C, Pascal, C++, Java, PHP, Python, etc. Linguagens de programação Classificação segundo sua proximidade com a linguagem de máquina Para cada processador, há uma linguagem de montagem já que há uma relação direta entre as instruções em linguagem de montagem e em linguagem de máquina. Linguagens de programação Assembly: problemas • A implementação de programas nesse tipo de linguagem ainda é muito complexa e dependente do conhecimento das instruções do processador. • Para aumentar a produtividade dos programadorese a portabilidade dos programas, foram criadas as linguagens de programação de alto nível. Linguagens de programação Linguagens de alto nível • Essas linguagens são independentes do processador em que serão executadas. • Seu código é mais elaborado, contemplando operações mais complexas e mais próximas da “lógica humana”. • Para que possam ser processadas por um computador, os comandos da linguagem precisarão ser traduzidos para a linguagem de máquina. Linguagens de programação Linguagens de alto nível • A tradução da linguagem de alto nível para a linguagem de máquina é feita por meio de: o Compilador o Interpretador Compilação de um programa Código Objeto O código-objeto fica em disco e só é carregado para a memória no momento da execução. O interpretador faz o mesmo trabalho, porém não gera o arquivo em código-objeto. Interpretação de um programa As instruções são traduzidas para a linguagem de máquina em tempo de execução, instrução por instrução. Linguagens de alto nível Vantagens: • Aumento de produtividade. • Portabilidade de programas, ou seja, independência de plataforma mediante nova compilação do código-fonte. Linguagens de programação e SO SO (Sistemas Operacionais): Os SO constroem uma camada entre hardware e software, facilitando a utilização dos recursos da máquina real por meio da criação de uma máquina virtual. Linguagens de programação e SO SO (Sistemas Operacionais): recursos Arquivos • Permitem a manipulação de dados em disco sem que seja necessário o conhecimento dos detalhes do funcionamento dos discos, como trilhas, setores, velocidade da rotação, posicionamento dos dados no disco e outros mais. Gerência de recursos da máquina: • evita a má utilização e até mesmo a danificação de seus componentes por um programador. Linguagens de programação e SO SO (Sistemas Operacionais): recursos Interfaces a operações complexas que outros programas podem utilizar • As interfaces são denominadas CHAMADAS DE SISTEMAS (System Calls) • As operações são disponibilizadas em bibliotecas do sistema. • Os compiladores utilizam essas interfaces Linguagens de programação e SO Integração dos Compiladores com o SO Linking O código-objeto torna-se portável para qualquer máquina que utilize o mesmo SO. Portabilidade de Java Linguagens de programação Problema: Imprimir na tela uma mensagem de boas vindas. Assembly variable: .message db “Sejam bem vindos ao curso de LP!$” code: mov ah,9 mov dx,offset .message int 0x21 ret Linguagens de programação Problema: Imprimir na tela uma mensagem de boas vindas. C #include <stdio.h> main() { printf(“Sejam bem vindos ao curso de LP!”); } Linguagens de programação Problema: Imprimir na tela uma mensagem de boas vindas. Pascal Program ola; Begin writeln(“Sejam bem vindos ao curso de LP!”); end. Linguagens de programação Problema: Imprimir na tela uma mensagem de boas vindas. Java public class Ola { public static void main(String[] args) { System.out.println(“Sejam bem vindos ao curso de LP!”); } } Algoritmo Problema: Imprimir na tela uma mensagem de boas vindas. Portugol – Português estruturado algoritmo "olá" Inicio escreva( “Sejam bem vindos ao curso de LP!”); fim Linguagens de programação O que vimos? As linguagens de programação de alto nível se aproximam da lógica humana de resolver problemas. Contudo: Ainda é complicado resolver um problema utilizando uma LP, pois as pessoas não estão acostumadas a construir algoritmos. Linguagens de programação AS LPs se diferenciam da Linguagem Natural • É dirigida para orientar máquinas e não pessoas. As máquinas: • Não tomam decisões com base em premissas. • Não escolham alternativas, mesmo que nos sejam óbvias. • Não corrigem comandos mal redigidos. • Não podem descobrir a intenção do programador. Linguagens de programação As linguagens de programação precisam ter: Rigidez sintática • O compilador é um tradutor relativamente limitado, que só consegue fazer as traduções sobre um idioma bastante limitado, com construções muito bem definidas. Linguagens de programação As linguagens de programação precisam ter: Rigidez semântica • O computador definitivamente não pode lidar com ambiguidades. • Por isso, não adianta o programador ter uma intenção se não conseguir exprimi-la de forma exata. • Podemos dizer que o computador é um ótimo cumpridor de ordens, porém não tem idéia de quais ordens está cumprindo, nem o contexto em que essas ações estão inseridas. Linguagens de programação As linguagens de programação precisam ter: Rigidez semântica • Diferentemente da linguagem de programação, a linguagem natural apresenta ambiguidades. • Veja o exemplo: “A menina ouviu o barulho da janela”. Interpretações possíveis: 1. A menina ouviu o barulho produzido pela janela. 2. A menina estava junto à janela e ouviu o barulho. 3. A menina ouviu o barulho que veio através da janela. Qual linguagem utilizar para a escrita de algoritmos? Natural ou de programação? Qual linguagem utilizar para a escrita de algoritmos? Natural ou de programação? Linguagens Representação de Algoritmos Linguagem Natural Os algoritmos são expressos diretamente em linguagem natural, como nos primeiros exemplos citados. Fluxograma Esta é um representação gráfica que emprega formas geométricas padronizadas para indicar as diversas ações e decisões que devem ser executadas para resolver o problema. Pseudo-linguagem Emprega uma linguagem intermediária entre a linguagem natural e uma linguagem de programação para descrever os algoritmos. Representação de Algoritmos Fluxograma Representação de Algoritmos Fluxograma: símbolos Terminador Processo Entrada manual Decisão Exibição Conector Conector de página Fluxo Representação de Algoritmos Pseudocódigo Algoritmos: exercícios 1. Crie um algoritmo, representando-o em um fluxograma, que exiba na tela uma mensagem para o usuário. 2. Crie um algoritmo, representando-o em um fluxograma, que some dois números digitados pelo usuário e exiba na tela o resultado dessa soma. 3. Crie um algoritmo, representando-o em um fluxograma, que leia a média final de um aluno e verifica e exiba na tela se o aluno foi aprovado (média final maior ou igual a 60), reprovado(média final menor ou igual a 40) ou se ficou em exame final (média final maior que 40 e menor que 60). Algoritmos: exercícios 4. Defina o que é um algoritmo. 5. Diferencie um algoritmo de um programa. 6. Explique como um programa é executado em um computador. 7. Defina o que é uma linguagem de programação de alto nível e uma linguagem de programação de baixo nível. 8. Dado um programa executável em um sistema operacional, o que é preciso fazer para que tal programa possa ser utilizado em outro sistema operacional? 9. Explique por que um código Java é portável em vários sistemas operacionais. 10. Por que a linguagem natural não é adequada para a construção de algoritmos para computador? 11. Quais as vantagens e desvantagens da utilização de fluxograma e de pseudocódigo na construção de algoritmos? Linguagens de Programação Slide 2 Slide 3 Slide 4 Slide 5 Slide 6 Slide 7 Slide 8 Slide 9 Slide 10 Slide 11 Slide 12 Slide 13 Slide 14 Slide 15 Slide 16 Slide 17 Slide 18 Slide 19 Slide 20 Slide 21 Slide 22 Slide 23 Slide 24 Slide 25 Slide 26 Slide 27 Slide 28 Slide 29 Slide 30 Slide 31 Slide 32 Slide 33 Slide 34 Slide 35 Slide 36Slide 37 Slide 38 Slide 39 Slide 40 Slide 41 Slide 42 Slide 43 Slide 44 Slide 45 Slide 46 Slide 47 Slide 48 Slide 49 Slide 50 Slide 51 Slide 52 Slide 53 Slide 54
Compartilhar