Baixe o app para aproveitar ainda mais
Esta é uma pré-visualização de arquivo. Entre para ver o arquivo original
DADE DE TECNOLOGIA TECBRASIL Aula 1 – Algoritmos PARTE 1 INTRODUÇÃO Construir algoritmos é objetivo fundamental de toda a programação. Algoritmo é uma sequência de passos que visam atingir um objetivo bem definido (Forbellone, 1999). Em geral, um algoritmo destina-se a resolver um problema: _ Fixa um padrão de comportamento a ser seguido. _ Uma norma de execução a ser trilhada. _ Com o objetivo de alcançar, como resultado final, a solução de um problema. Algumas qualidades essenciais de um bom algoritmo são as seguintes: a) Clareza: que as ações sejam expressas de forma clara e sem ambigüidades. b) Eficácia: deve chegar a um resultado final. c) Eficiência: deve obter resultado com a melhor relação custo/benefício. NOÇÕES DE LÓGICA A Lógica trata da correção do pensamento. Como filosofia, ela procura saber por que pensamos assim e não de outra forma. Como arte ou técnica, ela nos ensina a usar corretamente as leis do pensamento. Pode-se ainda dizer que a Lógica tem em vista a “ordem da razão”. Isto dá a entender que a nossa razão pode funcionar desordenadamente. Por isso, a Lógica ensina a colocar ordem no pensamento. Exemplo: a) Todo mamífero é animal. Todo cavalo é mamífero. Portanto, todo cavalo é animal. Lógica no dia-a-dia: Sempre que pensamos, a Lógica ou a falta de Lógica, nos acompanha necessariamente. Também quando falamos, pois a palavra falada é a representação do pensamento; e, visto que a palavra escrita é a representação da palavra falada, também pensamos quando escrevemos, utilizando a Lógica ou a falta de Lógica. Daí percebe se a importância da Lógica nas nossas vidas, não só na teoria, como também na prática, já que para pensar, falar ou escrever corretamente é necessário colocar ordem no pensamento, e isto é, utilizar Lógica. Exemplo: a) A gaveta está fechada. A caneta está na gaveta. Preciso primeiro abrir a gaveta, para depois pegar a caneta. CONCEITOS DE ALGORITMO “Algoritmo é a descrição de uma sequência de passos que deve ser seguida para a realização de uma tarefa” (Ascencio 1999 apud Ascencio 2002). “Algoritmo é uma sequencia finita de instruções ou operações cuja execução, em tempo finito, resolve um problema computacional, qualquer que seja sua instância” (Salvetti 1999 apud Ascencio 2002). “Algoritmo são regras formais para a obtenção de um resultado ou da solução de um problema, englobando fórmulas de expressões aritméticas” (Manzano 1997 apud Asencio 2002). "Algoritmo é um conjunto finito de regras, bem definidas, que nos levam à solução de um problema em um tempo finito." "Algoritmo é a descrição de um conjunto de ações que, obedecidas, resultam numa sucessão finita de passos, atingindo o objetivo." “Do ponto de vista computacional, um algoritmo pode ser entendido como a definição de passos a partir do entendimento lógico de um problema realizado por um programador com o objetivo de transformar esse problema em um elemento (programa) que seja possível de ser tratado e executado por um computador.” (Ordem de Pensamento e, portanto, Lógica) Analisando as definições anteriores, pode-se observar que executamos vários algoritmos no nosso diaa- dia, como: “Somar 3 números”, “Fazer um sanduíche”, “Trocar uma lâmpada”, “Ir para a faculdade”, “Sacar dinheiro do banco 24h”. Existem várias formas de executar as atividades acima. Cada pessoa executa as atividades de forma diferente, da forma como sabe, como tem conhecimento. Essas várias formas de fazer as atividades são corretas, por existem inúmeras maneiras de se resolver um problema, isto é, podem existir vários algoritmos para resolver um mesmo problema. ALGORITMOS Para descrever um algoritmo, pode-se usar representações gráficas ou textuais. O uso dessas representações vai depender do grau de detalhamento que se deseja de um algoritmo. As principais formas de representação de um algoritmo são: _ Algoritmos naturais; _ Fluxograma convencional; _ Diagrama de Chapin; _ Pseudocódigo ou metalinguagem. ALGORITMOS NATURAIS São algoritmos usados no nosso dia-a-dia, descritos em linguagem natural, como por exemplo, uma receita culinária, a troca de um pneu furado ou a troca de uma lâmpada. Além dos que usamos no nosso dia-a-dia, os algoritmos são muito usados para a especificação de tarefas que devem ser repetidas sempre da mesma maneira. Para automatizar uma tarefa, é fundamental descrever seus passos de forma detalhada e clara, para que qualquer um que venha a executá-la, saiba exatamente o que fazer. Assim, se uma indústria precisa que uma tarefa seja automatizada, deve descrevê-la através de um algoritmo. Este algoritmo poderá ser lido por um operário ou transformado em programa para uma máquina. Para programar computadores são necessários, também, algoritmos que, traduzidos para a linguagem de programação do computador, farão com que este execute as tarefas desejadas. Existem várias formas de se representar um algoritmo. Pode-se escrevê-lo através da linguagem natural que usamos no dia-a-dia. Esta maneira, porém, pode levar a muitas ambigüidades. Por exemplo, a instrução "afrouxar ligeiramente as porcas" num algoritmo de troca de pneus está sujeita a interpretações diferentes por pessoas distintas. Uma instrução mais precisa seria: “afrouxar a porca, girando a 30º no sentido anti-horário”. MÉTODO PARA CONSTRUÇÃO DE ALGORITMOS A construção de um algoritmo é um procedimento bastante particular de cada pessoa, pois envolve o raciocínio de cada indivíduo, suas experiências anteriores, seus hábitos e sua criatividade. O mesmo problema apresentado a um grupo de pessoas, provavelmente terá soluções completamente diversas, apesar de todas funcionarem. Mesmo assim, há algumas dicas que podem ajudar na organização do raciocínio no momento da elaboração de um algoritmo: a) Ler atentamente o enunciado: É justamente o enunciado do exercício que fornece o encaminhamento necessário à resolução do problema, que se torna, portanto, dependente de sua completa compreensão. b) Retirar do enunciado a relação das entradas de dados: A entrada é o meio pelo qual o usuário pode informar dados que serão utilizados pelo programa em seu processamento. Através do enunciado podemos descobrir quais são os dados que devem ser fornecidos, a partir dos quais desenvolveremos os cálculos. A entrada é feita pelo comando leia. c) Retirar do enunciado a relação das saídas de dados: Para que o usuário possa ter acesso aos resultados do processamento do programa, toda linguagem de programação fornece mecanismos de apresentação (saída) dos dados. Através do enunciado podemos descobrir quais são os dados que devem ser emitidos para compor o resultado final, objetivo do algoritmo. A saída é feita pelo comando escreva. d) Determinar o que deve ser feito para transformar as entradas determinadas nas saídas especificadas: Nesta fase é que teremos a construção do algoritmo propriamente dito, pois, a partir de alguns requisitos especificados, devemos determinar qual seqüência de ações é capaz de transformar um conjunto definido de dados nas informações de resultado. e) Construir o algoritmo: Com base no conhecimento disponível a respeito do problema (passos anteriores), podemos montar o algoritmo definitivo. Ex.: Calcular a média final dos alunos de uma disciplina. Os alunos realizaram 2 provas: P1 e P2. Onde a média final = (P1+P2) / 2. Para montar o algoritmo proposto faremos 3 perguntas: 1) Quais são os dados de entrada? P1 e P2. 2) Qual será o processamento? Somar os dados de entrada e dividir o resultado por 2 (P1+P2)/2. 3) Quais serão os dados de saída? O resultado do processamento, ou seja, a média final. início Informar nota da prova 1 Informar nota da prova 2 Somar todas as notas e dividir o resultado por 2 Mostrar o resultado da divisão fim f) Testar (executar) o algoritmo: Implica executar todas as ações descritas segundo o fluxo de execução estabelecida, verificando se os resultados obtidos correspondem ao esperado da montagem do algoritmo, detectando então algum possível erro no desenvolvimento deste. Essa atividade é conhecida por “teste de mesa”. TIPOS DE ALGORITMOS Os três tipos de algoritmos mais usados são mostrados abaixo. Considere o problema abaixo e observe como o mesmo é escrito nos diferentes tipos. PROBLEMA: Faça um algoritmo para mostrar o resultado da multiplicação de dois números. 1) Descrição Narrativa: consiste em analisar o enunciado do problema e escrever a solução do problema em linguagem natural. 2) Fluxograma: consiste em analisar o enunciado do problema e escrever a solução do problema utilizando símbolos gráficos pré-definidos. 3) Pseudocódigo ou Portugol: consiste em analisar o enunciado do problema e escrever a solução do problema por meio de regras pré-definidas. CONCEITO DE VARIÁVEL Para resolver problemas no computador é necessário manipular dados, sejam números ou caracteres. Se é necessário calcular o resultado de um único cálculo, provavelmente, a melhor solução seria uma calculadora. No entanto, quando é necessário calcular e armazenar vários cálculos e seus resultados, a solução indicada é utilizar programas de computador. A utilidade de se escrever um programa aparece quando necessitamos trabalhar com muita informação ao mesmo tempo. Uma variável, é um tipo de dado, armazenado na memória do computador que pode receber e armazenar dados (números e caracteres), informações e conhecimentos. As variáveis são identificadas por um nome único e caracterizada por um tipo de variável, de acordo com o tipo de dado que será armazenado. ATRIBUIÇÃO DE VALORES Para um programa, uma variável é um pedaço de memória identificado de alguma forma onde serão armazenados dados. Existem várias maneiras de indicarse a atribuição de um valor a uma variável: A = 5 b := b + 4 d ← 8 E uma linguagem de programação isto é feito pela mais fundamental das instruções, denominada de “instrução de atribuição”. A sintaxe (maneira como se escreve) varia de acordo com a linguagem de programação, e o funcionamento é simples: após a execução da instrução pelo computador, a variável (o pedaço de memória com um nome ) recebe o valor indicado. Exemplo: x = 10 ESTRUTURA DE UM ALGORITMO Na criação de algoritmos, utilizam-se os conceitos de bloco lógico, entrada e saída de dados, variáveis, constantes, atribuições, expressões relacionais e aritméticas, bem como comandos que traduzem estes conceitos de forma a representar o conjunto de ações. Para que esse conjunto de ações se torne viável, deve existir uma perfeita relação lógica ligada ao modo pelo qual essas ações são executadas, pelo qual é regido o fluxo de execução. Através das estruturas básicas de controle de fluxo de execução sequenciação, seleção, repetição e da combinação delas, pode-se criar um algoritmo para solucionar qualquer problema. Algoritmo nome_do_algoritmo Variáveis declaração de variáveis Início Comando 1 Comando 2 Comando 3 Comando 4 ... Comando n Fim BIBLIOGRAFIA Ascencio, Ana Fernanda Gomes e Campos, Edilene Aparecida Veneruchi de. Fundamentos da Programação de Computadores – Algoritmos, Pascal, C/C++. São Paulo: Prentice Hall, 2002. PARTE 2 ESTRUTURA DE UM ALGORITMO Na criação de algoritmos, utilizam-se os conceitos de bloco lógico, entrada e saída de dados, variáveis, constantes, atribuições, expressões, relacionais e aritméticas, bem como comandos que traduzem estes conceitos de forma a representar o conjunto de ações. Para que esse conjunto de ações se torne viável, deve existir uma perfeita relação lógica ligada ao modo pelo qual essas ações são executadas, pelo qual é regido o fluxo de execução. Através das estruturas básicas de controle de fluxo de execução seqüenciação, seleção, repetição e da combinação delas, pode-se criar um algoritmo para solucionar qualquer problema. ALGORITMOS ESTRUTURADOS Muitos programadores preparam um programa iniciando com um diagrama de blocos para demonstrar sua linha de raciocínio, tendo como objetivo estabelecer uma seqüência de operações a serem efetuadas em um programa. Esta técnica permite posteriormente uma codificação, praticamente em qualquer linguagem de programação. A técnica mais importante no projeto de lógica de programa é chamada de programação estruturada, a qual consiste em uma metodologia de projeto, objetivando: 1. Agilizar a codificação da escrita da programação; 2. Permite a verificação de possíveis falhas apresentadas pelos programas; 3. Facilitar as alterações e atualizações dos programas. A programação estruturada deve ser composta de quatro passos fundamentais: 1. Escrever as instruções em seqüências ligadas entre si apenas por estruturas seqüenciais, respectivas ou de selecionamento. 2. Escrever instruções em grupos pequenos e combiná-los. 3. Distribuir módulos do programa entre os diferentes programadores que trabalharão sob a supervisão de um programador sênior, ou chefe de programação. 4. Revisar o trabalho executado em reuniões regulares e previamente programadas, em que compareçam apenas programadores de um mesmo nível. REPRESENTAÇÃO DE ALGORITMOS É comum os profissionais de desenvolvimento da área de TI denominaram símbolos que representam as linhas do raciocínio lógico. A representação desses símbolos se dá através de quatro formas, a saber: FLUXOGRAMA É uma ferramenta usada pelo profissional de sistemas. Tem como finalidade descrever o fluxo, seja manual ou mecânico, especificando os suportes usados para os dados e as informações. Usa símbolos convencionais, permitindo poucas variações. Representando alguns dados, do processamento de dados e da saída de dados, acompanhados dos procedimentos requeridos pelo analista de sistemas, e a serem realizados pelo programador através do desenvolvimento do raciocínio lógico, o qual deverá solucionar o problema do programa a ser processado pelo computador. Exemplo: DIAGRAMA DE CHAPIN É uma forma de especificação gráfica que permite o desenvolvimento de algoritmos estruturados. Exemplo: PORTUGUÊS ESTRUTURADO Tendo estabelecido os passos anteriores (fluxograma, diagrama de Chapin), será efetuada a codificação. Esta fase obedece ao que está definido no fluxograma ou no diagrama, pois ela é a representação gráfica da lógica de um programa, porém sempre deverá ser relacionado com todas as variáveis que serão utilizadas dentro do programa. Este relacionamento, além de definir tipos de dados que serão utilizados, define também o espaço de memória que será necessário para manipular as informações fornecidas durante a execução do programa. O português estruturado é uma linguagem de programação de computadores baseada na categoria pseudocódigo. Assim sendo, o computador que vai utilizar essa linguagem de programação é imaginário, ou seja, a própria mente do desenvolvedor. Programa nome_do_programa Var declaração de variáveis Subalgoritmos Início Corpo do algoritmo Fim Português estruturado é formado pelas instruções: programa, var, inteiro, real, caractere, lógico, inicio, leia, escreva, fim, se, então, senão, fim-se, enquanto, faça, fimenaquanto, repita, até-que, para, de, até, passo, fim-para, conjunto, tipo, registro, fim registro, procedimento, caso, seja, fim-caso e função, além de operadores aritméticos (adição, subtração, multiplicação, divisão, exponenciação e atribuição), operadores relacionais (igual, diferente, maior, menor, maior ou igual, menor ou igual) e operadores lógicos (.e. , .ou. , .não.). O conceito de comando advém do fato de se passar uma ordem a ser realizada pelo computador. Assim sendo, um comando pode ser escrito em uma ou mais linhas e ser formado por uma ou mais instruções. Por exemplo, o programa representado abaixo possui: • Na primeira linha de código ocorre a definição de um comando representado por uma instrução escrita em apenas uma linha: Programa Calcula_Media. • Da segunda até a quarta linha de código está a definição de um único comando escrito em três linhas, a partir da segunda linha, representado pela instrução VAR e seguido das demais linhas, respectivamente, com as instruções caractere e real. • Da quinta até a oitava linha e da décima terceira até a vigésima linha de código ocorre o uso de um comando por linha. • A sétima e oitava linhas não possuem instruções escritas, mas possuem a definição de expressões matemáticas. A décima e décima primeira linhas também não possuem instruções escritas, mas têm a definição de expressões lógicas usadas para atribuir um determinado valor à variável RESULTADO. • Da nona até a décima segunda linha acontece a definição de um único comando escrito em 4 linhas. Exemplo: LINGUAGEM DE PROGRAMAÇÃO Uma linguagem de programação é um método padronizado para expressar instruções para um computador. É um conjunto de regras sintáticas e semânticas usadas para definir um programa de computador. Uma linguagem permite que um programador especifique precisamente sobre quais dados um computador vai atuar, como estes dados serão armazenados ou transmitidos e quais ações devem ser tomadas sob várias circunstâncias. O conjunto de palavras, compostos de acordo com essas regras, constituem o código fonte de um software. Esse código fonte é depois traduzido para código de máquina, que é executado pelo processador. Uma das principais metas das linguagens de programação é permitir que programadores tenham uma maior produtividade, permitindo expressar suas intenções mais facilmente do que quando comparado com a linguagem que um computador entende nativamente (código de máquina). Assim, linguagens de programação são projetadas para adotar uma sintaxe de nível mais alto, que pode ser mais facilmente entendida por programadores humanos. Linguagens de programação são ferramentas importantes para que programadores e engenheiros de software possam escrever programas mais organizados e com maior rapidez. Linguagens de programação também tornam os programas menos dependentes de computadores ou ambientes computacionais específicos (propriedade chamada de portabilidade). Isto acontece porque programas escritos em linguagens de programação são traduzidos para o código de máquina do computador no qual será executado em vez de ser diretamente executado. Uma meta ambiciosa do Fortran, uma das primeiras linguagens de programação, era esta independência da máquina onde seria executada. TIPOS PRIMITIVOS DE DADOS Antes de iniciar o estudo, é necessário considerar que um computador nada mais é do que uma ferramenta utilizada para solucionar problemas que envolvam a manipulação de informações, as quais se classificam, a grosso modo, em dois tipos básicos: dados e instruções. Os dados são representados por elementos advindos do mundo externo, os quais representam as informações que os seres humanos manipulam. Eles devem ser abstraídos para serem processados em um computador. Os dados podem ser categorizados em três tipos: numéricos, caracteres e lógicos. Os tipos de dados numérico inteiro, numérico real, caracteres e lógico são também referenciados como tipos de dados primitivos ou tipos de dados básicos. INTEIROS Toda informação numérica que pertença ao conjunto dos números inteiros relativos (negativos, nulo, positivos), excluindose destes qualquer número fracionário. Exemplos: a) Ele tem 15 irmãos. b) Ela tem 20 anos de idade. c) 9. REAIS Toda a informação numérica que pertença ao conjunto dos números reais (negativos, positivos, nulo). Exemplos: a) Ela tem 1,73 metro de altura. b) Meu saldo bancário é de R$ 125,07. CARACTERES Toda a informação composta por um único caracter alfanumérico (0..9 / A..Z / a..z) e/ou caracteres especiais (#, /, $, %, *, ?, ~, >, !, @, ...). OBS.: o espaço é considerado caracter especial. Exemplos: a) 0 1 2 3 4 5 6 7 8 9 b) A B C D E F ... STRING Toda a informação composta por um conjunto de caracteres (cadeia) alfanuméricos (0..9 /A..Z / a..z) e/ou caracteres especiais (#, /, $, %, *, ?, ~, >, !, @, ...). OBS.: o espaço é considerado caracter especial. Exemplos: c) Constava na prova: “Use somente caneta”. d) O endereço é: “Rua 24 de Outubro, número 1215 – Apto 101 – POA/RS”. e) O nome do escritor é: “Mário Quintana”. LÓGICOS Toda a informação que pode apenas assumir duas situações (biestável, ou seja, dois estados). Exemplos: a) Verdadeiro ou Falso. b) Aberto ou Fechado. c) A porta pode estar aberta ou fechada. d) A lâmpada pode estar acesa ou apagada. TIPO DE INFORMAÇÕES As informações tratadas em um algoritmo podem ser classificadas em dois tipos: CONSTANTES São informações que não sofrem alterações, que não muda com o decorrer do tempo. Dentro do algoritmo, constantes são valores que permanecem os mesmos do início ao fim. As informações constantes do tipo CARACTERE devem ser representadas entre aspas. Exemplos: a) ‘Não Fume’ b) 5 c) Falso d) 71 VARIÁVEIS Informações que têm a possibilidade de serem alteradas em algum instante no decorrer do tempo. Temse como definição de variável tudo aquilo que está sujeito a variações, que é incerto, instável ou inconstante. E quando se fala de computadores, é preciso ter em mente que o volume de informações a serem tratadas é grande e diversificado. Desta forma, os dados a serem processados serão bastante variáveis. Todo dado a ser armazenado na memória de um computador deve ser previamente identificado, ou seja, primeiro é necessário saber o seu tipo para depois fazer o seu armazenamento adequado. Armazenado o dado, ele pode ser utilizado e manipulado a qualquer momento. Exemplos: a) Temperatura b) Índice da inflação c) Alíquotas do imposto d) Comprimento e) Altura f) Peso As variáveis de memória No ambiente computacional, as informações variáveis são guardadas em dispositivos eletrônicos analogamente chamados de “memória”. Podemos imaginar essa “memória” como sendo um armário cheio de gavetas, no qual as gavetas seriam os locais físicos responsáveis por armazenar objetos; os objetos (que podem ser substituídos) seriam as informações e as gavetas, as variáveis. Visto que, na memória (armário) existem inúmeras variáveis (gavetas), precisamos diferenciá-las, o que é feito por meio de identificadores (etiquetas). Cada variável (gaveta), no entanto, pode guardar apenas uma informação (objeto) de cada vez, sendo sempre de mesmo tipo (material). Portanto, precisamos definir nomes para determinadas gavetas especificando qual o material dos objetos que lá podem ser armazenados. Variáveis são posições de memória com as seguintes características: . • Tem um nome, que a diferencia das demais; . • Tem um tipo de dado associado, que indica o tipo de informação que poderá ser armazenada na variável; . • Tem um conteúdo, que é o dado guardado na variável; . • Tem um endereço, que a localiza na memória. Observações: 1. 1. Nome de uma variável é único em um algoritmo e deve seguir as regras de formação de identificadores; 2. 2. Uma variável somente pode receber como conteúdo um dado do tipo que foi definido para ela; 3. 3. O conteúdo de uma variável é SUBSTITUÍDO por outro conteúdo que venha a ser colocado na variável; 4. 4. O nome e o tipo de dado de uma variável, uma vez definidos, não mudam por todo o algoritmo; 5. 5. O uso do nome de uma variável em uma expressão significa o uso do seu conteúdo (naquele momento) dentro da expressão; 6. 6. O uso de um conteúdo de variável em uma expressão não modifica o seu valor. Regras para Formação de Identificadores Identificadores são quaisquer nomes que sejam usados para identificar informações variáveis ou constantes dentro de um algoritmo. A criação de um nome deve obedecer algumas regras de utilização das mesmas: 1. Devem começar com um caracter alfabético; 2. Podem ser seguidas por mais caracteres alfabéticos e/ou numéricos; 3. Não é permitido o uso de outros caracteres especiais; 4. Não poderá ser nome de uma variável, uma palavra reservada a uma instrução do programa; 5. O nome de uma variável não poderá possui espaços em branco; 6. Não poderão ser utilizados outros caracteres a não ser letras e números, exceto o uso do caracter especial ‘sublinha’ (), e/ou underline; Exemplos: 1. Identificadores NÃO permitidos: _XPTO, 1ABC3, EF*GH, 5X, NOTA/2, String, REAL. 2. Identificadores permitidos: X, NOME_VAR, A12B, MEDIA. BIBLIOGRAFIA Ascencio, Ana Fernanda Gomes e Campos, Edilene Aparecida Veneruchi de. Fundamentos da Programação de Computadores – Algoritmos, Pascal, C/C++. São Paulo: Prentice Hall, 2002. Ascencio, Ana Fernanda Gomes e Campos, Edilene Aparecida Veneruchi de. Fundamentos da Programação de Computadores – C/C++ e Java. São Paulo: Prentice Hall, 2ª Ed., 2007.
Compartilhar