Prévia do material em texto
Prof. Sidney Cassemiro do Nascimento Algoritmos ICC UFS 2009/2 22 Conteúdo Motivação Introdução Conceitos Algoritmos – 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 estruturado para 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áveis Atividade finita Algoritmos 1111 Conceitos Exemplos Instruções para preparo de uma receita Instruções para utilização de caixas bancários Instruções para utilização de aparelho celular Regras para cálculo do imposto de renda Instruçõ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ção O 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) Problema Calcular a área de um quadrado 1) Algoritmo 1) Obtenha o lado 2) área = lado X lado 3) Informe a área 1) Programa Fonte ... write ('Lado: '); readln (lado); area = lado * lado; writeln ('A Área é : ', area); ... 1) Ling. de Máquina ... 01101010 01101011 11101011 11101001 01101111 01101010 11001010 10101000 ... Algoritmos 1818 Algoritmos Principais características dos algoritmos – Concebidos por seres humanos – Representados por programas (software) escritos em linguagens de programação – Executados por máquinas Fí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 geral Impossibilidade 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. – FLUXOGRAMA Utiliza uma linguagem de representação gráfica para descrever algoritmos. – PORTUGOL Utiliza 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 : Real Inicio Leia (Reais) Euros 0.397182 * Reais Escreva (Euros) FimAlgoritmo Algoritmos 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 dadosvã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 algoritmos A programação de um sistema computacional pode ser resumida em 3 passos básicos ProcessamentoEntrada Saída Dispositivo de Entrada Dispositivo de 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 - Estrutura algoritmo “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 Primitivos Os 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, Derivados Homogêneos, Derivados Heterogêneos Tamanho Estáticos ou Dinâmicos Algoritmos 3232 Tipos de Dados Primitivos Tipo de Dados Primitivos – Não permitem a sua decomposição em outros tipos – São a base para os tipos derivados – Exemplos: Tipo Valores Inteiros ...-2, -1, 0, 1, 2, 3... Reais -0.5, 1.67, -52.92, 1.11 Lógicos True (Verdadeiro), False (Falso) Caracteres ‘A’, ‘b’, ‘C’, ‘c’, ‘0’, ‘1’, ‘#‘, ... Algoritmos 3333 Tipos de Dados Primitivos Tipo 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 Primitivos Tipo 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 Primitivos Tipo 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 - Identificadores Representam 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áveis Sã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 : Inteiro Nome, Logradouro: Caractere Nota1, Nota2, Media: Real Achou: 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ção Tem 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 = 2 MOD 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ção Quociente(a,b) Retorna o quociente da divisão inteira de a por b Resto(a,b) Retorna o resto da divisão inteira de a por b Potência(a,b) Retorna o valor de a elevado a b Raiz(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 a Seno(x) Retorna o seno de x Cosseno(x) Retorna o cosseno de x Modulo(x) Retorna o módulo ou valor absoluto de x Inteiro(x) Retorna a parte inteira de x. Inteiro(10/3) = 3 Algoritmos Obs.: Não disponíveis no VisuAlg 4545 Operações Relacionais Sã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ção e 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 Algoritmos4949 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ída O comando de entrada é utilizado para que se possa ler um determinado dado do meio externo Esse dado é geralmente passado pelo usuário através do teclado ou de outros dispositivos de entrada Esses dados lidos serão armazenados na memória do computador através das variáveis A 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ída O 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ência Utilizado 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ção Usado 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ção A 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ção Duplicidades 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’) fimse escreva (‘Média = ‘, Media) 6060 Qualidade de Programação A qualidade de um software se mede pelo produto desenvolvido e pelo seu processo de construção Benefí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ção Algoritmo sem qualidade algoritmo “Maior” var N1, N2, N3, Ma: Inteiro Inicio leia (N1, N2, N3) se N1 > N2 entao Ma <- N1 senao Ma <- N2 fimse se N3 > Ma entao Ma <- N3 fimse escreva(‘O maior é: ‘,Ma) fimalgoritmo Algoritmos 6262 Qualidade de Programação Algoritmo com qualidade {Algoritmo que, dado 3 números inteiros diferentes, identifica quem é o maior} algoritmo “MaiorNumero” var numero1, numero2, nunmero3, maiorNumero: Inteiro Inicio 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 Aninhado Abaixo segue um exemplo de um trecho de um código utilizando comando de seleção aninhado: se Num1 > Num2 entao escreva(‘O maior número é: ’, Num1) senao se Num1 < Num2 entao escreva(‘O maior número é: ’, Num2) senao escreva(‘Os números são iguais’) fimse fimse Algoritmos 6565 Comando escolha O 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 Slide 1 Slide 2 Slide 3 Slide 4 Slide 5 Slide 6 Slide 7 Slide 8 Slide 9 Slide 10 Slide 11 Slide 12 Slide 13 Slide 14 Slide 15 Slide 16 Slide 17 Slide 18 Slide 19 Slide 20 Slide 21 Slide 22 Slide 23 Slide 24 Slide 25 Slide 26 Slide 27 Slide 28 Slide 29 Slide 30 Slide 31 Slide 32 Slide 33 Slide 34 Slide 35 Slide 36 Slide 37 Slide 38 Slide 39 Slide 40 Slide 41 Slide 42 Slide 43 Slide 44 Slide 45 Slide 46 Slide 47 Slide 48 Slide 49 Slide 50 Slide 51 Slide 52 Slide 53 Slide 54 Slide 55 Slide 56 Slide 57 Slide 58 Slide 59 Slide 60 Slide 61 Slide 62 Slide 63 Slide 64 Slide 65 Slide 66 Slide 67 Slide 68 Slide 69 Slide 70