01-Algoritmos[1]

Prof. Sidney Cassemiro do Nascimento

Algoritmos

ICCUFS

2009/2

22

Conteúdo

MotivaçãoIntroduçãoConceitosAlgoritmos– Principais características dos algoritmos– Quais as limitações dos algoritmos?– Formas de representar um algoritmo

33

Conteúdo

Algoritmo (Portugol)– Identificadores, variáveis e constantes– Tipos de dados – Operadores aritméticos, relacionais e lógicos– Comandos de entrada e saída e atribuição – Conceito de bloco de comandos – Estruturas de controle de fluxo – condicionais (se, se-

senão e caso) – Estruturas de controle de fluxo – repetições (enquanto,

repita-até e para)

44

Motivação

Algoritmos– Resolvem problemas do mundo real;– Executam operações sobre um conjunto de dados;– Os dados precisam ser organizados de forma coerente;– Dados organizados expressam uma abstração do mundo

real.

Conceito de Dado:– “Informação organizada, com sentido lógico para quem a

manipula”.

Algoritmos

55

Motivação

Por que estudar Construção de Algoritmos?– é um passo fundamental para desenvolver o

raciocínio lógico e o pensamento estruturadopara todos os estudantes de disciplinas científicas e técnicas

– programação de computadores é uma ferramenta para resolução de problemas

Algoritmos

66

Introdução

O que é ciência da computação?– Conceitos da disciplina

“Ciência da computação é – e sempre será – o interesse entre a manipulação mecanizada e humana de símbolos [algoritmos], usualmente referidos como ‘computação’ e ‘programação’, respectivamente.”

Edsger W. Dijkstra, 1989

Algoritmos

77

Introdução

“Ciência (engenharia) da computação é o estudo sistemático de processos algorítmicos — teoria, análise, projeto, eficiência, implementação e aplicação — que descrevem e transformam informação.”

ACM/IEEE-CS , 1989

Algoritmo – conceito fundamental na ciência da computação

Algoritmos

88

Introdução

A Programação de Computadores– A Ciência da Computação podem ser aplicada

em qualquer área do conhecimento humano.

– O computador é uma máquina especial pelo fato de ser programável.

– Ferramentas computacionais são criadas objetivando facilitar a vida do homem.

Algoritmos

99

Introdução

Como programar computadores?– O computador só entende a linguagem de

máquina

– São programados através das Linguagens de Programação

Alto nível: JAVA, C#, C++, PASCAL, ...Baixo nível: linguagens de máquina e assembler (montagem)

Algoritmos

1010

Conceitos

“Algoritmos, de maneira geral, representam um conjunto de passos ou instruções que têm por objetivo resolver um determinado problema”

Conjunto de passos que definem a forma como uma tarefa é executada

Passos ordenados, não ambíguos e executáveisAtividade finita

Algoritmos

1111

Conceitos

ExemplosInstruções para preparo de uma receitaInstruções para utilização de caixas bancáriosInstruções para utilização de aparelho celularRegras para cálculo do imposto de rendaInstruções para inscrição em um concurso...

Algoritmos

1212

Conceitos

O que é Programação? = ABSTRAÇÃO

O que é abstração?– Operação mental que observa a realidade e

captura apenas os aspectos relevantes para um contexto.

Algoritmos

1313

Realidade

AbstraçãoO que você abstrai dessa realidade?

Sistema de Controle de Compras e Vendas de Veículos

Abstração+

Programação

Algoritmos

1414

Conceitos

Hardware– Conjunto de componentes eletrônicos que formar a

parte física do computador– Processador, Placa Mãe, Disco rígido

Software– Conjunto de instruções e dados processado pelos

circuitos eletrônicos do hardware– Sistemas Operacionais, Editores de textos,Planilhas

eletrônicas, Navegadores– Programas

Agem como instruções para o processador

Algoritmos

1515

Conceitos

Compiladores– Traduzem programas de linguagem humana para

linguagem de máquina

Linguagens de Programação– Técnica de comunicação padronizada para enviar

instruções a um computador– Cada linguagem tem sua própria sintaxe e gramática– Existem diferentes tipos de linguagens de

programação

Algoritmos

1616

Ciclo de Vida do Desenvolvimento de Programas

Definição do Problema

Codificar e Depurar

Análise do Problema

Projetar e Representar o Algoritmo

Algoritmos

1717

Etapas da atividade de Programação

1) ProblemaCalcular a área de umquadrado

1) Algoritmo1) Obtenha o lado2) área = lado X lado3) Informe a área

1) Programa Fonte...write ('Lado: ');readln (lado);area = lado * lado;writeln ('A Área é : ', area);...

1) Ling. de Máquina...01101010 0110101111101011 1110100101101111 0110101011001010 10101000...

Algoritmos

1818

AlgoritmosPrincipais características dos algoritmos– Concebidos por seres humanos– Representados por programas (software) escritos em

linguagens de programação

– Executados por máquinasFísicas - hardware

– Computadores (analógicos ou digitais), mecânicos, eletromecânicos, eletrônicos, ...

Abstratas– Engendradas na mente humana, formalismo matemático,

máquinas virtuais implementadas em programas de computador

Algoritmos

1919

Algoritmos

Quais as limitações dos algoritmos?– Não são capazes de calcular funções não-computáveis

Função para provar teoremas em geralImpossibilidade de se construir uma máquina que, de modo consistente, resolva todos os problemas da matemática, apenas com os recursos do próprio sistema

– Não são auto-organizáveis - depende do ser humano– A capacidade (“inteligência”) das máquinas limita-se ao

conhecimento embutido no algoritmo

Algoritmos

2020

Formas de representar um algoritmo

Como representar um

algoritmo?

Algoritmos

2121

Formas de representar um algoritmo

Algoritmos podem ser representados, dentre outras maneiras, por:– DESCRIÇÃO NARRATIVA

Utiliza uma linguagem de escrita natural para descrever algoritmos.

– FLUXOGRAMAUtiliza uma linguagem de representação gráfica para descrever algoritmos.

– PORTUGOLUtiliza uma linguagem de escrita artificial (PSEUDO-CÓDIGO) para descrever algoritmos.

Algoritmos

2222

Formas de representar um algoritmo

Exemplo:– Algoritmo para converter um valor em

reais (R$) para Euros (€)

Algoritmos

2323

Formas de representar um algoritmo

Descrição narrativa do algoritmo Reais-Euros:

1. solicite o valor em Reais;

2. transforme o valor em Reais para Euros;

3. informe o valor em Euros.

Algoritmos

2424

Fluxograma do algoritmo Reais-Euros

Início

Reais

Euros = 0.397182 * Reais

Euros

Fim

Início do algoritmo

Entrada de Reais (R$)

Cálculo de Euros (€)

Apresentação do resultado

Fim do algoritmo

Formas de representar um algoritmo

Algoritmos

2525

Formas de representar um algoritmo

Portugol do algoritmo Reais-Euros

Algoritmo “Reais-Euros”Var

Reais, Euros : RealInicio

Leia (Reais)Euros 0.397182 * ReaisEscreva (Euros)

FimAlgoritmoAlgoritmos

2626

Formas de representar um algoritmo Vantagens Desvantagens Descrição Narrativa

O português é bastante conhecido por nós.

Imprecisão. Pouca confiabilidade (a

imprecisão acarreta a desconfiança).

Extensão (normalmente, escreve-se muito para dizer pouca coisa).

Fluxograma Padrão mundial. Ferramenta bem

conhecida. Figuras dizem muito mais

que palavras.

Complica-se à medida que o algoritmo cresce.

Pouca atenção aos dados, não oferecendo recursos para declará-los.

Portugol Independência de linguagem de programação.

Usa o português como base.

Define-se melhor quais e como os dados vão estar estruturados.

Passagem quase imediata do algoritmo para uma linguagem de programação qualquer.

Exige a definição de uma linguagem não real para trabalho.

Não é padronizada.

Algoritmos

2727

Construindo algoritmosA programação de um sistema computacional pode ser resumida em 3 passos básicos

ProcessamentoEntrada Saída

Dispositivode Entrada

Dispositivode Saída

Memória

UCP

Algoritmos

2828

Construindo algoritmos

Uma boa prática para construir algoritmos é dividir o problema em 3 fases:

– ENTRADA: São os dados de entrada do algoritmo.– PROCESSAMENTO: São os procedimentos utilizados

para chegar ao resultado final.– SAÍDA: São os dados já processados.

Entrada Processamento Saída

Algoritmos

2929

Portugol - Estruturaalgoritmo “Nome_Do_Algoritmo”

“Tem como objetivo identificar o algoritmo, devemos utilizar um Nome_Do_Algoritmo o mais claro possível, para facilitar a identificação”

var“Declaração das variáveis. Devemos aqui, informar quais e os tipos das variáveis que serão utilizadas no algoritmo.”

inicio“Corpo do Algoritmo. Aqui será escrita a sequência de comandos que devem ser executados para solucionar o referido problema”

fimalgoritmo

Algoritmos

3030

Algoritmo - Tipos de Dados PrimitivosOs dados, ao serem manipulados pelo computador, precisam ter um tipo associado a ele

Os tipos primitivos são os tipos que são nativos da linguagem de programação

Veremos mais adiante que podemos criar os nossos próprios tipos

Algoritmos

3131

Tipos de Dados Primitivos

Conjunto de valores ao qual pertence o dado– Ex.: números inteiros, números reais, lógicos, caracteres, etc.– Todo dado organizado e coerente possui um tipo

Classificação

Visão dos Dados Classificação

Decomposição Primitivos, DerivadosHomogêneos, DerivadosHeterogêneos

Tamanho Estáticos ou Dinâmicos

Algoritmos

3232

Tipos de Dados PrimitivosTipo de Dados Primitivos– Não permitem a sua decomposição em outros

tipos– São a base para os tipos derivados– Exemplos:

Tipo ValoresInteiros ...-2, -1, 0, 1, 2, 3...Reais -0.5, 1.67, -52.92, 1.11Lógicos True (Verdadeiro), False (Falso)Caracteres ‘A’, ‘b’, ‘C’, ‘c’, ‘0’, ‘1’, ‘#‘, ...

Algoritmos

3333

Tipos de Dados PrimitivosTipo de Dados Derivados Homogêneos– Agrupam dados primitivos do mesmo tipo em

um conjunto– Exemplos:

Tipo Valores

Vetores [0, 1, 2, 3, 4, 5]Matrizes [0, 1, 2], [4, 5, 6]Cadeias ‘palavra’

Algoritmos

3434

Tipos de Dados PrimitivosTipo de Dados Derivados Heterogêneos– Agrupam dados primitivos de tipos diferentes

em um conjunto– Exemplos:

Tipo Valores

Registro {0, 1, 2.5, ‘palavra’, [0,1], ’s’}

Algoritmos

3535

Tipos de Dados PrimitivosTipo de Dados Estáticos– Possuem um tamanho finito no número de

elementos de seu conjunto.– Exemplos: vetores, matrizes, cadeias de

caracteres, etc.

Tipo de Dados Dinâmicos– Possuem um tamanho indeterminado no

número de elementos de seu conjunto, ao longo de seu ciclo de vida.

– Exemplos: Pilhas, Filas, Listas e Arvores

Algoritmos

3636

Algoritmo - IdentificadoresRepresentam os nomes escolhidos para rotular as variáveis, procedimentos, funções e nomes de programas. Normalmente, obedecem as seguintes regras:1.O primeiro caracter deve ser uma letra;2.Os nomes devem ser formados por caracteres

pertencentes ao seguinte conjunto:{a,b,c,..z,A,B,C,...Z,0,1,2,...,9,_};

3. Não deve haver espaço em branco;4. Não deve haver identificadores repetidos;5. Não existe distinção de maiúsculas e minúsculas;6. Os nomes escolhidos devem ser claros a fim de

explicitar seu conteúdo uso, mas também não deve ser extenso para não dificultar a escrita.

Algoritmos

3737

Algoritmo - VariáveisSão as unidades básicas de armazenamento das informações em programação

As variáveis representam espaços onde podemos armazenar e manipular dados

Para cada variável é necessário ter um valor associado a ela

Algoritmos

3838

Algoritmo - Variáveis

As variáveis devem ser declaradas da seguinte forma:Var

Cod, Mat : InteiroNome, Logradouro: CaractereNota1, Nota2, Media: RealAchou: Logico

Algoritmos

3939

Algoritmo - Constantes

São usadas em expressões para atribuir valores a variáveis ou em comandos

Seus valores serão sempre os mesmos, ou seja, uma vez declarado, o seu valor não se altera mais durante o algoritmo

Existem três tipos de constantes:– Numérica– Lógica– Caractere

Algoritmos

4040

Algoritmo - Operações

Para solucionar alguns problemas computacionalmente será necessário a utilização de alguns operações

Temos quatro tipos de operações:– Operação de Atribuição– Operações Aritméticas– Operações Relacionais– Operações Lógicas

Algoritmos

4141

Operação de AtribuiçãoTem como finalidade armazenar um valor, variável ou expressão na variável

É necessário que o tipo do valor, variável ou expressão seja compatível com o tipo da variável

A sintaxe de uma operação de atribuição é a seguinte: NomeDaVariavel Valor, Variável ou Expressão

Algoritmos

4242

Operações Aritméticas

São utilizados em expressões para realizar operações aritméticas com variáveis

Os operadores e funções recebem argumentos (parâmetros) e retornam um resultado, o qual pode ser atribuído a uma variável ou utilizado numa expressão

Os operadores são representados por símbolos e as funções por palavras

Algoritmos

4343

Operações Aritméticas

Operador Descrição+, - Operadores unários, isto é, são aplicados a um único operando. Exemplos: -3,

+x+ Adição- Subtração* Multiplicação/ Divisão\ Operador de divisão inteira. Por exemplo, 5 \ 2 = 2MOD ou % Operador de módulo (isto é, resto da divisão inteira).

Por exemplo, 8 MOD 3 = 2^ Operador de potenciação. Por exemplo, 5 ^ 2 = 25.

Algoritmos

4444

Operações Aritméticas

Função DescriçãoQuociente(a,b) Retorna o quociente da divisão inteira de a por bResto(a,b) Retorna o resto da divisão inteira de a por bPotência(a,b) Retorna o valor de a elevado a bRaiz(a,b) Retorna a raiz b de a. Raiz(a,b)Sorteio(a) Retorna um número aleatório, em intervalo fechado, entre 1 e aSeno(x) Retorna o seno de xCosseno(x) Retorna o cosseno de xModulo(x) Retorna o módulo ou valor absoluto de xInteiro(x) Retorna a parte inteira de x. Inteiro(10/3) = 3

Algoritmos

Obs.: Não disponíveis no VisuAlg

4545

Operações RelacionaisSão utilizados para relacionar variáveis ou expressões, resultando num valor lógico (Verdade ou Falso)

Operador Descrição= Igual<> Diferente< Menor> Maior<= Menor ou Igual>= Maior ou Igual

Algoritmos

4646

Operações Lógicas

São utilizadas para avaliar expressões lógicas

Uma expressão lógica representa a união de operações relacionais

Uma operação lógica permite que o resultado de várias expressões relacionais seja transformado em um único resultado lógico

Algoritmos

4747

Operações Lógicas

Operador Descriçãoe Operador que resulta VERDADEIRO somente se seus

dois operandos lógicos forem verdadeiros.

ou Operador que resulta VERDADEIRO quando um dos seus operandos lógicos for verdadeiro.

xou Operador que resulta VERDADEIRO se seus dois operandos lógicos forem diferentes, e

FALSO se forem iguais nao Operador unário de negação.

nao VERDADEIRO = FALSO, e nao FALSO = VERDADEIRO.

Algoritmos

4848

Prioridade de Operadores

Durante a execução de uma expressão que envolve vários operadores, é necessário a existência de prioridades

Caso não exista essa prioridade entre operadores é possível obter valores não condizentes com a realidade

Algoritmos

4949

Prioridade de Operadores

1º Operações embutidas em parênteses “mais internos”

2º Funções (Quociente, Resto, Potência e Funções Primitivas)

3º Multiplicação e/ou divisão

4º Adição e/ou Subtração

5º Operadores Relacionais

6º Operadores Lógicos

Algoritmos

5050

Comandos de Entrada e SaídaO comando de entrada é utilizado para que se possa ler um determinado dado do meio externoEsse dado é geralmente passado pelo usuário através do teclado ou de outros dispositivos de entradaEsses dados lidos serão armazenados na memória do computador através das variáveisA sintaxe para ler um dado é mostrada abaixo:

leia (<lista-de-variáveis>) Ex1: leia(matricula)Ex2: leia(codigo, curso)

Algoritmos

5151

Comandos de Entrada e SaídaO comando de saída é utilizado para permitir que se possa escrever algo na tela do computador– Ex: Um resultado, uma mensagem de erro, etc.

A sintaxe do comando de saída é mostrada abaixo:

escreva (<lista-de-expressões>) A expressão mostrada acima pode ser uma variável ou uma cadeia de caracteres, como mostrado nos exemplos abaixo:

– Ex1: escreva(curso)– Ex2: escreva(‘Matricula: ‘, matricula)

Algoritmos

5252

Comandos de Controle

São os comandos utilizados nos algoritmos para ajudar a solucionar o problema em questão

São três os comandos de controles conhecidos e utilizados na programação:– Sequência– Seleção– Repetição (enquanto, repita e para)

Algoritmos

5353

SequênciaUtilizado para executar comandos passo a passo, na qual todos os comandos serão executados nas ordem escrita sem desvio

Pode possuir um ou mais comandos– Quando tiver mais de um comando, identificar

pelos identificadores inicio e fim (Obrigatório)– Quando tiver apenas um comando, o uso do

inicio e fim é condicional

Algoritmos

5454

Sequência

inicio

fim

Importante a indentação dos comandos (recuo para direita) e também a linha indicando o inicio e fim– Lembrar que o programa não será mantido apenas por

você, outras pessoas irão também dar manutenção nele

Comando_1...Comando_N

Algoritmos

5555

SeleçãoUsado para fazer comparações e simular uma decisão no fluxo do algoritmo

Usado para tomar decisões, ou seja, desviar a condição do algoritmo de acordo com uma condição

O comando de seleção pode ser de dois tipos:– Simples– Composto

Algoritmos

5656

SeleçãoA sintaxe do comando simples é mostrada abaixo: se <expressão-lógica> entao

    <sequência-de-comandos>fimse

O comando de seleção simples funciona da seguinte maneira:

1.A expressão lógica é resolvida;2.Se o resultado da expressão for verdadeiro, então a

sequência-de-comandos será executada;3.Caso o resultado seja falso a sequência-de-

comandos não será executada.

Algoritmos

5757

Seleção

A sintaxe do comando composto é mostrada abaixo:

se <expressão-lógica> entao    <sequência-de-comandos-1>senao    <sequência-de-comandos-2>

fimse

Algoritmos

5858

Seleção

O comando de seleção composta funciona da seguinte maneira:

1.A expressão lógica é resolvida;2.Se o resultado da expressão for verdadeiro, então a

sequência-de-comandos-1 será executada;3.Caso o resultado seja falso a sequência-de-

comandos-2 será executada.

Algoritmos

5959

SeleçãoDuplicidades em Seleção– Como na seleção composta apenas um blocos de

comandos será executado, atentar para não repetir o mesmo comandos nos dois blocos

Algoritmos

se media >= 5 entao escreva (‘Aprovado’) escreva (‘Média = ‘, Media)senao escreva (‘Reprovado’) escreva (‘Média = ‘, Media)fimse

se Media >= 5 entao escreva (‘Aprovado’)senao escreva (‘Reprovado’)fimseescreva (‘Média = ‘, Media)

6060

Qualidade de ProgramaçãoA qualidade de um software se mede pelo produto desenvolvido e pelo seu processo de construçãoBenefícios de um código com qualidade– Reduz defeitos e validação dos requisitos de software– Boa leitura e entendimento– Facilidade de manutenção

Técnicas de qualidade de programação– Identação e espaçamentos– Comentários

Textos explicativos. Não é executado.EX: {isso é um comentário}

– Clareza na lógica– Variáveis representativas

Algoritmos

6161

Qualidade de ProgramaçãoAlgoritmo sem qualidadealgoritmo “Maior”var N1, N2, N3, Ma: InteiroInicio

leia (N1, N2, N3)se N1 > N2 entao

Ma <- N1senao

Ma <- N2fimsese N3 > Ma entao

Ma <- N3fimseescreva(‘O maior é: ‘,Ma)

fimalgoritmo

Algoritmos

6262

Qualidade de ProgramaçãoAlgoritmo com qualidade

{Algoritmo que, dado 3 números inteiros diferentes, identifica quem é o maior}algoritmo “MaiorNumero”var numero1, numero2, nunmero3, maiorNumero: InteiroInicio

leia (numero1, numero2, numero3) {lendo os números}{Verificando quem é o maior número}se numero1 > numero2 entao

maiorNumero <- numero1 {guardando o 1º número como o maior} senao maiorNumero <- numero2 {guardando o 2º número como o maior} fimse se nunmero3 > maiorNumero entao maiorNumero <- nunmero3 {guardando o 3º número como o maior} fimse escreva(‘O maior é: ‘, maiorNumero) {exibindo o maior número} fimalgoritmo

Algoritmos

6363

Comando de Seleção Aninhado

É possível ter casos em que seja necessário a utilização de um comando de seleção dentro de outro comando de seleção

O comando de seleção aninhado permiti a avaliação de diversas condições para os possíveis valores de um dado conjunto de variáveis

Algoritmos

6464

Comando de Seleção AninhadoAbaixo segue um exemplo de um trecho de um código utilizando comando de seleção aninhado:

se Num1 > Num2 entaoescreva(‘O maior número é: ’, Num1)

senaose Num1 < Num2 entao

escreva(‘O maior número é: ’, Num2)senao

escreva(‘Os números são iguais’)fimse

fimse

Algoritmos

6565

Comando escolhaO comando ESCOLHA (CASO), corresponde ao comando SE-ENTAO, mas de uma forma mais compacta nas operações de seleção.

escolha  <expressão-de-seleção>caso <exp11>, <exp12>, ..., <exp1n>

    <sequência-de-comandos-1>caso <exp21>, <exp22>, ..., <exp2n>

<sequência-de-comandos-2>...outrocaso

<sequência-de-comandos-extra>fimescolha

Algoritmos

6666

Comando de Repetição - Enquanto

A sintaxe do comando enquanto é mostrada abaixo:

enquanto <expressão-lógica> faca   <sequência-de-comandos>

fimenquanto

Esta estrutura repete uma sequência de comandos enquanto uma determinada condição (especificada através de uma expressão lógica) for satisfeita.

Algoritmos

6767

Comando de Repetição - Repita

A sintaxe do comando repita é mostrada abaixo:

repita   <seqüência-de-comandos>

ate <expressão-lógica>

Esta estrutrura repete uma sequência de comandos até que uma determinada condição (especificada através de uma expressão lógica) seja satisfeita.

Algoritmos

6868

Comandos de Repetição - Observações

O comando enquanto e o repita são bastante parecidos, mas apresentam algumas diferenças peculiares;O comando enquanto primeiro avalia a expressão lógica e em seguida executa a sequência-de-comandos;O comando repita primeiro executa a sequência-de-comandos para em seguida avaliar a expressão lógica ;O comando enquanto executa a sequência-de-comandos enquanto o resultado da expressão lógica for verdade;O comando repita executa a sequência-de-comandos até que o resultado da expressão lógica seja verdade;Os comandos enquanto e repita possuirão, para uma mesma situação, as expressão lógica invertidas.

Algoritmos

6969

Comando de Repetição - Para

A sintaxe do comando para é mostrada abaixo:para <variável> de <valor-inicial> ate <valor-

limite> [passo <incremento>] faca   <sequência-de-comandos>

fimpara

O comando para incrementa, a variável, a partir do valor-inicial de uma unidade ou incremento, até que, esta atinja o valor-limite. E para cada incremento a sequência-de-comandos é executada.

Algoritmos

7070

Comando de Repetição - Para

O <incremento> é opcional. Quando presente, precedida pela palavra passo, é uma expressão que especifica o incremento que será acrescentado à variável contadora em cada repetição do laço. Quando esta opção não é utilizada, o valor padrão de <incremento> é 1. Vale a pena ter em conta que também é possível especificar valores negativos para <incremento>.

Algoritmos