Prof. José Miranda

O conciso dicionário Oxford define um algoritmo com um “processo ou regras para (máquina) cálculos”.

A execução de um algoritmo não deve incluir qualquer decisão subjetiva, nem deve exigir o uso de intuição ou criatividade (embora veremos uma exceção a esta regra)

Quando conversamos sobre algoritmo vem logo à mente os computadores.

Nem por isso, outros métodos sistemáticos no intuito de resolver problemas poderiam ser incluídos.

Por exemplo, os métodos que aprendemos na escola para multiplicar e dividir inteiros são também algoritmos

Geralmente um método é elaborado para resolver um problema que surge dentro do escopo de um modelo.

Por sua vez, um modelo foi criado para facilitar e responder a um questionamento da natureza.

O mais famoso algoritmo na história data do tempo dos gregos: Isto é, o algoritmo de Euclides para calcular

o múltiplo divisor comum de dois inteiros É também possível considerar certas

receitas de pratos como algoritmos, garantindo que eles não incluam instruções como “adicione sal para dar sabor”

Quando nós nos organizamos para resolver um problema, é importante decidir qual algoritmo deverá ser usado para sua solução.

A resposta pode depender de muitos fatores: O tamanho do exemplo a ser usado. A maneira ou jeito com que o problema é

apresentado A rapidez e o tamanho de memória do

equipamento de cálculo disponível, e assim por diante.

Realizar um cálculo aritmético elementar como exemplo.

Suponha que você tenha de multiplicar dois números inteiros usando somente lápis e papel.

Se você fosse criado no ocidente, as chances são que você multiplicaria o multiplicando sucessivamente por cada algarismo do multiplicador, tomado da direita para esquerda escrevendo esses resultados intermediários um debaixo do outro deslocando cada linha para esquerda e finalmente você adicionaria todas essas filas para obter sua resposta.

Este é o clássico algoritmo da multiplicação. Todavia, podemos usar um algoritmo bem

diferente para fazer a mesma coisa. Usaremos o conhecido algoritmo chamado

“multiplicação à la russe”:

Escreva o multiplicador e multiplicando lado a lado. Crie colunas, uma de baixo de cada operando,

repetindo a seguinte regra até que o número debaixo do multiplicador for 1.

Divida o número debaixo do multiplicador por dois, ignorando qualquer fração.

Dobre o número debaixo do multiplicando adicionado ele a ele mesmo.

Finalmente, descarte a linha em que o número debaixo do multiplicador é par, e então adicione todos os números que restaram na coluna debaixo do multiplicando.

Vamos multiplicar 45 por 19 como é mostrado abaixo:

Neste exemplo nós obtemos 19 + 76 + 152 + 605 =855. Embora este algoritmo possa parecer engraçado a priori,

ele é essencialmente um método usado no maquinário de muitos computadores.

Para usar isso, não há necessidade de memorizar qualquer tabela de multiplicação: tudo que precisamos saber é como adicionar tudo, e como dobrar um número ou dividi-lo por 2.

45 19 1922 38 --- 11 76 765 152 1522 304 ---1 608 608 855

Veremos ao longo de nossa primeira abordagem de algoritmo que há algoritmos mais eficientes usados para multiplicar números inteiros maiores.

Mas também veremos que alguns desses algoritmos mais sofisticados são mais lentos do que aqueles mais simples quando os operandos não são suficientemente grandes.

Neste ponto é importante decidir como nós vamos representar nossos algoritmos.

Se nós tentarmos descrever em nossa língua, nós rapidamente descobriremos que as linguagens nativas não são adaptadas a esse tipo de coisa.

Para evitar qualquer confusão, nós especificaremos no futuro nosso algoritmos fornecendo um programa.

Todavia, nós não iremos nos confinar ao uso de uma única linguagem de programação específica, por outro lado, podemos abordar diferentes linguagens para depois decidir qualquer mais conveniente para nossas atuais necessidades no tocante a validação de nossos algoritmos.

Assim, a figura do laboratório nos dará um teor prático ao longo de toda a disciplina.

Dessa maneira, os pontos essenciais de um algoritmo não serão obscurecidos pelos detalhes de programação relativamente irrelevantes.

Iremos usar frases do português em nossos programas onde quer que isso pareça favorecer a simplicidade e a clareza.

Essas frases em Português não deverão ser confundidas com comentários no programa.

Assim optaremos em sempre colocar os comentários em chaves { }.

Declarações de quantidades escalares (inteiro, real, ou Booleano) são geralmente omitidas.

Parâmetros escalares das funções e procedimentos são passados por valor pelo menos um especificação diferente é fornecida explicitamente, e as agrupamentos (ARRAY) são passados por referência.

A notação usada para especificar que uma função ou um procedimento tem um parâmetro de agrupamento varia de caso a caso.

Podemos escrever por exemplo: procedimento proc1(T: grupo) ou mesmo procedimento proc2(T)

Se o tipo e as dimensões do agrupamento T não forem importantes ou se eles são evidentes oriundo do contexto.

Em tal caso #T denota o número de elementos no agrupamento T.

Se os limites ou o tipo de T são importantes, escrevemos: procedimento proc3(T[1..n]) ou mais geral procedimento proc4(T[a..b]: inteiros).

Em casos n, a, e b deveria ser considerado como parâmetros formais, e seus valores são determinados pelos limites do parâmetro real correspondente a T quando o procedimento for chamado.

Essas fronteiras podem ser especificadas explicitamente, ou mudadas, pela chamada do procedimento da seguinte forma: proc3(T[1..m]).

Para evitar proliferação das frases: começo do procedimento e fim do procedimento, o alcance de uma colocação tais como se, enquanto, ou para, como também tais como aquelas encontradas em uma declaração, procedimento, função, ou gravação, é mostrada pela endentação das colocações afetadas.

A colocação retorno marca o fim dinâmico de um procedimento ou uma função.

No último caso também fornece o valor da função. Os operadores de div e mod representam divisões de

inteiros (descartando qualquer resultado ponto flutuante) e o resto de uma divisão, respectivamente.

Logo iremos falar de conceitos de recursão e ponteiros. O último representado por uma seta apontando para

cima ” “.

Por exemplo, aqui está uma descrição formal da multiplicação à la russe.

função russe(A,B) equanto I >0 do grupos X, Y se X[I] ímpar

então prodprod +Y[I]{inicialização} I I – 1 X[1] A; Y[1] B retorne prod I 1{criar as duas colunas}enquanto X[I] > I faça X[I+1]X[I] div 2 Y[I+1]Y[I] + Y[I] II + 1 prod 0

Em nossa abordagem inicial focaremos na criação de algoritmos para resolver um mesmo problema de modo que possamos escolher o melhor.

Isso levanta a questão de como decidir qual dos diversos algoritmos é o preferido.

A abordagem empírica consiste de programar algoritmos competitivos e provando os em diferentes instâncias com a ajuda de um computador.

Os computadores das mais variadas arquiteturas têm funcionamento similar.

Acima temos uma figura mostrando uma arquitetura simplificada de um computador

Na CPU (processador) existe um conjunto relativamente pequeno de instruções.

Cada tipo de processador tem um conjunto diferente de instruções apesar de similares entre si.

O local de onde as instruções são buscadas pelo processador é a memória.

Essas instruções podem ser desce de operações matemáticas a instruções com os dispositivos de entrada e saída.

Um programa de computador um conjunto de instruções que será executado pelo processador em uma determinada sequência.

Esse programa leva o computador a realizar alguma tarefa.

Assim, notamos que um programa nada mais é do que um algoritmo.

Podemos considerar essas primeiras instruções como a primeira linguagem de programação do computador ou linguagem de máquina.

A linguagem de programação pode ser classificada em níveis.

Existe a linguagem de baixo nível como é o caso de uma linguagem de máquina, ASSEMBLY como é mostrada abaixo

INC CONT ; Incrementa a variável de memória CONT MOV TOTAL, 48 ; Transfere o valor 48 para variável de

memória TOTAL ADD AH, BH ;Adicinar o conteúdo do registrador BH para o

registrador AH AND MASK1, 128 ; Realizar operação AND na variável MASK1 e

128 ADD MARKS, 10 ; Adicionar 10 a variável MARKS MOV AL, 10 ; Transferir o valor 10 para o registrador AL

A palavra ASSEMBLY vem da palavra montar, que podemos também chamar de linguagem de montagem e para executar é usado um programa chamado ASSEMBLER (montador).

A linguagem de montagem é muito próxima da linguagem de máquina e por isso é conhecida como de baixo nível.

Todo o processo de programação e desvio de problemas pode ser sintetizado a seguir

Edit

Assemble

Link

Run

prog.asm

prog.obj prog.lst

prog.exe prog.map

library.lib

Debug

Para cada processador, há uma linguagem de montagem já que uma relação direta entre as instruções em linguagem de montagem e em linguagem de máquina.

Isto faz com que o código tenha que ser refeito se quisermos executar um programa em um processador não compatível com o qual ele foi escrito inicialmente.

Para resolver isso foi criada as linguagens de alto nível.

Essas linguagens são independentes do processador em que são executadas.

Suas características principais soa que seu código é mais elaborado contemplando operações mais complexas e mais próximas da lógica humana.

Para que possam ser processadas tais linguagens são traduzidas para a linguagem de máquina.

Essa tradução é realizada por um compilador

O compilador, a partir do código em linguagem de alto nível, chamado de código-fonte, gera um arquivo com o código em linguagem de máquina, conhecido como código-objeto.

Esse código-objeto fica em disco e só é carregado em memória no momento da execução.

O interpretador faz o mesmo trabalho, porém não gera o arquivo em código-objeto.

As instruções são traduzidas para linguagem de máquina em tempo de execução, instrução a instrução.

Podemos notar que programar um computador tornou-se muito mais fácil do que anteriormente.

Vamos ver agora um de Shell que é o “PROMPT” do sistema operacional Unix e Linux

É o servo que recebe os comandos digitados pelo usuário e os executa

USUÁRIO SHELL KERNEL DISCO RÍGIDO Enquanto o Shell script é um arquivo que guarda vários

comandos que pode ser executado sempre que for requisitado.

Podemos também usar o PROMPT do sistema operacional Windows para realizar programas combinados com comandos

Esses são exemplos de interpretadores.

A linguagem Java tem uma arquitetura diferente, o que fornece a seus programas mais portabilidade que outras linguagens de programação de alto nível.

A compilação do código Java não gera código executável em nenhum sistema operacional.

Em vez disso, gera um código “pseudo-executável”, chamado BYTECODE.

Esse código é uma espécie de baixo nível que , porém, não é uma linguagem de máquina de algum processador, nem faz interface específica com algum determinado sistema operacional.

Para que esse código possa ser executado em algum sistema operacional, é necessário que mais uma camada de software esteja ai instalada.

A camada de software funciona como um sistema operacional genérico, deixando transparentes as particularidades do sistema operacional real.

Essa camada é chamada de máquina Java virtual. A máquina faz a tradução dos BYTECODES para

código executável naquele sistema operacional. Isso faz com que um programa escrito em Java e

que seja compilado para BYTECODE possa ser executado em qualquer máquina que tenha a JVM adequada instalada.

Durante a execução, esse código será traduzido em tempo real para a linguagem proprietária e executado.

A tradução em tempo real pode ser entendida como uma espécie de interpretação.

Portanto, é difícil afirmar que a linguagem de programação Java seja um linguagem puramente compilada ou interpretada.

public class Operacoes

{

public static void main(String[ ] args)

{

Scanner entrada = new Scanner(System.in);

int num1; int num2;

System.out.print ("Digite o primeiro número: ");

num1 = entrada.nextInt( );

System.out.print("Digite o segundo número: ");

num2 = entrada.nextInt();

System.out.println();

System.out.println(num1 + " + " + num2 + " = " + (num1 + num2) );

System.out.println(num1 + " - " + num2 + " = " + (num1 - num2) );

System.out.println(num1 + " * " + num2 + " = " + (num1 * num2) );

}

}

Linguagem natural: Mostra uma maior flexibilidade e liberdade de expressar

todos os procedimentos, porém torna o processo da criação do algoritmo sem uma padronização importante.

Na linguagem natural teremos também corremos o grande risco do subjetivismo, isto é, a forma seria muito realçada do que a eficácia do algoritmo.

Fluxograma: Os fluxogramas apresentam os algoritmos de forma gráfica. São formados de caixas que contêm as instruções a serem

executadas. Tais caixas ligadas por setas que indicam o fluxo das ações. Algumas caixas especiais indicam a possibilidade de o fluxo

seguir caminhos distintos, dependendo de certas situações que podem ocorrer durante a execução do algoritmo.

Pseudocódigo: Visa trazer o máximo possível de vantagens como o código

pronto para a execução, a rigidez sintática e a semântica que são importantes e imprescindíveis para que o algoritmo possa ser lido e executado pelo computador.

O pseudocódigo ao contrario da linguagem propriamente dita tem um grau de rigidez sintática intermediária entre as linguagens natural e de programação.

Além disso, podemos utilizar o idioma nativo. Em geral, linguagem de programação são construídas

utilizando palavras reservadas em inglês, uma espécie de padrão.

Porém, o pseudocódigo deve manter, tanto quanto possível, a rigidez semântica.

Um pseudocódigo bastante conhecido aqui é o Portugol, que apresenta aceitação e tem sua razões obvias para isso.

var num1, num2, maior: inteiro;inicio leia (num1, num2); se (num1 > num2) então maiornum1; senão maiornum2; escreva (maior); fim

Defina o que é um algoritmo Cite alguns critérios de escolha de um algoritmo dentre

diversos testados Diferença de um algoritmo e um programa Explique como um programa é executado em um computador Defina o que é uma linguagem de programação de baixo

nível e uma de alto nível Dado um programa executável em um sistema operacional, o

que é preciso fazer para que tal programa possa ser utilizado em outro sistema operacional?

Explique por que um código Java é portável em vários sistemas operacionais.

Explique um pouco do que vem a ser o Shell script Quais as vantagens e desvantagens da utilização de

fluxogramas e de pseudocódigo na construção de algoritmos?

A representação gráfica baseada nas formas geométrica apresentadas anteriormente implicam no uso e implementação de ações distintas.

O uso de diagramas facilita o entendimento das ideias de uma pessoa ou equipe e justifica sua popularidade.

A representação gráfica baseada em diagrama de bloco é também referenciada erroneamente no Brasil como fluxograma.

O termo fluxograma deve ser utilizado, apenas na esfera da analise de sistemas, e não em programação.

Possivelmente o erro de definição do termo ocorre devido à estrutura da palavra original inglesa, flowchart (flow=fluxo, chart=diagrama), portanto diagrama de fluxo.

No entanto, diagrama de fluxo não é o mesmo que fluxograma.

Vale lembrar que fluxograma é um conceito macro e diagrama é micro do processo de documentação gráfica da linha de raciocínio a ser usada na programação de um computador eletrônico.

Além da representação tradicional, há a representação alternativa denominada diagrama de

quadro (ou diagrama de NS ou diagrama de CHAPIN) .

Apesar de utilizada por alguns professores, essa forma não impede de ser apresentada.

O diagrama NS ou NSD foi desenvolvido por Isaac Nessi e Bem Sheiderman nos anos de 1972/73 e ampliado por Ned Chapin no ano de 1974.

Esse modelo de diagramação substitui o formato tradicional por uma forma estrutural diferente baseada no uso de quadros.

Inicio

A, B

R

Fim

Inicio

Fim

Leia A, B

RA+BEscreva

R

Inicio

A, B

A>B

RA+B

RA+B

R

Fim

Inicio

Inicio

A>B

RA+BEscrever

RFim

N S

Crie um diagrama de bloco para adicionar três valores numéricos e a média ponderada para pesos escolhidos por você;

Usando o método de Euclides para determine o máximo divisor comum de dois valores numéricos inteiros positivos através de um fluxograma;

Usando a série de Taylor para criar um algoritmo para 5 termos da série.

Um computador, independentemente de ser de grande, médio ou de pequeno porte, executa basicamente três ações de trabalhos: A entrada de dados; O processamento de dados; A saída de dados.

A etapa de entrada de dados é a parte que o computador recebe os dados do mundo, podendo armazená-los na memória principal para realizar algum tipo de processamento, ou armazenar na memória secundária para usar futuramente.

A etapa de processamento de dados é quando o computador, por meio de um programa (software) executado em sua memória primária , realiza a transformação dos dados de entrada ou previamente armazenados em sua memória secundária, tornando-os elementos que possam ser usados como fontes de informação para o mundo exterior.

Essa etapa é realizada de forma muito comum nas linguagens de programação, pois independentemente do tipo de linguagem em uso, sofre muito pouca variação.

A etapa de saída de dados o computador envia os dados processados na memória principal ou armazenados na memória secundária para o mundo externo.

Os dados processados podem ser usados como fontes de informações, e assim facilitar a vida das pessoas que necessitam tomar decisões.

Essa etapa, assim como a entrada de dados, é realizada de forma bastante variada nas linguagens de programação.

Dados são elementos do mundo exterior, que representam dentro de um computador digital as informações manipuladas pelos seres humanos.

Os dados a serem utilizados devem primeiramente ser abstraídos para serem então processados.

Eles podem ser classificados em três tipos primitivos ou tipos básicos; numéricos (representados por valores numéricos inteiros ou reais), caracteres (representados por valores alfabéticos ou alfanuméricos) e lógicos (valores dos tipos falso e verdadeiro)

Inteiro: os dados numéricos positivos e negativos pertencem ao conjunto de números inteiros, excluindo dessa categoria qualquer valor numérico fracionário (que pertence ao conjunto de números reais), por exemplo, os valores 35, 234, -54, -9. entre outros.

Em nossa abordagem do dado inteiro iremos fazer em português com o comando inteiro.

O tipo de dado inteiro é utilizado em operações de processamento matemático.

Real: são reais os dados numéricos positivos e negativos que pertencem ao conjunto de números reais, incluindo nessa categoria todos os valores fracionários e inteiros,

Por exemplo, os valores 35, 0, -57, -4, 5.2, entre outros.

Iremos ao redigirmos os passos de um algoritmo usar o comando real para referenciar um dado real em nosso portugol.

Caractere/Cadeia: são caracteres delimitados pelos símbolos aspas (“ “).

Eles são representados por letras (de A até Z), números (de zero até 9), símbolos (por exemplo, todos os símbolos imprimíveis existentes num teclado) ou palavras contendo esses símbolos.

O tipo de dado caractere é conhecido também como alfanumérico, string (linha ou conjunto de pontos)

Iremos em nossa abordagem nos referir aos tipos alfanuméricos ou STRING como caractere ou cadeia.

Lógico: são lógicos os dados com valores binários do tipo sim ou não, verdadeiro e falso, 1 e zero, entre outros, em que apenas um dos valores pode ser escolhido.

Iremos nos referir a tais tipos como lógico.

Variáveis são os elementos que estão sujeitas a variações ou mudanças, que são incertas, instáveis ou inconsistentes.

E quando se fala de computadores, é preciso ter em mente que o volume de dados a serem tratados é grande e diversificado.

Desta forma, os dados a serem processados são bastante variáveis.

Todo dado a ser armazenado na memória de um computador deve ser previamente identificado segundo seu tipo, ou seja, primeiramente é necessário saber o tipo do dado para depois fazer seu armazenamento.

No entanto, há algumas programas que usam linguagens, como é o caso Matlab que geralmente dispensa a declaração de variáveis, como mostra o exemplo abaixo.

a = 1while length(a) < 10a = [0 a] + [a 0]end

O qual imprimi como saída o triângulo de Pascal:

11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 11 7 21 35 35 21 7 11 8 28 56 70 56 28 8 11 9 36 84 126 126 84 36 9 1

(com “a=” antes de cada linha)

No entanto, há algumas programas que usam linguagens, como é o caso Matlab que geralmente dispensa a declaração de variáveis, como mostra o exemplo abaixo.

a = 1while length(a) < 10a = [0 a] + [a 0]end

O qual imprimi como saída o triângulo de Pascal:

11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 11 7 21 35 35 21 7 11 8 28 56 70 56 28 8 11 9 36 84 126 126 84 36 9 1

(com “a=” antes de cada linha)

Constante é tudo que é fixo, estável, inalterável, imutável, continuo, incessante, invariável, de valor fixo e que é aplicado em diversos pontos de vista.

Assim sendo, do ponto de vista computacional, que é semelhante ao matemático ou científico, constante é uma grandeza numérica fixa que determina um valor invariável em um sistema ou expressão, independente das variáveis envolvidas

O uso de constantes fica bem claro quando vamos modelar um sistema real, pois de certo haverá grandezas envolvidas que precisam ser definidas e declaradas com valor invariável

Eremos aqui mostrar um trecho de programa em MATLAB que determina a dinâmica de um pêndulo

clear; comprimento= 1;gravidade=9.8; npointos = 250;dt = 0.04; omega = zeros(npoints,1); alfa = zeros(npoints,1); tempo = zeros(npoints,1); alfa(1)=0.2; for passo= 1:npointos-1 omega(passo+1) = omega(passo) - (gravidade/comprimento)*teta(passo)*dt; alfa(step+1) = alfa(passo)+omega(passo)*dt tempo(passo+1) = tempo(passo) + dt; end plot(time,alfa,'r' ); xlabel('tempo (segundos) '); ylabel(‘alfa (radiandos)');

Ângulo alfamassa

comprimento

Pêndulo simples

São responsáveis pelas operações matemáticas a serem realizadas em um computador.

O termo operador é utilizado na área da programação para estabelecer as ferramenta de interações com as variáveis e constantes gerando uma ação computacional.

A tabela a seguir apresenta os operadores aritméticos a serem usados e considerados na elaboração de expressões aritméticas em no presente curso.

Tabela de operadores aritméticosOperador Operação Descrição Tipo Prioridade Resultado

+ “+n” ou “n” Manutenção do

Sinal

Unário __ Positivo

- -n Inversão de Sinal

Unário __ Negativo

X n Atribuição do valor “n”

a “x”

Binário __ Positivo ou Negativo

X n Exposição do valor de

x

Binário 1 Inteiro ou Real

(1/n)X (1/n) Radiciação

de n√XBinário 1 Real

/ X /n Divisão de “X” por “n”

Binário 2Real

* X * n Multiplicação de “X” por

“n”

Binário 2 Inteiro ou Real

div X div n Divisão de “x” por “n”

Binário 4 Inteiro

Um operação muito comum em programação de computadores é usar expressão aritmética para o estabelecimento de processamentos matemáticos.

As expressões aritméticas são realizadas a partir do relacionamento existente entre variáveis e constantes numéricas com a utilização dos operadores aritméticos.

Como por exemplo de uma expressão aritmética considere a fórmula de cálculo de área de um círculo.

A=π.R2

Crie um diagrama de bloco e sua codificação respectivamente do cálculo de área de um circulo.

Desenvolver um diagrama de bloco e seu programa em portugol do cálculo da conversão da temperatura Fahrenheit para Celsius.

Elaborar um programa para determinar montante de juros simples dado o capital inicial.

Agora iremos entender a capacidade de computadores tem de realizar tomadas de decisões por meio de processamento lógico.

A tomada de decisão realizada pelo computador estabelece uma ação de desvio na operação do fluxo do programa.

Desta forma, um determinado trecho do programa pode realizar um ou outra tarefa de processamento.

Tabela de operadores aritméticos

Operador Descrição

= Igual a

> Maior que

< Menor que

>= Maior ou igual a

<= Menor ou igual a

<> Diferente de

A tomada de decisão simples (desvio condicional simples) do ponto de vista do diagrama de blocos é representada pelos símbolos decisão e conector.

A partir do símbolo decisão é estabelecido o foco do desvio do fluxo de um programa.

Esse desvio é processado apenas para o lado que indicar o resultado da condição verdadeira

Condição

Instruções executadas após

condição ser verdadeira

Instruções executadas após

condição ser verdadeira

• Observe o diagrama de blocos com rótulos S e N para a execução de uma tomada de decisão simples com base na CONDIÇÃO definida no símbolo decisão.

• Note que o uso das linhas de fluxo com as setas indicando a direção do fluxo de processamento do digrama.

N S

início

A, B

XA+B

X>10

Fim

X

programa ADIÇÃO_DE_NÚMEROSvarA, B, X: realinicio leia A, BXA + Bse ( X > 10) então escreva Xfim_sefim