Upload
acfava
View
934
Download
0
Embed Size (px)
DESCRIPTION
material sobre algoritmos
Citation preview
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