Capitulo 1 - Computacao Cientifica

Prévia do material em texto

Computação Científica Computação CientíficaCapítulo 1. Computação Científica1. DefiniçãoA Computação Científica é uma área de estudo que, utilizando computadores, se interessa pelaconstrução de modelos matemáticos e pelas técnicas para determinar soluções numéricas, naanálise e resolução de problemas reais (científicos e da engenharia). A Computação Científicaconsiste, em termos práticos, na aplicação da simulação computacional e de outras formas decomputação, na análise e resolução de problemas reais em várias áreas científicas e tecnológicas.Muitos cientistas e engenheiros desenvolvem aplicações computacionais para modelar sistemasreais, as quais ao serem executadas requerem grandes quantidades de dados iniciais e deparâmetros de entrada. Normalmente, tais modelos requerem uma grande quantidade de cálculos,o que faz com que a relação com a Computação Numérica seja muito forte. Por sua vez, aComputação Numérica define-se como a utilização de computadores na manipulação de números.Em algumas áreas do conhecimento, a experimentação em laboratório é extremamente cara ouaté mesmo impossível, fazendo com que a Computação Científica tenha um papel de grandeimportância, pois configura uma terceira vertente da ciência, complementando a experimentação(observação) e a teoria.Considere-se o seguinte exemplo: tendo em conta a grande aproximação da antena do telemóvelcom a cabeça humana, essencialmente na realização de chamadas, os utilizadores são expostos acampos eletromagnéticos de níveis consideráveis em períodos de tempo cada vez maiores. Devido àimpossibilidade técnica e ética de efetuar medições dos níveis destes campos em seres humanos ouanimais, as simulações numéricas são de crucial importância nestes estudos. Com a ComputaçãoCientífica é possível identificar as áreas e os tecidos mais afetados, que normalmente são aquelesmais próximos da antena, e os pontos de concentração de ondas eletromagnéticas.A construção de Modelos Matemáticos é possivelmente a vertente da Computação Científica naqual os investigadores têm ocupado mais tempo no seu estudo, tendo-se notado um aumento daquantidade de modelos matemáticos para resolver problemas reais, os quais são cada vez mais demaior complexidade, assim como no desenvolvimento de modelos já existentes.Computação Científica 1
Modelo genérico Computação Científica2. Modelo genéricoDe uma maneira geral, um modelo é uma estrutura (abstrata ou física) construída para exibirfunções e características (consideradas) fundamentais de um dado sistema “real”. Segundodiferentes perspetivas, a mesma “realidade” dá origem a diferentes modelos.É importante que o comportamento do modelo seja fiel à realidade (ou, melhor, à simplificaçãoda realidade que se idealizou). Mas também é importante que seja de fácil manipulação! Os modelos permitem a experimentação sem interferência com a realidade, assim como podemexplicitar relações que não eram claras até ao momento da sua construção e análise.O termo "modelo" é habitualmente usado por uma estrutura, que tenha sido construídapropositadamente, para expor aspetos e características de alguns objetos entre si. Geralmenteapenas alguns destes aspetos e características serão mantidos no modelo, dependendo da utilizaçãopara o qual o modelo é construído.É suposto que um modelo seja uma representação suficientemente precisa das característicasessenciais da situação a analisar (da realidade), de modo que as conclusões (soluções) obtidas apartir dele sejam também válidas para o problema real.O modelo é um esquema simplificado para a interpretação da realidade. Em consequência dacomplexidade do mundo real, é necessário formular modelos simplificadores que levem àcompreensão de certo fenómeno. A mera acumulação de observações não pode fornecer explicaçãosatisfatória do fenómeno e, portanto, o investigador tem necessidade de sistematizar e racionalizaros factos conhecidos, selecionando os aspetos mais importantes e desprezando os que considerairrelevantes.De uma maneira geral, pode-se considerar que existem três tipos de modelos: icónicos,analógicos e simbólicos. Os modelos icónicos são representações reduzidas de estados, objetos ouacontecimentos; representam o fenómeno real apenas com uma transformação de escala; porexemplo, os mapas. Os modelos analógicos, são aqueles em que se emprega uma propriedade pararepresentar outra; por exemplo, utilizar gráficos a cores e com legendas. Nos modelos simbólicosas propriedades do fenómeno real são expressas simbolicamente; por exemplo, os modelosmatemáticos, em que as propriedades do fenómeno são expressas por expressões matemáticas.3. Modelo matemáticoJá é antiga a constatação de que a Matemática é um instrumento poderoso de interpretação eintervenção no mundo real. De acordo com esta consciência, analisar situações da vida real eidentificar modelos matemáticos que permitam a sua interpretação, é uma das tarefas maisimportantes dos Matemáticos.2 Computação Científica
Computação Científica Modelo matemáticoExistem, na literatura, muitas definições de modelo matemático. Para Edwards e Hamsom("Guide to mathematical modelling". CRC Press. 1990) "um modelo matemático é o produto datransferência de um conjunto de elementos matemáticos (como sejam, funções ou equações), comvista à obtenção de uma representação matemática de uma parcela do mundo real". Já para Swetze Hartzler ("Mathematical modeling in the secondary school curriculum". The National Council ofTeachers of Mathematics: Reston, Virginia. 1991), "modelo matemático de um objeto ou de umfenómeno real é um conjunto de regras ou leis, de natureza matemática, que representamadequadamente o objeto ou o fenómeno na mente de um observador".Os modelos matemáticos são também representações idealizadas, mas expressas em termos desímbolos e expressões matemáticas, e que consistem num sistema de equações e de expressõesmatemáticas relacionadas, que descrevem os aspetos essenciais do problema. Os modelosmatemáticos podem ter diversas formas como uma única equação, um sistema de equações, umsistema de inequações ou, para casos mais complexos, um conjunto de equações diferenciais.O modo como a teoria e as aplicações da Matemática se relacionam é então designado pormatematização ou modelação matemática. Isto significa, como afirma Ian Stwart (matemáticoinglês), que "Qualquer descrição matemática do mundo real é um modelo. Manipulando o modeloesperamos compreender algo da realidade. E já não perguntamos se o modelo é verdadeiro,perguntamos unicamente se as suas implicações podem ser verificadas experimentalmente".4. Tipos de modelos matemáticosOs modelos matemáticos podem ser, pela sua natureza, de dois tipos: - modelos prescritivos,- modelos descritivos.Os modelos matemáticos prescritivos têm como característica principal, o facto de o resultadode uma operação ser prescrita para solucionar um problema do sistema real. Os modelosprescritivos baseiam-se na representação dos objetivos e das restrições de um processo para o qualse deseja descobrir soluções ótimas; ou seja, o modelo é elaborado segundo uma técnica quepermite encontrar a melhor solução, ou política de ação, para os condicionamentos representados.São os modelos de otimização, os quais podem ser resolvidos usando dois tipos diferentes demétodos: exatos e aproximados.Nos métodos exatos, a solução obtida é a melhor solução, dentre todas as possíveis, dados oscondicionamentos do modelo apresentado. A solução otimiza (maximiza ou minimiza) uma funçãode mérito (por exemplo, o custo total de produção) e em simultâneo respeita (não viola) todas asrestrições do problema (por exemplo, satisfazer a procura). Mas, dependendo do tipo de problemaa ser resolvido, pode ser extremamente caro, em termos computacionais, tentar resolvê-lo usandométodos exatos.Computação Científica 3
Tipos de modelos matemáticos ComputaçãoCientíficaPor exemplo, um problema de programação linear contínuo (isto é, que não contenha variáveisinteiras/discretas na sua formulação) pode ser resolvido de forma exata e eficiente mesmo quecontenha milhares (ou até milhões) de variáveis e restrições, pois há métodos polinomiaiseficientes para isso. Um exemplo são os modelos de programação matemática para os quais existemmétodos exatos para os resolver.No entanto, se o problema for de programação linear mista (contendo variáveis contínuas einteiras), então deve-se analisar caso a caso e decidir-se se pode resolver-se de forma exata ouaproximada (heuristicamente). Neste caso, mesmo que Resolver o problema usando um método aproximado (heurístico) significa que este não podegarantir que se obtenha a solução ótima em todos cenários analisados por ele. O que pode garantiré uma solução de “boa qualidade” com baixo custo computacional. Uma abordagem heurísticatenta utilizar um método racional para encontrar uma boa (próxima do ótimo) solução.Geralmente a heurística apresenta uma maneira mais rápida e fácil de resolver um problema, emrelação ao modelo matemático prescritivo “puro”. Exemplos de métodos heurísticos são osAlgoritmos Evolutivos (Algoritmos Genéticos, Pesquisa Tabu, ...), Redes Neuronais e Busca Local.Mas isto não significa que se deve resolver todos os problemas de grande dimensão e caros, emtermos computacionais, usando métodos aproximados.Por exemplo, suponha-se que existam 3 trabalhos para serem realizados e 3 máquinas disponíveispara os realizar. O custo de cada máquina para cada trabalho está na seguinte tabela:Máquina 1 Máquina 2 Máquina 3Trabalho 1 10 25 14Trabalho 2 13 5 6Trabalho 3 8 6 25Heurística 1: Alocação do menor custo dos trabalhos. Qual o custo total?Heurística 2: Alocação do menor custo das máquinas. Qual o custo total?Usando a Heurística 1 e afetando por ordem os Trabalhos, o custo total é 40 (10 + 5 + 25),correspondente aos seguintes pares de afetação: (Trabalho 1, Máquina 1), (Trabalho 2, Máquina 2) e(Trabalho 3, Máquina 3). Os Trabalhos 1 e 2 correspondem a custos mínimos e o Trabalho 3 não (oscustos mais baixos para este estão associados a Máquinas já afetadas).Usando a Heurística 2 e afetando por ordem as Máquinas, o custo total é 24 (8 + 5 + 11),correspondente aos seguintes pares de afetação: (Máquina 1, Trabalho 3), (Máquina 2, Trabalho 2) e(Máquina 3, Trabalho 1). As Máquinas 1 e 2 correspondem a custos mínimos e a Máquina 3 não (oscustos mais baixos para esta está associada ao Trabalho 2 já afetado). Note-se que a melhor solução, com custo total de 22 (10 + 6 + 6) e que corresponde aos pares deafetação (Trabalho 1, Máquina 1), (Trabalho 2, Máquina 3) e (Trabalho 3, Máquina 2), é um poucomelhor do que a solução obtida pela heurística 2. 4 Computação Científica
Computação Científica Tipos de modelos matemáticosOs modelos matemáticos descritivos são utilizados para acompanhar o comportamento de umsistema. As suas conclusões são obtidas através da perceção do modelador. Os modelos deste tipomais usuais são os modelos de simulação.Os modelos descritivos são utilizados na representação de sistemas reais (ou propostos) e naexperimentação de diferentes cenários e políticas de ação nos mesmos. As grandes motivações parao uso destas técnicas são a flexibilidade na representação de modelos complexos e a facilidade deaplicação, o que possibilita prever o comportamento do sistema modelado no horizonte deplaneamento escolhido. Os resultados dos testes apresentam uma visão futura do sistema,auxiliando no processo de tomada de decisões no momento. Ao contrário dos modelos prescritivos,os modelos descritivos são utilizados para comparar políticas de ação já escolhidas pelo decisor,não esperando que o modelo indique a melhor solução possível. Por exemplo, suponha-se que se pretende testar duas políticas de filas de espera paraatendimento numa Agência Bancária: 1ª) cada caixa tem a sua própria fila; 2ª) uma fila única paratodas as caixas. Neste caso, pode-se supor que o tempo de atendimento é baseado numadistribuição de Poisson e que os tempos de chegada dos clientes à Agência são baseados numadistribuição Exponencial Negativa. Depois, simulam-se as duas políticas, levando em linha de contaas distribuições envolvidas para verificar qual delas é a melhor (segundo um dado objetivo).5. Modelação matemáticaPara a resolução de problemas que surgem nas diversas áreas do conhecimento (nas Ciências,nas Engenharias e outras), torna-se necessário a construção de modelos matemáticos quedescrevam o melhor possível o comportamento dos sistemas reais.O processo de resolução de um problema pode ser visto como uma sequência de etapas quedevem ser realizadas e melhoradas, até que o modelo matemático construído (ou escolhido) para arepresentação do problema forneça resultados satisfatórios. A construção de um bom modelomatemático exige alto nível de abstração e de conhecimentos académicos (teoria) e/ou empíricos(prática) sobre o problema em análise.Embora não seja possível o controlo sobre a maioria dos sistemas reais, atendendo ao nível decomplexidade de cada um deles, é possível controlar a complexidade dos modelos matemáticos quese constroem para descrever o comportamento daqueles sistemas reais. Os sistemas reaiscomplexos podem ser aproximados por modelos matemáticos simples, os quais usam equaçõesmatemáticas que podem ser resolvidas usando métodos exatos. No entanto, estes modelos simplesoferecem, provavelmente, uma descrição muito distante do comportamento dos sistemas reais.Uma descrição mais precisa do sistema real pode ser conseguida com a introdução de maiscaracterísticas do sistema no modelo matemático, o que implica a utilização de equaçõesmatemáticas mais complexas e mais difíceis de resolver. Para estes casos, podem não existirComputação Científica 5
Modelação matemática Computação Científicasoluções exatas para o modelo, havendo necessidade de se recorrer à determinação de soluções“aproximadas”, obtidas através de métodos numéricos ou de métodos heurísticos.Existem, na literatura, vários e diferentes diagramas para descrever o processo de resolução deum problema (modelação matemática). Assim, pode-se considerar que este processo é compostopor cinco etapas principais (ver diagrama em baixo):1ª) Definição (Formulação) do Problema,2ª) Construção do Modelo Matemático,3ª) Determinação da Solução (do Modelo),4ª) Validação do Modelo e Análise da Solução,5ª) Implementação da Solução.
A sequência de etapas apresentada não é rígida, sendo que cada uma delas depois de iniciadas,sobrepõem-se no tempo. Há uma interação contínua entre as várias etapas, fazendo com que elasse tornem mutuamente dependentes. Muitas podem ser simultâneas e, em vários estudos, porexemplo, a etapa que consiste em formular o problema só fica completa quando o processo estávirtualmente terminado.Por outro lado, não é raro acontecer que os resultados finais estejam distantes do que seesperaria obter, ainda que todas as fases de resolução do problema tenham sido realizadascorretamente, havendo necessidade de regressar à 1ª etapa para redefinição do problema. Ou seja,pode-se considerar que o processo é cíclico, o denominado Ciclo de Modelação. Por exemplo, se aotestar-se o modelo se conclui que ele é deficiente, a formulação do problema e a construção do6 Computação Científica
Computação Científica Modelação matemáticamodelo podem ser revistas e modificadas. Ou seja, as diferentes fases influenciam-se mutuamentedurante todo o processo de resolução do problema real.Todo este processo inicia-se com a definição da situação real que se pretende estudar. Primeiro,o analista deve adquirir um conhecimento profundo do problema real (Perceção do Problema –etapa secundária). A partir daqui, o analista deve conseguir identificar com precisão em queconsiste o problema (Definiçãodo Problema). Uma vez ultrapassada esta etapa, e tendo em conta a definição do problema feita antes, deve-se proceder à recolha de dados necessários à construção do modelo (Recolha de Dados – etapasecundária). Segue-se, então, a escolha da estrutura matemática utilizada para representar oproblema (Construção do Modelo matemático): são escolhidas as variáveis que se relacionam, dealgum modo, entre si; selecionam-se as hipóteses (considera-se o atrito ou despreza-se?, considera-se a espessura de um material ou despreza-se?, etc). A validade das conclusões apenas pode serconsiderada tendo como referência as hipóteses selecionadas. Só depois se pode enunciar oproblema matemático propriamente dito: que equações ou inequações há que resolver, quais são asvariáveis, o que é constante, etc..Definido o modelo matemático associado ao problema, este terá que ser implementado, testadoe analisado de modo a retirar conclusões/soluções (Determinação da Solução do modelo). Estaetapa inicia-se com a escolha do método mais adequado à resolução do modelo construído (Seleçãodo Método – etapa secundária).As soluções obtidas, por sua vez, terão que ser interpretadas à luz da situação inicial de forma afazer-se a avaliação do modelo, verificando-se se o modelo construído pode ser uma representaçãodo problema real (Validação do modelo e Análise da Solução). Há que se analisar qual osignificado da solução no contexto do problema: 3 quê? -16 quê? metros? dias? graus? (se obtiver-se-5 metros como comprimento de uma vedação, confrontando com a realidade sabemos que tal nãoé possível; então, ou errámos os cálculos ou as nossas hipóteses não são aceitáveis).Posteriormente, consoante os resultados, decide-se da necessidade de redefinir o modelo, deconsiderar novas variáveis ou de alterar a via de resolução. Pode então ser necessário escolhernovas hipóteses e repetir todo o processo até chegarmos a uma solução que, confrontada outra vezcom a realidade, seja admissível.Por fim há que elaborar um relatório em que a solução do problema é usada para explicar ofenómeno, ou para prever a evolução futura ou para servir de suporte à tomada de decisão. Doponto de vista científico este passo é muito importante, pois obriga o cientista, ou equipa decientistas, a documentar o que fez, surgindo por vezes ideias unificadoras ou generalizadoras quenão ocorreram no decurso do processo. A comunicação sob a forma matemática é uma ferramentaimportante nos dias de hoje para todos os cientistas e investigadores.Computação Científica 7
Modelação matemática Computação Científica5.1. Definição (formulação) do ProblemaNesta etapa elabora-se a definição (formulação) matemática do problema real a ser resolvido.Normalmente, começa-se com um diagnóstico da situação e termina-se com uma descrição formaldo problema. Uma definição cuidadosa do problema é crucial, sendo que sem um cuidado e gastode tempo significativos pode-se estar, mais tarde, a resolver o problema errado. Ou seja, deve-seevitar extrair a resposta certa do problema errado!Nesta etapa, deve-se identificar as entidades associadas ao problema que são as seguintes: osdados (o que é conhecido), o objetivo (que é desconhecido e pretende-se determinar) e asrestrições (as condições do problema apresentadas).Nesta etapa deve-se realizar- a observação e análise do sistema real;- a descrição exata do objetivo de estudo;- a identificação das alternativas de decisão do sistema:- o reconhecimento das limitações e dos requisitos do sistema;assim como identificar - o agente de decisão (quem exerce o controlo sobre o sistema);- quais os seus objetivos (por exemplo, minimizar custos);- quais as suas decisões alternativas com que são confrontadas com o objetivo (isto é, asvariáveis controláveis ou de decisão);- quais os parâmetros (ou variáveis não controláveis pelo agente de decisão) que influenciamo resultado das suas decisões.Deve também discutir- o tempo disponível para o estudo;- o envolvimento do agente de decisão (e organização) no estudo;assim como estabelecer o diagnóstico inicial, - observando e analisando a forma como o sistema real opera;- recolhendo informações;- concebendo um sistema idealizado.As condições mínimas para a existência de um problema de decisão, são as seguintes:- existe pelo menos um agente de decisão, num determinado contexto;- o agente de decisão tem pelo menos um objetivo a atingir;- existem pelo menos duas alternativas de decisão;
– as alternativas de decisão não correspondem ao mesmo grau de satisfação do objetivo.8 Computação Científica
Computação Científica Modelação matemática5.2. Construção do Modelo MatemáticoA Construção do Modelo Matemático consiste na transformação do problema real numproblema matemático através de uma formulação matemática, a qual deve ser tratável em termoscomputacionais. Esta etapa deve começar por tentar selecionar um modelo, entre os vários jáconhecidos e que possam ser aplicados ao problema em estudo (é frequente ser possível aplicardiferentes modelos ao mesmo problema real), introduzindo as variáveis e os parâmetros do modelo,obtendo e apresentando os resultados. Deve existir, nesta etapa, uma grande flexibilidade, deforma a permitir diversas abordagens e alguma criatividade individual. De referir que geralmente omodelo matemático possui mais soluções que o problema real.Também deve haver uma grande comunicação com a fase da “Recolha de Dados”, pois o modelopode necessitar de algo mais do que foi feito na etapa anterior (na fase da “Recolha de Dados”),quer em termos dos dados recolhidos quer na forma como são apresentados.Nesta etapa deve-se reproduzir as relações entre os componentes do problema (objetivos,variáveis de decisão, parâmetros, restrições, ...). Os passos essenciais a ter em consideração são osseguintes:- identificar a estrutura de relações causa-efeito;- quantificar essas relações de forma determinística ou probabilística.Na identificação das relações causa-efeito, deve-se proceder à- identificação de todas as relações entre as variáveis de decisão, os parâmetros do modelo ea medida (ou medidas) de utilidade;- identificação de variáveis auxiliares que agregam informação de diversas variáveis;- formulação das primeiras hipóteses no sentido da simplificação do problema através dainclusão de apenas as relações relevantes.A qualificação das relações causa-efeito pode ser feita segundo três abordagens distintas:- método dedutivo, no qual é possível explicitar as relações entre os componentes do modeloatravés de expressões matemática (seja de forma determinística ou probabilística);- método de simulação, quando aquelas relações são de tal forma complexas não é possívelou aconselhável usar o método dedutivo, sendo que o melhor que o analista consegue fazeré imitar o comportamento do sistema idealizado;
– método de inferência estatística, quando pelo facto das relações serem inúmeras ecomplexas não é possível ou aconselhável usar o método dedutivo, mas é possível, pelaanálise estatística de dados, inferir aquelas que melhor reproduzem o comportamento dosistema sem demasiada complexidade.Computação Científica 9
Modelação matemática Computação CientíficaNa Construção de um Modelo existem algumas regras de devem ser cumpridas, tais como:1. Não construir um modelo complexo quando um simples basta;2. Não construir um modelo para servir ao seu método preferido;3. Conduzir a fase de construção do modelo rigorosamente;4. Validar o modelo antes de o implementar;5. Nunca tomar o modelo demasiado a sério;6. Não pressionar o modelo a fazer algo para que não foi concebido;7. Não desperdiçar os benefícios da fase da modelação;8. Não supor que o modelo contém mais informação do que a realidade;9. Não substituir o agente de decisão pelo modelo.Antes de finalizar esta etapa, deve-se verificar se- o modelo construído é tratável (isto é, consegue-se extrair informação útil a partir dele);- o modelo construído pode ser (mais) simplificado.5.3. Determinaçãoda Solução (do Modelo)Esta etapa inicia-se com a escolha do método numérico mais apropriado para resolver o modelomatemático obtido na etapa anterior (Seleção o Método – etapa secundária). Na escolha do métodomais eficiente deve-se ter em conta os seguintes aspetos:- precisão desejada para os resultados;- capacidade do método em conduzir aos resultados desejados (velocidade de convergência);- esforço computacional despendido (tempo de processamento e economia de memória,necessários para a resolução do problema).Depois de feita a escolha do método, este é descrito através de um algoritmo, o qual éposteriormente implementado num computador através de uma linguagem de programação.Construído o programa em computador, a sua execução tem em vista a obtenção dos resultadosnuméricos (soluções). Esta etapa pode, então, ser subdividida nas três fases seguintes (depois deefetuada a escolha do método):a) elaboração do algoritmo,b) implementação do algoritmo (codificação do programa),c) processamento (execução) do programa.Na fase de elaboração do algoritmo, é feito a descrição do algoritmo através de um conjuntode comandos que, quanto ativados (executados), resultam numa sucessão finita de ações(acontecimentos). No entanto, em vez de se implementar um método diretamente numa linguagemde programação, é preferível descrevê-lo através de uma notação algorítmica. Desta forma, épossível abstrair-se dos detalhes da linguagem de programação do computador e concentrar-seapenas nos aspetos matemáticos do método.10 Computação Científica
Computação Científica Modelação matemáticaAlém do mais, a descrição do método numa notação algorítmica facilita a sua implementação emqualquer linguagem de programação. Mais adiante é apresentada a notação algorítmica adotadapara descrever os métodos numéricos incluídos neste documento.Na fase de implementação do algoritmo (codificação do programa), o algoritmo éimplementado na linguagem de programação escolhida. Uma vez que os aspetos matemáticos dométodo já foram pensados na fase de elaboração do algoritmo, agora apenas é necessáriopreocupar-se com os detalhes de implementação na linguagem adotada.Na fase de processamento (execução) do programa, o código obtido da implementação doalgoritmo numa linguagem de programação deve ser executado pelo computador. Se for detetadoalgum erro lógico na fase de processamento, isto é, se a execução do programa produzir resultadosinesperados, então deve-se retornar à fase de elaboração do algoritmo para o corrigir. Casocontrário, serão obtidos os resultados do modelo matemático (a solução), que se espera possa sertambém a solução do problema real.5.4. Validação do Modelo e Análise da SoluçãoNesta etapa, é verificada a consistência da solução obtida para o modelo (validação do modelo)e a sua adequação ao problema real (análise da solução).Se a solução não se mostrar satisfatória (modelo não válido) deve-se construir um novo modelomatemático, através de uma nova formulação matemática, e determinar uma nova soluçãonumérica.Alguns modelos matemáticos podem produzir várias soluções (e não apenas uma) e algumasdelas (ou todas) não terem sentido físico ou químico, como, por exemplo, tempo negativo,concentração complexa, etc. Um dos objetivos desta etapa é justamente discernir qual a soluçãoválida para o problema real dentre as várias fornecidas pelo modelo matemático (se existiremalgumas). Desta forma, deve-se ter em atenção os seguintes aspetos:- se os resultados obtidos (soluções) são coerentes com o histórico do modelo;- como se comporta o modelo para (pequenas) variações dos parâmetros do modelo (análisede sensibilidade); detetar possíveis deficiências do modelo:- exclusão de variáveis relevantes;- inclusão de variáveis irrelevantes;- avaliação imprecisa de uma ou mais variáveis relevantes;- definição inapropriada da medida do grau de satisfação do objetivo;- relações entre componentes do modelo mal estabelecidas;- Teste: verificar se as soluções obtidas através do modelo são melhores do que as que seriamimplementadas se o modelo não tivesse sido desenvolvido.Computação Científica 11
Modelação matemática Computação Científica5.5. Implementação da SoluçãoNesta etapa deve-se ter em atenção os seguintes aspetos:- garantir que do “papel” para o sistema real não se desvirtua a solução;- ter abertura para readaptações (modelo e/ou solução) causadas por dificuldades deimplementação;- verificar a existência de problemas:- técnicos;- associados ao comportamento individual dos elementos da organização;- relacionados com o ambiente organizacional;- dar importância aos aspetos comportamentais;- verificar se a “realidade” ainda é a mesma do início do estudo.5.6. ExemploDefinição do ProblemaUm fabricante de plásticos produz 2 tipos de plástico: o especial e o normal.Cada tonelada de plástico especial exige 2 horas na máquina A e 5 horas na máquina B; cadatonelada de plástico normal exige 2 horas na máquina A e 3 horas na máquina B.Como a máquina A está disponível 8 horas por dia e a máquina B está disponível 15 horas por dia,quantas toneladas de cada tipo de plástico devem ser produzidas diariamente de maneira que asduas máquinas se mantenham totalmente ocupadas?Construção do Modelo Matemáticoplástico especial = variável Xplástico normal = variável Y }  {2X + 2Y = 85X + 3Y = 15Determinação da Solução do ModeloO processo consiste na resolução de um sistema de duas equações com duas incógnitas, usando ométodo de substituição de variáveis.
{2X + 2Y = 85X + 3Y = 15  {X = 4 −Y20 −5Y + 3Y = 15  {X = 4 −YY = 5 /2  {X = 3/2 = 1.5Y = 5 /2 = 2.5Análise dos Resultados (Solução)Devem ser produzidas: 1,5 toneladas de plástico especial (variável X) e 2,5 toneladas de plástico normal (variável Y).12 Computação Científica
Computação Científica Elaboração de algoritmos6. Elaboração de algoritmosUma das etapas mais importantes na resolução de um problema é a da determinação da soluçãodo modelo, pois envolve uma das fases mais importantes neste processo, que é a elaboração de umalgoritmo que traduza o método associado ao modelo matemático construído. Este algoritmodeverá ser posteriormente implementado numa linguagem de programação para se obter osresultados numéricos (solução do problema) usando um computador.Depois de selecionado o método associado ao modelo matemático construído, o qual é definidoatravés de expressões aritméticas e lógicas, o passo seguinte é a realização de uma descriçãodaquele método através de um algoritmo. A descrição do algoritmo, através de uma notaçãoalgorítmica, melhora o seu entendimento, pois apenas os aspetos do raciocínio matemático sãorealçados, sem ser necessário levar em consideração os detalhes de implementação de umalinguagem de programação.6.1. Estrutura do algoritmoUm algoritmo deve iniciar-se comAlgoritmo <nome-do-algoritmo>e terminar comfim_algoritmoTambém{ Objetivo: <objetivo-do-algoritmo> }deve ser utilizado para descrever a finalidade do algoritmo. Os dados necessários para a execução de um algoritmo são requisitados por meio do comandoparâmetros de entrada: <lista-de-variáveis>onde <lista-de-variáveis> são os nomes das variáveis, separadas por vírgulas, contendo os valoresfornecidos. Não é necessário descrever exatamente como os valores dessas variáveis serãofornecidas ao algoritmo. Compete ao programador decidir durante a codificação do programa se osdados serão fornecidos pelo teclado, lidos de um ficheiro, passados como argumentos de umsubprograma ou, até mesmo, definidos como constantes dentro do próprio programa.Da mesma forma, os valores de interesse calculados pelo algoritmo são disponibilizados pelocomandoparâmetros de saída: <lista-de-variáveis>podendo a <lista-de-variáveis> ser ampliada ou reduzida pelo programador.6.2. Variáveis e comentáriosUma variável corresponde a uma posição de memória do computador onde está, ou poderáestar,armazenado um determinado valor. As variáveis são representadas por identificadores que sãoComputação Científica 13
Elaboração de algoritmos Computação Científicacadeias de carateres alfanuméricos, podendo os elementos de vetores e matrizes seremreferenciados por subscritos ou índices (por exemplo, vi ou v(i) e mij ou m(i,j)).Um comentário é um texto inserido em qualquer parte o algoritmo para aumentar a sua clareza.Este texto deve ser delimitado por chavetas ( { <texto> } ), como por exemplo, { cálculo da raiz }.6.3. Expressões e comando de atribuiçãoExistem três tipos de expressões, dependendo dos tipos dos operadores e das variáveisenvolvidas, que são: aritméticas, lógicas e literais.6.3.1. Expressões aritméticasUma expressão aritmética é aquela cujos operadores são aritméticas e cujos operandos sãoconstantes e/ou variáveis numéricas. A notação é semelhante àquela utilizada para representaruma fórmula como, por exemplo,(b2 - 4ac), cos(2 + x) ou massa x velocidade.O símbolo  é usado para atribuir o resultado de uma expressão a uma variável, ou seja, <variável>  <expressão>Por exemplo,velocidade  deslocamento/tempo. A seguir apresentam-se algumas funções matemáticas que podem ser usadas na elaboração dosalgoritmos, pois consideram-se predefinidas:Funções trigonométricas: sen (seno), cos (coseno), tan (tangente) e sec (secante)Funções exponenciais: exp (exponencial), log10 (logaritmo decimal), loge (logaritmo natural) eraiz2 (raiz quadrada).Funções numéricas: abs (valor absoluto), arredonda (arredonda para o inteiro mais próximo),max (maior valor), min (menor valor), quociente (divisão inteira), sinal (sinal(x) = 1, se x > 0;0, se x = 0; -1, se x < 0), resto (resto de divisão inteira) e trunca (arredonda para baixo).6.3.2. Expressões lógicasUma expressão lógica é aquela cujos operadores são valores lógicos e cujos operandos sãorelações e/ou variáveis do tipo lógico. Uma relação é uma comparação realizada entre valores domesmo tipo. A natureza da comparação é indicada por um operador relacional definido conforme atabela que se segue, sendo que o resultado de uma relação ou de uma expressão lógica éverdadeiro (V) ou falso (F).Os operadores relacionais são os seguintes: > (maior que), ≥ (maior ou igual a), < (menor que), ≤ (menor ou igual a), = (igual a) e ≠ (diferente de). 14 Computação Científica
Computação Científica Elaboração de algoritmos6.3.3. Expressões literaisUma expressão literal é formada por operadores literais e operandos, os quais são constantese/ou variáveis do tipo literal. O caso mais simples de uma expressão literal é uma constante literal,que é constituída por uma cadeia de carateres delimitada por aspas. Por exemplo, mensagem  “matriz singular”em que mensagem é uma variável literal e "matriz singular" uma constante literal.6.4. Comandos de entrada e saídaO comando leia: <lista-de-variáveis>é usado para indicar que a <lista-de-variáveis> está disponível para leitura nalgum dispositivoexterno. Por sua vez, o comandoescreva: <lista-de-variáveis>deve ser utilizado para indicar onde certos valores de interesse estão disponíveis no programa edevem ser escritos nalgum dispositivo externo. Compete ao programador decidir pela ampliação da<lista-de-variáveis> ou mesmo a omissão do comando escreva.6.5. Estruturas condicionaisO uso de uma estrutura condicional torna possível a escolha dos comandos a serem executadosquando certa condição for satisfeita ou não, possibilitando, desta forma, alterar o fluxo natural decomandos. Esta condição é representada por uma expressão lógica, sendo que as estruturascondicionais podem ser simples ou compostas.6.5.1. Estrutura condicional simplesEsta estrutura apresenta a seguinte forma:se <condição> então<comandos>fim_seNeste caso, a sequência de <comandos> será executada se e só se a expressão lógica <condição>tiver como resultado o valor verdadeiro.6.5.2. Estrutura condicional compostaQuando houver duas alternativas possíveis, deve ser usada uma estrutura da seguinte forma:se <condição> então<comandos_1>senão<comandos_2>fim_seComputação Científica 15
Elaboração de algoritmos Computação CientíficaSe a expressão lógica <condição> tiver como resultado o valor verdadeiro, então será executadaapenas a sequência <comandos_1> (a sequência <comandos_2> não será executada). Por outro lado,se o resultado de <condição> for falso, então a sequência <comandos_1> será a única a serexecutada.6.6. Estruturas de repetiçãoUma estrutura de repetição faz com que uma sequência de comandos seja executadarepetidamente até que uma dada condição de interrupção seja satisfeita. Existem, basicamente,dois tipos de estruturas de repetição, atendendo a se o número de repetições é indefinido oudefinido.6.6.1. Número indefinido de repetiçõesEste tipo de estrutura de repetição apresenta a seguinte forma:repita<comandos_1>se <condição> entãointerrompafim_se<comandos_2>fim_repita<comandos_3>O comando interrompa faz com que o fluxo de execução seja transferido para o comandoimediatamente a seguir a fim_repita (a sequência <comandos_3>). Assim, as sequências<comandos_1> e <comandos_2> serão repetidas até que a expressão lógica <condição> resulte novalor verdadeiro. Quando isso ocorrer, a repetição será interrompida (<comandos_2> não serárealizada) e a sequência <comandos_3> será executada.A forma "repita ... fim_repita" é o caso geral de uma estrutura de repetição "repita ... até". Se asequência <comandos_1> não existir, ter-se-á uma estrutura de repetição com interrupção no início(estrutura "enquanto ... faz"). Da mesma forma, se não houver a sequência <comandos_2>, entãoserá uma estrutura com interrupção no final (estrutura "repita ... até").6.6.2. Número definido de repetiçõesQuando se conhece com antecedência quantas vezes a sequência de comandos deve serrepetida, pode ser usado o seguinte tipo de estrutura de repetição:para <controle>  <valor-inicial> até <valor-final> passo <delta> faça<comandos>fim_para16 Computação Científica
Computação Científica Elaboração de algoritmosNesta estrutura, é atribuído inicialmente à variável <controle> o valor de <valor-inicial> everificado se ele é maior do que o <valor-final>: se for maior, então a sequência <comandos> nãoserá executada; se for menor ou igual, então a sequência <comandos> será executada e a variável<controle> será incrementada com o valor de <delta>. Novamente, é verificado se a variável<controle> é maior do que o <valor-final>: se não for maior, então a sequência <comandos> seráexecutado; e assim sucessivamente.As repetições processam-se até que a variável <controle> seja maior do que o <valor-final>. Se oincremento <delta> tem o valor 1, o passo <delta> pode ser omitido desta estrutura de repetição.6.7. Falha no algoritmoO comandoabandoneé usado para indicar que haverá uma falha evidente na execução do algoritmo; por exemplo, umadivisão por zero, ou o uso inapropriado de parâmetros. Neste caso, a execução será canceladaatravés do comando abandone.6.8. Exemplos de algoritmosProblema 1: Dado um vetor x com n componentes (elementos), elaborar um algoritmo paradeterminar a média aritmética x̄ e o desvio padrão s dos seus elementos, sabendo quex̄ = 1n ∑i=1n xi, e s = √ 1n −1(∑i=1n xi2 − 1n(∑i=1n xi)2).Algoritmo Média_desvio{ Objetivos: Calcular média aritmética e desvio padrão }parâmetros de entrada: n, x { tamanho e elementos do vetor }parâmetros de saída: Média, DesvioPadrãoSoma  0Soma2  0para i  1 até n façaSoma  Soma + x(i)Soma2  Soma2 + x(i)2fim_paraMédia  Soma / nDesvioPadrão  raiz2 ((Soma2 – (Soma2 / n)) / (n-1))escreva: Média, DesvioPadrãofim_algoritmoComputação Científica 17
Elaboração de algoritmos Computação CientíficaProblema 2: Implementar um algoritmo para calcular a norma-2 (norma Euclidiana) de um vetor xde tamanho n, definida pela seguinte expressão:
∥x ∥2 = √∑i=1n ∣xi∣2.Algoritmo Norma2{ Objetivos:Calcular a norma-2 (Euclidiana) de um vetor }parâmetros de entrada: n, x { tamanho e elementos do vetor }parâmetros de saída: N2 { norma-2 do vetor }Soma  0para i  1 até n façaSoma  Soma + (abs(x(i)))2 fim_paraN2 raiz 2(Soma)escreva: N2fim_algoritmoProblema 3: Implementar um algoritmo para calcular a norma- (norma de máxima magnitude) deum vetor x de tamanho n, definida pela seguinte expressão:
∥x ∥∞ = max1≤i≤n ∣xi∣.Algoritmo NormaInf{ Objetivos: Calcular a norma- de um vetor }parâmetros de entrada: n, x { tamanho e elementos do vetor }parâmetros de saída: Ninf { norma- do vetor }Ninf abs(x(1))para i  2 até n façase abs(x(i)) > Ninf entãoNinf  abs(x(i)) fim_sefim_paraescreva: Ninffim_algoritmo18 Computação Científica
Computação Científica Elaboração de algoritmos6.9. Complexidade computacionalÉ usual definir-se uma função de complexidade para medir o custo de execução de umalgoritmo. Esta função tanto pode ser uma medida do tempo necessário para executar o algoritmoque resolve um problema de tamanho n, como o espaço de memória requerido para esta execução.Como os algoritmos aqui estudados são polinomiais e as operações aritméticas têm diferentestempos de execução pelo computador, a função de complexidade será definida, separadamente,para a adição/subtração, multiplicação e divisão.A complexidade computacional de um algoritmo refere-se à estimativa do esforço computacionaldespendido para resolver o problema, sendo medido pelo número de operações aritméticas elógicas efetuadas para resolver um sistema linear de ordem n.Os problemas possuem complexidade computacional, podendo ser enquadrados em dois grupos:
➔ grupo composto pelos algoritmos polinomiais, sendo a função de complexidade da forma:O(cn pn + cn-1 pn-1 + ... + c1 p1 + c0).
➔ grupo formado pelos algoritmos exponenciais, sendo a função de complexidade da forma:O(cn), c > 1.Como exemplo, considere-se o polinómio de Lagrange de grau n definido da seguinte forma:Ln(x ) = ∑i=0n yi ∏j=0j≠in x−xjxi−xj .Expandindo, resulta a Expressão 1 seguinte:Ln(x ) = y0 × x −x1x0 −x1 × x −x2x0 −x2 × ... × x −xnx0 −xn ++ . . . +
+ yn × x −x0xn −x0 × x −x1xn −x1 × ... × x −xn−1xn −xn−1cujo algoritmo é o seguinte:Algoritmo Lagrange_Expressão_1{ Objetivos: Interpolar usando polinómio de Lagrange }parâmetros de entrada: m, x, y, z { nº de pontos, abcissas, ordenadas e valor a interpolar }parâmetros de saída: r { valor interpolado }r  0para i  1 até m façap  y(i)para j  1 até m façase i  j entãoComputação Científica 19
Elaboração de algoritmos Computação Científicap  p * ( (z – x(j)) / (x(i) – x(j)) )fim_sefim_parar  r + pfim_paraescreva: rfim_algoritmoConsiderando que o número de pontos m usados na interpolação é igual a n+1, onde n é o graudo polinómio, então a complexidade computacional do algoritmo é:Adições: ∑i=1m 2(m−1) + 1 = 2(m2−2m + m) = 2(n + 1)2 −(n + 1) = 2n2 + 3n + 1 ;Multiplicações: ∑i=1m (m −1) = m2 −m = (n +1)2 −(n + 1) = n2 + n ;Divisões: ∑i=1m (m −1) = (m2 −m) = (n + 1)2 −(n + 1) = n2 + nO polinómio de Lagrange também pode ser expandido de modo a resultar a Expressão 2 seguinte:Ln(x ) = y0 × (x −x1)× (x −x2)× ... × (x −xn)(x0 −x1) × (x0 −x2) × ... ×(x0 −xn) +
+ y1 × (x −x0) × (x −x2) × ... ×(x −xn)(x1 −x0) × (x1 −x2) × ... ×(x1 −xn) + + . . . +
+ yn × (x −x0)× (x −x1) × ... × (x −xn−1)(xn −x0)× (xn −x1)× ... × (xn −xn−1)Ao analisar-se a complexidade computacional do algoritmo desta expressão, verifica-se que onúmero de adições é o mesmo e o de multiplicações é da mesma ordem (n2). No entanto, o númerode divisões utilizadas na Expressão 2 é de uma ordem grandeza a menos (n).O polinómio de Lagrange serve para exemplificar que uma mesma notação matemática poderesultar em algoritmos de diferentes complexidades. Isto deve estar presente ao elaborar-se umalgoritmo.20 Computação Científica
	Capítulo 1. Computação Científica
	1. Definição
	2. Modelo genérico
	3. Modelo matemático
	4. Tipos de modelos matemáticos
	5. Modelação matemática
	5.1. Definição (formulação) do Problema
	5.2. Construção do Modelo Matemático
	5.3. Determinação da Solução (do Modelo)
	5.4. Validação do Modelo e Análise da Solução
	5.5. Implementação da Solução
	5.6. Exemplo
	6. Elaboração de algoritmos
	6.1. Estrutura do algoritmo
	6.2. Variáveis e comentários
	6.3. Expressões e comando de atribuição
	6.3.1. Expressões aritméticas
	6.3.2. Expressões lógicas
	6.3.3. Expressões literais
	6.4. Comandos de entrada e saída
	6.5. Estruturas condicionais
	6.5.1. Estrutura condicional simples
	6.5.2. Estrutura condicional composta
	6.6. Estruturas de repetição
	6.6.1. Número indefinido de repetições
	6.6.2. Número definido de repetições
	6.7. Falha no algoritmo
	6.8. Exemplos de algoritmos
	6.9. Complexidade computacional