Algoritmos e Cálculos Numérico

Prévia do material em texto

ALGORITMOS E CÁLCULO NUMÉRICO Fabio Santiago Silvano Antonio Alves Pereira Junior Alysson Nunes Diógenes Celso Pessanha Machado Cynthia da Silva Barbosa Patrícia Sebajos Vaz Rafael Ramon Ferreira Rafaela Rodrigues Oliveira Raphael de Oliveira Freitas Renata Gomes de Oliveira Martins SOLUÇÕES a H EDUCACIONAIS INTEGRADASRevisão técnica: Marcos Antônio Abdalla Mestre em Engenharia Elétrica Graduado em Engenharia Industrial Elétrica Rute Henrique da Silva Ferreira Doutora em Sensoriamento Remoto Mestre em Educação A396 Algoritmos e cálculo numérico [recurso / Fabio Santiago... [et al.] ; revisão técnica: Marcos Antônio Abdalla Júnior e Rute Henrique da Silva - Porto Alegre : SAGAH, 2021. ISBN 978-65-5690-126-8 1. Algoritmo - Cálculo numérico. I. Santiago, Fabio. CDU Catalogação na publicação: Mônica Ballejo Canto - CRB 10/1023ALGORITMOS E CÁLCULO NUMÉRICO Fabio Santiago Cynthia da Silva Barbosa Mestre e doutor em Engenharia Mestre em Modelagem Mecânica e Computacional Bacharel em Aplicada MBA em Projetos de Aplicações Digitais e Computação Cientifica Patrícia Sebajos Vaz Silvano Antonio Alves Graduada em Engenharia Elétrica Pereira Junior Mestre em Rafael Ramon Ferreira em Processos Estocásticos Mestre em Licenciado e bacharel em Fisica Graduado em Alysson Nunes Diógenes Rafaela Rodrigues Oliveira Doutor e mestre em Engenharia Especialista em Design Educacional Elétrica e em Metodologia do Ensino de Graduado em Engenharia Elétrica Graduado em Celso Pessanha Machado Raphael de Oliveira Freitas Doutor e Mestre em Educação Doutor e Mestre em Educação em Ciências e Especialista em Especialista em Financeira, em Estatística e em Aplicada Educação Profissional Renata Gomes de Oliveira Martins Mestra em Ensino de Ciências e Licenciada em Porto Alegre 2021SAGAH EDUCAÇÃO 2021 Gerente editorial: Arysinha Affonso Colaboraram nesta edição: Editora: Maria Eduardo Fett Tabajara Editoração: Finalizando Ideias IMPORTANTE Os links para sites da web fornecidos neste livro foram todos testados, e seu funcionamento foi comprovado no momento da publicação do material. No entanto, a rede é extremamente dinâmica; suas estão constantemente mudando de local e conteúdo. Assim, os editores declaram não ter qualquer responsabilidade sobre qualidade, precisão ou integralidade das informações referidas em tais links. Reservados todos os direitos de publicação à SAGAH EDUCAÇÃO uma empresa do GRUPO A EDUCAÇÃO S.A. Rua Ernesto Alves, 150 - Bairro Floresta 90220-190 - Porto Alegre - RS Fone: (51) SAC 0800 703-3444 - www.grupoa.com.br proibida a duplicação ou reprodução deste volume, no todo ou em parte, sob quaisquer formas ou por quaisquer meios (eletrônico, mecânico, gravação, fotocópia, distribuição na web e outros), sem permissão expressa da Editora.Apresentação A recente evolução das tecnologias digitais e a consolidação da internet modificaram tanto as relações na sociedade quanto as noções de espaço e tempo. Se antes dias ou até semanas para saber de aconte- cimentos e eventos distantes, hoje temos a informação de maneira quase instantânea. Essa realidade possibilita a ampliação do conhecimento. No entanto, é necessário pensar cada vez mais em formas de aproximar os estudantes de conteúdos relevantes e de qualidade. Assim, para atender às necessidades tanto dos alunos de graduação quanto das instituições de ensino, desenvolvemos livros que buscam essa aproximação por meio de uma linguagem dialógica e de uma abordagem didática e funcional, e que apresentam os principais conceitos dos temas propostos em cada de maneira simples e concisa. Nestes livros, foram desenvolvidas seções de discussão para reflexão, de maneira a complementar o aprendizado do aluno, além de exemplos e dicas que facilitam o entendimento sobre o tema a ser estudado. Ao iniciar um você, leitor, será apresentado aos objetivos de aprendizagem e às habilidades a serem desenvolvidas no seguidos da introdução e dos conceitos básicos para que você possa dar continuidade à leitura. Ao longo do livro, você vai encontrar hipertextos que the auxiliarão no pro- cesso de compreensão do tema. Esses hipertextos estão classificados como: Saiba mais Traz dicas e informações extras sobre o assunto tratado na seção.6 Apresentação Fique atento Alerta sobre alguma informação não explicitada no texto ou acres- centa dados sobre determinado assunto. Exemplo Mostra um exemplo sobre o tema estudado, para que você possa compreendê-lo de maneira mais eficaz. Todas essas facilidades vão contribuir para um ambiente de aprendiza- gem dinâmico e produtivo, conectando alunos e professores no processo do conhecimento. Bons estudos!Prefácio Muitos dos alunos dos cursos universitários que utilizam a matemática (basicamente, todos os da área de exatas) cursaram ou ainda cursarão as temidas disciplinas de cálculo e equações diferenciais. Algo em comum entre essas disciplinas é a resolução dos problemas, e isso envolve vários fatores, como o conhecimento de técnicas matemáticas visando à simplificação de equações, a aplicação de teoremas e regras, muita paci- ência e bastante prática. Com todos esses ferramentais, pode-se, então, obter a solução exata de determinados problemas. No entanto, existem problemas cuja solução analítica é muito complexa ou que até mesmo não têm uma resposta exata. Para esses casos, existe a solução numérica, que entrega um conjunto de respostas aproximadas para a solução de certos problemas. o cálculo numérico é, então, uma ferramenta utilizada para resolver problemas matemáticos utilizando métodos iterativos (ou aproximações sucessivas) aplicados em calculadoras ou computadores, com o intuito de obter a solução aproximada de determinados problemas. Esses problemas podem ser, por exemplo, resoluções de derivadas, integrais, equações diferenciais ordinárias ou parciais. A resolução de problemas numéricos utilizando métodos iterativos pode necessitar de um número muito grande de iterações (devido à precisão da solução solicitada), e isso torna o compu- tador uma ferramenta fundamental, uma vez que a realização das iterações à mão é impraticável. Nesta obra, o aluno ou profissional terá acesso a um rico conjunto de ensinamentos sobre algoritmos e cálculo numérico. o objetivo é preparar o leitor para implementar as técnicas de resolução de cálculo numérico, e para isso serão apresentados o método de Newton-Raphson (para obter raizes de conjuntos de equações) e o método de mínimos quadrados (para realizar a8 Prefácio aproximação de polinômios). Também serão vistos métodos para a solução de derivadas, integrais e equações diferenciais. Desejo a todos uma boa leitura e um excelente aproveitamento deste conteúdo, de grande importância. Marcos Antônio Abdalla JúniorSumário Introdução à lógica proposicional 11 Alysson Nunes Diógenes Conceitos básicos 12 Como usar a tabela verdade? 16 Semäntica 18 Introdução à lógica de predicados 25 Fabio Santiago Lógica de predicados 26 Lógica dos conjuntos 31 Comparação da lógica de predicados com a lógica proposicional 35 Tipos de dados e variáveis 41 Silvano Antonio Alves Tipos de dados 41 Dados booleanos e dados literais 44 Variáveis 46 Introdução à construção de algoritmos 51 Antonio Alves Junior o que são algoritmos 52 Construção de algoritmos 54 Algoritmos e pseudocódigo 56 Introdução ao cálculo numérico e ao erro computacional 61 Cynthia da Silva Métodos numéricos 62 Erros numéricos computacionais 65 Exemplos de cálculo de erros numéricos 7010 Sumário Método de Newton-Raphson 75 Sebajos Voz o método de Newton-Raphson 76 o método de Newton-Raphson no cálculo de raizes de equações 83 o erro estimado 87 Regressão por mínimos quadrados 91 de Freitas Método dos minimos quadrados discreto, continuo e não linear 91 Diferenças entre a regressão e a interpolação no processo de aproximação de valores estimados 98 Regressão para ajustar uma reta a um conjunto de dados 99 Diferenciação numérica 103 G. de Oliveiro Martins Derivada 104 Equação da derivada 106 Diferenciação numérica 109 Integração numérica 115 Rafuel Integral de uma função 116 Regras de Newton-Cotes da integração numérica 117 Exemplos resolvidos 126 Quadratura de Gauss 129 Fabio Santiago Integração Gauss-Legendre 130 Integração Gauss-Lobatto 136 Integração dupla 140 Métodos numéricos para resolução de equações diferenciais ordinárias 145 Celso Definição de equações diferenciais ordinárias 146 Método de Euler para equações diferenciais ordinárias de primeira ordem 148 de Taylor para equações diferenciais de segunda ordem 152 Método de Runge-Kutta 157 Rodrigues Definição 158 Método de Runge-Kutta Método de Euler 161 Exemplos do método de Runge-Kutta 161Introdução à lógica proposicional Alysson OBJETIVOS DE APRENDIZAGEN > Diferenciar lógica de sintaxe. Identificar como é usada a tabela verdade. > Explicar a da lógica proposicional. Introdução As regras da lógica matemática especificam métodos de de afirmações matemáticas. o filósofo grego Aristóteles foi o pioneiro do raciocínio lógico, que fornece a base teórica para muitas áreas da e, consequentemente, do cálculo numérico. Tem, portanto, muitas aplicações, como em projeto de com- putadores, em inteligência artificial, na definição de estruturas de dados para linguagens de programação, etc. MADRE, 1994). Especificamente, a lógica proposicional se preocupa com afirmações às quais os valores de verdade, "verdadeiro" e "falso", podem ser atribuídos. o objetivo é analisar essas afirmações individualmente ou de forma composta, tarefa fun- damental na matemática. Por isso, neste capítulo, apresentaremos os conceitos básicos e as principais ferramentas da lógica proposicional. A seguir, serão examinadas as regras sintáticas que definem a linguagem da lógica proposicional. Em seguida, será introduzida a noção de atribuição de verdade, utilizada para definir o significado das sentenças da lógica proposi- cional. Depois, será apresentado um método mecânico para avaliar sentenças para determinada atribuição de verdade e um método para encontrar atribui-12 Introdução à lógica proposicional ções de verdade que satisfaçam as frases. capítulo é encerrado com alguns exemplos de lógica proposicional na formalização de linguagem natural e de circuitos digitais. Conceitos básicos A lógica proposicional se preocupa com proposições e seus inter-relacio- namentos. A noção de uma proposição, aqui, não pode ser definida com precisão. Grosso modo, uma proposição é uma condição do mundo que é verdadeira ou falsa, como, por exemplo, a possibilidade de que esteja chovendo, a possibilidade de que esteja nublado e assim por diante. A con- dição, então, não precisa ser verdadeira para que seja uma proposição. Por exemplo, veja as frases a seguir: 1. Como 2. Elefantes são menores do que formigas. 3. o Brasil é um de dimensões continentais. 4. 5. Hoje não está chovendo e tenho dinheiro; logo, vou à praia. 6. 2+2=4 Todas as frases, com exceção da primeira e da sexta, são proposições. Isso pode ser verificado porque, independentemente de serem verdadeiras ou falsas, essas frases fazem uma afirmativa. Por outro lado, nem a frase 1, nem a 6 são afirmações. Sintaxe Na lógica, sintaxe é qualquer coisa que tenha a ver com linguagens formais ou sistemas formais, sem levar em conta qualquer interpretação ou significado dado a eles. A sintaxe se preocupa com as regras usadas para construir ou transformar os simbolos e palavras de uma linguagem, em contraste com a semântica de uma linguagem, que se preocupa com seu significado (MEN- DELSON, 2009). Ou seja, a sintaxe apenas define um conjunto de fórmulas, sistemas, teoremas, provas e interpretações, enquanto a semântica indica o sentido de frases formadas com a sintaxe. Na ciência da computação, o termo sintaxe se refere às regras que go- vernam a composição de expressões bem formadas em uma linguagem de programação. Como na lógica matemática, é independente da semântica eIntrodução à lógica proposicional 13 da interpretação. Na lógica proposicional, existem dois tipos de sentenças: sentenças simples e sentenças compostas. Frases simples expressam fatos simples sobre o mundo, enquanto frases compostas expressam relações lógicas entre as frases mais simples de que são compostas. Frases simples, na lógica proposicional, frequentemente são chamadas de constantes proposicionais ou, às vezes, de constantes lógicas. A seguir, escreve-se constantes de proposição como cadeias de letras, digitos e subli- nhados ("_"), em que o primeiro caractere é uma letra Por exemplo, chover é uma constante de proposição, assim como c32hover e chover_ou_nevar. Chover não é uma constante de proposição porque começa com um caractere maiúsculo; 324567 não é porque começa com um número; chover-ou-nevar falha porque contém hifens (em vez de sublinhados). As sentenças compostas são formadas a partir de sentenças mais simples e expressam relações entre as sentenças constituintes. Existem cinco tipos de frases compostas (MENDELSON, 2009): 1. negações; 2. conjunções; 3. disjunções; 4. implicações; 5. bicondicionais. Uma negação consiste no operador de negação - e em uma sentença arbitrária, chamada de alvo. Por exemplo, dada a sentença p, pode-se formar a negação de p como (-p). Uma conjunção (operador E) é uma sequência de sentenças separadas por ocorrências do operador A e colocadas entre parênteses. As sentenças constituintes são chamadas de conjuntos. Por exemplo, pode-se formar a conjunção de p e na forma Fique atento Frases compostas podem ser formadas utilizando mais de uma con- junção. Note, por exemplo a frase composta, Uma disjunção (operador OU) é uma sequência de sentenças separadas por ocorrências do operador e colocadas entre parênteses. As sentenças constituintes são chamadas de disjuntos. Por exemplo, pode-se formar a disjunção de p e q na forma:14 Introdução à lógica proposicional Uma implicação (operador LOGO) consiste em um par de sentenças se- paradas pelo operador = e colocadas entre parênteses. A frase à esquerda do operador é chamada de antecedente e a frase à direita é chamada de A implicação de Um bicondicional é uma combinação de uma implicação e uma implicação reversa. Por exemplo, podemos expressar a bicondicional Observe que as frases constituintes em qualquer sentença composta po- dem ser sentenças simples ou sentenças compostas, ou, ainda, uma mistura das duas. Por exemplo, esta é uma sentença composta: desvantagem de nossa notação é que os parênteses tendem a se acumular e precisam ser combinados corretamente. Seria bom se dispensar os parênteses, por exemplo, simplificando a frase anterior para a seguinte: não se pode retirar inteiramente dos parênteses, uma vez que isso poderia causar Por exemplo, a frase anterior pode ter resul- tado da retirada dos parênteses de qualquer uma das duas seguintes frases. A solução para esse problema é o uso da chamada precedência do opera- dor, que é uma sequência de prioridades para operadores. A tabela a seguir fornece uma hierarquia de precedências para os operadores. o operador tem precedência maior do que tem precedência mais alta do que tem precedência mais alta do que e tem precedência maior do que Assim, a sequência de prioridades é (MENDELSON, 2009): A Em frases sem parênteses, é comum que uma expressão seja ladeada por operadores, um de cada lado. Ao interpretar essas frases, a questão é se a expressão se associa ao operador a sua esquerda ou ao operador a sua direita. Pode-se usar a precedência para fazer essa determinação. Em particular, concorda-se que um operando em tal situação sempre se associa ao operador de precedência superior. Os exemplos a seguir mostram como essas regras funcionam em vários casos. As expressões à direita são as versões entre parênteses das expressões à esquerda.Introdução à lógica proposicional 15 PA-q Quando um operando está rodeado por dois operadores A ou por dois operadores o operando é associado à esquerda. Quando um operando está rodeado por dois operadores = ou por dois operadores o operando é associado à direita, como nos exemplos a seguir. Observe que só porque a precedência permite excluir os parênteses em alguns casos, não significa que se deve dispensá-los totalmente. Considere o exemplo mostrado anteriormente. A precedência elimina a ambiguidade ao ditar que a frase sem parênteses é uma implicação com uma disjunção como antecedente. No entanto, isso cria um problema para os casos em que se deseja expressar uma disjunção com uma implicação como disjunta. Nesses casos, deve-se manter, pelo menos, um par de parênteses. Encerra-se a seção com duas definições simples que são úteis na discussão da lógica proposicional. Um vocabulário proposicional é um conjunto de constantes proposicionais. Uma linguagem proposicional é o conjunto de todas as sentenças proposicionais que podem ser formadas a partir de um vocabulário proposicional. Exemplo Construa uma frase composta utilizando as proposições: Deus ajuda quem cedo madruga Tiago acorda cedo Deus ajudará Tiago Resposta:16 Introdução à lógica proposicional o provérbio popular pode ser convertido em frases e em vocabulário pro- posicional. Para isso, pode-se reescrever as proposições da seguinte forma: Deus ajuda quem cedo madruga E Tiago acorda cedo LOGO Deus ajudará Tiago Assim, chamando as proposições de ordem em que foram listadas: Como usar a tabela verdade? Antes de apresentar a tabela verdade, é importante conhecer o conceito de avaliação. Avaliação Avaliação é o processo de determinar os valores de verdade de sentenças compostas, dadas uma atribuição de verdade para os valores de verdade de constantes proposicionais (VAN DALEN, 2012). De fato, existe uma técnica simples para avaliar frases complexas. Substi- tui-se valores verdadeiros e falsos pelas constantes de proposição na frase, formando uma expressão com 1s e Os e operadores lógicos. Usa-se a de operador para avaliar subexpressões com esses valores verdade como argumentos. Em seguida, repete-se, trabalhando de dentro para fora, até ter-se um valor verdade para a frase como um todo. Como exemplo, considere a atribuição de verdade i mostrada a seguir. Usando o método de avaliação, pode-se ver que i Note que o operador (OU) retorna 1 quando um ou os dois valores comparados são 1. Da mesma forma, o operador A (E) apenas retorna 1 quando ambos os valores comparados são 1. 1Introdução à lógica proposicional 17 Agora considere a atribuição de verdade j definida como segue: Nesse caso, i não satisfaz 0 Usando essa técnica, pode-se avaliar a verdade de sentenças arbitrárias em uma linguagem. o custo é proporcional ao tamanho da frase. Claro que, em alguns casos, é possivel economizar e fazer ainda melhor. Por exemplo, ao avaliar uma conjunção, se for descoberto que o primeiro conjunto é falso, então não há necessidade de avaliar o segundo conjunto, pois a sentença como um todo deve ser falsa 2007). Satisfação A satisfação é o oposto da avaliação (VAN DALEN, 2012). Começa-se com uma ou mais sentenças compostas e tenta-se descobrir quais atribuições de verdade satisfazem essas sentenças. Uma boa característica da lógica proposicional é que existem procedimentos eficazes para encontrar atribuições de verdade que satisfazem sentenças da lógica proposicional. Nesta seção, estuda-se um método baseado em tabelas verdade. Uma tabela verdade para a linguagem proposicional é uma tabela que mostra todas as atribuições de verdade para as constantes propo- sicionais na linguagem. As colunas da tabela correspondem às constantes de proposição da linguagem e as linhas correspondem a diferentes atribuições de verdade para essas Veja, a seguir, uma tabela verdade para uma linguagem proposicional com apenas três constantes de proposição Cada coluna corresponde a uma constante de proposição e cada linha corresponde a uma única atribuição de verdade.18 Introdução à lógica proposicional q 1 1 1 1 1 1 0 1 1 0 o 0 1 1 0 1 o 0 1 Observe que, para uma linguagem proposicional com n constantes de proposição, há n colunas na tabela verdade e linhas. Na solução de problemas de satisfação, começa-se com uma tabela verdade para as constantes proposicionais da linguagem. Em seguida, pro- cessa-se as sentenças sucessivamente, para cada sentença, colocando um "x" próximo às linhas na tabela verdade correspondente a atribuições de verdade que não satisfazem a sentença. As atribuições de verdade restantes no final desse processo são todas as atribuições de verdade das sentenças de entrada. Como exemplo, considere a sentença r. Pode-se encontrar todas as atribuições de verdade que satisfazem essa sentença construindo uma tabela de verdade para e r. Veja na tabela a seguir. Colocou-se um "x" próximo a cada linha que não satisfaça a sentença (linhas 2, 3, 4, 6). Finalmente, considera-se as linhas restantes (1, 5, 7, 8) como respostas. q 1 1 1 1 1 1 0 1 1 0 0 1 1 (Continua)Introdução à lógica proposicional 19 (Continuação) p q 0 1 o 0 1 0 A desvantagem do método da tabela verdade é a complexidade computa- Conforme mencionado, o tamanho de uma tabela verdade para uma lin- guagem cresce exponencialmente com o número de constantes proposicionais na linguagem. Quando o número de constantes é pequeno, o método funciona bem. Quando o número é grande, o método tende a se tornar impraticável. Mesmo para problemas de tamanho moderado, pode ser entediante. Mesmo para uma aplicação simples em que existam 16 constantes de proposição, existem 65.536 atribuições de verdade (BICEN, 2020). Ao longo dos anos, os pesquisadores propuseram maneiras de melhorar o desempenho da verificação da tabela verdade. No entanto, a melhor abordagem para lidar com grandes vocabulários é usar manipulação (ou seja, racio- cinio lógico e testes) em vez de verificação da tabela verdade (VAN DALEN, 2012). Saiba mais Tabelas verdade também podem ser utilizadas para otimização de circuitos de portas lógicas. Diferentemente da sintaxe, que não se preocupa com o sentido de uma frase, a é o ramo da lógica que trata do sentido que das frases. o tratamento da em lógica é semelhante a seu tratamento em álgebra. A álgebra não se preocupa com a importância das variáveis no mundo real. o que é inte- ressante são as relações entre os valores das variáveis expressas nas equações que escrevemos. Os métodos algébricos são projetados para respeitar essas relações, independentemente do que as variáveis representam (VAN DALEN, 2012). Fique atento A se preocupa com o uso correto dos operadores para que uma frase faça sentido.20 Introdução à lógica proposicional De maneira semelhante, a lógica não se preocupa com o significado das cons- tantes proposicionais no mundo real. É curioso notar a relação entre os valores de verdade de sentenças simples e os valores de verdade de sentenças compostas dentro das quais as sentenças simples estão contidas. Assim como acontece com a álgebra, os métodos de lógico são independentes do significado das constantes proposicionais tudo o que importa é a forma das frases. Embora os valores atribuídos às constantes de proposição não sejam cruciais no sentido que acabamos de descrever, ao falar da lógica, às vezes é útil tornar explicitas as atribuições de verdade e considerar várias atribuições ou todas as atribuições e assim por diante. Essa atribuição é chamada de atribuição de verdade. Formalmente, uma atribuição de verdade para um vocabulário proposicio- nal é uma função que atribui um valor de verdade a cada uma das constantes proposicionais do A seguir, usamos o dígito 1 como sinônimo para verdadeiro e 0 como para falso, e nos referimos ao valor de uma constante ou expressão sob uma atribuição de verdade i sobrescrito da constante ou expressão com i como sobrescrito. A atribuição mostrada a seguir é um exemplo para o caso de um vocabulário proposicional com apenas três constantes de proposição: e A seguinte atribuição é outra atribuição verdadeira para o mesmo vocabulário: 1 Observe que as fórmulas anteriores não são sentenças em si mesmas na lógica proposicional. a lógica proposicional não permite sobrescritos e não usa o Em vez disso, essas são declarações informais sobre atribuições de verdade específicas. Embora falar sobre lógica proposicional usando uma notação semelhante a essa lógica proposicional possa, às vezes, ser confuso, isso permite transmitir metainformação com precisão e eficiência. Para minimizar problemas, usa-se essa metanotação com pouca frequência e apenas quando há pouca chance de confusão.Introdução à lógica proposicional 21 Olhando para as atribuições de verdade anteriores, é importante ter em mente que, no que diz respeito à lógica, qualquer atribuição de verdade é tão boa quanto qualquer outra. A própria lógica não fixa a atribuição de verdade de constantes de proposições individuais. Por outro lado, dada uma atribuição de verdade para as constantes pro- posicionais de uma linguagem, a lógica fixa a atribuição de verdade para todas as sentenças compostas nessa linguagem. Na verdade, é determinar o valor verdade de uma frase composta aplicando repetidamente as seguintes regras. Se o valor verdade de uma frase é "verdadeiro", o valor de verdade de sua negação é "falso". Se o valor de verdade de uma frase é "falso", o valor de verdade de sua negação é "verdadeiro": 1 0 0 o valor verdade de uma conjunção é "verdadeiro" se, e somente se, os valores de verdade de seus conjuntos forem ambos "verdadeiros"; caso con- trário, o valor verdade é "falso": 1 1 1 1 1 0 0 0 0 o valor verdade de uma disjunção é "verdadeiro" se, e somente se, o valor de verdade de pelo menos uma das disjunções for "verdadeiro"; caso contrário, o valor verdade é "falso". Observe que essa é a inclusiva ou interpretação do operador e é diferenciada da exclusiva ou interpretação na qual uma disjunção é verdadeira se, e somente se, um número impar de seus disjuntos for "verdadeiro":22 Introdução à lógica proposicional 1 1 1 1 0 1 0 1 1 0 0 o valor verdade de uma implicação é "falso" se, e somente se seu antece- dente for "verdadeiro" e seu consequente for "falso"; caso contrário, o valor verdade é "verdadeiro". Isso é chamado de implicação material (VAANANEN, 2007): 1 1 1 0 0 0 1 1 1 Uma bicondicional é "verdadeira" se, e somente se, os valores "verdadeiros" de seus constituintes concordarem, ou seja, se forem "verdadeiros" ou "falsos": 1 1 1 1 0 1 0 0 1Introdução à lógica proposicional 23 Referências BICEN, Y. Propositional logic concept for fault diagnosis in complex systems. Engineering Science and Technology, an International Journal, 23, 5, p. 1068-1073, out. 2020. Acesso em: 25 nov. 2020. COUDERT, MADRE, Metaprime: an interactive fault-tree analyzer. IEEE Transactions on Reliability, 43, n° 1, p. 121-127, mar. 1994. MENDELSON, E. Introduction to mathematical logic. 5th ed. London: Chapman and Hall, 2009. J. Dependence logic: a new approach to independence friendly logic. Cam- bridge: Cambridge University Press, 2007. VAN DALEN, D. Logic and structure. Berlin: Springer, 2012. Leitura recomendada ALENCAR FILHO, E. de. Iniciação à lógica matemática. 21. ed. Barueri: Nobel, 2017. Fique atento Os links para sites da web fornecidos neste capítulo foram todos testados, e seu funcionamento foi comprovado no momento da publicação do material. No entanto, a rede é extremamente dinâmica; suas páginas estão constantemente mudando de local e Assim, os editores declaram não ter qualquer responsabilidade sobre qualidade, precisão ou integralidade das informações referidas em tais links.Introdução à lógica de predicados Fabio Santiago OBJETIVOS DE APRENDIZAGEM > Definir lógica de predicados. > Explicar a lógica dos conjuntos. > Comparar lógica de predicados e lógica proposicional. Introdução Neste capítulo, você vai aprender os conceitos fundamentais sobre o tema da lógica de predicados, de fundamental importância para desenvolver uma solução algorítmica para determinado problema, possibilitando, assim, sua implementação posterior por meio de uma adequada linguagem de programação. Nesse sentido, inicialmente será definida a lógica dos predicados, momento em que serão apresentados a simbologia a ser utilizada, as fórmulas, os quan- tificadores e os enunciados. Em um segundo momento, será trabalhado o tema da lógica dos conjuntos por meio dos diagramas de Venn para a representação dos enunciados. Por fim, haverá um estudo comparando os predicados e a lógica proposicional, quando serão apresentados exemplos de aplicações. Ao final deste capítulo, você terá aprendido os fundamentos da lógica de predicados, o que lhe auxiliará no desenvolvimento de seus futuros algoritmos e implementações computacionais.26 Introdução à lógica de predicados Lógica de predicados Ao desenvolver uma implementação computacional empregando uma lingua- gem definida como procedural, o código computacional deve detalhar de forma única a tarefa que deve ser resolvida. Nesse sentido, tais linguagens fazem uso de conectivos, sentenças lógicas, regras para tomadas de decisão e testes lógicos entre elementos, que fazem parte do tema da lógica de predicados. o estudo da lógica de predicados tem como ponto inicial o conhecimento de sua sintaxe, pois é a partir dela que todos os outros conceitos são desen- volvidos. Assim, como observa Bravo (2016), a lógica de predicados é composta por conectivos lógicos: negação "e" "V" ou. se e somente se. Segundo os de Paulo Pereira 2016a, 2016b, 2016c), parte expressiva da lógica de predicados resulta do uso dos conectivos, pois eles possibilitam formar sentenças de maior complexidade a partir de sen- tenças simples. Também fazem parte da composição da lógica de predicados: objetos; predicados; variáveis; quantificadores. De acordo com Pereira ([2016?]), na lógica de predicados, a noção de objetos é utilizada em um sentido bastante amplo, podendo ser: esse livro, o sol, um dragão, entre outros. Nesse sentido, ainda segundo o autor, um objeto pode ser qualquer coisa a respeito de qualquer coisa. Saiba mais Como observa Bravo (2016), os objetos podem ser do tipo concreto (p. ex., este livro), abstrato conjunto vazio, a paz), fictício (p. ex., Unicórnio e Saci-Pererê), além de atômicos ou compostos (p. ex., um teclado é composto por teclas).Introdução à lógica de predicados 27 Segundo Pereira ([2016?]), um predicado denota uma relação entre objetos de determinado contexto de discurso. Para que você consiga compreender essa relação, considere o exemplo a seguir. Exemplo Considere a imagem a seguir. B A C A partir da imagem, pode-se afirmar que o bloco B está sobre o bloco A, pelo uso do predicado sobre e escrevendo Sobre (b, a). Com o objetivo de afirmar que o bloco é azul, é possível empregar o predicado cor e escrever cor (B, azul). Por sua vez, para afirmar que o bloco A é maior do que o bloco C, pode-se empregar o predicado maior e escrever maior (A, Os dois últimos elementos que compõem a lógica de predicados - as variáveis e os quantificadores - são os responsáveis por tornar essa lógica mais expressiva que a lógica dos proposicional, uma vez que a utilização de variáveis permite estabelecer fatos a respeito de objetos de determinado contexto de discurso sem, no entanto, nomear de forma esse objetivo. Por sua vez, os quantificadores universais para todo existencial possibilitam estabelecer fatos sobre todos os objetos de determinado con- texto, sem a necessidade de enumerar de forma explicita todos os elementos, e por meio do uso do quantificador existencial. Como observa Abar (2004), de modo geral temos que: P(x): x tem a propriedade : a propriedade P vale para todo x, ou, ainda, todos os objetos do universo considerado são detentores da propriedade P (3x)P(x): existe no mínimo um objeto do universo considerado que tem a propriedade P.28 Introdução à lógica de predicados Para elucidar os conceitos apresentados, que talvez possam estar muito abstratos nesse momento, considere os exemplos a seguir. Exemplo 1 Considere as seguintes afirmações: Todo P é o (universal afirmativa). Nenhum P é Q ou todo P não é o (universal negativa). Algum P é (particular afirmativa). Algum P não é o (particular negativa). Utilizando a lógica de predicados, formalize cada uma das sentenças anteriores. Solução: Todo P é Q (universal afirmativa) Q(x)). Nenhum P é ou todo Pnão é o (universal negativa) Algum P é o (particular afirmativa) Algum P não é o (particular negativa) (3x)(P(x)^~Q(x)). Exemplo 2 Considere as seguintes sentenças: Existem plantas que são Alguns políticos não são honestos. Há aves que não voam. Formalize cada uma delas com o uso da lógica de predicados. Solução: Existem plantas que são (3x) (plantas (x) Alguns políticos não são honestos Há aves que não voam (3x) (aves (x)^~voam(x)).Introdução à lógica de predicados 29 Exemplo 3 Considere as seguintes sentenças: Todos os humanos são racionais. Alguns animais são racionais. Portanto, alguns animais são racionais. Utilizando a lógica de predicados, transcreva cada uma das afirmações. Solução: Inicialmente, definimos que a propriedade P simboliza ser humano, Q ser racional, e R ser animal. Assim, têm-se: Todos os humanos Alguns animais são racionais Portanto alguns animais são racionais: Exemplo 4 Considere a sentença "Toda filha do meu pai é minha bem como os seguintes predicados: é filha de de Formalize a sentença através da lógica de predicados. Solução: Considere e como o objeto "eu"; assim, temos que: Ou, de outra forma, considerando p(x) a função pai de "x", a sentença anterior poderia ser escrita como:30 Introdução à lógica de predicados No último exemplo, você teve contato com o conceito de função, no con- texto da lógica dos predicados. Fique atento Segundo Silva (2014), a lógica de predicados pode fazer uso do con- ceito de função. Considere a sentença "Toda criança é mais jovem do que sua a qual pode ser formalizada por: Sendo os predicados: é uma criança. M(y,x) é a mãe de. x é mais jovem do que y. As funções visam a simplificar o que está sendo dito. Nesse sentido, a formalização da sentença anterior poderia ter sido feita por meio de pois seria empregar a função m(x) para re- presentar a mãe de x em vez do predicado A partir dos exemplos apresentados, pôde aprender a manipular a lógica dos predicados. Para finalizar este tópico inicial, reunimos no Quadro 1 as regras de inferência, com os seguintes pontos fundamentais: o que é deduzir, regras e as restrições de uso para cada uma. Quadro 1. Regras de Inferência De Podemos deduzir Regra Restrição de Uso onde é uma Particularização Se t for uma variável, variável ou um universal não deve estar símbolo constante dentro do escopo de um quantificador para t x(P(x)) P(t), onde t Particularização necessário que seja é uma variável existencial a primeira regra a ou um usar constante não utilizado anteriormente na sequência de demonstração (Continua)Introdução à lógica de predicados 31 (Continuação) De Podemos deduzir Regra Restrição de Uso P(x) Generalização P(x) não pode ter universal sido deduzida de nenhuma hipótese na qual é uma variável livre nem pela particularização existencial, de uma fbf* na qual x é uma variável livre P(x) ou P(a) 3x(P(x)) Generalização Para in de P(a) a existencial x não pode aparecer em P(a) bem definida. Fonte: Adaptado de Bravo (2016). No tópico a seguir, você aprenderá como um ferramental lógico matemático pode ser utilizado com o auxílio de conjuntos e do diagrama de Venn. Lógica dos conjuntos Os diagramas de Venn empregados na teoria dos conjuntos podem ser úteis para verificar a validade de um argumento na lógica de predicados, bem como, segundo Pereira ([2016?]), para formalizar argumentos na lógica de predicados. Nesse sentido, para dar a este estudo, considere quatro tipos de sentenças de especial interesse, denominadas enunciados categóricos - universal afirmativo, universal negativo, particular afirmativo e particular negativo para cada um dos quais serão apresentados sua definição e o diagrama de Venn. o enunciado categórico universal afirmativo é enunciado como Q(x)). que, na forma de conjuntos, estabelece que o conjunto dado por P é um subconjunto de Q.32 Introdução à lógica de predicados Exemplo 1 Utilizando a lógica de predicados, formalize e, em seguida, represente por meio do diagrama de Venn, a sentença: "Todo ser humano é mortal". Solução: Incialmente, traduzindo a sentença, tem-se que sendo H(x): é ser humano; e M(x): é mortal. Na Figura 1, há a representação do diagrama de Venn para o enunciado categórico universal afirmativo. M H x Figura 1. Representação universal afirmativo pelo diagrama de Venn. Na categoria dos enunciados categóricos, também há o universal negativo, que corresponde aos enunciados na forma quando se considera a notação de conjuntos, os conjuntos P representados como conjuntos disjuntos. Exemplo 2 Utilizando a lógica de predicados, formalize e, em seguida, represente, por meio do diagrama de Venn, a sentença: "Nenhum ser humano é extraterreste". Solução: Incialmente, traduzindo a sentença, tem-se que sendo H(x): é ser humano; e E(x): é extraterrestre. Na Figura 2, é exibida a repre- sentação do diagrama de Venn para o enunciado categórico universal negativo.Introdução à lógica de predicados 33 H E Figura 2. Representação universal negativo pelo diagrama de Venn. Por sua vez, o enunciado particular afirmativo é enunciado na forma quando se considera a notação de conjuntos; este enun- ciado categórico afirma que os conjuntos P e Q não apresentam interseção vazia. Exemplo 3 Utilizando a lógica de predicados, formalize e, em seguida, represente, por meio do diagrama de Venn, a sentença: "Alguns homens são inteligentes". Solução: Incialmente, ao traduzirmos a sentença, temos que: 3x(H(x) (x)), sendo H(x): é ser homem; e é inteligente. Na Figura 3, há a representação do diagrama de Venn para o enunciado particular afirmativo. H x Figura 3. Representação particular afirmativo pelo diagrama de Venn.34 Introdução à lógica de predicados Por fim, o último enunciado categórico é o particular negativo, com a forma (P((x)) cuja representação via diagrama de Venn estabelece que existem elementos de P que não pertencem ao conjunto A Figura 4 mostra a representação via diagrama de Venn para o particular negativo. P Figura 4. Representação particular negativo pelo diagrama de Venn. Fique atento Como observa Abar (2004), as intepretações dadas pelo diagrama de Venn são úteis na verificação da validade de um argumento cujas premissas e conclusão são enunciadas como categóricas, mas não devem ser empregados como instrumentos de prova rigorosos. Abar (2004) propõe um procedimento para verificar a validade de um argumento categórico a partir de três passos: 1. transferimos para o diagrama, formado por três as informações das premissas, iniciando pelos enunciados universais; 2. verificamos se a informação dada na conclusão está ai representada sem nenhuma condição e de modo único; 3. se isso ocorre, então o argumento é válido. A seguir, você aprenderá como utilizar o procedimento proposto por Abar (2004) para verificar a validade de um argumento categórico.Introdução à lógica de predicados 35 Exemplo 4 Considere os seguintes argumentos categóricos: 1. Todos os cientistas são 2. Alguns cientistas são inventores. 3. Alguns estudiosos são inventores. Verifique a validade deles por meio do diagrama de Venn. Solução: Inicialmente, considerando os três diagramas com cada um dos enunciados categóricos (Figura 5) e identificando em vermelho a premissa (1), em amarelo a premissa (2) e, por fim, em laranja a premissa 3. Como se pode observar, todos estão bem definidos e, logo, tem-se um argumento válido. Figura 5. Verificação dos argumentos categóricos pelo diagrama de Venn. Com este exemplo, você encerra o estudo sobre o uso do diagrama de Venn e a lógica de predicados. No tópico a seguir, estudaremos a diferença entre as lógicas de predicados e a proposicional. Comparação da lógica de predicados com a lógica proposicional Neste tópico, você identificará as diferenças entre a lógica de predicados e a lógica proposicional, inicialmente a partir da definição de cada uma delas e, depois, pelos aspectos que as diferenciam. Segundo Martins (2018), a lógica proposicional representa a forma mais simples de lógica, na qual os fatos inerentes ao mundo real são apresentados por sentenças sem argumentos, chamados proposições. Ainda conforme o autor, proposição é uma sentença, de qualquer natureza, que pode ser qualificada como verdadeira ou falsa.36 Introdução à lógica de predicados Exemplo 1 Utilizando a lógica proposicional, transcreva as sentenças a seguir. Mundo real Proposição lógica Hoje está ensolarado. P A rua está seca. o Se está ensolarado, então a rua está seca. P Q Como observa Alvim (2020), a lógica proposicional cobre a análise de proposições compostas, isto é, proposições simples ligadas por conectivos Entretanto, esta não é expressiva o suficiente para capturar to- das as afirmações. Para compreender esse tipo de limitação, considere as seguintes sentenças: Todos os matriculados em cálculo numérico são estudantes dedicados. Felipe está matriculado em cálculo numérico. De maneira intuitiva, você conseguiu concluir que: "Felipe é um estudante dedicado". Apesar de fácil dedução, esse tipo de inferência somente é com o uso de predicados e quantificadores, os quais estão presentes na lógica de proposições, como estudado nos tópicos anteriores. Exemplo 2 Considerando a lógica de predicados, formalize cada uma das sentenças. Sentença Predicado Sentença formal Nenhuma arara é A(x): "x é uma arara" pequena. As araras coloridas são C(x): "x é colorido" (A(x) grandes. Existe uma arara que não P(x): "x é pequeno" 3x: é colorida, nem pequena.Introdução à lógica de predicados 37 o Quadro 2, desenvolvido por Silva (2018), resume de forma didática as diferenças entre a lógica proposicional e a de predicados. Quadro 2. Diferença entre a lógica proposicional e a lógica de predicados Lógica Proposicional Lógica de Predicados Modela sentenças Modela objetos por meio de Fácil compreensão variáveis Primeiro aprendizado na área de Modela relações entre objetos representação do conhecimento e Modela funções raciocínio Permite composição de atributos Não consegue modelar de Permite derivação de forma simples objetos e suas relacionamentos de forma mais propriedades simples Não consegue modelar Consegue tratar problemas quantidades de quantificação por meio de Não consegue enumerar objetos quantificadores de modo simples Fonte: Adaptado de Silva (2018). Por fim, é importante considerar a conexão entre linguagem e as lógicas proposicional e de predicados. Como observa Silva (2018), as linguagens lógicas têm o papel de representar conhecimento para um agente. Esse conhecimento apresenta um aspecto ontológico, que consiste na representação do ambiente no qual o agente está inserido, e um aspecto epistemológico, que consiste na que o agente encontra nos fatos. o Quadro 3 relaciona o modo como cada uma das lógicas representa esses aspectos. Quadro 3. Relação entre as lógicas de predicados e proposicional e a linguagem Aspecto Linguagem Aspecto ontológico epistemológico Lógica proposicional Fatos Verdadeiro, falso e desconhecido Lógica de predicados Fatos, objetos e Verdadeiro, falso e relações desconhecido Fonte: Adaptado de Silva (2018).38 Introdução à lógica de predicados Referências ABAR, C. Noções de lógica matemática. Universidade Católica de São Paulo, São Paulo, 2004. Disponível em: htm. Acesso em: 28 dez. 2020. ALVIM, M. S. Os fundamentos: lógica de predicados. Belo Horizonte: Departamento de Ciência da Computação, Universidade Federal de Minas Gerais, 2020. 52 p. (Notas de aula da disciplina Introdução à Lógica Computacional). Disponível em: https://home- pdf. Acesso em: 28 dez. 2020. BRAVO, R. S. F. Lógica de predicados. Niterói: Instituto de Computação, Universidade Federal Fluminense, 2016. 49 p. (Notas de aula da disciplina Fundamentos Matemáticos para Computação). Disponível em: http://www.ic.uff.br/-ueverton/files/aulasFMC/ Aula%2014.pdf. Acesso em: 28 dez. 2020. LÓGICA: CONECTIVOS S. n.], 2016a. 1 video (17 min 59 s). Publicado pelo canal Equaciona Com Paulo Pereira. Disponível em: https://www.youtube.com/ watch?v=i8jbzEWEOYk. Acesso em: 28 dez. 2020. LÓGICA: EQUIVALÊNCIAS LÓGICAS. 2016b. 1 video (8 min 30 s). Publicado pelo canal Equaciona Com Paulo Pereira. Disponível em: https://www.youtube.com/ Acesso em: 28 dez. 2020. LÓGICA: QUANTIFICADORES. 2016c. 1 video (6 min 46 s). Publicado pelo canal Equaciona Com Paulo Pereira. Disponível em: Acesso em: 28 dez. 2020. MARTINS, L. G. A. Apostila de lógica proposicional: fundamentos básicos. Faculdade de Computação, Universidade Federal de 2018. 28 p. Disponível em: Acesso em: 28 dez. 2020. PEREIRA, S. L. Logica de predicados. São Paulo: Instituto de Matemática e Estatística, Universidade de São Paulo, [2016?]. Disponível em: https://www.ime.usp.br/-slago/ Acesso em: 28 dez. 2020. SILVA, F. D. Lógica de predicados. Rio de Janeiro: Centro de Ciências Exatas e Tecnologia, Universidade Federal do Estado do Rio de Janeiro, 2018. 59 p. Dispo- nivel em: 28 dez. 2020. SILVA, R. D. Lógica de predicados. Curitiba: Departamento Acadêmico de Informática, Universidade Tecnológica Federal do Paraná, 2014. 7 p. (Notas de aula da disciplina Lógica para Computação). Disponível em: http://www.dainf.ct.utfpr.edu.br/-rdutra/ Acesso em: 28 dez. 2020. Leituras recomendadas ABE, J. M.; SCALZITTI, A.; SILVA FILHO, J. Introdução à lógica para a ciência da compu- tação. São Paulo: Arte & Ciência, 2002. 247 p. GENESERETH, M. R.; NILSSON, N. J. Logical foundations of artificial intelligence. Palo Alto: Morgan Kaufmann, 405 p.Introdução à lógica de predicados 39 Fique atento Os links para sites da web fornecidos neste capítulo foram todos testados, e seu funcionamento foi comprovado no momento da publicação do material. No entanto, a rede é extremamente dinâmica; suas páginas estão constantemente mudando de local e conteúdo. Assim, os editores declaram não ter qualquer responsabilidade sobre qualidade, precisão ou integralidade das informações referidas em tais links.Tipos de dados e variáveis Silvano Antonio Alves Pereira Junior OBJETIVOS DE APRENDIZAGEM > Reconhecer os tipos de dados numéricos. > Definir dados lógicos. > Identificar os principais atributos de uma variável. Introdução Neste capítulo, vamos tratar das principais categorias de dados utilizadas em algoritmos e programas. Nesse contexto, é importante recordar que algoritmos são como receitas: eles estabelecem passos claros e objetivos para que possamos alcançar um objetivo. Pense, por um instante, na receita de um bolo. Em verdade, graças a poderosos algoritmos, você pode buscar, na internet, por alguma das inúmeras receitas de bolo. Essas receitas costumam demandar ingredientes como ovos, farinha, manteiga, sal, açúcar e leite. Pois algoritmos são como receitas de bolo: também necessitam de ingredientes para que possam funcionar. No caso dos algoritmos, os ingredientes são os dados, cujas principais categorias veremos a seguir. Tipos de dados Como mencionado na introdução deste capítulo, dados são os ingredientes dos mais diversos algoritmos e programas. Ao escrever um programa, é co- mum que seja necessário armazenar os dados na memória do computador.42 Tipos de dados e variáveis As linguagens de programação podem apresentar diferentes tipos nativos de dados, isto é, classes de dados que a própria linguagem fornece ao usuário por padrão. Você verá, a seguir, os principais tipos de dados. Eles costumam aparecer, com uma ou outra peculiaridade, na maior parte das linguagens de progra- mação. Ainda que o objetivo do texto seja prover uma primeira apresentação de algoritmos e métodos numéricos utilizados na resolução de problemas matemáticos e de engenharia, os tipos de dados serão apresentados com suas tênues diferenças em duas das mais utilizadas linguagens de programação: C e Python. Para caminhar nessa direção, considere a seguinte situação: um engenheiro precisa escrever um programa que calcule o volume de um reservatório de forma Você talvez recorde, de suas aulas de matemática, que o volume de um cilindro pode ser calculado se, por exemplo, conhecermos o raio e a altura do cilindro. A Figura 1 apresenta como esse cálculo pode ser realizado a partir desses dados. V r h Figura 1. Cálculo do volume de um Fonte: Adaptada de Rogawski e Adams (2018). Observando a Figura 1, você pode relembrar que o volume do cilindro é igual ao produto de II pelo quadrado do raio do cilindro (r2) pela altura do cilindro (h). Observe que a fórmula nos indica uma maneira objetiva de calcular o volume uma vez que sejam conhecidos o valor dos dados e h). Nessa situação, os dados com os quais o engenheiro precisa trabalhar são dados numéricos. Essa é a primeira categoria de dados que veremos aqui. Em grande parte dos problemas, os dados numéricos se apresentam sob duas formas: os números inteiros e os números de ponto flutuante. Os números inteiros são utilizados para armazenar valores inteiros, isto é, números que pertencem aos conjuntos N e Z; portanto, podem ser positivos ou negativosTipos de dados e variáveis 43 e não possuem parte fracionária. os números de ponto flutuante são utilizados para armazenar números reais, ou seja, números que pertencem aos conjuntos Q e R; portanto, podem ser positivos ou negativos e possuem parte fracionária. A forma como as linguagens de programação implementam esses tipos de dados pode Veja, nos Quadros 1 e 2, como esses tipos podem ser representados em e Python. Quadro 1. Tipos de dados numéricos para a linguagem C Tipo Tamanho (bytes) int ao menos 2, usualmente 4 float 4 double 8 short int 2 long int ao menos 4, usualmente 8 Quadro 2. Tipos de dados numéricos para a linguagem Python Tipo Tamanho (bytes) int 24 float ao menos 16, usualmente 24 Observe que os conjuntos numéricos possuem operações matemáticas bem conhecidas e estabelecidas, como soma, subtração, produto e divi- são, além de outras relações nesses conjuntos, como a relação de igualdade (=) e de maior (>), entre outras. Os tipos de dados também refletem essas operações, isto é, um dado numérico do tipo float pode ser somado, multiplicado, etc., a outro dado do tipo float, ou mesmo a um dado do tipo inteiro. Fique atento Perceba que, no caso da linguagem C, mais explicitamente, os tipos de dados ocupam tamanhos diferentes na memória do computador, sendo importante escolher o tipo de dado que melhor se encaixa na tarefa a ser realizada.44 Tipos de dados e variáveis Dados booleanos e dados literais Embora possivelmente sejam os dados mais importantes no contexto do cálculo numérico, os dados de tipo numérico não são os únicos tipos de dados utilizados. Como apresentado na seção anterior, os dados de tipo numérico carregam consigo estruturas que possibilitam realizar operações e relações. No caso das relações, como a de maior ou igual (>=), podemos comparar dois números, digamos, números inteiros. Essa operação pode ser encarada, em certo sentido, como uma proposição lógica. Veja o exemplo a seguir. Exemplo Imagine que o engenheiro que escreveu um programa para calcular o volume de reservatórios tenha utilizado seu programa para calcular o volume de dois reservatórios: R1 = 100 e R2 = 120 Aqui, temos que R2 >= R1, uma vez que 120 é um número maior que 100. Por outro lado, encarar a expressão R2 R1 como uma proposição lógica: "R2 é maior ou igual a R1", que, nesse caso, seria uma proposição verda- deira. Em contrapartida, a expressão R1 R2 teria valor lógico falso. Perceba que, se o engenheiro desejar adicionar, a seu programa, a possibilidade de comparar o volume dos reservatórios, ele precisaria lidar com operações lógicas, com a necessidade de armazenar o resultado destas em Aqui, são úteis e necessários os dados de tipo lógico, ou booleano. Dados booleanos são usados para representar os dois únicos valores lógicos verdadeiro e falso (EDELWEISS; LIVI, 2014). No escopo do estudo de métodos numéricos, os dados booleanos desempenharam impor- tante papel ao possibilitarem o armazenamento dos valores lógicos e como ferramenta para o controle de fluxo de programas. Saiba mais Os dados lógicos também são chamados de dados booleanos em homenagem ao matemático inglês George Boole, cujo trabalho nos campos de equações diferenciais e lógica pavimentaram o caminho para muito do que utilizamos ainda hoje. Boa parte do trabalho pioneiro de Boole pode ser encontrado em seu livro As leis do pensamento, cuja primeira edição foi publicada em 1854. Ele também é conhecido por ter trabalhado junto com Augustus DeMorgan na criação das famosas Leis de DeMorgan.Tipos de dados e variáveis 45 Assim como no caso dos dados de tipo numérico, os dados boleanos carregam consigo uma estrutura com as operações lógicas. Isso significa que podemos utilizar operadores lógicos como E (A), OU (v) e NÃO (-) sobre essa categoria de dados. Além dos dados numéricos e booleanos aqui apresentados, existem outros tipos de dados. Entre eles, merecem destaque os dados do tipo caractere e string, algumas vezes chamados de dados literais. Como apresentado por Edelweiss e Livi (2014), os caracteres permitem representar um ASCII qualquer, como uma letra do alfabeto, um dígito numérico (aqui, sem conotação quantitativa, apenas como repre- sentação de um símbolo) ou um caractere especial (um espaço em branco também corresponde a um caractere especial). Em muitas linguagens de programação, os caracteres são representados entre apóstrofos. as strings são sequências de um ou mais caracteres. Quaisquer caracteres podem ser utilizados (letras, dígitos e símbolos), incluindo o que representa um espaço em branco. Strings também são normalmente representadas entre apóstrofos em um programa. São exemplos de caractere: 'X', Como apresentado, uma string será formada a partir de um conjunto de caracteres. São exemplos de strings: e Retomando o exemplo do engenheiro que escreveu um programa para calcular o volume dos reservatórios cilíndricos, poderia ser de grande ajuda para ele utilizar dados como strings para dar nome a cada um dos reservatórios. Ambas as linguagens citadas na seção anterior possuem suporte built-in (embutido de maneira nativa na linguagem) para esses tipos de dados, cada qual a sua maneira. Em C, encontramos o tipo de dado char, o caractere, e strings são então como listas (array) de caracteres. Em contra- partida, em Python, existe a apenas o tipo string, sendo que um caractere é tratado como uma string de um único caractere. Ambas as linguagens possuem estruturas nativas para dados booleanos. Agora que você conhece os principais tipos de dados utilizados em um programa, estamos aptos a estudar o conceito de variável. Antes, porém, é importante que você tenha clareza sobre quando cada tipo de dado deve ser utilizado. Enquanto dados numéricos inteiros e de ponto flutuante são excelentes opções para representar números, quando estiverem envolvidos em cálculos, os dados literais são de grande utilidade para representar ou indicar nomes, em um contexto que ficará mais claro a seguir.46 Tipos de dados e variáveis Variáveis De conhecimento dos principais tipos de dados, agora você estudará um dos elementos mais importantes em um programa, ainda mais para um estudante de cálculo numérico: as variáveis. Um programa ou algoritmo manipula dados que podem ou não ser mo- dificados ao longo de sua execução. Dados que podem mudar de valor ao longo da execução são chamados de variáveis. Essencialmente, uma variável representa um espaço de memória identifi- cado e reservado para guardar um valor durante a execução (EDELWEISS; LIVI, 2014). Uma vez alocada a variável, ela passa a ser referenciada no programa por meio do nome dado pelo programador, não sendo necessário saber seu endereço físico na memória. Veja o exemplo a seguir, adaptado de Ascencio e Veneruchi (2012), que visa elucidar o conceito de variável. Exemplo Dois estudantes, João e Paulo, estão tentando realizar uma conta. João "Vamos multiplicar dois números. o primeiro número é 7". Paulo guarda o primeiro número na cabeça (sua Então João diz: segundo número é 2". Paulo também guarda o segundo número na cabeça, sem esquecer o primeiro número, ou seja, cada número foi armazenado em posições diferentes da memória humana, sem sobreposição. Paulo não precisou se esquecer (apagar da memória) que o primeiro número era 7, para guardar (escrever na que o segundo número era 2. João, finalmente, pergunta: "Qual é o resultado da multiplicação?". Então Paulo utiliza os dados armazenados na memória, realiza a conta e responde dizendo que o resultado é 14. Assim, toda vez que um programa ou algoritmo recebe um dado ele precisa armazená-lo na memória do computador. Ao associar o dado a uma variável, o programa precisar deixar muito claro alguns atributos dessa variável. o primeiro atributo que o programador deve especificar ao associar uma posição da memória a uma variável é o nome da variável. Mais uma vez, no caso do programa para calcular o volume do reservatório de água, a variável de nome "r" poderia ser utilizada para armazenar o raio, enquanto uma variável de nome "h" poderia ser utilizada para armazenar a altura doTipos de dados e variáveis 47 Existem algumas boas práticas que devem ser observadas quando damos nomes a variáveis. Algumas delas podem variar de linguagem para linguagem, mas listamos, a seguir, algumas das principais. Deve começar com uma letra ou subscrito. Não deve começar com um Pode conter letras maiúsculas, números e subscrito. Não se deve utilizar Não se deve utilizar acentos. Exemplo Exemplos de nomes inválidos: 1num, ?who e +p. Exemplos de nomes válidos: var, numero, media e soma. Vale ressaltar que algumas linguagens de programação fazem diferença entre letras maiúsculas e letras Essas linguagens são chamadas de case-sensitive, como C e Python, por exemplo. Assim, as variáveis "soma" e "SOMA" são diferentes nessas linguagens. Ainda, é comum que linguagens de programação possuam algumas pala- vras reservadas, isto é, palavras que possuem uma interpretação especial na linguagem e não podem ser utilizadas como variáveis. Algumas das palavras reservadas em muitas linguagens são: and, as, assert, break, class, continue, def, del, elif, else, except, exec, finally, for, from, global, if, import, in, is, lambda, nonlocal, not, or, pass, raise, return, try, while, with, yield, True, False e None. o segundo atributo que uma variável precisa indicar é o tipo do dado que está sendo armazenado na memória. Novamente, os tipos implementados podem variar a depender da linguagem, mas os tipos aqui apresentados formam um bom ponto de partida, principalmente para o estudo de cálculo numérico. Por último, e não menos importante, ao associarmos uma posição da memória a uma variável, necessitamos indicar qual é o dado a ser armaze- nado naquela posição. o processo de associar uma variável a uma posição da memória, completos os três atributos acima discutidos, chamamos de declaração de variável. A Figura 2 ilustra um simples processo de atribuição de variáveis na lin- guagem48 Tipos de dados e variáveis sum Open Save 1 2 3 nain() 4 a, b, sun; 5 a = 6 b 7 sun = a + 8 9 valor da soma 10 11 return 12 Figura 2. Atribuição de variáveis em C. Na Figura 2, as variáveis a, b e sum são declaradas como sendo do tipo inteiro (int). Em seguida, é declarado que a variável a guardará o valor 1, a variável b guardará o valor 2 e, por fim, a variável sum guardará o valor da soma das variáveis a e b. Note que as variáveis possuem os três atributos bem definidos: 1. nome; 2. tipo de dado; 3. dado armazenado. Veja, a seguir e para encerrar este outro exemplo que trata da declaração e da utilização de variáveis. Exemplo Imagine que um engenheiro deseja escrever um programa que calcule a média dos custos de duas obras pelas quais ele é responsável. Quantas variáveis seriam necessárias? Quais seriam boas opções de nome para essas variáveis? Em primeiro lugar, precisamos identificar os dados que o engenheiro forne- cerá ao programa e o que ele espera obter como resultado. Ele precisaria fornecer os custos de cada obra. Aqui, surgem as duas primeiras variáveis Podemos por exemplo, como: Você poderia, sem cometer crime algum, utilizar nomes como obra2, co2, ou quaisquer outras possibilidades que respeitem as regras apresen- tadas acima. Existe, entretanto, a boa prática de utilizar nomes que sejam o mais autoexplicativos oTipos de dados e variáveis 49 Uma vez que esses dados estejam guardados na memória do computador, o programa precisará executar o cálculo da média: custo_medio = custo_obra1 + custo_obra2) / 2. Aqui o engenheiro poderia criar outra variável, digamos, com o nome custo_medio, que seria responsável por armazenar o resultado da operação. Uma alternativa, muito útil em alguns casos, seria também armazenar a soma dos custos em uma variável com o nome custo_total: / 2. Dessa forma, não apenas o custo médio das obras, mas também seu custo total armazenado em memória, podendo ser acessados enquanto permanecerem gravados. Assim, o engenheiro poderia utilizar três ou quatro variáveis, dependendo de quais informações ele desejar manter em Por fim, todas as variáveis utilizadas formam variáveis numéricas do tipo ponto flutuante. Atente-se, ainda, ao fato de que o número dois no denominador da fórmula que calcula a média será utilizado de forma literal no código, sem a criação de uma Referências ASCENCIO, A. F. G; CAMPOS, E. A. V. Fundamentos da programação de computadores: algoritmos, Pascal, C/C++ e 3. ed. São Paulo: Pearson Prentice Hall, 2012. EDELWEISS, N.; LIVI, M. A. Algoritmos e Programação com Exemplos em Pascal e ed. Porto Alegre: Bookman, 2014. ROGAWSKI, J.; ADAMS, C. Cálculo. 3. ed. Porto Alegre: Bookman, 2018. 1. Leituras recomendadas CHAPRA, S. C.; CANALE, R. P. Métodos Numéricos para Engenharia. 7. ed. Porto Alegre: AMGH, 2016. CHAPRA, Métodos Numéricos Aplicados com para Engenheiros e Cientistas. 3. ed. Porto Alegre: AMGH, 2013. DORNELLES FILHO, A.A. Fundamentos de Cálculo Numérico. 1. ed. Porto Alegre: Book- man, 2016. FARRER, H. et Programação Estruturada de Computadores - Algoritmos 3. ed. Rio de Janeiro: LTC, 1999.50 Tipos de dados e variáveis MANZANO, J. A. N. G.; OLIVEIRA, J. F. Algoritmos: Lógica Para Desenvolvimento de Pro- gramação de Computadores. 29. ed. São Paulo: Érica, VARGAS, J. V. C.; ARAKI, L. K. Cálculo numérico aplicado. 1. ed. São Paulo: Manole, 2016. XAVIER, G. F. C. Lógica de programação. 13. ed. São Paulo: SENAC, 2001. Fique atento Os links para sites da web fornecidos neste capítulo foram todos testados, e seu funcionamento foi comprovado no momento da publicação do material. No entanto, a rede é extremamente dinâmica; suas páginas estão constantemente mudando de local e Assim, os editores declaram não ter qualquer responsabilidade sobre qualidade, precisão ou integralidade das informações referidas em tais links.Introdução à construção de algoritmos Silvano Antonio Alves Pereira OBJETIVOS DE > Definir algoritmo e sua função. > Identificar os passos para a construção de um algoritmo. > Criar exemplos de algoritmos usando pseudocódigos. Introdução Os algoritmos fazem parte de nosso cotidiano, desde aplicativos que utilizamos em nossos celulares até os programas mais complexos utilizados em problemas de engenharia. Mesmo em tarefas mais simples, como cozinhar, é que você esteja utilizando um algoritmo. Para entender como funcionam e aprender a criar seus próprios algoritmos, você estudará, neste capítulo, as principais cara- terísticas de um algoritmo e verá também importantes passos a serem seguidos na elaboração de um algoritmo. Por fim, você será introduzido a uma forma de representar algoritmos para que outros também possam ler e compreender os que você venha a escrever.52 Introdução à construção de algoritmos o que são algoritmos Como um primeiro esforço na direção da definição de um algoritmo, podemos invocar seu aspecto mais intuitivo. Nesse sentido, algoritmos são muitas vezes comparados com receitas culinárias. Veja o seguinte exemplo de uma receita: Bolo de fubá ingredientes: 3 ovos inteiros 2 xicaras de 2 xicaras de fubá 3 colheres (sopa) de farinha de trigo 1/2 copo (americano) de óleo 1 copo (americano) de leite 1 colher (sopa) de fermento em pó Modo de preparo: 1. Em um liquidificador, adicione os ovos, o açúcar, o fubá, a farinha de trigo, o óleo, o leite e o fermento em pó. Depois, bata até a massa ficar homogênea. 2. Despeje a massa em uma forma untada e polvilhada. 3. Leve para assar em forno médio (180°C) pré-aquecido por 40 min. A receita apresenta cada um dos ingredientes necessários, as etapas e as ações necessárias para transformar os ingredientes em seu resultado (o bolo). As instruções são também apresentadas de maneira clara e bem definida. Aqui, bem definida quer dizer que não há espaço para dúvidas na execução das instruções oriundas das próprias informações. Imaginando, por um instante, que a receita do bolo de fubá seja uma espécie de algoritmo, tentados a definir um algoritmo como uma sequência de passos, ou etapas, que visam a atingir um objetivo bem definido. Embora seja um exemplo bastante comum na literatura, o exemplo do bolo ilustra, de maneira simples, os principais elementos de um algoritmo. Vamos destacá-los a seguir e então apresentaremos a definição mais precisa de um algoritmo. Estado inicial e estado final (previsível) No exemplo do bolo, a receita começa a ser preparada quando reunimos todos os ingredientes e equipa- mentos necessários e começamos a executar o passo 1 da receita. Além disso, é fácil aceitar que o estado final da receita deve ser um bolo. Não é diferente