Baixe o app para aproveitar ainda mais
Prévia do material em texto
1 Algoritmos I • Semestre letivo: 2018.1 • Professor: Fabio Henrique Silva • Ementa: Introdução à Lógica de Programação. Pseudo- linguagem. Programação estruturada. Tipos de dados simples. Estruturas de controle. Funções e Procedimentos. 2 • Os objetivos dessa disciplina são: Apresentar as técnicas de programação estruturada, tipos de dados simples, estruturas de controle e modularização. Conceituar algoritmos e programas. Reconhecer operadores aritméticos, relacionais, funcionais e lógicos. Construir algoritmos utilizando estruturas de controles sequenciais, condicionais e de repetição. Reconhecer a necessidade de utilizar subrotinas. Objetivos da Disciplina Conteúdo Programático Unidade 1: Elementos básicos da pseudolinguagem 1.1 Noção de Algoritmos 1.2 Constantes e Variáveis 1.3 Operadores Aritméticos, Relacionais e Lógicos 3 Conteúdo Programático Unidade 2: Estruturas de Programação 2.1 Estrutura Sequencial 2.2 Estrutura Condicional Simples 2.3 Estrutura Condicional Composta Conteúdo Programático Unidade 3: Estruturas de Repetição 3.1 Estrutura de Repetição PARA 3.2 Estrutura de Repetição Enquanto 3.3 Estrutura de Repetição REPITA 4 Conteúdo Programático Unidade 4: Subrotinas 4.1 Conceitos de Modularização 4.2 Procedimentos 4.3 Funções Básica: • FARRER, H. et al. Algoritmos Estruturados. Rio de Janeiro: LTC, 1999. • FORBELLONE, V.; EBERSPACHE, F. Lógica de Programação. São Paulo: Makron Books, 2000. • GUIMARAES, A. M. Algoritmos e Estrutura de Dados. Rio de Janeiro: LTC, 1994. Complementar: • HOLZNER, S. C: Programação: o guia prático para a programação eficiente. Rio de Janeiro: Campus, 1993. • KERNIGHAN, Brian W, RITCHIE, Dennis M. C: a linguagem de programação padrão ANSI. Rio de Janeiro: Campus, 1989. • MANZANO, J. A. N. G. Estudo dirigido de algoritmos. 13.ed. rev, atual e ampl. São Paulo: Érica, 2010. • SCHILDT, H. C completo e total. 3. ed. rev. e atual. São Paulo: Makron Books, 2009. • TREMBLAY, J.P. Ciência dos computadores: uma abordagem algorítmica. São Paulo: McGrawn-Hill, 1986. Bibliografia 5 Referências Adicionais • Apresentação “Lógica de Programação - Forbellone / Eberspacher” • SEBESTA, R. W. Conceitos de linguagens de programação. 9. ed. Porto Alegre: Bookman, 2011. • Apresentação “Algoritmos I”, prof. Jorge Viana Doria Junior • Apresentação “Programação Estruturada (Modularização/Subprogramação)”, prof. Fabíola Gonçalves, UFU • Apostila “Algoritmos”, prof. Helio Gouvea Prado UNIDADE 1: ELEMENTOS BÁSICOS DA PSEUDOLINGUAGEM 6 1.1 Noção de Algoritmos George Boole • Filósofo britânico (1815-1864) que criou a álgebra booleana, fundamental para o desenvolvimento da computação moderna • Se dedicou a "entender os processos de pensamento da mente humana" 7 George Boole Se você hoje usa um computador digital agradeça também a mim ;) Lógica • Além da aplicação na matemática... ‒Busca a "correção do pensamento", determinar quais operações são válidas e quais não são fazendo análise das formas e leis do pensamento ‒Procura saber por que pensamos assim e não de outro jeito 8 Lógica no dia-a-dia • Kaiton é um país do planeta Stix. Todos os Xinpins são de Kaiton. Logo, todos os Xinpins são Stixianos. • A gaveta está fechada. A caneta está dentro da gaveta. Precisamos primeiro abrir a gaveta para depois pegar a caneta. Lógica de Programação • Objetiva a racionalidade e o desenvolvimento de técnicas que cooperem para a produção de soluções logicamente válidas e coerentes, que resolvam com qualidade os problemas que se deseja programar Uso das leis do pensamento, da "ordem da razão" e de processos de raciocínio e simbolização formais na programação de computadores 9 Algoritmo • O objetivo principal da Lógica de Programação é a construção de algoritmos coerentes e válidos • Algoritmo é uma sequência de passos que visam atingir um objetivo bem definido ‒Na medida em que especificamos uma sequência de passos, usamos a ordem ("pensamos com ordem"), logo usamos a lógica ‒O algoritmo sempre produz uma ou mais saídas, sem necessariamente exigir dados de entrada Exercício 1 • Pense e escreva em um papel, aplicativo notepad (ou apenas na mente) as ações necessárias para que você execute uma tarefa, cotidiana ou não • Sugestões: Trocar uma lâmpada Fazer um cupcake Voltar para casa de trem https://static.pexels.com/photos/45227/bulb-electricity-energy-glass-45227.jpeg; https://pixabay.com/p-1270278/?no_redirect; https://pixabay.com/p-1464837/?no_redirect 10 Exercício 2 • Imagine que, por exemplo, na sua volta para casa de trem, as seguintes situações podem ocorrer: ‒O trem estar quebrado ‒N trens estarem quebrados ("N" definido) ‒N trens estarem quebrados ("N" indefinido) • Como você reescreveria suas ações do Exercício 1 para situações análogas às relatadas acima? Programa • Qualquer pessoa com suas experiências pode resolver os problemas esperados e inesperados na prática • Um programa de computador tradicional não tem conhecimento prévio nem adquire experiências • Devemos determinar em detalhes todas as ações que ele deve executar, prevendo obstáculos e formas de transpô-los ‒Tal atividade é realizada pelos programadores 11 Representação de Algoritmos • Lembrando: Algoritmo é uma linha de raciocínio • Formas de representar algoritmos incluem: ‒Texto ‒Gráfico * Fluxograma * Chapin início ir para o primeiro soquete soquetes restantes < 10 acionar o interruptor pegar uma escada posicionar escada buscar lâmpada nova acionar o interruptor não acendeu? subir na escada retirar a lâmpada queimada colocar lâmpada nova acionar o interruptor não acendeu? retirar a lâmpada queimada colocar lâmpada nova ir ao próximo soquete fim F F F V V V Fluxograma tradicional 12 Diagrama de Chapin Forma Textual ir para o primeiro soquete soquetes testados < 10 acionar o interruptor pegar uma escada colocar a escada embaixo do soquete buscar lâmpada nova acionar o interruptor subir na escada retirar lâmpada queimada colocar lâmpada nova lâmpada não acendeu retirar lâmpada queimada colocar lâmpada nova ir para o próximo soquete lâmpada não acendeu • acionar o interruptor; • se a lâmpada não acender, então • pegar uma escada; • posicionar a escada embaixo da lâmpada; • buscar uma lâmpada nova; • acionar o interruptor; • subir na escada; • retirar lâmpada queimada; • colocar lâmpada nova; • enquanto a lâmpada não acender, faça • retirar lâmpada queimada; • colocar lâmpada nova; Fluxograma - Símbolos Início ou final do fluxograma Operação de cálculo, de atribuição e chamada ou retorno de subalgoritmo Operação de entrada de dados Operação de saída de dados Decisão 13 INICIO AV1, AV2 MEDIA ← (AV1 + AV2)/2 MEDIA >= 7 "Aprovado" "AV3" FIM Conjunto de Regras • Expressar ações usando a gramática em uma língua produz ambiguidades ‒"O pregador foi grampeado durante o conserto" • É necessário usar regras que restrinjam o uso da língua (português) na representação de algoritmos e intencionalmente se aproximem das linguagens de programação reais: pseudocódigo 14 algoritmo "resultado" inicio real : AV1, AV2, MEDIA; leia (AV1, AV2); MEDIA (AV1 + AV2)/2; se MEDIA >= 7 entao escreva ("Aprovado") senao escreva ("AV3"); fimse; fim. Exemplos de Linguagens • Os computadores são usados em um infinidade de diferentes áreas ‒Por exemplo: Aplicações científicas, aplicações comerciais, inteligência artificial, programação de sistemas, scripting, propósitos especiais • Em virtude disso, linguagens de programação com metas muito específicas têm sido desenvolvidas 15C++ - Linguagem Orientada a Objeto ("Hello World") FORTRAN – Linguagem Imperativa ("Hello World") LISP – Linguagem Funcional (Cálculo de número fatorial) program helloworld print *, "Hello world!" end program helloworld #include <iostream> int main() { std::cout << "Hello, world!\n"; } (defun factorial (n) (if (= n 0) 1 (* n (factorial (- n 1))))) Exercício 3 • Crie um algoritmo que resolva o problema da Torre de Hanói 16 Exercício 3 Problema com 4 discos("minúsculo", "pequeno","médio", "grande"): Todos os discos devem ser movidos do primeiro para o terceiro pino mantendo a mesma ordem da situação inicial Apenas 1 disco pode ser movido por vez Um disco pequeno nunca pode estar por baixo de um disco maior 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Exercício 3 Passo 1: mover disco minúsculo para segundo pino Passo 2: mover disco pequeno para terceiro pino Passo 3: mover disco minúsculo para terceiro pino Passo 4: mover disco médio para segundo pino Passo 5: mover disco minúsculo para primeiro pino Passo 6: mover disco pequeno para segundo pino Passo 7: mover disco minúsculo para segundo pino Passo 8: mover disco grande para terceiro pino Passo 9: mover disco minúsculo para terceiro pino Passo 10: mover disco pequeno para primeiro pino Passo 11: mover disco minúsculo para primeiro pino Passo 12: mover disco médio para terceiro pino Passo 13: mover disco minúsculo para segundo pino Passo 14: mover disco pequeno para terceiro pino Passo 15: mover disco minúsculo para terceiro pino 17 1.2 Constantes e Variáveis Informação • O ser humano aprendeu a se comunicar por meio de informações, que são formadas pelos dados ‒Exemplo de dados: 21, setembro, dia, árvore ‒Exemplo de informação: 21 de setembro é o dia da árvore • O homem fornece e coleta informações para o computador, que é uma máquina capaz de manipular muitos dados 18 https://elrobotpescador.files.wordpress.com/2015/02/garry-kasparov-deep-blue-ibm.jpg Você está demorando muito para mover sua peça... (Estou processando os dados para te aplicar um xeque-mate) https://elrobotpescador.files.wordpress.com/2015/02/garry-kasparov-deep-blue-ibm.jpg 19 Tipos Primitivos • Dividindo as informações manipuladas pelo computador em 4 tipos básicos: ‒ Inteiro ‒Real (ou numérico) ‒Caractere (ou literal) ‒Lógico Tipos Primitivos • Inteiro: Números inteiros relativos (negativa, nula, positiva) ‒Ex.: Ele tem 15 irmãos • Real: Números reais (negativa, nula, positiva) ‒Ex.: Ela tem 1,73 metro de altura • Caractere: Caracteres alfanuméricos ‒Ex: Constava na prova: "Use somente caneta!" • Lógico: Pode assumir apenas duas situações ‒Ex: A lâmpada pode estar acessa ou apagada 20 Exercício 1 • Classifique o conteúdo das variáveis abaixo de acordo com seu tipo: 0 "abc" "João" 5.7 1012 FALSO -49 342 569 "Lucas" "Verdadeiro" 0.00001 Verdadeiro "444" -78.1 Exercício 1 • Classifique o conteúdo das variáveis abaixo de acordo com seu tipo: 0 inteiro "abc" literal "João" caractere 5.7 real 101 inteiro FALSO lógico -49 inteiro 342 inteiro 9 inteiro "Lucas" caractere "Verdadeiro" caractere 0.00001 real Verdadeiro lógico "444" caractere -78.1 real 21 Armazenamento de Dados • Os dados são "guardados" na memória e manipulados pelo processador • A mudança das linguagens de máquina para as linguagens de montagem foi, em grande parte: ‒ Uma substituição dos endereços de memória numéricos por nomes, tornando os programas mais legíveis ‒ Uma saída para o endereçamento absoluto, pois o tradutor que convertia os nomes para os endereços também os escolhia Variável • Trata-se de uma ABSTRAÇÃO de uma célula ou conjunto de células de memória do computador • É um valor que pode sofrer alteração no decorrer do tempo ‒Ex: Cotação do dólar, o peso de uma pessoa, o preço da gasolina ‒Valores devem ser compatíveis com seus tipos, ex.: Tipo inteiro não pode receber valor do tipo real (mas o contrário pode ser válido) 22 Variável • Analogias: ‒ Memória: Armário ‒ Variáveis: Gavetas do armário ‒ Identificadores: Etiquetas das gavetas ‒ Dado: Objeto guardado na gaveta (cadagaveta armazena um objeto por vez) ‒ Tipo primitivo: Material do objeto, cadagaveta rotulada armazena o mesmo tipode material ‒ Declaração de variáveis: Ação deetiquetar gavetas especificando qualmaterial dos objetos serãoarmazenados http://www.oursouthernhomesc.com/wp-content/uploads/2013/05/organized_pantry12-577x1024.jpg Regras de Formação dos Identificadores • Para nomear variáveis e constantes, devemos obedecer as seguintes regras: 1. Os nomes devem iniciar por caractere alfabético 2. Pode ser seguido por mais caracteres alfabéticos ou numéricos 3. Não devem ser usados caracteres especiais 4. Não devem ser usados nomes reservados da linguagem de programação que se vai usar 23 Regras de Formação dos Identificadores • Cada linguagem possui sua regra de estilo que embora não seja obrigatório, é recomendável, como por exemplo, não usar acentuação, escrever variáveis em letras maiúsculas • Exemplos: ‒ Identificadores válidos: ALPHA, X, BJ153, MEDIA, INSS ‒ Identificadores inválidos: 5X, E(13), A:B, X-Y, NOTA/2, AWQ*, P&AA Declaração de Variáveis • As variáveis devem ser declaradas, ou seja, definir seu tipo e nome. 24 Exemplos de Declarações tipo de dado: VARIÁVEL1, VARIÁVEL2, ..., VARIÁVELN; • Exemplos: inteiro: X; caractere: NOME, ENDEREÇO, DATA; real: ABC, XPTO, PESO, DÓLAR; lógico: RESPOSTA, H286; Constante • É uma variável vinculada a um valor somente no momento em que ela é vinculada a um armazenamento • Seu valor não sofre nenhuma variação no decorrer do tempo ‒Ex: O valor de PI, a velocidade da luz, 5, "Não fume" 25 1.3 Operadores Aritméticos, Relacionais e Lógicos Expressões Aritméticas • Operadores aritméticos: utilizados para a realização de cálculos matemáticos Operador Função Exemplos + Adição 2 + 3, X + Y - Subtração 4 - 2, N – M * Multiplicação 3 * 4, A * B / Divisão 10 / 2, C / D pot(x,y) Potenciação (x elevado a y) pot(2, 3) raiz(x) Raiz quadrada (de x) rad(9) mod Resto da divisão 9 mod 4 resulta 1 div Quociente da divisão inteira 9 div 4 resulta 2 26 Prioridade das Operações para Operadores Aritméticos 1. Parênteses mais internos 2. pot, raiz 3. mod, div *, / 4. +, - Expressões Lógicas • Operadores relacionais: utilizados para a estabelecer relação de comparação entre valores Operador Função Exemplos = Igual a 3 = 3, X = Y > Maior que 5 > 4, X > Y < Menor que 3 < 6, X < Y >= Maior ou igual a 5 >= 3, X >= Y <= Menor ou igual a 3 <= 5, X <= Y <> Diferente de 8 <> 9, X <> Y 27 Expressões Lógicas • Operadores lógicos: utilizados para a efetuar avaliações lógicas entre valores Operador Função Exemplos não Negação não V, não X e Conjugação V e V, X e Y ou Disjunção V ou V, X ou Y • Tabelas Verdade: Conjunto de todas as possibilidades de cada operador lógico A B A e B F F F F V F V F F V V V A B A ou B F F F F V V V F V V V V A não A F V V F Prioridade das Operações para Operadores Lógicos 1. não 2. e, ou 28 Prioridade das Operações para Todos os Operadores 1. Parênteses mais internos 2. Operadores aritméticos 3. Operadores relacionais 4. Operadores lógicos
Compartilhar