Matemática para Computação - Algoritmos e Modelagem Numérica

MARINA VARGAS MARINA VARGAS MATEMÁTICA PARA COMPUTAÇÃO M AT E M ÁT I C A COMPUTAÇÃO PARA Código Logístico I000122 Fundação Biblioteca Nacional ISBN 9786558210719 9 7 8 6 5 5 8 2 1 0 7 1 9 Para elaborar um algoritmo numérico precisamos de algumas etapas anteriores Definição do problema É a primeira etapa Como o próprio nome sugere é preciso compreender o que se deseja estruturar e as possibilidades de resposta Exemplo Queremos encontrar a divisão exata de a 2 com a 0 usando apenas as quatro operações fundamentais Modelagem A segunda etapa é por meio de uma formulação matemática Transformamos o problema real em um problema matemático Exemplo Usando o exemplo anterior escrevemos a 2x x Z7 Assim modelamos a definição do problema colocando as características matemáticas necessárias para resolvêlo Nesse caso identificamos que a precisa ser um número par para que tenhamos divisão exata Solução numérica Nesta terceira etapa escolhemos o método numérico apropriado para resolver o modelo matemático É nesse ponto que precisamos avaliar os métodos existentes e escolher aquele que resulte em menor erro numérico A escrita do algoritmo entra nessa etapa e é idealizada aplicando as possibilidades do método escolhido As duas últimas etapas não serão abordadas neste capítulo visto que não é escopo desta obra trabalhar com as linguagens de programação entretanto para que possamos registrar os passos seguintes à escrita do algoritmo temos Matemática para Computação Marina Vargas IESDE BRASIL 2021 20201 IESDE BRASIL SA É proibida a reprodução mesmo parcial por qualquer processo sem autorização por escrito da autora e do detentor dos direitos autorais Projeto de capa IESDE BRASIL SA Imagem da capa whiteMoccamajcotLanticaShutterstock Todos os direitos reservados IESDE BRASIL SA Al Dr Carlos de Carvalho 1482 CEP 80730200 Batel Curitiba PR 0800 708 88 88 wwwiesdecombr CIPBRASIL CATALOGAÇÃO NA PUBLICAÇÃO SINDICATO NACIONAL DOS EDITORES DE LIVROS RJ V427m Vargas Marina Matemática para computação Marina Vargas 1 ed Curitiba PR Iesde 2021 160 p il Inclui bibliografia ISBN 9786558210719 1 Computação Matemática 2 Programação Computadores 3 Algoritmos 4 Matrizes Matemática I Título 2172772 2172772 CDD 5181 CDU 519165004021 Marina Vargas Pósdoutora em Mecânica Computacional pela Universidade Federal do Paraná UFPR Doutora e mestre em Métodos Numéricos em Engenharia pela UFPR Especialista em Educação Matemática e licenciada em Matemática pela Universidade Paranaense Unipar Professora no ensino superior nas modalidades presencial e a distância ministra as disciplinas Cálculo de Funções de uma e mais Variáveis Álgebra Linear Geometria Analítica Métodos Numéricos Teoria dos Números Pesquisa Operacional Matemática Aplicada Estatística Aplicada e Métodos Quantitativos Atua também como professora conteudista em diversas instituições e empresas Atualmente desenvolve pesquisas nas áreas de programação matemática mecânica computacional educação matemática e educação em engenharias SUMÁRIO Agora é possível acessar os vídeos do livro por meio de QR codes códigos de barras presentes no início de cada seção de capítulo Acesse os vídeos automaticamente direcionando a câmera fotográfca de seu smartphone ou tablet para o QR code Em alguns dispositivos é necessário ter instalado um leitor de QR code que pode ser adquirido gratuitamente em lojas de aplicativos Vídeos emQR code SUMÁRIO Agora é possível acessar os vídeos do livro por meio de QR codes códigos de barras presentes no início de cada seção de capítulo Acesse os vídeos automaticamente direcionando a câmera fotográfca de seu smartphone ou tablet para o QR code Em alguns dispositivos é necessário ter instalado um leitor de QR code que pode ser adquirido gratuitamente em lojas de aplicativos Vídeos emQR code 1 Por que estudar matemática 9 11 O que é matemática computacional 9 12 Idealização de um algoritmo numérico 15 13 Relações de recorrência 19 14 Conceito de função no aspecto computacional 22 15 Diferenças entre problemas qualitativos e quantitativos 24 2 Noções sobre sistemas de numeração 29 21 Sistemas de numeração 29 22 Representação numérica 35 23 Representação em ponto flutuante 43 24 Erros numéricos 46 3 Matrizes 54 31 Vetores de uma matriz 55 32 Análise do algoritmo padrão para multiplicação de matrizes 58 33 Bases 61 34 Fatoração matricial Método de Gauss 64 35 Decomposição LU e LDU 69 36 Inversa de uma matriz 75 4 Sistemas de equações lineares 81 41 Sistemas equivalentes e operações 82 42 Sistemas triangulares e escalonados 86 43 Eliminação gaussiana 94 44 Condicionamento de sistemas lineares 101 45 Métodos iterativos 108 5 Grafos e árvores 123 51 O que é um grafo terminologia e tipos 124 52 Representação computacional de um grafo 132 53 Conceito de árvore 138 54 Raízes e árvores binárias 142 55 Introdução a procedimentos de busca 145 Resolução das atividades 150 This image is blankempty Nesta obra buscamos trazer os conceitos básicos da matemática para o trabalho não só com algoritmos a serem implementados nas mais diversas linguagens de programação mas principalmente a lógica por trás dos cálculos computacionais Quando mencionamos cálculos computacionais além de pensarmos a forma como a máquina opera e portanto trabalha com sistemas de numeração erros numéricos e vetores é necessário falarmos de conceitos como sistemas em rede e grafos pois estes estão diretamente relacionados às teorias mais atuais da computação como inteligência artificial redes neurais etc Desse modo destinamos o primeiro capítulo a apresentar um pouco da história do desenvolvimento da computação que está diretamente ligada ao desenvolvimento da matemática Apresentamos alguns dos nomes importantes dessa história e mostramos suas contribuições para a matemática computacional Além disso contextualizamos conceitos como algoritmo e relações de recorrência e tratamos da diferença entre problemas qualitativos e quantitativos No segundo capítulo discorremos sobre os sistemas de numeração aditivos e posicionais destacando o sistema de numeração posicional decimal relacionandoo com o sistema por trás das máquinas eletrônicas o sistema posicional binário Também trabalhamos o conceito de erro entre o resultado esperado e o resultado encontrado Para esse fim construímos um fluxograma que mostra com base em um modelo real as ramificações possíveis até que seja obtida a solução numéricacomputacional desejada A proposta do Capítulo 3 é a explanação sobre os conceitos de vetores e matrizes e as operações que os representam Essa escolha se dá pela facilidade em operar computacionalmente por meio dessas estruturas matemáticas Assim seu entendimento é essencial para a matemática computacional Além disso trabalhamos com a decomposição de matrizes preparando caminho para o tema do próximo capítulo APRESENTAÇÃO Vídeo 8 Matemática para Computação Nesse contexto entramos no quarto capítulo que trata dos sistemas de equações e visa trazer técnicas numéricas e algoritmos que permitam a implementação computacional desses sistemas Podemos exemplificar essa necessidade por meio de uma extensa lista de aplicações entre elas redes de computadores resolução de modelos que representam fenômenos físicos e gerenciamento de sistemas No entanto além desse contexto elas podem ser diretamente aplicadas ao próximo capítulo que aborda os grafos O Capítulo 5 apresenta a concepção de grafo Por intermédio de um grafo podemos representar problemas aplicados e identificar situações em que a busca por um caminho mínimo não só agiliza processos mas também minimiza custos Para essa construção retomamos o uso de matrizes e vetores sendo essa uma importante forma de implementação desse conceito É fácil notarmos que os três últimos capítulos têm uma conexão importante dentro da matemática computacional e se comunicam com a computação de maneira quase que natural Esse é um dos fatores para que esses conceitos estejam em todos os melhores cursos de computação e tecnologia da informação com todas as suas ramificações Este é o foco desta obra Nossa proposta é trazer o raciocínio lógico matemático por trás da necessidade de implementação computacional de problemas aplicados na área da tecnologia da informação e computação Esperamos que este livro auxilie no aprendizado para a formação de um melhor profissional na área escolhida Bons estudos Por que estudar matemática 9 1 Por que estudar matemática A matemática está por trás da lógica de programação de uma maneira que você talvez nunca tenha parado para pensar A ciência da programa ção começou por intermédio de matemáticos curiosos e muito à frente de seus tempos que tentavam otimizar processos e avançar com a possibi lidade dos cálculos serem realizados por máquinas A ideia era que essas máquinas recebessem mais do que números ou seja que pudessem re ceber instruções E eles conseguiram Neste capítulo destinado ao estudo da ligação da matemática com a computação vamos conhecer um pouco da história desses matemáticos e compreender por que é tão importante conhecer matemática para dis cutirmos sobre computação Com o estudo deste capítulo você será capaz de compreender a matemática por trás de conceitos computacionais reconhecer a diferença entre matemática teórica e matemá tica computacional identificar o uso de cálculos numéricos por trás de algoritmos relacionar o conceito de função em diferentes realidades computacionais compreender as dimensões quantitativas de um problema Objetivos de aprendizagem 11 O que é matemática computacional Vídeo Quando pensamos em matemática computacional precisamos en tender em primeiro lugar como um computador faz cálculos Aqui estamos chamando de computador todos os objetos que são capazes de realizar cálculos discretos como calculadoras computadores celu 10 Matemática para Computação lares dentre outros Assim todos os objetos que utilizam o princípio de abertura e fechamento de chaves e que permitem ou não a passagem de energia serão analisados perante a mesma lógica de construção para obtenção da chamada matemática computacional Quando escrevemos os cálculos percebemos que eles serão reali zados usando um princípio mecânico básico de abertura e fechamento de chaves e que estamos envolvendo nesse processo uma lógica bi nária Essa lógica precisa ser processada e interpretada É nesse ponto que entram os diferentes hardwares de processamento e em conjun to os softwares que interpretam esses dados processados É justamente por esse desenvolvimento que começamos a identifi car a existência de erros numéricos os quais podem surgir no processo de cálculo Além disso é por meio da lógica binária que identificamos o teor discreto da matemática computacional Agora vamos conhecer alguns dos nomes que permitiram que a ma temática computacional acontecesse 111 Ada Lovelace Augusta Ada Byron King Condessa de Lovelace nasceu em 10 de dezembro de 1815 na cidade de Londres e faleceu em 27 de novembro de 1852 aos 36 anos no bairro Marylebone na mesma cidade em que nasceu na Inglaterra Ada Lovela ce é conhecida como a primeira programadora da história Ela viveu em uma época em que as mulheres não eram bemvistas em universidades Por esse motivo e com estímulo de sua mãe Anne Isabella Anabella Byron Baro nesa de Wentworth Ada estudou em casa com tutores como Augustus De Morgan e Mary Sommerville que se tornou não apenas sua tutora mas sua amiga BIM 2018 Foi Sommerville quem apresentou Ada ao cientista Charles Babba ge 17911871 matemático conhecido por ter criado a primeira má quina capaz de resolver e imprimir cálculos matemáticos A invenção chamada de máquina analítica Figura 1 é considera da precursora dos computadores modernos BROMLEY 1982 Ada Lovelace K el so n Wi ki me di a C o m m on s Por que estudar matemática 11 Charles Babbage Co nn or ma h Wi ki me di a Co m m on s Figura 1 Réplica da máquina analítica Bruno BarralWikimedia Commons Mas foi Lovelace quem criou o primeiro algoritmo resolvido pela máquina analítica publicado como nota de rodapé de um artigo de Babbage Nesse material Ada descreveu a possibilidade de a máqui na realizar cálculos complexos envolvendo letras números e sím bolos além de instruções que permitiam repetição looping Além disso constava nessas notas um algoritmo que permitia o cálculo para os números de Bernoulli Foi por causa desse artigo que Babbage percebeu a geniali dade da moça e aceitou trabalhar em conjunto com ela o que se transformou em uma grande amizade Na matéria Ada Lovelace desafiou o machismo e se tornou a primeira programadora da história que retrata a história de Ada Lovelace sob o olhar da escritora Angela Saini Simões 2021 relata que a matemática estava muito à frente de seu tempo quan do teve a genial ideia do que um algoritmo seria capaz de fazer Ada e Babbage trabalharam juntos ao longo de muitos anos Nesse período ela desenvolveu diversos algoritmos que permitiriam que a má quina analítica computasse valores de funções matemáticas Esses algo ritmos foram posteriormente analisados por um outro matemático que será apresentado mais à frente Para conhecer um pouco mais da história e feitos de Babbage e Lovelace sugerimos dois vídeos O primeiro conta a vida de Lovelace Já o segundo traz a parceria entre Lovelace e Babbage na idealização e construção da máquina analítica Biografias 23 Ada Lovelace a primeira programadora Disponível em httpswww youtubecom watchvgcNKhlKW7uQab channelOMundoDaCiC3 AAncia Acesso em 31 maio 2021 O primeiro Computador do Mundo Charles Babbage Ada Lovelace Documentário Disponível em https wwwyoutubecom watchv35MwtZ5MKjM Acesso em 31 maio 2021 Vídeo 12 Matemática para Computação Mas o que é um algoritmo Fazendo uma analogia simples um algoritmo é como uma receita de bolo que mostra detalhadamente os métodos necessários para re solver uma atividade Na matemática um algoritmo é fundamental para que consigamos resolver uma expressão A seguir veremos que na computação tam bém é essencial Exemρlo 1 Pense em um cálculo qualquer Pode ser um cálculo simples como 2 2 2 Um algoritmo para esse cálculo pode ser montado como a seguir Início Resolva primeiro os parênteses Laço Dentro dos parênteses procure operações de multiplicação e divisão Se não houver resolva as operações de adição e subtração Com o resultado da soma elimine os parênteses e some esse nú mero com o restante das parcelas Fim O Exemplo 1 traz um algoritmo muito simples escrito de maneira direta e no momento sem pensarmos como essa lista de regras seria realmente programada para que a máquina pudesse resolver Porém com esse exemplo conseguimos visualizar a necessidade de regras claras sobre a maneira de resolução pois sem elas o computador não irá operar corretamente Essa forma de escrita que adotamos para re presentar um algoritmo é conhecida como pseudocódigo ou portugol Fica claro que sem os algoritmos e esse avanço trazido por Ada Lovelace é quase impossível pensarmos na ciência da computação e na matemática avançada da maneira que a vemos hoje Por que estudar matemática 13 112 Alan Turing Alan Mathison Turing nasceu em 23 de junho de 1912 na cidade de Paddington na Inglaterra e faleceu em 7 de junho de 1954 aos 41 anos em Wilmslow Inglaterra Alan Turing é conhecido como o pai da ciência da computação e da inteligência artificial Estudou na Universidade de Cambridge onde obteve seu bacharelado em matemática e concluiu seu mestrado Prosseguiu seus estudos obtendo seu doutorado em matemática pela universidade de Princeton Dentre os vários projetos que fizeram desse matemático o cien tista do século 20 em pesquisa 1 realizada pela BBC no ano de 2019 ficando à frente de Albert Einstein e Marie Curie está a chamada má quina de Turing também conhecido como máquina universal A máquina de Turing é um modelo abstrato que permite mani pular símbolos em uma fita de acordo com regras preestabelecidas restringindose apenas aos aspectos lógicos do seu funcionamento como a memória os estados e as transições Por meio dessa máqui na podemos modelar qualquer computador digital Turing foi um dos responsáveis para que os Aliados incluindo a Inglaterra ganhassem uma importante vantagem em relação à Alemanha na Segunda Guerra Mundial Sua máquina física Bombe construída com os conceitos da máquina universal e tendo como referência os trabalhos de Lovelace e Babbage dentre outros per mitiu que os Aliados quebrassem o código alemão Enigma em Blet chley Park Dessa forma eles passaram a ter conhecimento das estratégias que seriam usadas e puderam se antecipar aos ataques levando à vitória Muitos outros nomes estão envolvidos na construção histórica da computação e na forma como trabalhamos com a matemática hoje Dentre eles citamos John Von Neumann 19031957 e Norbert Wiener 18941964 Contudo percebemos que Ada Lovelace e Alan Turing dois ma temáticos viram a matemática muito além do que cálculos reali zados à mão com abordagem abstrata e sem aplicação no mundo Alan Turing Br un o B arr al Wi ki me di a Co m m on s Acesse na íntegra a pes quisa Scientists of the 20th Century Disponível em httpswwwbbccouk programmesp06y1tmk Acesso em 30 ago 2021 1 Para saber um pouco mais sobre a vida e con tribuição de Turing suge rimos a matéria 17 fatos e curiosidades sobre a vida do Alan Turing publicada pela revista Galileu Disponível em httpsrevistagalileu globocomCulturanoticia201806 17fatosecuriosidadessobrevi dadoalanturinghtml Acesso em 31 maio 2021 Leitura O filme O jogo da imitação de 2014 indicado ao Oscar em duas categorias retrata vida e morte de Alan Turing o processo de criação da máquina física Bombe e a guerra Direção Morten Tyldum Reino Unido Warner Bros 2014 Filme 14 Matemática para Computação físico Por meio de seus raciocínios analíticos viram a possibilidade de resolver problemas de maneira mais rápida e otimizada e con seguiram colocar em prática o que hoje chamamos de matemática computacional 113 Por que estudar matemática computacional A matemática computacional permite que trabalhemos com pro blemas extremante complexos que não poderiam ser resolvidos por uma única pessoa e muitas vezes nem mesmo por uma grande equipe Esse conceito pode parecer absurdo mas é a realidade de nossos dias Os computadores mudaram a vida em sociedade e por meio deles conseguimos trabalhar com operações complexas com modelos cada vez mais elaborados que representam o mundo real e analisar uma infinidade de dados que não conseguiríamos avaliar em gera ções passadas Além disso entenda sem uma quantidade de dados razoavel mente grande em torno de milhões não teríamos os serviços cada vez mais personalizados os sistemas otimizados e a precisão em diversos processos que são exigências do mundo atual Dessa forma podemos entender a matemática computacional como uma nova ciência que une os conceitos da computação e da matemática e nos permite resolver problemas por exemplo repre sentar o genoma humano calcular a eficiência e ajuste de foguetes dentre outros que não seriam possíveis sem os computadores Contudo para que possamos levar para o computador a mate mática por traz desses avanços inicialmente precisamos compreen der alguns conceitos como o que são dados quantitativos como montar uma relação de recorrência ou ainda como escrever um algoritmo que resolva problemas envolvendo vetores matrizes sis temas de equações funções dentre muitos outros É desses questionamentos que nasce a ciência matemática com putacional Desse modo precisamos entender a matemática e como Por que estudar matemática 15 a máquina processa essa matemática Com certeza Além disso pre cisamos representar os problemas cotidianos em modelos matemá ticos para que tenhamos essa associação Desse modo vamos trazer um pouco mais da matemática que precisamos compreender para que seja possível criar as oportunida des de aplicação usando os computadores Everett CollectionShutterstock Figura 2 Mecanismo de Gottfried Leibniz 12 Idealização de um algoritmo numérico Vídeo Em 1671 o filósofo e mate mático Gottfried Wilhelm Leibniz um dos criadores juntamente com Isaac Newton do cálculo diferencial e integral construiu um mecanismo Figura 2 que permitia realizar multiplica ções e divisões mediante adi ções e subtrações sucessivas Na época a metodologia usada por Leibniz ocasionava muitos erros sendo descartado seu uso Entretanto mantevese a ideia principal que permitia por meio de operações simples escrever outras operações A primeira calculadora capaz de efetuar as quatro operações aritméticas básicas foi construí da pelo francês Charles Xavier Thomas em 1820 Considerada a primei ra calculadora possível de ser comercializada a máquina de Thomas executava as multiplicações por meio de somas como idealizado por Leibniz e as divisões podiam ser executadas com auxílio do usuário Contudo nenhuma dessas máquinas era programável ou seja era possível entrar com valores numéricos mas não era possível passar instruções 16 Matemática para Computação Vimos que um algoritmo é constituído exatamente de ins truções a serem realizadas e esse feito começa a ser possível apenas com a criação da máquina de Lovelace e Babbage e posteriormente com a máquina de Turing Um algoritmo é uma etapa essencial para que uma construção matemática possa ser executada por um computador Ao construirmos um algoritmo não preci samos pensar qual será a linguagem de programação utili zada mas sim como queremos que o cálculo seja realizado Exemρlo 2 Acompanhe o algoritmo a seguir e observe o resultado obtido Variáveis inteiras a soma Seja a0 e Soma0 Se Soma6 faça aa1 SomaSomaa Imprima Soma Vamos interpretar esse algoritmo Variáveis inteiras a soma Declaração de variáveis Nesse pon to apresentamos a que conjunto elas pertencem Seja a0 e Soma0 Valores iniciais das variáveis Se Soma6 faça Note que nesse ponto temos um laço ou looping que será executado enquanto a condição Soma6 for válida aa2 Cada vez que entramos no laço precisamos pegar o último valor de a e acrescentar 1 gerando um novo valor de a SomaSomaa Cada vez que entramos no laço precisamos pegar o último valor de Soma e acrescentar a gerando um novo valor para Soma Imprima Soma Quando não for mais possível realizar o laço ou seja quando Soma 6 imprimese o último valor encontrado para a variável Soma Charles Xavier Thomas B as tie nM W iki m ed ia C o m m on s Por que estudar matemática 17 Quadro 1 Resumo do algoritmo a Soma Início 0 0 Laço a011 Soma011 Laço a112 Soma123 Laço a213 Soma336 Imprime Soma6 Fonte Elaborado pela autora De acordo com Campos Filho 2007 p 1 o cálculo numérico é uma metodologia para resolver problemas matemáticos por intermédio de um computador sendo ampla mente utilizado por engenheiros e cientistas Uma solução via Cálculo numérico é sempre numérica enquanto os métodos analíticos usualmente fornecem um resultado em termos de funções matemáticas Para a construção de um algoritmo numérico são necessárias as quatro operações aritméticas fundamentais e as operações lógicas que são comparação conjunção disjunção e negação A vantagem é que essas operações são exatamente as operações realizadas pelo processador de um computador O processo se dá inicialmente pelo fechamento e abertura de cha ves que permitem a passagem ou não de energia Esse mecanismo é compilado em zeros e uns Isto é quando a energia passa o compila dor entende esse resultado como 1 sim Quando a energia não passa esse resultado é igual a 0 não O processador permite que os cálculos binários sejam realizados e a partir desse ponto entra em jogo o sistema operacional que transfor ma tudo o que você faz nessa linguagem binária a qual é passada para o software podendo por sua vez fazer o que você quer Para auxiliar no entendimento desse processo binário sugerimos o artigo Aritmética de números binários e suas relações com circuitos lógicos dos auto res Rafael Pinheiro Leite e Prof Dr Matheus da Silva Menezes Acesso em 31 maio 2021 httpsrepositorioufersaedubrbitstreamprefix58541RafaelPLARTpdf Artigo This image is blankempty Por que estudar matemática 19 Codificação do algoritmo Processamento do programa A transformação do algoritmo para a linguagem de programação escolhida Implementação do algoritmo na linguagem de programação escolhida Nesse caso o programa será escrito em um arquivo para ser executado STRIPBALLShutterstock STRIPBALLShutterstock KhvostShutterstock Observe que a idealização de um algoritmo numérico passa pela etapa de modelagem do problema que só é possível com o conheci mento matemático sobre esse conteúdo Já na etapa de solução numé rica além do entendimento dos métodos numéricos disponíveis para a resolução do modelo é preciso analisar os possíveis erros obtidos com essa escolha Essa etapa é otimizada quando entendemos os tipos de erros que podem ser gerados pelo computador Muitos algoritmos usam as chamadas relações de recorrência para realizar seus cálculos e convergir para a resposta desejada Vamos en tender esse conceito na sequência 13 Relações de recorrência Vídeo A base da maior parte dos algoritmos matemáticos vem do conceito de relação de recorrência Uma relação de recorrência é uma técnica matemática que nos auxilia na definição de sequências conjuntos ope rações ou algoritmos Para que tenhamos uma fórmula de recorrência 20 Matemática para Computação precisamos analisar as características do problema e escrever uma re gra que o represente Com o intermédio dessa regra podemos calcular qualquer termo em função dos antecessores Nesta seção vamos trazer como objeto para entendermos as relações de recorrência a famosa fórmula de re corrência de Fibonacci Leonardo de Pisa mais conhecido como Fibonacci que significa fi lho do Bonacci descreveu sua sequência pela primeira vez em seu livro Liber Abaci em 1202 a fim de modelar um problema relacionado com o crescimento de uma população de coelhos Fibonacci desejava descrever a quantidade de casais em uma po pulação de coelhos após n meses Figura 3 partindo dos seguintes pressupostos ZAHN 2011 1 nasce apenas um casal no primeiro mês 2 casais amadurecem sexualmente após o segundo mês de vida 3 assumimos que não há problemas genéticos no cruzamento consanguíneo 4 todos os meses cada casal dá à luz um novo casal 5 os coelhos nunca morrem Figura 3 Sequência de casais em uma população de coelhos MagicleafShutterstock 24 Matemática para Computação formula 43 314r3 return formula Agora podemos usar essa função Assim se escrevermos esfera2 teremos como retorno o valor formula 33 37 75 Entretanto nos dois sentidos podemos perceber o princípio fun damental de uma função matemática que é o de ser uma regra que vincula dois conjuntos de dados diferentes 15 Diferenças entre problemas qualitativos e quantitativos Vídeo Um problema é dito qualitativo quando os dados usados para re solver o modelo são dados qualitativos ou seja são baseados em cará ter subjetivo em que são usadas narrativas escritas ou faladas Uma pesquisa qualitativa pode reunir informações como o nome das pessoas que foram avaliadas em um determinado estudo o estilo de vida desse grupo de pessoas as preferências alimentares hobbies dentre outras informações que em geral são fornecidas por meio de narrativas questionários abertos entrevistas observações etc e que não são codificadas usando um sistema numérico Uma pesquisa qualitativa pode ser dividida em pesquisa nominal ou ordinal Como a própria nomenclatura sugere uma pesquisa nominal é aquela em que temos como resposta à pesquisa nomes sendo que não é possível ordenar tais respostas Por exemplo uma pesquisa que possui o campo sexo terá como resposta masculino ou feminino Esse tipo de resposta pode ser quantificado contudo não conseguimos colocar ordem de importância para tal Ainda no campo da pesquisa qualitativa podemos ter dados ordi nais Nesse caso é possível categorizar as variáveis em relação a de terminado grau para cada categoria Por exemplo uma pesquisa que procura analisar o grau de instrução de seus participantes pode conter a variável nível de escolaridade como ensino fundamental e ensino médio É possível construir uma classe para cada grau de escolaridade e até quantificar os participantes em cada uma dessas mas a variável continua tendo um teor puramente qualitativo Por que estudar matemática 25 O interesse quando modelamos um problema com o auxílio de pes quisas quantitativas é identificar e compreender os fenômenos através de dados numéricos Por exemplo se desejamos saber a quantidade de pessoas que to maram determinado remédio ou votaram em determinado candidato precisaremos realizar pesquisas quantitativas Podemos pensar na escolha de um método ou outro da seguinte forma Método qualitativo geralmente é utilizado para categorizar uma determinada situação classificar problemas e gerar hipóteses etc Método quantitativo é utilizado como o próprio nome remete a quantificar objetos Os métodos quantitativos são muito usa dos na estatística Em geral adotamse questionários que permi tem a contagem das variáveis pesquisadas O que caracteriza um método como quantitativo ou qualitativo são as variáveis que ele apresenta Assim chamamos de variáveis quanti tativas as que possuem características que podem ser quantificadas isto é medidas em determinada escala quantitativa Por esse motivo são representadas numericamente e podem ser divididas em duas ca tegorias discretas ou contínuas As variáveis discretas são representadas por valores números in teiros Alguns exemplos são quantidade de filhos de pessoas em de terminado local e de produtos na geladeira As variáveis contínuas recebem valores em uma escala contínua em que podem estar presentes valores representados por frações e decimais finitos ou infinitos É comum a necessidade de instrumen tos de medição para avaliar uma variável quantitativa contínua como balanças réguas relógios e outros instrumentos de medição Alguns exemplos desse tipo de variável são idade peso altura etc As variáveis qualitativas ao contrário não são representadas por valores que podem ser quantificados Elas representam categorias ou seja algum tipo de classificação para pessoas objetos ou situações e podem estar subdivididas em duas categorias nominais ou ordinais As variáveis nominais não exigem ordenação por exemplo sexo cor dos olhos religião profissão etc Já as variáveis ordinais exigem ordenação dos dados coletados São exemplos classe social A B C e escolaridade 1º ano 2º ano 3º ano Tanto um problema qualitativo como um problema quantitativo pode ser investigado para que seja resolvido com o auxílio de um al goritmo executado computacionalmente Mas é na pesquisa quantita tiva que esses resultados têm ganhado destaque A ciência de dados Figura 5 considerada uma ciência estatística teve seu início com a ideia de podermos resolver problemas matemáti cos de maneira computacional Figura 5 Áreas da ciência de dados CIÊNCIA DE DADOS Megadados Classificação de dados Análise de dados Estatística Solucionador Tomada de decisão Conhecimento aberto buffaloboyShutterstock Ela pode ser definida como um conjunto de ferramentas e métodos que nos permitem analisar visualizar e tomar decisões com base em dados RAMOS 2021 É aqui que a matemática e a computação novamente se encon tram A quantidade de dados gerados por ferramentas como Google Netflix Twitter Uber entre outras que usamos no nosso dia a dia é imensa Para coletar organizar e aplicar em modelos que deem um retorno para essas empresas em forma de resultado financeiro é ne cessário que diversas áreas da matemática sejam envolvidas dentre elas encontrase a estatística talvez a mais utilizada nesse sentido DianaKarchShutterstock Rede neural 26 26 Matemática para Computação Matemática para Computação Por que estudar matemática 27 De acordo com Ramos 2021 o chamado cientista de dados é o profissional responsável por aplicar técnicas modelos tecnologias e processos para extrair informação relevante dos dados Tudo isso com muita estatística e programação aplicada Dessa forma pensar em algoritmos que possibilitam o uso des ses dados é fundamental para o crescimento das empresas Esses algoritmos poderão por exemplo estar vinculados ao marketing digi tal fazendo com que dados quantitativos e qualitativos gerem lucro Nesse ponto entram os chamados algoritmos de inteligência artifi cial Um dos quesitos necessários para esse tipo de algoritmo é que ele processe um grande volume de dados quantitativos ou qualitativos A diferença desse tipo de algoritmo para os demais é a possibi lidade de se aplicar um fator de decisão ou seja a existência de variáveis randômicas ou condicionadas dentro de um domínio deter minado que permitirão que os resultados não sejam únicos e sim ter uma gama de possibilidades definidas para o contexto aplicado Nesse ponto podemos ter algoritmos construídos com o uso de diferentes funções É possível trabalhar em diferentes camadas e com funções matemáticas específicas para cada camada de dados Perceba que mesmo nesse quesito o domínio sobre o algoritmo está na mão do programador É ele quem determina o que serão es ses fatores de decisão e como será seu comportamento matemático para que o cálculo se torne randomizado A compreensão da mate mática levará à obtenção dos resultados desejados CONSIDERAÇÕES FINAIS Neste capítulo trouxemos uma pequena parte do gigantesco mundo da matemática aplicada à computação à qual nos referimos como mate mática computacional As possibilidades são enormes a depender da área almejada É possí vel trabalhar desde processos de otimização de redes até a bela área da programação gráfica passando pelo rico campo da inteligência artificial e da ciência de dados Independentemente da área escolhida a necessi dade da compreensão da matemática que envolve todos esses cálculos é imprescindível para sua correta implementação Desse modo esperamos que você se sinta motivado a seguir nesse caminho que relaciona essas duas ciências matemática e computação 28 Matemática para Computação ATIVIDADES Sabendo que um algoritmo é compreendido como um processo que mostra detalhadamente os métodos necessários para a resolução de uma atividade e que podemos pensar nessa estrutura em formato de pseudocódigo como estrutura inicial descreva um pseudocódigo para o cálculo da expressão numérica 1 35 1 Atividade 1 Descreva o modelo matemático que pode ser utilizado para representar a definição do problema a para a 0 usando apenas as quatro operações aritméticas Atividade 2 Uma pesquisa foi realizada coletando dados referentes à altura de alu nos de uma sala de aula Esse tipo de dado é qualitativo ou quantitativo Justifique Atividade 3 REFERÊNCIAS BIM S A A vida de Ada Lovelace Porto Alegre Sociedade Brasileira de Computação 2018 BROMLEY A G Charles Babbages Analytical Engine 1838 Annals of the History of Computing v 4 n 3 1982 Disponível em httpathenaunioneduhemmenddCourses cs80anenginepdf Acesso em 31 maio 2021 CAMPOS FILHO F F Algoritmos numéricos uma abordagem moderna de Cálculo Numérico São Paulo LTC 2007 GUIDORIZZI H L Um curso de cálculo 6 ed v 1 Rio de Janeiro LTC 2018 KHOURY J Application to a probleme of Fibonacci Disponível em httpaix1uottawa cajkhouryfibonaccihtm Acesso em 31 maio 2021 RAMOS R Ciência de dados uma breve história O Estatístico Disponível em https oestatisticocombrcienciadedadosumabrevehistoria Acesso em 31 maio 2021 SIMÕES I Ada Lovelace desafiou o machismo e se tornou a primeira programadora da história Darkside Disponível em httpsdarksideblogbradalovelacedesafiouo machismoesetornouaprimeiraprogramadoradahistoria Acesso em 31 maio 2021 ZAHN M Sequência de Fibonacci e o Número de Ouro Rio de Janeiro Ciência Moderna 2011 Noções sobre sistemas de numeração 29 2 Noções sobre sistemas de numeração Você já parou para pensar que o sistema de numeração que usamos na atualidade passou por diversas transformações ao longo da história para chegar ao que ele é hoje Além disso por muito tempo ele não foi único Diferentes civilizações construíram seus próprios sistemas de numeração com os conhecimen tos que tinham na época E você sabia que esse sistema numérico que usamos o indoarábico fortemente desenvolvido embasado e com toda a estrutura matemática moderna construída sobre ele é deixado de lado quando pensamos em cálculos realizados por um computador Além do sistema de numeração adotado quando o computador é usa do ainda precisamos admitir propagações de erro Sim o computador comete muitos erros numéricos Com o estudo deste capítulo você será capaz de compreender os diferentes sistemas de numeração identificar erros numéricos e como interpretálos caracterizar as diferentes representações numéricas computacionais compreender o conceito de erro numérico Objetivos de aprendizagem 21 Sistemas de numeração Vídeo Um dos sistemas de numeração mais antigos foi encontrado por meio de pesquisas arqueológicas na Tchecoslováquia Europa em 1937 com data entre aproximadamente 35000 aC e 20000 aC Basicamente 30 Matemática para Computação os pesquisadores encontraram um osso tíbia de lobo jovem com mar cações unitárias feitas por meio de traços cortes transversais na forma I II III IIII Ao todo eram 57 traços sendo os primeiros 25 agrupados de 5 em 5 ALMEIDA 2011 Essa descoberta nos mostra a necessidade da contagem e possibili ta discutir sobre os sistemas de numeração O tipo de contagem observada nesse estudo é dita aditiva em que para se ter o próximo número basta acrescentar uma marcação Além disso o sistema de numeração foi composto de apenas um sím bolo sendo chamado de sistema de numeração de base 1 A obra Através do espelho e o que Alice encontrou por lá escrita em 1871 pelo matemático Lewis Carroll 18321898 e traduzida para mui tos idiomas inclusive o português traz um diálogo entre a rainha Branca e Alice que demonstra a dificuldade que teríamos se o sistema de numeração de base 1 fosse adotado atualmente Alice fala para a rainha que aulas servem para nos ensinar a fazer contas e a rainha lhe pergunta e sabe Adição Quanto é um mais um mais um mais um mais um mais um mais um mais um mais um mais um Alice lhe res ponde não sei Perdi a conta CARROLL 2013 p 186 Na história da matemática identificamos diversas civilizações que adotaram sistemas ditos aditivos Mas como exatamente algebricamente podemos definir um sistema aditivo Vamos assumir que b é um número natural tal que determinado sistema aditivo está escrito na base b Assim temos duas condições que precisam ser respeitadas 1 O sistema deverá ter b símbolos para sua representação numérica ou seja teremos a1 a2 ab símbolos para representar os números de um até b Esses números deverão ser representados em ordem crescente Caso tenha se interessado pelas obras de Carroll e queira saber um pouco mais sobre esse assunto sugerimos o texto Lewis Carroll e a matemática do País das Maravilhas publicado pela Sociedade Brasileira de Matemática Disponível em httpswww sbmorgbrnoticiaslewiscarroll eamatematicadopaisdas maravilhas Acesso em 2 jun 2021 Leitura Noções sobre sistemas de numeração 31 2 Devese obedecer a regra do sucessor que implica assumir que se um número termina em ai com i b então a representação de seu sucessor será obtida por meio da substituição de ai por ai1 Caso a representação de um número termine em ab seu sucessor será obtido acrescentando a1 à representação dada Entre alguns dos sistemas aditivos mais importantes na história en contramse o sistema hieroglífico Figura 1 desenvolvido pelos egíp cios por volta de 3400 aC e o sistema de numeração da antiga Grécia desenvolvido por volta do século IV aC Figura 1 Sistema numeral egípcio Numerais egípcios Sistema numérico hieroglífico egípcio Sistema egípcio de numeração hierática SidheShutterstock No entanto foi com o sistema chamado posicional que a matemáti ca começou a se desenvolver com maior rapidez 32 Matemática para Computação Não se tem consenso de qual foi a civilização que idealizou primeiro o chamado sistema de numeração posicional em que se encontram o nosso sistema posicional de base decimal e o sistema binário computacional mas o que se sabe é que para esse tipo de construção foi necessário o desenvolvimento lógico da ideia de agrupamentos entre os números Nesse contexto histórico identificouse que os hindus praticaram o sistema posicional decimal e tiveram a preocupação de construir uma representação visual dele que pudesse ser transferida de maneira escrita Entretanto foram os árabes que divulgaram esse sistema de numeração pelo ocidente e por esse motivo o chamamos de sistema indoarábico Figura 2 Evolução do sistema posicional decimal Hindu 300 aC Hindu 500 dC Árabe 900 dC Árabe Espanha 1000 dC Italiano 1400 dC Hoje Fonte Elaborada pela autora Um sistema de numeração posicional é aquele em que a posição na qual o algarismo se encontra modifica o seu valor ou seja no caso do sistema posicional de base decimal o sistema que usamos se o algarismo 1 estiver na posição casa da unidade ele vale 1 unidade Se o mesmo algarismo estiver na posição da dezena casa da dezena ele vale 10 unidades Se estiver na posição da centena vale 100 unidades e assim sucessivamente Usando o sistema numérico posicional decimal a Tabela 1 apre senta alguns exemplos com diferentes posicionamentos para o al garismo 1 Noções sobre sistemas de numeração 33 Tabela 1 Posição do algarismo 1 em relação ao valor numérico obtido Classes Milhões Milhares Unidades simples Ordens c d u c d u c d u 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 Fonte Elaborada pela autora Um sistema de numeração posicional pode ser definido de maneira geral algébrica assim como fizemos para os sistemas posicionais Nesse contexto usaremos b ℕ como uma base qualquer Assim para construir um sistema posicional de base b precisamos garantir duas con dições Por isso considere b 1 Inicialmente precisamos determinar b símbolos sendo um desses destinado a representar a casa vazia zero e os demais destinados a representar os números de 1 a b 1 1 Se o número a ser representado tem como unidade um dos algarismos que representam 0 1 b 2 ele terá um sucessor substituindose esse algarismo por seu sucessor apresentado na ordem crescente que será b 1 2 Se o número a ser representado tem como unidade o algarismo que representa b 1 ele já é o último algarismo dessa base Nesse caso a representação do sucessor será obtida substituindose esse algarismo por zero e em seguida aplicandose recorrentemente os itens 1 e 2 dessa regra à casa seguinte 3 Se a casa seguinte for vazia considerase como se ela tivesse o valor zero Atualmente o sistema de numeração posicional de base dez siste ma indoarábico em que a posição do algarismo indica a potência de 10 que o dígito representa é usado em todo o mundo sendo utilizado de maneira tão intuitiva como uma criança pequena que usa os dedos para contar que é difícil imaginar qualquer tipo de construção numéri ca sem essa formatação 34 Matemática para Computação Observe o exemplo de como decompomos um número no sistema posicional decimal por meio da representação geral enunciada Exemρlo 1 x 195710 1 103 9 102 5 101 7 100 Note que com esse formato fica evidente o uso da chamada base decimal Essa formatação será adotada para a escrita das próximas ba ses que estudaremos nesta obra Queremos conceituar e identificar as características não só para o sistema posicional decimal mas para outros sistemas posicionais que são usados na matemática e na computação permitindo assim uma visão do cálculo numérico envolvido nesse processo Definição 1 Dados um número natural com b 1 e o conjunto de símbolos 0 1 2 b 1 a sequência de símbolos dndn1 d1d0 d1d2 b representa o número positivo dn bn dn1 bn1 d0 b0 d1 b1 d2 b2 Para representar números negativos usamos o símbolo à esquer da do numeral conforme exemplificamos a seguir Exemρlo 2 x 195789710 x 1 103 9 102 5 101 7 100 8 101 9 102 7 103 x 1000 900 50 7 08 009 0007 Portanto percebemos que além da escolha do sistema de numera ção aditivo ou posicional há muitas representações distintas em rela ção à quantidade de algarismos envolvida em cada um desses modelos bases adotadas Noções sobre sistemas de numeração 35 Na próxima seção focamos nos sistemas posicionais mais utilizados pela matemática moderna e pela matemática computacional 22 Representação numérica Vídeo Entender a representação numérica do sistema escolhido não só possibilita sua compreensão mas viabiliza realizar operações com o tipo de numeração escolhido além de permitir verificar possíveis erros cometidos nos cálculos Como nosso foco é trabalhar com a matemática para a computa ção dedicaremos esta seção à representação numérica implícita nas máquinas digitais eletrônicas ou seja nos computadores Assim o primeiro sistema que vamos discutir é o chamado sistema de numeração posicional de base dois ou base binária 221 Sistema binário Quando pensamos em um sistema de numeração que permita realizar operações no computador chamamos de computador as má quinas digitais eletrônicas a base utilizada é a base dois Seu uso está diretamente vinculado ao desenvolvimento das máquinas digitais Durante muitos séculos se creditou a Gottfried Wilhelm Leibniz 16461716 a idealização da base binária Para saber mais sobre Leibniz e a relação desse matemático com a base da computação sugerimos a leitura de Leibniz e nosso mundo digital de Gilberto Garbi publicado pela Revista do Professor de Matemática RPM Acesso em 2 jun 2021 httpswwwrpmorgbrcdrpm841html Artigo Contudo pesquisas recentes demonstram que em uma pequena ilha da Polinésia séculos an tes da idealização de Leibniz o povoado de Mangareva já utilizava a base binária para rea lizar cálculos que permitiam a comercialização de seus produtos Gottfried Wilhelm Leibniz Ni ck u Sh utt ers to ck 36 Matemática para Computação Ao analisar a pesquisa dos cientistas noruegueses Andrea Bender e Sieghard Beller do departamento de ciência psicossocial da Universidade de Bergen na Noruega Javier Sampedro 2013 descreve que os pesquisadores mostram agora como os habitantes da Mangareva não só inven taram o sistema para contar peixes frutas cocos polvos e outros bens de diferente valor em suas transações comerciais como tam bém que isso conduziu a uma aritmética binária que teria mere cido a aprovação do Leibniz por sua simplicidade e naturalidade Dos fatos históricos sabemos que a base binária foi deixa da de lado até mesmo por Leibniz e apenas séculos após sua morte em 1841 foi redescoberta pelo matemático George Boole 18151864 o qual desenvolveu a chamada álgebra booleana que permitiu o desenvolvimento do computador digital eletrônico imprescindível para o desenvolvimento em praticamente todas as áreas do conhecimento na atualidade O computador lida com grandezas representadas como se quências de bits base 2 Quando precisamos transcrever um método matemático para um mé todo numérico ou seja para a matemática computacional precisamos em primeiro lugar compreender como um computador manipula as in formações no nosso caso as informações são numéricas e simbólicas Toda informação manipulada por um computador é representada como uma sequência de bits binary digits Ao agrupar 8 bits temos 1 byte quando agrupados Figura 3 os bytes darão origem aos kilobytes megabytes gigabytes terabytes etc termos comumente usados na computação e no nosso dia a dia Figura 3 Sequência de bits Rahimov EminShutterstock Medidas de informação eletrônica Célula de memória de 8 bits 0 1 0 1 1 0 1 0 1 byte 8 bit 1 KB 8192 bit 1 KB 1024 byte 1 MB 1024 KB 1 GB 1024 MB 1 TB 1024 GB KB kilobyte MB megabyte GB gigabyte TB terabyte Sugerimos a leitura na íntegra do texto Um sistema binário inventado na Polinésia séculos antes de Leibniz do autor Javier Sampedro Disponível em httpsbrasil elpaiscombrasil20131216 sociedad1387215405275511 html Acesso em 2 jun 2021 Leitura George Boole W dw d Wi ki me di a Co m mo ns Noções sobre sistemas de numeração 37 Um bit aceita duas respostas possíveis 0 não falso desligado 1 sim verdadeiro ligado Na área eletrônica interpretase isso como passagem de ener gia sim ou sem passagem de energia não Essa leitura do código binário é feita milhares de vezes por segundo Esse tipo de representação também chamado de representação binária matematicamente pode ser traduzido como um sistema de numeração na base dois Exemρlo 3 Assim para a codificação de um número natural entre 0 e 255 por exemplo seriam suficientes 8 bits pois 28 256 Desse modo para representálos restaria apenas atribuir valores 0 ou 1 O número natural 255 será representado em uma sequência de bits sequência binária por 11111111 Mais adiante explicaremos os processos de conversão Como demonstramos o sistema de numeração na base dois também chamado de binário na área da computação tem seus al garismos reconhecidos e representados por meio dos bits binary digits Já identificamos que um bit pode assumir dois valores dis tintos 0 ou 1 Embasados nos conhecimentos adquiridos até o momento so bre base binária começamos a trabalhar com as mudanças de base Com essa finalidade o exemplo a seguir apresenta uma mudan ça da base binária para a base decimal tendo como ideia principal o tipo de conversão adotada pelo computador flight of imaginationShutterstock Representação do código binário pelos botões com símbolos I ligado e O desligado Figura 4 0 ou 1 Para conhecer mais sobre a relação entre bits e bytes e a sucessão de agrupamentos sugerimos a leitura de Qual a diferen ça entre Kilobyte Megabyte Gigabyte e Terabyte pu blicado no site da Copel Telecom Disponível em httpswww copeltelecomcomsiteblog kilobytemegabytegigabyte terabyte Acesso em 2 jun 2021 Leitura 38 Matemática para Computação Exemρlo 4 Seja x 1001101 então 1 23 0 22 0 21 1 20 1 21 0 22 1 23 8 0 0 1 05 0 0125 9625 Portanto 10011012 962510 Note que no exemplo utilizado respeitamos a posição de cada um dos elementos e fizemos a conversão em primeiro plano assumindo o valor de cada posição e na sequência somando esses resultados Esse é o processo que será adotado para as bases que veremos na sequência 222 Sistema quaternário No sistema quaternário a base b é igual a 4 e portanto temos o conjunto de algarismos 0 1 2 3 Exemρlo 5 Seja x 30124 então 3 42 0 41 1 40 2 41 48 0 1 05 495 Portanto 30124 49510 Mais adiante veremos como converter uma base decimal para uma base qualquer Na sequência apresentamos a base hexadecimal ou seja uma base formada por 16 algarismos 223 Sistema hexadecimal O estudo do sistema hexadecimal auxilia no processo de represen tação de sequências maiores de bits por exemplo com 16 ou 32 bits Se b 10 usamos as letras A B C para denotar A 10 B 11 C 12 Para ficar claro esse sistema vamos exemplificar Noções sobre sistemas de numeração 39 Exemρlo 6 Se temos b 16 ou seja o conjunto de algarismos 0 1 2 3 4 5 6 7 8 9 A B C D E F e queremos converter o número x E2AC16 para a base decimal fazemos E2AC16 14 163 2 162 10 161 12 160 E2AC16 57344 512 160 12 58028 A base hexadecimal também é amplamente usada na computação Você já ouviu falar do tripleto hexadecimal também chamado de web color Figura 5 O tripleto hexadecimal recebe esse nome porque é uma combina ção de 3 bytes pois cada cor formada possui três duplas escritas em formato hexadecimal Cada dupla representa uma cor sendo elas ver melho verde e azul RGB A variação da combinação hexadecimal no tripleto dará origem às demais cores Figura 5 Web color R A NonenmacherWikimedia Commons Uma tabela bem extensa de combinações de cores pode ser encontrada no site Nas artes gráficas Disponível em httpnasartesgraficasblogspotcom201408listadecoreshtml Acesso em 2 jun 2021 Exemplo 7 A cor azulmarinho é escrita como 12 0A 8F no sistema triplet hexadecimal Portanto cada dupla terá 16 possibilidades para a primeira posição e mais 16 para a segunda formando um byte de 256 possibilidades Como temos três duplas as possibilidades de combinação serão 256 256 256 16777216 Essa estrutura de cores é usada para documentos HTML CSS entre outros É possível observar os códigos hexadecimais de uma quantidade considerável de cores e a conversão para outros sistemas de cores que podem ser adotados computacionalmente A seguir veremos o processo da transformação inversa ou seja conhecendo um número na base 10 converteremos ele para a base b desejada 224 Processo inverso Nesta seção trabalharemos com a conversão de números na base decimal x10 os quais serão convertidos para uma base b qualquer Ou seja queremos trabalhar com a seguinte representação algébrica x10 dn dn1 d0 d1 b x10 dn bn dn1 bn1 d0 b0 d1 b1 Inicialmente para conseguirmos realizar a conversão separamos a parte inteira de x10 da sua parte fracionária também chamada de mantissa obtendo x10 xi xf Assim temos xi dn bn dn1 bn1 d0 b0 xf d1b1 d2b2 Portanto precisamos determinar os valores para o conjunto dn dn1 que é composto tanto de elementos da parte inteira como de elementos da parte fracionária Parte inteira xi dn bn dn1 bn1 d0 b0 b xib dn bn1 dn1 bn2 d1 d0b Observe que d0 é o resto da divisão de xi por b pois d1 d2 b1 dn1 bn2 dn bn1 é inteiro e d0b é uma fração com d0 b Da mesma forma o resto da divisão de d1 d2 b1 dn1 bn2 dn bn1 por b é d1 Ou seja repetindo esse processo encontramos os algarismos d0 d1 d2 dn Para a análise da parte inteira temos uma ferramenta extremamente simples que pode ser usada a divisão Por meio de sucessivas divisões podemos rapidamente converter um número da base decimal para a base binária Exemplo 8 Para a conversão de 310 para a base binária fazemos 3 2 1 Resto 1 1 2 0 Resto 1 O resultado será obtido justamente por meio dos restos Portanto 310 112 Também podemos converter um número na base 10 para a base binária por meio das divisões sucessivas como é feito no exemplo a seguir Exemplo 9 A conversão do número 14210 para a base binária poderia ser resolvida assim 14210 100011102 Por fim um exemplo da conversão de bases de um número decimal Exemplo 10 Vamos converter o número 3625 para a base binária b 2 Primeiramente decompomos 3625 na soma de suas partes inteira e fracionária x 3 0625 Logo xi 3 e xf 0625 Nesse exemplo resolveremos a parte inteira dessa conversão Assim precisamos fazer sucessivas divisões por b 2 Então xi 3 1 2 1 1 21 1 20 Portanto xi 1 21 1 20 112 Para a parte fracionária do número temos o seguinte Parte fracionária xf d1b1 d2b2 b b xf d1b d2b Nesse produto note que a parte inteira é d1 e a parte fracionária é d2b ao multiplicarmos novamente por b temos d2 Para encontrar os algarismos restantes repetimos esse processo Exemplo 11 Continuando o Exemplo 10 agora precisamos fazer sucessivas multiplicações por b 2 para obtermos a parte fracionária do número 3625 xf 0625 2 xf 125 21 1 21 025 21 1 21 05 21 21 1 21 05 22 1 21 1 21 22 1 21 1 23 Portanto xf 1 21 0 22 1 23 1012 Logo 362510 111012 Outras ferramentas computacionais podem ser usadas entre elas encontramse algumas linguagens de programação como Sclilab e Python Aqui relembramos que o processo aplicado pelo computador é o de converter de binário para decimal mas as conversões são importantes para garantir a veracidade dos nossos cálculos e a viabilidade de possíveis aplicações 23 Representação em ponto flutuante Um número na matemática pode ser infinito e isso é impossível de ser representado no computador visto que este trabalha com um número de bits limitado e predefinido WEBER 2004 Pensando na estrutura numérica computacional dizemos que há três formas possíveis de representação de um número no computador I Inteiro natural II Inteiro relativo III Generalização dos dois casos anteriores ou seja um número real É possível representar números inteiros ou seja considerar a parte negativa do conjunto atribuindo um bit mais à esquerda chamado de sinal ou bit forte Por meio desse primeiro bit saberemos se o número é positivo ou negativo Já no caso dos números reais ou seja considerando também números decimais a Institute of Electrical and Electronic Engineers IEEE define uma fórmula para ser aplicada padrão IEEE754 Essa representação Quadro 1 é chamada de representação em ponto flutuante Seja um computador de 32 bits essa estrutura fica escrita da seguinte forma 1s bE F Quadro 1 Organização do ponto flutuante S bit E F Fonte Elaborado pela autora Em que b é a base S 0 número positivo ou S 1 número negativo E deve ser calculado por m E M com m sendo o valor mínimo que a máquina pode representar e M sendo o valor máximo m M F chamado de mantissa conterá os bits situados após a vírgula Acompanhe o exemplo a seguir para compreender melhor Exemplo 12 Considere uma máquina com registro de 32 bits e base b 2 Pelo padrão IEEE754 Quadro 2 1 bit será usado para o sinal S 8 bits serão usados para o expoente c7 c0 e 23 bits serão usados para a mantissa d1 d23 Quadro 2 Padrão IEEE754 S c7 c6 c0 d1 d2 d22 d23 Fonte Elaborado pela autora Noções sobre sistemas de numeração 45 Assumindo que E c BIAS em que BIAS é o valor do deslocamento do expoente polarização temos x 1S 2cBIAS F com c c7c6 c02 e F 1d1d2 d22d23 De acordo com Gilat e Subramaniam 2008 p 23 grifos do original computadores armazenam números e realizam cálculos em precisão simples ou em precisão dupla Na precisão simples os números são armazenados em uma cadeia de 32 bits 4 bytes e na precisão dupla em uma cadeia de 64 bits 8 bytes Exemρlo 13 Queremos representar em notação ponto flutuante os números x 110 y 1110 z 23110 assumindo precisão simples 32 bits e base hexadecimal No primeiro caso x 110 teremos a primeira casa composta do sinal logo S 0 pois 1 é positivo Assim 0 0 1 0 0 0 0 0 0 Agora no segundo caso y 1110 como o valor é negativo a pri meira casa será representada por S 1 Assim 1 b 0 0 0 0 0 0 0 No último caso ou seja z 23110 teremos S 0 e a representação 0 e 7 0 0 0 0 0 0 Note que na representação em ponto flutuante dos três números não usamos as casas referentes a d1 d2 d22 d23 Isso porque em nenhum deles há parte fracionária 46 Matemática para Computação Note que aumentar o número de bits na mantissa melhora a preci são Já aumentar a quantidade de bits no expoente permite que tenha mos um intervalo de números representáveis muito maior Com isso é possível perceber padrões muito bem definidos para a construção do cálculo numérico e da matemática computacional 24 Erros numéricos Vídeo Quando falamos de erros estamos tratando da diferença entre o valor real e o valor obtido É comum que sejam necessárias diversas simplificações do pro blema real para que se tenha um modelo matemático com solução possível Observe a Figura 6 a seguir que apresenta a comparação entre um modelo físico geoide e um modelo matemático elipsoide da super fície da Terra Figura 6 Comparação entre modelos Modelo físico geoide jdrvartShuterstock Modelo matemático elipsoide AlexanderZamShuterstock Assim sendo o processo de propagação de erros começa quan do transformamos um problema real em um modelo físico e este em um modelo matemático Tal modelo matemático poderá ser resolvido de modo que tenhamos uma solução analítica ou uma solução numérica Noções sobre sistemas de numeração 47 KubkoShutterstock Problema real Modelo físico Modelo matemático Solução analítica Solução numérica Implementação computacional Resultado numérico Note que ao desenvolvermos o modelo matemático precisamos escolher entre a obtenção de uma solução analítica e uma solução numérica Neste ponto temos um grande questionamento Por que usar um método numérico A resposta é mais simples do que imaginamos Os modelos que possuem solução analítica precisam ser extremamente simplificados Já os modelos que podem ser resolvidos numericamente podem con 48 Matemática para Computação ter mais variáveis e equações e assim um requinte maior nas equa ções que os contemplam Como o modelo usado para a obtenção numérica é mais refinado o erro inerente ao método e à máquina pode ser muito menor se compa rado ao erro obtido com a solução analítica que foi encontrada por meio de um modelo muito mais grosseiro Com isso concluímos que nem sempre usamos o mesmo modelo matemático para as duas abordagens Em geral modelos matemáticos computacionais podem abranger um número maior de situações quan do comparados ao problema real Por meio do arredondamento e do truncamento que especificare mos na sequência conseguimos perceber a propagação de erros a que a resolução de um problema pode estar exposta Como vimos os números não são representados computacionalmen te de maneira exata Essa perda dependerá da capacidade da máquina A precisão denotada por p de um computador é o número de dígi tos significativos usados para representar um número Os dígitos signi ficativos são todos os dígitos certos adicionados ao primeiro algarismo duvidoso Dessa forma os números infinitos ou mesmo muito grandes aca bam sendo arredondados ou truncados ocasionando erros Esses mesmos números quando em operações ocasionarão a chamada pro pagação de erros Além desses erros ainda temos a chamada incerteza dos dados e os erros de modelagem matemática Nesse caso em vez de pensar na transformação de um número para sua forma finita levamos em con sideração a construção do modelo matemático e com isso a acurácia dos instrumentos de medição que estão envolvidos na construção desse modelo além das ferramentas matemáticas disponíveis para solucionar o problema Vamos entender qual tipo de ajuste é necessário quando arredon damos ou truncamos um número e o que isso acarreta para o cálculo 241 Erro de arredondamento O arredondamento de um número é feito analisando o primeiro al garismo após o dígito duvidoso acurácia Física Proxi midade entre o resultado de um instrumento de medida e o verdadeiro valor do que foi medido DICIO 2021 Glossário Caso o dígito duvidoso seja maior do que 5 aumentase de uma unidade o algarismo duvidoso e desprezamse os demais Caso o dígito duvidoso seja menor do que 5 mantémse o valor do algarismo duvidoso e desprezamse os demais Caso o dígito duvidoso seja igual a 5 há dois caminhos Se o algarismo duvidoso imediatamente anterior à parte desprezada for um número ímpar devese aumentálo em uma unidade Se o algarismo duvidoso imediatamente anterior à parte desprezada for um número par devese deixálo como está inalterado Para compreender essas especificações sobre arredondamento acompanhe o exemplo a seguir Exemplo 14 13 0333 033 π 31415926 3141693 155500 156 0805 080 Adotamos o arredondamento numérico porque computacionalmente não é possível representar números infinitos ou seja esse tipo de ajuste é feito por causa das limitações existentes na representação numérica em máquinas digitais Mas existem outros tipos de erros que podem se propagar quando transformamos um problema 242 Erro de truncamento O chamado truncamento será o corte aplicado aos dígitos não significativos de um número infinito ou muito grande de acordo com a precisão possível da máquina O truncamento também ocorre quando se aplica um método numérico na solução de um problema e esse método leva a uma sucessão de termos infinitos Computacionalmente essa abordagem não é possível nesses casos truncase a série de termos em determinado ponto no qual o erro seja aceitável Em geral é necessário definir em cada problema o que é considerado um erro aceitável Assim o resultado encontrado após o truncamento será analisado perante a obtenção desse erro Resumidamente um erro de truncamento ocorre quando transformamos uma representação de um processo infinito em uma representação finita É comum por exemplo truncarmos séries de funções como no exemplo a seguir Exemplo 15 Seja a função sen x escrita por meio de uma série de potências na forma sen x x x33 x55 x77 Sabemos que o valor de senπ6 é igual a 12 Contudo se calcularmos esse valor por meio de uma série de potências trigonométrica truncadas teremos senπ6 π6 π63321 π6554321 π677654321 Nesse caso senπ6 049999999187 Note que para esse cálculo além do erro de truncamento ainda temos um erro de arredondamento Portanto começamos a perceber a propagação de erros intrínseca em diversos métodos computacionais 243 Erro absoluto e erro relativo Com os ajustes numéricos necessários para a representação computacional arredondamento truncamento etc além dos ajustes nos modelos e nas demais aproximações aplicadas surge a questão referente à quantificação dos erros envolvidos nesses processos Para verificar se o resultado atingido foi bom é necessário comparálo ao resultado exato Nesse ponto surgem algumas métricas que nos permitem quantificar os erros As medidas de erro mais utilizadas são o erro absoluto e o erro relativo Definição 2 erro absoluto Sejam x um número real e x sua aproximação O erro absoluto da aproximação x é definido de acordo com Justo et al 2021 como EA x x Apresentamos a seguir um exemplo que nos auxilia na compreensão do cálculo para esse tipo de erro Exemplo 16 A área da circunferência é dada por A πr² Se r 3 então a área exata será dada por A 9π Mas o que ocorre se π for arredondado Sejam π1 314 e π2 3141593 Então A1 9 314 2826 e A2 9 3141593 28274337 Erro absoluto EA x x EA 28274337 2826 0014337 Em muitos casos desejamos calcular uma taxa entre o erro e a solução real Nessa situação precisamos do chamado erro relativo definido a seguir Definição 3 erro relativo Sejam x um número real e x sua aproximação O erro relativo da aproximação x é definido de acordo com Justo et al 2021 como ER x xx x 0 O erro relativo é adimensional e muitas vezes é expresso em porcentagens Leitura O relato de alguns acidentes atribuídos a erros de cálculo numérico pode ser encontrado na leitura de Some disasters attributable to bad numerical computing Apesar de o texto estar em língua estrangeira ele pode ser facilmente traduzido por meio de um tradutor online Disponível em httpwwwusersmathumneduarnolddisasters Acesso em 2 jun 2021 Além disso indicamos também a leitura de Erros de cálculo na engenharia Disponível em httpswwwaedbbrsegetarquivosartigos1823226187pdf Acesso em 2 jun 2021 Exemplo 17 Utilizando os mesmos dados do Exemplo 14 vamos calcular o erro relativo Sejam π1 314 e π2 3141593 Então A1 9 314 2826 e A2 9 3141593 28274337 Erro relativo ER x xx ER 28274337 282628274337 00005070675927 100 00507 Uma forma de minimizar o alastramento de erros em um modelo numérico é reduzir o número de operações Exemplo 18 Considere o polinômio dado por pnx an xn an1 xn1 a1 x1 a0 an x an1x an2x a1x a0 Note que a primeira representação do polinômio contém mais operações do que a segunda representação Sendo assim o erro geral no segundo caso será menor pois serão necessários menos ajustes numéricos e com isso um menor alastramento de erros Esse tipo de manipulação precisa ser trabalhado com suas especificidades dentro de cada método numérico e cada situação que permita a implementação computacional CONSIDERAÇÕES FINAIS Neste capítulo percorremos trechos da história da matemática que permitiram o desenvolvimento da história da computação Identificamos alguns matemáticos que estiveram diretamente relacionados com a construção não só das linguagens de programação mas da própria máquina digital eletrônica computador moderno e do modo como ela opera Percebemos a importância das estruturas lógicasmatemáticas envolvidas no processo por trás da lógica computacional e com isso repensamos algumas das estruturas matemáticas clássicas que quando convertidas para serem interpretadas pelo computador ainda mantêm suas características principais ou seja mantêm sua estrutura matemática Com base em todos esses conceitos reforçamos a importância do estudo da matemática para todos interessados pela área da computação com todas as suas ramificações e possibilidades ATIVIDADES Atividade 1 Podemos considerar o sistema de numeração romano um sistema aditivo ou um sistema posicional Explique Atividade 2 É possível converter um número na base 10 para a base hexadecimal por meio de divisões sucessivas Explique essa conversão e converta o número 910 para essa base Atividade 3 Considere a escrita do número de Napier da forma e 2718 e e Σ 1n de n0 a 10 11 12 13 No primeiro caso devemos usar qual tipo de ajuste numérico para obter um número finito E no segundo caso Quais são os erros envolvidos em cada um dos casos REFERÊNCIAS ALMEIDA M C Origens da matemática a préhistória da matemática o neolítico e o alvorecer da história Curitiba Progressiva 2011 v 1 CARROLL L Aventuras de Alice no país das maravilhas Através do espelho e o que Alice encontrou por lá São Paulo Zahar 2013 DICIO Dicionário Online de Português 2021 Disponível em httpswwwdiciocombr Acesso em 2 jun 2021 GILAT A SUBRAMANIAM V Métodos numéricos para engenheiros e cientistas uma introdução com aplicações usando o MATLAB Porto Alegre Bookman 2008 JUSTO D A R et al REAMAT cálculo numérico Porto Alegre UFRGS Disponível em httpswwwufrgsbrreamatCalculoNumericolivroscimainhtml Acesso em 2 jun 2021 SAMPEDRO J Um sistema binário inventado na Polinésia séculos antes de Leibniz El País 16 dez 2013 Disponível em httpsbrasilelpaiscombrasil20131216sociedade1387215405275511html Acesso em 2 jun 2021 WEBER R F Fundamentos de arquitetura de computadores v 8 Porto Alegre Bookman 2004 Assim quando o jogador pensa na movimentação que fará com sua peça ele identifica a linha e a coluna para onde fará o movimento Por exemplo o peão branco na casa 2D pode se movimentar para a 4D Outro peão branco localizado na casa 2C pode avançar para a 4C Na Figura 2 temos o peão preto que foi movido para a casa 5D Figura 2 Movimentação no tabuleiro de xadrez Note que compreender a movimentação por meio de linhas e colunas facilita muito a escrita de jogadas Se isso não fosse normalizado dessa forma seria bem difícil explicar diferentes jogadas e movimentações para outros jogadores por intermédio de obras literárias e artigos técnicos Partindo dessa ideia definimos matematicamente o conceito de matriz Definição 1 Chamase matriz de ordem m por n a um quadro de m n elementos dispostos em m linhas e n colunas da seguinte forma LEON 2019 Amn a11 a12 a1n a21 a22 a2n am1 am2 amn aijmn Se pensarmos em matriz como uma forma de organizar coisas em posições específicas é possível perceber que os elementos dessa matriz podem ser qualquer objeto Contudo matematicamente entendemos os elementos de uma matriz como números reais ou complexos funções ou ainda outras matrizes 54 Matemática para Computação 3 Matrizes Quando falamos em matemática para computação temos como objetivo possibilitar uma base para conceitos que serão usados não só como ferramenta para desenvolver e aprimorar o raciocínio lógico dentro da matemática e de outras disciplinas mas também como ins trumento essencial para a programação seja esta como objeto de aprendizagem teórico ou mesmo como objeto aplicado Você já se perguntou quanta matemática está por trás de um sim ples software de reconhecimento de imagem Ou como transformar um problema real em um problema computacional É a matemática envolvida nessas situações que queremos apresentar Assim iniciamos com o conceito de matriz possivelmente já visto por muitos de vocês no ensino médio mas que será reforçado nesse momento para que possamos ampliar o nosso ferramental aplicado à computação Dessa forma este capítulo trará a estrutura das matrizes e as suas propriedades pois queremos possibilitar o entendimento da relação desse conceito com estruturas vetoriais listas arrays dentre outros que são essenciais na maior parte das linguagens de programação Na sequência aprofundaremos a definição de operação matricial abordando determinantes matrizes inversas e fatoração de matrizes Essa base auxiliará no entendimento de construções da lógica da pro gramação e na aplicação dessa lógica voltada ao tratamento vetorial ao processamento numérico e à modelagem computacional A ideia é possibilitar um estudo crítico e de real aprendizado direcionado para as necessidades da profissão e do mundo que nos cerca Matrizes 55 Com o estudo deste capítulo você será capaz de relacionar o conceito de vetor e matriz pensar a definição de multiplicação matricial de modo computacional compreender o conceito de base de espaços formados por vetores para a agilidade dos resultados computacionais entender e aplicar o processo de fatoração matricial conhe cido por método de Gauss aplicar o conceito de algoritmo para resolver os processos de fatoração e decomposição matriciais interpretar a inversa de uma matriz por meio de processos de decomposição matricial Objetivos de aprendizagem 31 Vetores de uma matriz Vídeo Você conhece as regras do jogo de xadrez Antes de entender qual quer regra que envolva esse tipo de jogo precisamos conhecer o tabu leiro pois toda e qualquer regra estará vinculada à posição em que as peças se encontram Assim o tabuleiro de xadrez é formado por linhas representadas por números e colunas retratadas por letras conforme podemos observar na Figura 1 Figura 1 Linhas e colunas no xadrez VapartShutterstock A nomenclatura usual para uma matriz é dada por 01 Letras maiúsculas para simbolizar matrizes 02 Letras minúsculas para denotar seus elementos 03 A posição de cada elemento é apresentada por meio de subíndices sendo que usamos i para a posição do elemento em relação à linha e j para a posição do elemento em relação à coluna aij 04 Para indicar a ordem de uma matriz A isto é o número de linhas e colunas escrevese Amn sendo que m representa o número de linhas e n o de colunas Cada elemento da matriz A tem dois índices aij sendo que o primeiro índice representa a linha a que esse elemento pertence e o segundo a coluna Dessa forma aij com i variando de 1 a m e j de 1 a n representamos abreviadamente a matriz A de ordem m por n 01 Duas matrizes A aij e B bij de ordem m por n são iguais equivalentes se e somente se aij bij 02 A matriz de ordem n por 1 é uma matriz coluna An1 a11 a21 an1 aijn1 03 A matriz de ordem 1 por n é uma matriz linha A1n a11 a12 a1n aij1n 58 Matemática para Computação Cada linha ou coluna representa um vetor Assim se a matriz é de ordem m por n teremos vetores m vetores linha ou n vetores coluna Logo o que determina se olharemos para as linhas ou para as colu nas como vetores é a aplicação relacionada a essa matriz De acordo com Feofiloff 2018 um vetor ou arranjo array é uma estrutura de dados que armazena uma sequência de objetos todos do mesmo tipo em posições consecutivas da memória RAM random access memory do computador Essa estrutura permite acesso aleató rio qualquer elemento do vetor pode ser alcançado diretamen te sem passar pelos elementos anteriores o décimo elemento por exemplo pode ser alcançado sem que seja necessário passar antes pelo primeiro segundo etc nonos elementos Note que Feofiloff 2018 usa termos específicos da computação mas que são simplesmente conceitos matemáticos que já conhece mos vetores e matrizes Um array pode ser unidimensional ou multidimensional Quando o array é unidimensional temos o vetor que é capaz de armazenar mui tas variáveis do mesmo tipo Uma coleção de arrays ou seja um array multidimensional é entendida como uma matriz também pode ser compreendida como um vetor de vetores Cada elemento da matriz é acessado pelos seus índices ou seja i e j que determinam a posição desse elemento A proposta do nosso material não é a de simplesmente revisar o conceito de matriz mas a de trazer uma nova abordagem para este pensando na sua aplicação na computação Para isso vamos focar as maneiras de aplicarmos as matrizes e os seus vetores tendo como objetivo as operações realizadas computacionalmente É nesse contexto que entramos na próxima seção na qual aborda remos as operações matriciais e os algoritmos 32 Análise do algoritmo padrão para multiplicação de matrizes Vídeo Talvez você já tenha pensado no processo de adição e subtração matricial de maneira computacional A soma e a subtração entre duas matrizes exigem apenas que a ordem destas seja igual visto que para a obtenção do resultado será necessário somar ou subtrair respectivamente termo a termo dessas matrizes A soma de duas matrizes A aij e B bij de ordem m por n é uma matriz C cij tal que cij aij bij Para compreender essa operação acompanhe o exemplo a seguir Exemplo 1 Sejam as matrizes A 1 2 3 4 e B 4 5 6 7 então A B 14 25 36 47 5 7 9 11 A mesma propriedade é válida para a subtração entre matrizes como podemos notar no exemplo a seguir Exemplo 2 Sejam as matrizes A 1 2 3 4 e B 4 5 6 7 então A B 14 25 36 47 3 3 3 3 Contudo o processo de multiplicação não é tão intuitivo Por esse motivo apresentamos na sequência o algoritmo que permite fazermos multiplicações entre duas matrizes Algoritmo 1 Sejam A aijmn e B brsnp o produto de A por B é definido como AB cuvmp onde cuv k1n auk bkv au1 b1v aun bnv O produto entre duas matrizes Amn e Bnp só é possível se o número de colunas da matriz A for igual ao número de linhas da matriz B n l O resultado desse produto será uma matriz de ordem m p O elemento resultante desse produto será denotado por cij iésima linha e jésima coluna da matriz produto e obtido por meio da soma entre os produtos dos elementos da iésima linha da primeira matriz pelos elementos correspondentes da jésima coluna da segunda matriz Acompanhe o exemplo a seguir para compreender melhor como calculamos a multiplicação de matrizes Exemplo 3 Vamos efetuar o produto entre as matrizes A12 1 1 e B23 2 1 4 3 4 3 Verificamos se o número de colunas da matriz A é igual ao número de linhas da matriz B Nesse caso colunas de A linhas de B 2 Portanto o produto entre matrizes é possível e dará origem a uma matriz C com o número de linhas de A e o número de colunas de B ou seja originará uma matriz C13 C13 1 1 2 1 4 3 4 3 1 2 1 3 11 1 4 14 1 3 1 5 1 A multiplicação de matrizes tem as seguintes propriedades Em geral AB BA AB 0 sem que A 0 ou B 0 AI IA A onde I é a matriz identidade Distributividade AB C AB AC A BC AC BC ABC ABC AABt Bt At 0A 0 e A0 0 Fechamos esta seção com as propriedades algébricas da multiplicação entre matrizes Com isso temos em mãos as propriedades matriciais necessárias para resolvermos diversos exemplos e aplicações 33 Bases Vimos que uma matriz é constituída de linhas e colunas Essas mesmas linhas e colunas podem ser consideradas vetores dessa matriz Observe a Figura 3 que apresenta graficamente duas equações de retas representadas em um mesmo sistema de coordenadas cartesianas ℝ² Figura 3 Sistema de equação 2x y 4 3x y 2 Fonte Elaborada pela autora Esse sistema escrito como 2x y 4 3x y 2 pode ser representado na forma matricial a seguir 2 1 3 1 x y 4 2 Ao analisarmos os vetores linha da matriz dos coeficientes dados por v₁ 2 1 e v₂ 3 1 podemos expressar que v₁ não pode ser escrito como uma combinação linear de v₂ ou seja não podemos denotar como v₁ αv₂ Essa simples análise nos fornece a informação de que esses vetores são linearmente independentes e como eles são formados por duas coordenadas isto é são bidimensionais e estão contidos em um espaço bidimensional ainda podemos afirmar que esses mesmos dois vetores v₁ e v₂ formam uma base para o ℝ² No caso de um sistema de equações composto por n equações e n variáveis identificar que os vetores que formam a matriz dos coeficientes são também uma base para ℝⁿ nos permite afirmar que esse sistema é compatível e determinado então tem uma única solução Assim para identificar se n vetores de uma matriz formam uma base para o espaço ℝⁿ precisamos analisar duas situações I se os vetores são linearmente independentes LI II se os vetores geram ℝⁿ A base mais simples para um espaço de vetores é a base canônica Para o ℝ² ela é formada pelos vetores e₁ 1 0 e e₂ 0 1 Note que se admitirmos um outro vetor qualquer nesse sistema por exemplo o vetor v 5 3 este será escrito como uma combinação linear Figura 4 de e₁ e e₂ na forma 5 3 51 0 30 1 5v₁ 3v₂ Geometricamente o que estamos mostrando é que existem escalares α₁ 5 e α₂ 3 tais que v α₁ v₁ α₂ v₂ Vídeo Trouxemos o conceito de base pensando na proposta aplicada mas caso você tenha interesse em se aprofundar nesse tema com a visão da álgebra linear sugerimos o vídeo Combinações lineares subespaços gerados e bases A essência da Álgebra Linear capítulo 2 publicado pelo canal 3Bluw1Brown Disponível em httpswwwyoutubecomwatchvk7RMot2NWY Acesso em 6 jul 2021 Matrizes 63 Figura 4 Combinação linear entre v1 e v2 y x 3v2 v2 0 1 v1 1 0 5v1 Fonte Elaborada pela autora Portanto uma combinação linear pode ser definida como Definição 2 Sejam v1 vn elementos de um espaço de vetores V então v é uma combinação linear de v1 vn se existirem números reais α1 αn tais que v α1v1 αnvn 1 Já o que define a independência linear é Definição 3 Uma sequência de vetores v1 vn de um espaço vetorial V é linearmente independente LI se α1v1 αnvn 0 2 e isso só é verdade se α1 αn 0 Se dispusermos os vetores que desejamos analisar em uma matriz quadrada A como fizemos com a matriz dos coeficientes do sistema de equações anterior e calcularmos seu determinante podemos ter dois tipos de solução se det A 0 então os vetores são LD se det A 0 então os vetores são LI LD linearmente dependente Glossário Para compreender esses conceitos acompanhe o próximo exemplo Exemplo 4 Sejam os vetores u 1 2 3 v 3 1 6 e w 4 2 1 Queremos classificar os três vetores em LI ou LD Assim fazemos A 1 2 3 3 1 6 4 2 1 Aplicando a regra de Sarrus podemos escrever A 1 2 3 3 1 6 4 2 1 111 264 332 413 261 132 59 Logo os vetores u v e w são linearmente independentes pois o determinante de A resultou em um valor diferente de zero Portanto podese usar as matrizes e suas operações nesse caso o determinante para analisar se os vetores que a compõem são linearmente independentes Conhecendo a quantidade de elementos que está alocada nesses vetores e a dimensão do espaço a ser analisado é possível avaliar se esse espaço pode ser gerado por esses vetores Com essas duas conclusões em mãos podemos afirmar ou não a existência de uma base de vetores para o espaço avaliado 34 Fatoração matricial Método de Gauss Vídeo Computacionalmente podemos trabalhar com matrizes com um número muito grande de elementos Ao pensarmos por exemplo na análise de dados nas redes de computadores ou mesmo na área de inteligência artificial o número de elementos em uma matriz pode estar na casa dos milhares ou mais Portanto é impossível realizarmos cálculos de maneira manual sem a utilização de uma ferramenta computacional Dessa forma a correta manipulação desses dados dentro das matrizes é fundamental para que encontremos resultados coerentes Assim vamos abordar nesta seção a fatoração decomposição de matrizes para que possamos viabilizar algoritmos que nos permitam resolver determinantes encontrar a inversa ou mesmo resolver grandes sistemas de equações dentre outras aplicações Seja uma matriz Amn dada por A1 a111 a112 a11k a11m a11n a121 a122 a12k a12m a12n a1k1 a1k2 a1kk a1km a1kn a1m1 a1m2 a1mk a1mm a1mn E ainda seja Ak uma matriz semelhante a A1 já triangularizada Ak a111 a112 a11k a11m a11n 0 a222 a22k a22m a22n 0 0 akkk akkm akkn 0 0 akmk akmm akmn A triangularização de matrizes é um dos processos mais práticos para a resolução de diversos problemas dentro da álgebra como aqueles citados anteriormente Vamos entender esse processo de modo que seja possível transcrevêlo em formato de algoritmo Note que A2 M₁ A1 Am Mm1 Am1 Portanto precisamos de m 1 passos para concluir a decomposição Vamos escrever esse processo em etapas Se a111 0 então A A1 a111 a121 a1k1 a1m1 a1n1 a211 a221 a2k1 a2m1 a2n1 ak11 ak21 akk1 akm1 akn1 am11 am21 amk1 amm1 amn1 Assim existe uma matriz M1 m m M1 1 0 0 0 a211a111 1 0 0 1 1 am11a111 0 0 1 Com m21 a211a111 m31 a311a111 mm1 am11a111 tal que A2 M1 A1 Logo A2 a111 a121 a1k1 a1m1 a1n1 0 a222 a2k2 a2m2 a2n2 0 a2k2 akk2 akm2 akn2 0 am22 amk2 amm2 amn2 Note que M1 multiplica todas as colunas de A mas só zera a coluna 1 abaixo da posição 1 1 ou ocasionalmente alguma outra coluna Se a222 0 então existe uma matriz M2 m m tal que A3 M2 A2 M2 M1 A1 M2 1 0 0 0 1 a322a222 1 0 0 0 0 0 1 0 0 am22a222 0 1 Com m32 a322a222 m42 a422a222 mm2 am22a222 Logo A3 a111 a121 a1k1 a1m1 a1n1 0 a222 a2k2 a2m2 a2n2 0 0 akk3 akm3 akn3 0 0 amk3 amm3 amn3 Se akkk 0 então Ak1 Mk Ak Ak1 a111 a121 a1k1 a1n1 0 a222 a2k2 a2n2 0 0 0 0 akkk1 ak1nk1 0 0 0 0 0 0 amk1k1 amnk1 O processo deve ser seguido até o passo r em que r minm 1 n Dessa forma podemos escrever Ak1 Mk Ak Mk Mk1 M1 A1 Mas por que todo esse procedimento Porque sabemos que o determinante de uma matriz pode ser calculado por meio da multiplicação dos elementos da diagonal principal porém também porque usaremos métodos de decomposição aplicados a outras operações com matrizes por exemplo no cálculo da inversa de uma matriz Além disso outro motivo é o computador resolver processos numéricos discretos por etapas podendo ainda carregar muitos erros de arredondamento truncamento e cancelamento Dessa forma para implementar uma matriz e as operações sobre esta é necessário que tenhamos um passo a passo do processo numérico Transformar um problema matemático em um algoritmo nos oferece justamente esse passo a passo necessário para que o computador possa resolvêlo Agora vamos colocar na prática os passos observados na teoria Exemplo 5 Seja A 2 4 2 1 1 5 4 1 2 A decomposição de Gauss ocorrerá em r min2 3 2 passos Então fazendo o passo a passo temos Passo 1 a11 0 M1 1 0 0 12 1 0 42 0 1 A2 M1 A1 1 0 0 12 1 0 42 0 1 2 4 2 1 1 5 4 1 2 2 4 2 0 3 6 0 7 2 Passo 2 a22 0 M2 1 0 0 0 1 0 0 73 1 A3 M2 A2 1 0 0 0 1 0 0 73 1 2 4 2 0 3 6 0 7 2 2 4 2 0 3 6 0 0 12 Os elementos akkk são os elementos pivôs O resultado obtido com o método de Gauss pode ser aplicado em muitos contextos como citamos anteriormente Usando esse método como motor para as nossas próximas decomposições vamos ver algumas possibilidades para a decomposição matricial que podem agilizar o processo de cálculo computacional e minimizar os erros obtidos nesse processo 35 Decomposição LU e LDU Nesta seção apresentaremos alguns tipos de fatoração de matrizes que serão úteis para a resolução de sistemas de equações lineares Esses processos de fatoração também são chamados de métodos de decomposição Iremos então estudar a decomposição LU e a LDU Esse último método ainda pode ser ramificado em outros métodos dependendo do tipo de matriz que tivermos Vamos entender esses processos 351 Decomposição LU Seja uma matriz A de ordem m A decomposição dessa matriz em outras duas matrizes sendo a primeira uma matriz triangular inferior L lower e a segunda uma matriz triangular superior U upper é chamada de decomposição LU FRANCO 2006 A a11 a1m am1 amm l11 0 lm1 lmm u11 u1m 0 umm L U Esse tipo de decomposição não é único Ou seja podem existir diferentes matrizes triangulares inferiores e superiores que quando multiplicadas originarão a matriz A Assim para encontrálas usamos o processo de eliminação de Gauss que nos auxilia a escrever a matriz A na forma fatorada em matrizes mais simples Como vimos o processo de Gauss gera matrizes M1 M2 Mr com r minm 1 n tal que Ar1 Mr Mr1 M1 A As matrizes M não são singulares portanto podemos calcular suas inversas Assim A M11 M21 Mr1 Ar1 Portanto L M11 M21 Mr1 e U Ar1 com Triangular inferior L M11 M21 Mr1 1 0 0 1 m1 m2 mr 1 Triangular superior U a111 a222 ammm Para compreender como desenvolver a decomposição LU de uma matriz acompanhe o próximo exemplo Exemplo 6 Seja A 3 2 4 1 1 2 4 3 2 Determine a decomposição LU da matriz A Usando a decomposição de Gauss temos como primeiro pivô o elemento na posição a111 3 Assim os multiplicadores são m21 a211 a111 13 e m31 a311 a111 43 A A1 3 2 4 1 1 2 4 3 2 L2m21L1 L3m31L1 3 2 4 0 13 23 0 13 103 O próximo pivô é a222 13 Então o multiplicador é m32 a322 a222 1 1 A2 3 2 4 0 13 23 0 13 103 L3m32L2 3 2 4 0 13 23 0 0 4 Portanto L carrega os multiplicadores triangular inferior e U é a última matriz após a triangularização triangular superior L 1 0 0 13 1 0 43 1 1 e U 3 2 4 0 13 23 0 0 4 Além da decomposição LU que como vimos não é única podemos nos basear nela para um outro tipo de decomposição chamado de LDU Vamos entendêlo na sequência Curiosidade Na linguagem MATLAB é possível usar as funções intrínsecas dessa linguagem para calcular a decomposição LU Assim tendo a matriz A basta fazer L U luA L U P luA 352 Decomposição LDU A decomposição LDU ao contrário da LU é única desde que os pivôs sejam diferentes de zero Como o próprio nome nos leva a perceber A será fatorada decomposta em uma matriz triangular inferior L uma matriz diagonal D e uma matriz triangular superior U na forma Gauss pode ser aplicado sem troca de linhas ou colunas Dessa maneira Assim Portanto Definindo então D1 existe e Definindo temos que E como Então A L An L DD1 An LDU Assim A pode ser decomposta da forma descrita Acompanhe o exemplo a seguir para praticar a decomposição em LDU de uma matriz Exemplo 7 Decomponha a matriz A em LDU Para decompor a matriz A em LDU utilizamos a decomposição de Gauss Assim calculamos M1 usando inicialmente o pivô e encontramos e Portanto a matriz obtida é Desse modo obtemos nessa etapa a matriz Agora precisamos calcular M2 usando como pivôs Portanto Assim Nesse momento temos Agora basta organizar U na forma Portanto Dependendo de como D é tratado existem três tipos de decomposições 1 Decomposição de Doolittle direto de Gauss 2 Decomposição de Crout 3 Decomposição de Cholesky Observação a decomposição de Cholesky pode ser encontrada baseada em Gauss pois se A é simétrica A LDU e U LT Contudo a decomposição de Cholesky só é possível quando A for uma matriz positiva definida por A LDLT Se D 0 então Matrizes 75 Quando aplicamos os processos de decomposição para agilizar a resolução de sistemas de equações percebemos que cada tipo desses sistemas se comporta melhor com uma decomposição específica Se as matrizes são esparsas adotamos um método se temos uma matriz em blocos podemos adotar outro O importante é termos o conhecimento prévio das ferramentas que podem ser utilizadas para que possamos definir em cada caso qual a melhor estratégia de resolução considerando a agilidade a rapidez computacional e a minimização de erros Uma matriz é denomi nada positiva definida se os determinantes das n submatrizes principais de A forem positivos ou seja Akk 0 para todo 1 k n A matriz identidade é um exemplo de matriz positiva definida Saiba mais 36 Inversa de uma matriz Vídeo Há algumas maneiras de calcular a inversa de uma matriz Uma de las exige o cálculo do determinante Como vimos o determinante pode ser encontrado por meio da triangularização de uma matriz Após esse processo basta multiplicar os elementos da diagonal resultante Logo pensando computacionalmente o cálculo do determinante de uma matriz depende de operações elementares as quais não alteram a solução do sistema que podem ser descritas dos seguintes modos I Permuta da iésima linha pela jésima linha Li Lj é trocar as linhas o que é equivalente a trocar a posição das equações II Multiplicação da iésima linha por um escalar não nulo λ Li λLi referese ao mesmo que multiplicar um número não nulo na equação correspondente III Substituição da iésima linha pela iésima linha mais λ vezes a jésima linha Li Li λLj corresponde a somar o múltiplo da outra equação Vamos praticar o cálculo do determinante de uma matriz utilizando as operações elementares A plataforma da Khan Academy tem um material muito interessante sobre as operações aplicadas sobre linhas e colunas de uma matriz Além da leitura é possível resolver alguns exercícios sobre o assunto Disponível em httpsptkhana cademyorgmathprecalculus precalcmatriceselementarymatrix rowoperationsamatrixrowope rations Acesso em 6 jul 2021 Saiba mais Exemplo 8 Seja a matriz A 2 2 3 1 1 3 2 0 1 queremos calcular seu determinante por meio de uma triangularização Assim aplicando operações elementares temos 2 2 3 1 1 3 2 0 1 2 2 3 0 0 92 0 2 4 L3L3L1 L2L2 12 L1 2 2 3 0 0 92 0 2 4 2 2 3 0 2 4 0 0 92 L3L2 Nesse ponto já temos uma matriz triangularizada portanto det A 2 2 92 18 Com base nesse princípio desenvolvemos na sequência o cálculo da inversa de uma matriz conhecendo seu determinante 361 Inversa de uma matriz por meio de determinantes Uma das maneiras de encontrarmos a inversa de uma matriz quadrada A é por meio da matriz dos cofatores de A Com esse resultado é possível obter a matriz adjunta de A e na sequência sua matriz inversa Dessa forma inicialmente precisamos conhecer o cofator de cada um dos elementos de A dados por Aij 1ij Mij Assim Mij representa a matriz obtida da matriz original pela eliminação da iésima linha e da jésima coluna É possível formar uma nova matriz denominada de Ā em que Ā Aij Essa será a matriz dos cofatores A transposição dessa matriz Ā origina a chamada matriz adjunta de A denotada por adjA Logo adjA Āt Com o conceito de determinante de uma matriz e de matriz adjunta podemos enunciar um teorema que permite o cálculo da inversa de uma matriz A baseado nesses conceitos Teorema 1 Uma matriz quadrada A admite uma inversa se e somente se det A 0 KOLMAN HILL 2013 Nesse caso A1 1det A adjA Assim como as propriedades para as operações entre matrizes ou mesmo as propriedades para o determinante de uma matriz destinamos nesta seção um espaço para tratarmos das propriedades das matrizes invertíveis São elas Sejam duas matrizes quadradas A e B de ordem n com determinante diferente de zero e portanto não singulares o que nos permite afirmar que são invertíveis Portanto se existe A1 e B1 então A B é invertível e A B1 B1 A1 Seja A uma matriz quadrada de ordem n com BA I portanto B é também de ordem n Logo A é invertível ou seja A1 existe e além disso B A1 Dizemos que uma matriz A é semelhante a uma matriz B se e somente se existir uma matriz invertível Q tal que podemos escrever A Q1 BQ Em todos os casos podemos usar essas características algébricas para otimizar os processos numéricos e agilizar a obtenção de uma resposta Computacionalmente encontramos muitas vantagens quando podemos simplificar processos e uma delas é a possibilidade de diminuir o custo computacional Ainda é possível minimizar erros quando reduzimos a quantidade de operações realizadas Dessa forma o estudo das matrizes invertíveis e suas propriedades nos traz um ganho em diferentes áreas e aplicações 362 Inversa de uma matriz por meio do método de GaussJordan Vamos supor que uma matriz A de ordem n possa ser fatorada até ser equivalente à matriz identidade In Mk Mk1 M2 M1 A Sendo assim podemos multiplicar os dois lados da igualdade para obtermos a matriz inversa de A ou seja In A1 Mk Mk1 M2 M1 A A1 A1 Mk Mk1 M2 M1 In Na prática se temos uma matriz A de ordem n podemos escrever essa matriz da forma AIn2n Aplicando operações elementares sobre AIn2n precisamos obter IBn2x com B A1 Uma observação se ao realizar o procedimento ocorrer uma linha de zeros do lado esquerdo significa que a matriz A não tem inversa Para comprovar esse resultado basta calcular o determinante de A e verificar que ele é igual a zero O exemplo a seguir esclarece como encontrar a inversa de uma matriz por meio da triangularização ou seja pelo método GaussJordan Exemplo 9 Encontre a inversa de 2 6 1 3 Aplicando algumas operações elementares nessa matriz obtemos 2 61 0 L112 1 312 0 L2L2 L1 1 30 1 1 6 12 1 41 Sistemas equivalentes e operações Aprender a resolver os mais diversos tipos de sistemas de equações de maneira exata ou aproximada é uma tarefa de grande necessidade dentro das ciências Antes de discorrermos sobre as diferentes abordagens e métodos de resolução discutiremos nas subseções a seguir sobre a estrutura de um sistema de equações lineares e como podemos realizar operações nesse tipo de sistema 411 Sistemas equivalentes Analisar a equivalência entre objetos é comparálos dois a dois de acordo com algumas propriedades A definição de sistemas equivalentes está descrita a seguir Definição 1 Dois sistemas de equações lineares envolvendo as mesmas variáveis são equivalentes se e somente se tiverem o mesmo conjunto solução LEON 2019 p 4 Dessa maneira vamos supor um sistema AX1 B e um segundo sistema QX2 C Se X1 X2 os dois sistemas serão equivalentes Exemplo 1 O sistema 3x1 x2 4x3 2 x1 x2 x3 8 2x2 x3 1 é equivalente ao sistema 3x1 x2 4x3 2 4 3 x2 1 3 x3 26 3 3 2 x3 12 pois ambos apresentam como solução o vetor X 23 2 9 2 8 A definição e o exemplo nos levam a pensar que se temos um sistema no qual A é uma matriz complicada de ser resolvida ou seja exige muitos cálculos podemos transformála em uma matriz semelhante mais simples por exemplo uma matriz triangular de modo que não alteremos a solução do sistema Dessa maneira temos na definição de matrizes equivalentes uma ferramenta essencial para nos auxiliar na resolução de sistemas de equações Mas quais são as operações que podem ser aplicadas para essa transformação na matriz sem que o sistema seja alterado No tópico a seguir vamos apresentar as operações e aplicar em alguns exemplos 412 Operações elementares Um dos modos mais rápidos de encontrar o conjunto solução para um sistema de equações lineares é por meio do chamado escalonamento da matriz ampliada Uma matriz é denominada escalonada quando o número de zeros ao lado esquerdo do primeiro elemento não nulo da linha aumenta a cada linha Por exemplo a matriz a seguir está escalonada 1 2 0 1 0 2 0 1 0 0 1 0 0 0 0 3 No caso de ter esgotado o número de colunas isto é quando uma linha se torna nula todas as linhas seguintes devem ser linhas nulas Para obter uma matriz escalonada com base em uma matriz ampliada do sistema de equações lineares utilizamos operações elementares como a seguir Permuta da iésima linha pela jésima linha A troca de linhas corresponde à troca de posição das equações o que não influencia na solução do sistema Li Lj Multiplicação da iésima linha por um escalar não nulo λ Equivale a multiplicar um número não nulo na equação correspondente que também não altera a solução Li λLi Substituição da iésima linha pela jésima linha mais λ vezes a iésima linha Equivale a somar o múltiplo da outra equação que também não altera a solução do sistema Li Li λLj 80 Matemática para Computação ATIVIDADES Nas regras do xadrez cada peça tem uma movimentação possível Por exemplo o cavalo só pode se movimentar em L ou seja duas casas para a direita ou para a esquerda e uma para frente ou para trás uma casa para a direita ou para a esquerda e duas casas para frente ou para trás A figura a seguir é um exemplo das possíveis movimentações que um cavalo na casa 4D pode fazer 8 7 6 5 4 3 2 1 H G F E D C B A Explique usando a notação linhacoluna as possíveis movimentações do cavalo branco que está na casa 1G observação ele não pode ficar sobre outra peça branca Atividade 1 De acordo com o conceito de base para um espaço de vetores indique dois conjuntos de vetores que formam uma base para o ℝ³ Justifique o porquê dessas escolhas Atividade 2 Explique por que afirmamos que a decomposição LU não é única Atividade 3 REFERÊNCIAS FEOFILOFF P Vetores IME 2018 Disponível em httpswwwimeuspbrpfalgoritmos aulasarrayhtml Acesso em 6 jul 2021 FRANCO N M B Cálculo numérico 1 ed São Paulo Pearson Universidades 2006 KOLMAN B HILL D R Álgebra linear com aplicações 9 ed Rio de Janeiro Livros Técnicos e Científicos 2013 LEON S J Álgebra linear com aplicações 9 ed Rio de Janeiro Livros Técnicos e Científicos 2019 Sistemas de equações lineares 81 4 Sistemas de equações lineares Os sistemas de equações são encontrados em uma gama de apli cações e nas mais diversas áreas Das exatas às ciências biológicas passando pelas áreas tecnológicas e ciências sociais resolver um sis tema de equações pode nos levar a resultados de balanceamentos químicos respostas de sistemas elétricos equilíbrio de forças distri buições de alimentos dentre tantos outros De maneira mais conceitual porém ainda aplicada os sistemas de equações nos permitem encontrar o que se relaciona nas diferentes estruturas que os compõem ou seja pontos de intersecção retas co muns ao sistema e planos que se interceptam Para resolver um sistema de equações existem diversos métodos desde diretos e iterativos até exatos ou com solução aproximada mas em todos os casos se queremos expandir o conjunto de aplicações precisamos levar esses modos de resolução para um aspecto computa cional Esse é o tema do capítulo sobre sistemas de equações lineares Com o estudo deste capítulo você será capaz de analisar a equivalência entre sistemas de equações lineares e aplicar operações elementares sobre eles resolver sistemas de equações de maneira direta e iterativa analisar alguns algoritmos de resolução de sistemas de equa ções lineares para incentivar o pensamento computacional compreender as propriedades inerentes aos sistemas trian gulares ou triangularizados classificar os sistemas de equações lineares Objetivos de aprendizagem Vídeo O vídeo Exemplo prático sistemas equivalentes de equações da plataforma Khan Academy é um conteúdo interessante sobre o tema sistemas de equações Além de assistir ao vídeo você pode resolver exercícios usando a plataforma que é gratuita gamificada e adaptativa Essa prática te ajudará a fixar o conteúdo Disponível em httpsptkhanacademyorgmathalgebrasystemsoflinearequationsequivalentsystemsofequationsvidentifyingequivalentsystemsofequations Acesso em 14 jun 2021 1 3 1 2 0 0 1 1 1 12 1 6 1 0 1 4 1 2 0 1 1 12 1 6 Portanto A1 1 4 1 2 1 1 12 1 6 Com essas técnicas relembramos os conceitos de vetores e matrizes além de fazermos a manipulação de operações sobre essas estruturas Percebam que o nosso foco foi trazer novas ferramentas e abordagens que se adequem de maneira mais suave à necessidade de aplicação computacional dos conceitos matemáticos Desse modo são abordagens que quando transformadas em algoritmos podem ser implementadas com facilidade sendo que algumas linguagens de programação já têm essa base matemática implementada para uso direto das operações Mesmo nesses casos é importante saber o que está acontecendo por trás da resposta obtida Por esse motivo sempre estimulamos que os conceitos matemáticos envolvidos nas funções intrínsecas a cada uma das linguagens de programação sejam avaliados antes do seu uso As operações realizadas em uma matriz ampliada resultam em uma matriz equivalente Conforme o exemplo a seguir ilustra Exemplo 2 O sistema 3x1 x2 4x3 2 x1 x2 x3 8 apresentado no Exemplo 1 pode ser 2x2 x3 1 escrito na forma de matriz ampliada como Aplicando as operações anteriormente elencadas fazemos Na sequência desenvolvemos Note que após a aplicação de operações elementares obtemos uma matriz ampliada escalonada sendo que podemos transcrevêla da forma matricial para a forma de sistema 3x1 x2 4x3 2 43 x2 13 x3 263 32 x3 12 De acordo com Leon 2019 dois sistemas que possuem matrizes ampliadas equivalentes têm o mesmo conjunto solução Dessa maneira podemos definir Definição 2 Desde que possuam matrizes ampliadas equivalentes os sistemas podem ser denominados sistemas equivalentes LEON 2019 p 4 Uma importante característica dos sistemas de equações lineares é a possibilidade de verificação da solução prova real Para isso basta substituirmos a solução encontrada nas equações originais como é desenvolvido no exemplo a seguir Exemplo 3 No Exemplo 1 afirmamos que os sistemas 3x1 x2 4x3 2 x1 x2 x3 8 e 2x2 x3 1 3x1 x2 4x3 2 43 x2 13 x3 263 32 x3 12 eram equivalentes porque tinham a mesma solução Assim verificamos que eles realmente têm essa característica Como X 232 92 8T então substituindo essa solução no primeiro sistema temos que E o mesmo pode ser feito no segundo sistema Como ambos os sistemas têm X como solução eles são sistemas equivalentes 86 Matemática para Computação Com os sistemas equivalentes e operações definidos veremos na sequência a aplicação de inversão de matrizes para a solução de um sistema de equações 413 Análise da matriz inversa Um sistema linear da forma AX B com A sendo uma matriz de coefi cientes quadrada pode ser resolvido com a aplicação de matrizes inversas Note que para esse tipo de aplicação ser possível devemos ter sis temas de equações bem específicos com n equações e n variáveis Outra questão importante é a necessidade de que A seja invertível ou seja que tenha det A 0 Se essas exigências são verificadas podemos escrever Definição 3 Seja A uma matriz nn com A invertível então é válida a sequência de cálculos a seguir I AX B II A1 AX A1 B III In X A1 B IV X A1 B Portanto se A cumpre essas condições temos que X A1 B será a solução única para o sistema determinado 42 Sistemas triangulares e escalonados Vídeo O processo que permite o escalonamento de uma matriz tem como fundamentação teórica o método de Gauss fatoração ou eliminação gaussiana que nos permite escrever um sistema de equações lineares na sua forma triangular superior Por meio de um sistema de equações lineares na forma triangula rizada inferior ou superior é possível encontrar a solução utilizando substituições progressivas triangular inferior ou regressivas triangu lar superior Vamos entender esse processo No vídeo Testando uma solução para um sistema de equações do canal da Khan Academy Brasil você poderá rever esse procedimento sendo aplicado em outros siste mas de equações É uma ferramenta poderosa para verificar se a solução encontrada está correta Disponível em httpsyoutube sxJHonr96kA Acesso em 14 jun 2021 Vídeo Sugerimos que você assis ta ao vídeo Escalonamento disponível no canal Portal da Matemática OBMEP Com ele é possível reca pitular a decomposição gaussiana e começar a aplicála no contexto dos sistemas de equações lineares Disponível em httpswwwyoutu becomwatchvQmmYqR7zm4 Acesso em 14 jun 2021 Vídeo Seja um sistema de equações lineares da forma LX B com L l11 0 ln1 lnn X x1 xn B b1 bn Portanto esse é um sistema triangular inferior no qual a matriz dos coeficientes L tem seus elementos na forma lij 0 para i j Portanto l11 x1 b1 l21 x1 l22 x2 b2 ln1 x1 ln2 x2 lnn xn bn Podemos montar algoritmos para calcular a solução de sistemas lineares com essa característica e que poderão ser reescritos na linguagem de programação desejada Para estruturar tal algoritmo usaremos uma linha genérica li tal que li1 x1 li2 x2 lii xi bi Dessa maneira isolando xi obtemos xi bi li1 li2 x2 lii1 xi1 lii Portanto podemos denotar esse raciocínio como o algoritmo a seguir Algoritmo 1 x1 b1 l11 Para i 2 n faça xi bi Σj1 to i1 lij xj lii Para compreender melhor o Algoritmo 1 acompanhe o exemplo a seguir Exemplo 4 Seja um sistema de equações lineares triangular inferior da forma 1 0 0 2 3 0 1 2 1x1 x2 x3 2 2 1 Vamos resolver esse sistema usando o Algoritmo 1 Assim x1 b1l11 21 2 x2 b2 l21 x1l22 2 22 3 2 4 3 2 x3 b3 l31 x1 l32 x2l33 1 12 221 1 2 41 5 Portanto S 2 2 5 O mesmo princípio é adotado em um sistema de equações lineares triangular superior forma padrão obtida por meio do escalonamento Nesse caso usaremos como modelo um sistema de equações lineares da forma UX B com U u11 u1n 0 unn X x1 xn B b1 bn Portanto esse é um sistema triangular superior no qual a matriz dos coeficientes U tem seus elementos na forma uij 0 para i j Denotamos u11x1 u12 x2 u1n xn b1 u22 x2 u2n xn b2 unn xn bn Também podemos montar um algoritmo para a solução dos sistemas no formato UX B e para isso usaremos a iésima linha da forma uiixi ui i1xi1 uii2xi2 uinxn bi Isolando xi obtemos xi bi u ii1xi1 u ii2xi2 uinxn Portanto podemos escrever esse raciocínio da seguinte maneira Algoritmo 2 xn bnunn Para i n 1 n 2 1 faça xi bi ji1n uij xjuii Exemplo 5 Seja um sistema de equações lineares triangular superior da forma 1 2 1 0 3 0 0 0 1x1 x2 x3 2 2 1 Usando o Algoritmo 2 resolvemos esse sistema da seguinte forma x3 b3u33 11 1 x2 b2 u23 x3u22 2 01 3 23 x1 b1 u12 x2 u13 x3u11 2 223 111 133 Logo a solução para esse sistema de equações é S 133 23 1 Devemos notar que os algoritmos não dependem de linguagem de programação previamente escolhida e precisam ser adaptados à linguagem que queremos programar 421 Classificação de um sistema de equações lineares Começaremos esse tópico elencando três exemplos simples Figura 1 que serão resolvidos de forma escalonada e usados para exemplificar os tipos de soluções possíveis em um sistema de equações lineares Vamos utilizar uma calculadora online para resolver o escalonamento Figura 1 Sistemas de equações escalonados por meio de calculadora online Sistema Escalonamento por meio de calculadora online x1 x2 2 3x1 2x2 3 L2 3L1 L2 1 1 0 12 3 x1 2x2 3 3x1 6x2 9 L2 3L1 L2 1 2 0 03 0 x1 2x2 3 3x1 6x2 3 L2 3L1 L2 1 2 0 00 6 Fonte Elaborada pela autora Mediante o processo de escalonamento da matriz ampliada o sistema de equações lineares pode ser resolvido por meio de substituições regressivas Ao observarmos o primeiro sistema de equações da Figura 1 temos que se as matrizes ampliadas são equivalentes a solução do sistema gerado pela matriz escalonada é equivalente à solução do sistema original Assim podemos escrever x₁ x₂ 2 x₂ 3 Logo x₂ 3 e x₁ 1 Observando graficamente essas duas retas que formam o nosso sistema de equações lineares obtemos Observamos que as retas formadas pela eq1 e eq2 se interceptam em um ponto que não por acaso é a solução do sistema Ou seja a solução de um sistema de equações é justamente o ponto de interseção das retas que formam esse sistema Entretanto o que ocorre nos sistemas de equações seguintes No segundo sistema de equações da Figura 1 após o escalonamento podemos escrever o sistema de equações equivalente da seguinte maneira x₁ 2x₂ 3 0 0 x₁ 2x₂ 3 Observe o gráfico a seguir formado pelas retas Observamos que eq1 e eq2 presentes na Figura 3 se sobrepõem isto é são retas coincidentes Portanto nesse caso afirmamos que temos infinitos pontos de interseção o que nos permite concluir que temos infinitas soluções para o sistema de equações Vamos fazer o mesmo com o terceiro sistema de equações da Figura 1 Primeiro reescreveremos o sistema de equações equivalente escalonado da seguinte forma x₁ 2x₂ 3 0x₁ 0x₂ 6 O qual representamos graficamente como Já no sistema de equações x₁2x₂3 3x₁6x₂3 as equações eq1 e eq2 são paralelas o que nos mostra que não têm pontos de interseção Isso significa que o último sistema de equações representado na Figura 1 não tem solução Assim podemos afirmar que existem três tipos de soluções possíveis para um sistema de equações lineares I quando existe uma única solução denominase sistema compatível e determinado II quando existem infinitas soluções denominase sistema compatível e indeterminado III quando não existe solução denominase sistema incompatível Desejamos criar uma generalização para esse conceito para que possamos classificar um sistema de equações com base em sua matriz dos coeficientes e em sua matriz ampliada escalonada Desse modo introduziremos o conceito de posto de uma matriz Definição 4 O posto p de uma matriz A é o número máximo de linhas não nulas após o seu escalonamento Denotamos o posto da matriz dos coeficientes por pc e o posto da matriz ampliada por pa Assim seja um sistema de equações da forma a₁₁x₁ a₁ₙxₙ b₁ Quadro 1 Síntese de conceitos Reunimos no Quadro 1 os conceitos e as definições abordados até o momento É importante notar que para essa representação escolhemos alguns sistemas de equações lineares como exemplo para uma melhor compreensão dos resultados Primeiro sistema Segundo sistema Terceiro sistema Sistema de equações x1 x2 2 3x1 2x2 3 x1 2x2 3 3x1 6x2 9 x1 2x2 3 3x1 6x2 3 Matriz dos coeficientes 1 1 3 2 1 1 0 1 1 2 3 6 1 2 0 0 1 2 3 6 1 2 0 0 pc pc 2 pc 1 pc 1 Matriz ampliada 1 1 2 3 2 3 1 1 2 0 1 3 1 2 3 3 6 9 1 2 3 0 0 0 1 2 3 3 6 3 1 2 3 0 0 6 pa pa 2 pa 1 pa 2 Posto pa pc n pa pc n pc pa Denominação Compatível e determinado Compatível e indeterminado Incompatível Fonte Elaborado pela autora Percebemos que por meio da análise da matriz dos coeficientes e da matriz ampliada podemos classificar sistemas de equações de qualquer tamanho ou seja formados por m equações e n variáveis 43 Eliminação gaussiana Agora vamos resolver um sistema de equações lineares para que possamos por intermédio desse desenvolvimento definir o método da eliminação gaussiana usando para isso a fatoração matricial decomposição gaussiana Desse modo seja 2x1 4x2 2x3 6 x1 x2 5x3 0 4x1 x2 2x3 2 Portanto pela fatoração matricial escrevemos A A1 2 4 2 1 1 5 4 1 2 multiplicando por M1 A2 2 4 2 0 3 6 0 7 2 multiplicando por M2 A3 2 4 2 0 3 6 0 0 12 O que faz o M1 Zera todos os elementos abaixo da posição 1 1 O que faz o M2 Zera todos os elementos abaixo da posição 2 2 Com isso ao invés de resolvermos A1 x b resolvemos A3 x c em que A2 M1 A1 A3 M2 A2 M2 M1 A1 e M2 M1 A1 x M2 M1 b c Com base nesse exemplo podemos definir Definição 5 Uma matriz elementar triangular inferior de ordem n e índice k pode ser escrita como M In mekT Em que e1T m0 para i 1 k e m m1 m2 mn é ortogonal a todos os vetores canônicos e1 e2 ek Então 1 0 0 m1 m2 mn 0 m1 0 0 1 0 m1 m2 mn 0 m2 0 0 1 0 posição k m1 m2 mn 0 mk 0 Dessa forma temos M 1 1 1 0 0 0 mk1 mn posição k 0 1 1 0 0 0 0 0 0 mk1 mn 0 coluna k Logo M 1 0 0 0 0 0 1 0 0 0 mk1 0 0 mn 1 1 é a matriz elementar triangular inferior de ordem n e índice k Com a matriz elementar podemos extrair os seguintes resultados Resultado 1 se M In m ekT então M1 In m ekT Resultado 2 dado x com xk 0 existe uma única matriz elementar triangular M de índice k que anula todos os elementos de x abaixo da posição k mantendo todos os demais De acordo com a fatoração gaussiana se A é uma matriz com m linhas e n colunas então temos m 1 passos para obter a matriz Am tal que A1 A2 M1 A1 Am Mm1 Am1 Assim generalizando esse processo e escrevendo por meio de matrizes elementares teremos Ak1 Mk Ak Mk Mk1 M1 A1 em que Mk In m ekT Logo Ak1 In mk ekT Ak Que matricialmente é escrito como Ak1 Ak 0 0 0 mk1k mmk 0 0 akkk aknk Portanto Ak1 Ak 0 0 0 0 0 0 0 0 0kk 0 0 0 0 mk1k akkk mk1k aknk 0 x 0 0 0 mmk akkk mmk akkk aknk que apresenta o processo de atualização de Ak A matriz Ak1 pode ser obtida por intermédio da matriz Ak basta alterarmos o canto inferior direito isto é aijk1 aijk i 1 k e j 1 n aijk1 aijk 0 i k 1 m e j 1 k Logo aijk1 aijk mik akjk i k 1 m j k 1 n Esse processo nos permite escrever o algoritmo a seguir Algoritmo 3 Decomposição de Gauss da matriz A Seja A Rmxn m 1 r minm 1 n akkk 0 A a111 a121 a1k1 a1m1 a1n1 a222 a2k2 a2m2 a2n2 akkk akmk aknk m1 m2 mk ammm1 amnm1 Em que mk são as posições abaixo da diagonal que são zeradas Assim para k 1 2 r podemos escrever aik mik aik akk i k 1 m aij aij mik akj i k 1 m j k 1 n Observação os elementos akkk são chamados de elementos pivôs Vamos acompanhar o próximo exemplo para compreender como utilizar o Algoritmo 3 Exemplo 6 Seja A 2 4 2 1 1 5 4 1 2 a decomposição de Gauss ocorrerá em r min23 2 passos Então fazemos Passo 1 a11 0 M1 1 0 0 12 1 0 42 0 1 A2 M1 A1 1 0 0 12 1 0 42 0 1 2 4 2 1 1 5 4 1 2 2 4 2 0 3 6 0 7 2 Passo 2 a22 0 M2 1 0 0 0 1 0 0 73 1 A3 M2 A2 1 0 0 0 1 0 0 73 1 2 4 2 0 3 6 0 7 2 2 4 2 0 3 6 0 0 12 Se o Algoritmo 3 for aplicado a matriz encontrada será A3 2 4 2 12 3 6 2 73 12 O método de eliminação de Gauss pode ser observado na subseção a seguir mediante o chamado pivoteamento completo ou pivoteamento parcial 431 Pivoteamento completo Seja a matriz Ak da forma Ak akkk alkckk Caso o pivô akkk 0 e os demais akk1k akmk forem diferentes de zero então podemos realizar o chamado pivoteamento completo Agora vamos considerar a matriz A A1 e efetuar todas as trocas de linhas e colunas que foram aplicadas ao longo do processo até o passo k encontrando outra matriz A Definição 6 Após apresentarmos a distância entre vetores podemos trazer a definição de convergência que considera como base as definições 8 e 9 as quais usam como eixo central a definição 7 Definição 8 xk x em relação à norma se para todo ε 0 existe um Nε tal que xk x ε k Nε Definição 9 xk x em relação à norma limk xki xi i 1 2 n Concluímos que todas as normas vetoriais no ℝⁿ são equivalentes à convergência ou seja se xk x em relação a uma norma então xk x em relação a qualquer outra norma Quando se trata de matrizes as relações são semelhantes Definição 10 A norma de uma matriz An é uma função ℝnxn ℝ A A que satisfaz A 0 A ℝnxn A 0 A 0 matriz nula α A α A α ℝ A B A B Podemos definir a distância entre matrizes apesar de parecer um conceito bastante estranho da seguinte maneira dA B A B Com isso a norma de uma matriz é definida usando os conceitos vistos anteriormente para as normas vetoriais sendo que algumas normas matriciais costumam ser mais adotadas do que outras Observe a definição a seguir sobre uma dessas normas Definição 11 Se é uma norma vetorial então A maxx1 A x max1 i n j1n aij é uma norma matricial que se chama norma natural ou induzida Normas induzidas naturais têm diversas vantagens como Seja x 0 e uma norma natural ou induzida pela norma vetorial então Ax A x 1 Raio espectral ρA maxλ em que λ é um autovalor de A Algumas das normas mais utilizadas são I Norma 1 A ₁maxx₁1 A x ₁ max1 j n i1n aij II Norma euclidiana A₂maxx₂1A x₂ρAᵀ A III Norma do máximo ou norma infinita A maxx1 A x max1 i n j1n aij máximo da soma das linhas Com o conhecimento de algumas propriedades das normas de vetores e de matrizes podemos entrar no assunto condicionamento 442 Número de condicionamento Considere o sistema 1 1 1 2 x₁ x₂ 10 5 cuja solução exata é xexato 5 5 Estamos fazendo uma pequena perturbação no sistema quando alteramos os elementos da matriz dos coeficientes ou do vetor independente de maneira muito suave ou seja com uma pequena alteração Para esse sistema vamos perturbar o vetor de termos independentes b 10 5 para b₁ 1001 5 O sistema passa a ser 1 1 1 2 x₁ x₂ 1001 5 cuja solução é x 5007 5003 sendo que x xexato e o résiduo r Ax b é pequeno pois 1 1 1 2 5007 5003 10 5 Agora seja o sistema de equações representado por 1 1 1001 1 x₁ x₂ 10 10005 cuja solução exata também é xexato 5 5 ao perturbarmos o vetor de termos independentes b transformandoo em b₁ 10 101 encontramos 1 1 1001 1 x₁ x₂ 10 101 cuja solução é ẋ 100 90 Se olharmos apenas para o résiduo ou seja para r Ax b temos que 1 1 1001 1 100 90 10 101 b Contudo percebemos que a solução se apresentou muito diferente do que foi encontrado no primeiro sistema Por isso a pergunta que fazemos é Por que uma perturbação de mesma ordem de grandeza interferiu tanto em uma resposta mas não na outra A resposta para esse problema está justamente no condicionamento da matriz ou mais especificamente no número que representa esse condicionamento Vamos supor que x resolve exatamente A x b e ẋ resolve aproximadamente A x b isto é A ẋ b e r é o résiduo r b A ẋ Então x ẋ x condA r b Grafos e árvores 123 5 Grafos e árvores O primeiro teorema desenvolvido na teoria dos grafos é atribuído ao matemático Leonhard Euler Isso ocorreu no ano de 1736 Euler desen volveu um modelo que permitia encontrar um caminho passando pe las sete pontes da cidade de Königsberg antiga Prússia hoje chamada Kaliningrado na atual Rússia Mas não era um caminho qualquer Uma vez que se passasse por determinado trecho para chegar em uma das pontes aquele caminho precisava ser retirado do modelo e assim não era possível passar duas vezes pelo mesmo trecho do caminho Euler trabalhou sobre esse modelo assumindo algumas simplificações das ligações entre as regiões e desenvolveu um teorema que estabelece em que condições é possível percorrer cada trecho linha exatamente uma vez e voltar ao ponto inicial Esse tipo de modelo hoje em dia é usado por empresas como Amazon Uber e Correios que dependem por exemplo de rapidez no transporte de mercadorias Mas não é só o transporte de produtos que se beneficia desses conceitos Facebook Google e outras gigantes da tecnologia tam bém usam a teoria dos grafos para o transporte de informações Vamos ver ao longo do texto a teoria e as aplicações do conceito de grafos e a importância dessa grande área do conhecimento que por si só renderia uma obra inteira Com o estudo deste capítulo você será capaz de conhecer um pouco a história dos grafos suas terminologias e seus tipos vincular o conceito de grafos e árvores aos conceitos de funções aplicar a formulação matricial ou vetorial ao conceito de grafo por meio dos caminhos entre vértices e arestas compreender o conceito de árvore como subgrupo dos grafos identificar alguns algoritmos de busca representados por grafos ou árvores Objetivos de aprendizagem 51 O que é um grafo terminologia e tipos Vídeo A teoria dos grafos que teve início com um modelo desenvolvido por Euler em 1736 é hoje a base de diversas estruturas matemáticas e computacionais como as redes neurais a criação de fluxogramas as redes de comunicação os modelos de fluxo de dados os algoritmos de escalonamento e de pesquisa e ordenação o layout de circuitos e os modelos de máquinas de estado Haham hanukacommonswikiWikimedia Commons Leonhard Paul Euler é um dos grandes nomes da matemática e da física mas acabou exercendo influência em muitas outras áreas inclusive na mú sica Nascido na Basileia Suíça em 1707 passou a maior parte de sua vida na Rússia e na Alemanha e faleceu em São Petersburgo Rússia em 1783 O problema modelado por Euler é conhecido como o problema das sete pontes de Königsberg e con siste em um algoritmo que permite passar pelas sete pontes dessa cidade hoje chamada Kaliningrado na Rússia sem passar pelos caminhos já percorridos Na sequência de figuras a seguir é possível acom panhar o modelo usado nessa construção A Figura 1 mostra um pedaço do Rio Prególia onde ao fundo conseguimos observar uma das pon tes Na época de Euler as duas grandes ilhas localiza das nessa extensão do rio formavam um importante complexo interligado por 7 pontes 124 Matemática para Computação Matemática para Computação Figura 1 Modelo real Gumerov IldarWikimedia Commons Grafos e árvores 125 A Figura 2 foi idealizada para a comemoração dos 600 anos da fa mília real Seu desenho está embasado em uma gravura de Joachim Bering 1613 e data de aproximadamente 1813 Figura 2 Modelo físico MerianErbenWikimedia Commons A imagem original não apresenta as marcações destacadas sobre as pontes e sobre o Rio Prególia Por fim a Figura 3 apresenta o modelo matemático proposto por Euler que permitia a conexão entre as diferentes regiões do complexo formado pelo rio as ilhas e as sete pontes Figura 3 Modelo matemático NuxWikimedia Commons 126 Matemática para Computação Esse modelo foi idealizado em 1736 portanto muitas mudanças ocorreram ao longo dos anos sendo que uma delas foi a derrubada de algumas das pontes A Figura 4 a seguir apresenta a vista por satélite da cidade de Kaliningrado no ano de 2021 Figura 4 Visualização de Kaliningrado por satélite Fonte Google Earth 2021 A teoria dos grafos é bastante extensa e precisaríamos de pelo menos uma obra inteira para discutirmos sobre ela em todos os seus detalhes Mas traremos as características mais importantes quando pensamos em possibilidades de transcrição de grafos e árvores para algoritmos vincu lando esses conceitos às funções aos vetores e às matrizes A estrutura de um grafo está diretamente relacionada às funções e às matrizes De maneira não formal podemos afirmar que um grafo é um par ou um trio de conjuntos Formalmente temos a seguinte definição Definição 1 Um grafo é um objeto matemático ou uma estrutura matemática formado por dois conjuntos O primeiro deles que denotaremos por V é o conjunto de vérti ces O segundo é o conjunto que relaciona os vértices BOAVENTURA NETTO JURKIEWICZ 2017 Grafos e árvores 127 As relações entre vértices são chamadas de arestas Portanto o se gundo conjunto denotado por A é o conjunto de arestas Assim o gra fo é denotado por G V A Por sua vez o conjunto de arestas A que relaciona dois vértices v e w tem elementos denotados por v w sendo que v w V Com isso temos que os elementos do conjunto de arestas são pares ordenados Alguns autores referemse aos vértices como nós Portanto qual quer uma das nomenclaturas pode ser usada de acordo com a aplica ção e a área em que o grafo está inserido Exemρlo 1 Determine os conjuntos de vértices e arestas do grafo representa do na Figura 5 Figura 5 Grafo com quatro nós e cinco arestas Fonte Elaborada pela autora 1 4 2 3 Observando a figura identificamos os quatro vértices nós demar cados com a numeração de 1 a 4 Além disso conseguimos descrever as arestas que interligam alguns desses nós Usando a notação defini da anteriormente escrevemos G V A V 1 2 3 4 A 1 2 1 3 2 3 2 4 3 4 128 Matemática para Computação O número de vértices é representado por n V Logo para o Exemplo 1 temos n 4 Já o número de arestas é representado por a A observe que no grafo da Figura 5 temos a 5 Esse é um exemplo de grafo não orientado não dirigido não di recionado Essa estrutura matemática pode ser vista em muitas si tuações aplicadas Um circuito eletrônico é formado por componentes e placas mas em geral o que desejamos saber é o caminho percorrido pela corrente elétrica que passa por esses componentes Sistemas eletrônicos ou sistemas digitais funcionam por meio da abertura e do fechamento de chaves lógicas portas lógicas sendo que o fechamento permite que a energia passe pelo sistema e a abertura faz com que a energia seja cortada Essas duas variáveis são represen tadas matematicamente por 0 e 1 o que é conhecido como sistema binário ou base binária As portas lógicas são formadas com base em transistores mosfets e resistores e cada uma realizará uma operação lógica diferente tendo também uma simbologia padrão relacionada As Figuras 6 e 7 mostram um pouco dessa simbologia Figura 6 Porta lógica AND Fonte Elaborada pela autora A B X e Figura 7 Porta lógica OR Fonte Elaborada pela autora A B X ou A junção de diferentes portas lógicas está representada na Figura 8 Figura 8 Portas lógicas Fonte Elaborada pela autora A B C X e Y ou Para saber mais sobre circuitos e sistemas eletrônicos indicamos as seguintes leituras Organização estrutura da de computador que esclarece essa teoria com o auxílio de imagens e re sume algumas seções da obra Organização Estrutu rada de Computadores de Andrew S Tanenbaum Disponível em httpwwwdpi inpebrcarlosAcademicos CursosArqCompaula5bn1html Acesso em 24 ago 2021 Na Apostila de teoria para circuitos digitais escrita por Alexandre Santos de la Vega você saberá mais sobre a teoria para circuitos eletrônicos Disponível em httpwww telecomuffbrdelavegapublic CircDigapostilateocdpdf Acesso em 24 ago 2021 Leitura Grafos e árvores 129 Apesar de esse tipo de sistema parecer bastante complexo pode mos simplificálo usando vértices e arestas já que o que desejamos entender é o percurso realizado pela corrente elétrica Figura 9 Circuito eletrônico x grafo Esquema 1 3 Grafo 5 4 2 3 5 4 2 1 Fonte Adaptado de Goldbarg Goldbarg 2012 Quando conhecemos a direção das arestas ou seja o caminho impos to entre um vértice e outro temos um vetor que nos orienta sobre qual é o vértice de partida e qual é o vértice de chegada Nesse caso o grafo formado por esses vértices e essas arestas é chamado de grafo dirigido ou digrafo As Figuras 10 e 11 a seguir mostram exemplos de grafos digrafos Figura 10 Grafo dirigido com quatro nós e cinco arestas Figura 11 Digrafo composto por 20 nós e 20 arestas Fonte Elaborada pela autora 1 4 2 3 alriShutterstock Note que no grafo da Figura 10 temos os mesmos vértices do grafo da Figura 5 porém agora as arestas estão orientadas Dessa maneira escrevemos o conjunto de arestas como A 1 2 2 3 3 2 4 2 3 1 4 3 Podemos associar a cada aresta uma função Nesse caso teremos uma tripla ordenada da forma G V A f em que f é uma função O material Uma introdução sucinta à teoria dos grafos dos professores Feofiloff Kohayakawa e Wakabayashi apresenta de maneira bas tante didática e acessível a estrutura conceitual e alguns exemplos sobre a teoria dos grafos É um material bem completo que pode ser usado como complemento de nosso material Disponível em httpswwwime uspbrpfteoriadosgrafostexto TeoriaDosGrafospdf Acesso em 24 ago 2021 Leitura 130 Matemática para Computação f A P V que associa a cada aresta um subconjunto de dois ou de um elemento de V interpretado como os pontos terminais da aresta Em um grafo ou digrafo com pesos uma função adicional A ℝ associa um valor a cada aresta o que pode ser considerado como seu custo O exemplo a seguir esclarece esses conceitos Exemρlo 2 Considere o grafo representado na Figura 12 a seguir Determine o número e o conjunto de vértices e arestas desse grafo Figura 12 Grafo com custos nas arestas alriShutterstock Note que esse grafo apresenta valores em suas arestas portanto identificamos que esses valores podem ser descritos por uma função custo como definido anteriormente Na sequência apresentamos o conjunto de vértices sendo n o nú mero de elementos desse conjunto e então o número de vértices V A B C D E F n 6 Após essa etapa montamos o conjunto de arestas que leva em consideração o sentido de cada uma delas O valor a 9 representa o número de elementos desse conjunto logo é o número de arestas A A B A D B C B E C E C F D C D E E F Podemos analisar a adjacência entre vértices por meio da conexão entre arestas A definição para esse conceito é apresentada a seguir Existem diversos tipos de grafos completos regulares nulos entre outros Para saber mais sobre esse assunto e poder escolher qual o melhor tipo de grafo para determinada representa ção sugerimos o material Grafos e algoritmos de Filipe Chagas Disponível em httpsmedium comfilipechagasosgrafos eosalgoritmos697c1fd4a416 Acesso em 24 ago 2021 Saiba mais Grafos e árvores 131 Definição 2 Se um vértice v do grafo G é um dos extremos de alguma aresta a desse grafo então a incide em v e viceversa Dois vértices v e w de um grafo G são adjacen tes ou vizinhos se existir uma aresta de G cujos extremos são v e w Observe a Figura 13 para compreender a definição anterior A ares ta a4 incide sobre os vértices v1 e v3 logo v1 e v3 são adjacentes Figura 13 Grafo G Fonte Elaborada pela autora v1 v3 v4 a4 a1 a2 a3 a5 v2 Portanto a estrutura dos grafos é construída com base em modelos matemáticos que transmitirão um resultado aproximado ou exato a problemas físicos 511 Caminhos passeios e trilhas Agora vamos retomar a Figura 13 para tratar do conceito de caminho Ou seja as arestas serão interpretadas como estruturas que determinam caminhos Um caminho do vértice v1 para o vértice v4 no grafo G é uma se quência de vértices v1 v2 v3 v4 de tal modo que v1 v2 v2 v3 v3 v4 são arestas em A O comprimento ou tamanho de um caminho é o número de arestas que ele contém Um caminho simples é um caminho em que todos os vértices são diferentes com a possível exceção do primeiro e do último Um ciclo é um caminho simples em que o primeiro e o último vértices são iguais Um ciclo também pode ser chamado de caminho fechado Um trajeto é um caminho no qual todas as arestas são distintas 132 Matemática para Computação De acordo com Nicoletti e Hruschka Júnior 2018 quando nenhuma aresta aparece mais do que uma vez tendo em um grafo os vértices u e v sendo u o vértice inicial e v o vértice final chamamos de trilha Se u v teremos uma trilha aberta Caso u v obtemos uma trilha fechada ou circuito Ainda por Nicoletti e Hruschka Júnior 2018 p 78 temos que 1 Uma trilha é um passeio no qual nenhuma aresta é repetida 2 Um caminho é um passeio no qual nenhum vértice é repe tido 3 Consequentemente em um caminho nenhuma aresta pode ser repetida o que garante que todo caminho é uma trilha 4 Nem sempre toda trilha é um caminho 5 Por definição todo caminho é um passeio Afirmamos que uma estrutura matemática é um grafo conexo ou interligado se existir pelo menos um caminho entre cada par de vérti ces do grafo Caso contrário o grafo é chamado de desconexo Toda essa estrutura matemática pode ser usada em diversas situa ções aplicadas Por exemplo uma pequena empresa de entrega de re feições pode usar um modelo de grafo para resolver o problema da entrega de refeições quentes em um intervalo de tempo de duas horas e com o menor custo possível para a empresa ou seja minimizando o trajeto para as entregas Esse tipo de modelo que não é dos mais simples mas que pode ser idealizado por meio dos conceitos aprendidos neste capítulo precisa ser resolvido em tempo real É nesse momento que entra a computação científica Assim o grafo precisa ser escrito em um formato em que o computador possa lêlo e operálo Para essa transcrição serão necessários conceitos como funções matrizes e vetores que viabilizarão o cálculo de problemas logísticos como o citado anteriormente 52 Representação computacional de um grafo Vídeo Visualmente os grafos são estruturas bem fáceis de serem com preendidas mas quando precisamos levar essas informações para a área computacional a representação gráfica pode ser um complicador Assim foram desenvolvidas formas de representar os grafos por meio de matrizes e sequências fazendo com que a estrutura do grafo possa ser representada computacionalmente de maneira simples Para conhecer um pouco mais sobre grafos conexos e desconexos e visualizar exemplos desses casos indicamos o material Conceito básico da teoria de grafos Disponível em httpswwwinf ufscbrgrafosdefinicoesdefinicao html Acesso em 24 ago 2021 Saiba mais Grafos e árvores 137 522 Representação por meio de lista de adjacências Uma lista de adjacência em um grafo será composta por todos os vértices nos quais existe uma aresta como conexão Nesse caso essa será a lista de adjacência desse vértice Considere o grafo representado na Figura 18 a seguir Figura 18 Grafo não dirigido de cinco nós e cinco arestas Fonte Elaborada pela autora a4 a1 a2 a3 a5 v1 v3 v4 v2 v5 Teremos as seguintes listas vinculadas aos vértices v1 v2 v3 v4 e v5 respectivamente Adjv1 v2v4 Adjv2 v1v4 Adjv3 v4v5 Adjv4 v1v2v3 Adjv5 v3 Em um grafo dirigido o princípio será o mesmo Assim seja o grafo a seguir Figura 19 montaremos as listas de adjacência refe rentes a cada vértice 138 Matemática para Computação Figura 19 Digrafo de 3 vértices Fonte Elaborada pela autora a1 a2 a3 v2 v1 v3 Esse grafo será representado pelas seguintes listas de adjacência Adjv1 Adjv2 v1 Adjv3 v1 v2 Note que as listas de adjacência de cada vértice respeitam o sen tido da aresta Portanto é possível escolher por representações computacionais distintas Essa escolha levará em consideração características especí ficas da aplicação seleção da linguagem de programação necessidade de representação visual dentre outras características 53 Conceito de árvore Vídeo Talvez o exemplo mais simples que nos permita entender o conceito de árvore seja a árvore genealógica Figura 20 Ivan Alex BurchakShutterstock Figura 20 Árvore genealógica Grafos e árvores 139 Isso mesmo a árvore genealógica que estudamos desde a educação infantil a qual construímos diversas vezes em sala de aula e permite entendermos nossa ancestralidade é um grafo com características dis tintas que possibilita que a nomeemos de árvore Matematicamente uma árvore é um grafo conexo sem ciclos Com o desenvolvimento da teoria dos grafos muitas áreas benefi ciaramse de suas definições para que pudessem ser estruturadas e melhor explicadas conceitualmente Gustav Robert Kirchhoff nascido em Königsberg 18241877 exa tamente onde toda a teoria dos grafos começou utilizoua para de senvolver e validar seu trabalho com circuitos elétricos tendo como particular conceito nessa construção as árvores Esses resultados serviram de incentivo para que outros pesquisa dores e cientistas das mais diversas áreas utilizassem esses conceitos em seus trabalhos Como vimos uma lista encadeada é uma estrutura de dados linear Nela os elementos do conjunto são associados por relações de poste rior ou anterior na intenção de criar uma espécie de fileira imaginária As árvores são estruturas de dados não lineares nas quais os ele mentos costumam ser associados por relações de esquerdo direito inferior superior pai filho menor maior etc Essas estrutu ras formam grafos conexos e acíclicos Quando representados gra AaarglcommonswikiWikimedia Commons Gustav Robert Kirchhoff Figura 21 Tipos de árvores de decisão Zern LiewShutterstock O material de aula do professor José Augusto Baranauskas do depar tamento de ciência da computação e matemática da Universidade de São Paulo apresenta conceitos exercícios e aplicações computacionais sobre gra fos e árvores Os exemplos são bastante didáticos e os exercícios auxiliam na melhor compreensão do tema estudado Disponível em httpdcmffclrp uspbraugustoteachingaedii AEDIIGrafospdf Acesso em 24 ago 2021 Saiba mais ficamente formam diagramas que remetem à estrutura física de uma árvore da natureza com galhos ramificados De acordo com Almeida 2018 p 19 como nem todo grafo é uma árvore podemos afirmar que um grafo será uma árvore se e somente se existir um único ca minho entre dois vértices quais quer deste grafo Todo grafo conexo tem ao menos uma árvo re composta de todos seus vérti ces e algumas de suas arestas 140 Matemática para Computação Vamos entender esse princípio considere o grafo apresentado na Figura 22 Figura 22 Conceito de árvore geradora Fonte Elaborada pela autora a1 a4 a5 a6 a2 a3 v2 v5 v6 v4 v1 v3 Observe que se retirarmos a aresta a3 ainda assim todos os vértices estarão interligados Com isso se os vértices são por exemplo pontos de entregas de produtos e queremos analisar qual o caminho mínimo para passarmos por todos esses pontos precisaremos que eles este jam conectados mas não necessariamente usaremos todas as arestas como vias de acesso aos pontos de entrega Nesse momento entramos em um conceito chamado caminho míni mo que explicaremos melhor na sequência Mas independentemente de sabermos qual seria o trajeto mais curto precisamos encontrar todas as árvores possíveis presentes nesse grafo ou seja todas as formas de chegarmos a todos os vértices sem que exista dualidade entre os caminhos Esse tipo de problema é conhecido como problema de roteamento As três figuras a seguir apresentam as árvores geradoras para o gra fo apresentado na Figura 22 observe Figura 23 Primeiro exemplo de árvore geradora Fonte Elaborada pela autora a1 a4 a5 a6 a2 v2 v5 v6 v4 v1 v3 Grafos e árvores 141 Figura 24 Segundo exemplo de árvore geradora Fonte Elaborada pela autora a4 a5 a6 a2 a3 v2 v6 v4 v1 v5 v3 Figura 25 Terceiro exemplo de árvore geradora Fonte Elaborada pela autora a5 a1 a6 a2 a3 v2 v6 v4 v1 v5 v3 Em qualquer uma das três árvores temos todos os pontos de entrega interconectados Com isso podemos começar a pensar em qual dessas três árvores geradoras temos um conjunto de rotas que minimiza a dis tância para as entregas ou seja qual é a árvore geradora mínima Note que nesse caso é necessário conhecermos o valor das arestas ou a função aplicada em cada um desses caminhos que pode levar em consideração a distância o custo do combustível o tipo de meio de locomoção usado etc Portanto para esse fim precisamos de um grafo com pesos Observe a definição a seguir Definição 3 Uma árvore geradora mínima para um grafo com pesos é uma árvore geradora que tem o menor peso total possível dentre todas as possíveis árvores gerado ras do grafo 142 Matemática para Computação Note que dependendo da quantidade de vértices e arestas de um grafo o número de árvores geradoras pode ser enorme Por exemplo o grafo de Petersen que pode ser analisado na Figura 26 a seguir tem 2000 árvores geradoras Figura 26 Grafo de Petersen LeshabirukovWikimedia Commons Existem alguns algoritmos conhecidos para se obter uma árvore geradora mínima Desses o algoritmo de Kruskal 1956 e algoritmo de Prim 1957 talvez sejam os mais populares Ambos são chamados de algoritmos gulosos pois fazem escolhas levando em consideração a melhor solução imediata mais próxima Com os algoritmos de busca aplicados aos grafos e particularmen te às árvores notamos um campo imenso de aplicações possíveis que vai muito além dos denominados problemas de roteamento Na sequência vamos ver mais alguns conceitos importantes sobre árvores que podem ser aplicados a procedimentos de busca 54 Raízes e árvores binárias Vídeo Como foi mencionado nas seções anteriores uma árvore é um gra fo conexo e acíclico Na formação de uma árvore podemos destacar al guns pontos importantes sendo um deles o conceito de raiz da árvore Uma árvore que apresenta um vértice distinto facilmente distinguí vel é chamada árvore enraizada Figura 27 Esse vértice é considerado o vértice raiz Nesse caso afirmamos que os vértices têm hierarquia Assista aos vídeos Algo ritmo de Kruskal Árvore Geradora Mínima e Algo ritmo de Prim Teoria dos Grafos Exemplo Prático Disponível em httpswwwyoutube comwatchv3Q6RdxGmDgQ Acesso em 24 ago 2021 Disponível em httpswww youtubecomwatchvPgf AL1vYb4 Acesso em 24 ago 2021 Vídeo Os algoritmos de Kruskal e de Prim podem ser encontrados em diversas obras específicas sobre grafos Sugerimos a obra Grafos introdução e práti ca de Boaventura Netto e Jurkiewicz p 86 Kruskal e p 87 Prim BOAVENTURA NETTO P O JURKIEWICZ S 2 ed São Paulo Blücher 2017 Saiba mais Grafos e árvores 143 Podemos montar uma árvore genealógica como uma árvore enrai zada Para isso escolhemos um dos membros para o primeiro casal e partimos dali para seus filhos e assim sucessivamente Figura 27 Árvore enraizada tovovanShutterstock É visível a identificação da raiz de uma árvore e sua localização é mui tas vezes considerada o ponto de partida para algoritmos de busca para esse tipo de árvore Uma árvore não enraizada é uma árvore dita livre Nicoletti e Hruschka Júnior 2018 p 184 trazem a seguinte definição para árvore binária é um grafo vazio ou tem um vértice especial r chama do raiz e os demais vértices da árvore são subdivididos em dois subcon juntos disjuntos as subárvores esquerda e direita de r as quais são também árvores binárias A Figura 28 exemplifica tipos dessas árvores Figura 28 Tipos de árvores binárias ShadeDesignShutterstock Árvore equilibrada ou árvore binária cheia Árvore em profundidade Árvore em largura Grafos e árvores 147 551 Algoritmos de caminho mínimo A teoria dos grafos é largamente utilizada em problemas de rotea mento sendo nesses casos usados os chamados algoritmos de busca Dentre os algoritmos mais conhecidos encontramse o algoritmo do vizinho mais próximo o algoritmo de Dijkstra o algoritmo de Floyd etc O algoritmo de Dijkstra tem como conceito base a construção de uma matriz de distâncias a qual terá seus elementos sendo a menor distância entre dois vértices O cientista da computação holandês Edsger Wybe Dijkstra nasceu em Roterdã 1930 e faleceu em Nuenen Ele fez diversas contribuições nas áreas de desenvolvimento de algoritmos sistemas operacionais e processamento distribuído Em 1972 recebeu o prêmio Turing por suas contribuições no desenvolvimento de linguagens de programação O conjunto S que será construído com base no algoritmo Dijkstra é composto por vértices cujos caminhos mais curtos até um vértice origem já são conhecidos Esse conjunto produz uma árvore de caminhos mais curtos de um vértice origem s para todos os vértices que são alcançáveis a partir de s Não vamos nos aprofundar na estrutura desses algoritmos pois como comentamos no início do capítulo a teoria dos grafos é bastante extensa riquíssima e existem obras específicas sobre o tema Mas caso tenha curiosidade para conhecer e até implementar esses algoritmos sugerimos alguns materiais O Problema do Caixeiroviajante PCV é do tipo caminho mínimo Seu algoritmo é estruturado para que seja possível visitar em ordem sequencial um conjunto de pontos dispersos de um grafo ou seja sair de um vértice inicial visitar todos os outros e voltar para a origem inicial sem repetir nenhum vértice Podemos indicar muitas aplicações que usam o PCV Dentre elas escolhemos o artigo publicado pela Associação Brasileira de Engenharia de Produção ABREPO intitulado Teoria dos grafos aplicada à roteirização na logística de distribuição o problema do caixeiro viajante em uma empresa fabricante de farinha de trigo Acesso em 24 ago 2021 httpwwwabeproorgbrbibliotecaTNSTO291164439148pdf Artigo Assim vimos a estrutura de um grafo e suas ramificações Conhe cemos as terminologias do tema alguns tipos de grafos e formas de representação computacional que nos deram uma base importante e que conecta a matemática e a computação de maneira aplicada Assista aos dois vídeos sobre os algoritmos de Floyd e Dijkstra Algoritmo de Floyd e Algoritmo de Dijkstra Escolha uma linguagem de progra mação de seu domínio e reflita sobre as possibili dades de implementação computacional de um ou mais algoritmos de busca nessa linguagem Disponível em httpsyoutubeDfga Bkp02HY Acesso em 24 ago 2021 Disponível em httpsyoutubevzW VCqYDlAs Acesso em 24 ago 2021 Vídeo Hamilton RichardsWikimedia Commons Edsger Wybe Dijkstra 148 Matemática para Computação CONSIDERAÇÕES FINAIS Fechamos o capítulo destinado à teoria dos grafos e árvores e espera mos que após esta introdução você esteja curioso para aprender ainda mais sobre esse tema tão rico e aplicável em nosso cotidiano e em outras áreas do conhecimento Podemos até afirmar que as relações sociais por meios digitais não existiriam sem a teoria dos grafos e que nossa comida chegaria gelada caso o entregador de pizza não otimizasse sua rota de entrega Percebemos que muito dessa teoria é aplicada mesmo sem notarmos sua existência ou importância Mas agora que você conhece um pouco so bre ela poderá enxergar a matemática por trás de tarefas simples e com plexas por exemplo as conexões neurais realizadas pelo nosso cérebro Sim elas também podem ser representadas por grafos Indicamos que acesse os materiais sugeridos como complementação do conteúdo Acreditamos que o tripé teoria prática e aplicação é ne cessário para a boa compreensão de qualquer conceito ATIVIDADES Construa uma matriz de adjacência e uma matriz de incidência para o grafo apresentado a seguir e descreva as diferenças entre os dois resul tados Note que a1 v4 v1 a2 v5 v2 a3 v1 v3 a4 v2 v4 e a5 v3 v5 v1 v5 a1 a2 a3 a5 a4 v2 v4 v3 Atividade 1 Grafos e árvores 149 Seja o grafo exposto na figura a seguir v1 v6 v5 v2 v4 v3 Apresente uma árvore geradora para esse grafo usando o conceito de extração de arestas Atividade 2 Usando as árvores binárias desenvolva um grafo para representar a quantidade de jogos necessários em um torneio de vôlei com 16 inscritos Atividade 3 REFERÊNCIAS ALMEIDA L de A e Árvores algoritmos e aplicações 2018 Dissertação Mestrado em Matemática Instituto de Matemática Pura e Aplicada Rio de Janeiro Disponível em httpsimpabrwpcontentuploads201803TCC2018LauroeAlmeidapdf Acesso em 23 ago 2021 BOAVENTURA NETTO P O JURKIEWICZ S Grafos Introdução e prática São Paulo Blücher 2017 FLOYD T L Sistemas digitais fundamentos e aplicações Porto Alegre Bookman 2007 GOLDBARG M GOLDBARG E Grafos conceitos algoritmos e aplicações Rio de Janeiro Elsevier 2012 GOOGLE EARTH 2021 Disponível em httpsearthgooglecomwebsearchKalinin gradOblastdeKaliningradoRc3bassia546947304205645671341195937 9a69915150592d35y0h0t0rdataCpcBGm0SZwolMHg0NmUzM2Q4ZDRiN2MyM WE5OjB4NTA1MDk2MDAxNjEyNmVkMxmFG5VA71pLQCGx6pSxHM0QCosS2FsaW5pb mdyYWQsIE9ibGFzdCBkZSBLYWxpbmluZ3JhZG8sIFLDunNzaWEYASABIiYKJAm582YmF0Q 3wBHfSj8FUg3wBnqs6zuJxHwCGsWQUE7aBHwA Acesso em 23 ago 2021 NICOLETTI M C HRUSCHKA JÚNIOR E R Fundamentos da teoria dos grafos para computação Rio de Janeiro LTC 2018 Resolução das atividades 151 3 Uma pesquisa foi realizada coletando dados referentes à altura de alunos de uma sala de aula Esse tipo de dado é qualitativo ou quantitativo Justifique A altura coletada de um grupo de pessoas é um dado quantitativo Esse tipo de dado pode ser classificado por meio de relações numéricas de intervalos de classe por se tratar de um dado numérico que não pode ser representado por um número inteiro havendo a necessidade de ser representado por um decimal que pode assumir qualquer valor após a vírgula por exemplo 1521 cm É também chamado de dado quantitativo contínuo 2 Noções sobre sistemas de numeração 1 Podemos considerar o sistema de numeração romano um sistema aditivo ou um sistema posicional Explique O sistema de numeração romano usado em algumas representações até hoje como em relógios e para marcar itens é um sistema aditivo e podemos perceber essa dinâmica por exemplo quando precisamos escrever números como 20 XX e 30 XXX conforme é apresentado na figura a seguir imagestockdesignShutterstock Números Romanos Ele é um típico sistema de numeração aditivo mas que teve alguns avanços quando comparado a sistemas desse tipo que não permitiam a escrita rápida de números muito grandes 2 É possível converter um número na base 10 para a base hexadecimal por meio de divisões sucessivas Explique essa conversão e converta o número 910 para essa base Resolução das atividades 153 A figura a seguir é um exemplo das possíveis movimentações que um cavalo na casa 4D pode fazer 8 7 6 5 4 3 2 1 H G F E D C B A Explique usando a notação linhacoluna as possíveis movimentações do cavalo branco que está na casa 1G observação ele não pode ficar sobre outra peça branca Sabendo das possíveis movimentações do cavalo e assumindo que o cavalo branco que precisa ser movimentado está na posição 1G conforme a figura temos que este poderia se mover para as casas 3F ou 3H VapartShutterstock 156 Matemática para Computação 3 Explique com suas palavras o que significa a análise de convergência de um método e qual é a sua importância para garantir o resultado encontrado Basicamente a análise de convergência é o que nos permite decidir se o método leva a uma solução que se aproxima da solução exata ou não Os métodos ditos numéricos em geral são descritos por processos iterativos que por sua vez só são válidos se a solução aproximada convergir para a solução exata Quando analisamos a ordem de convergência e taxa de convergência já estamos considerando que o método converge primeira análise a ser verificada A ordem de convergência e taxa de convergência nos mostrarão como essa solução aproximada converge para a solução real e em qual velocidade 5 Grafos e árvores 1 Construa uma matriz de adjacência e uma matriz de incidência para o grafo apresentado a seguir e descreva as diferenças entre os dois resultados Note que a1 v4 v1 a2 v5 v2 a3 v1 v3 a4 v2 v4 e a5 v3 v5 v1 v5 a1 a2 a3 a5 a4 v2 v4 v3 158 Matemática para Computação 2 Seja o grafo exposto na figura a seguir v1 v6 v5 v2 v4 v3 Apresente uma árvore geradora para esse grafo usando o conceito de extração de arestas Podemos descrever algumas árvores geradoras mas escolhemos a seguinte v5 v1 v6 v2 v3 v4 Note que todos os vértices são acessados por alguma aresta e temos uma árvore geradora mínima 3 Usando as árvores binárias desenvolva um grafo para representar a quantidade de jogos necessários em um torneio de vôlei com 16 inscritos A árvore binária nesse caso pode ser dita invertida pois assumiremos que os vértices pendentes são os 16 times inscritos e os vértices internos mais a raiz os jogos Portanto podemos representála como a figura a seguir Resolução das atividades 159 v1 v3 v5 v7 v9 v11 v13 v15 v2 v4 v6 v8 v10 v12 v14 v16 v17 v18 v19 v20 v21 v22 v23 v24 v25 v26 v27 v28 v29 v30 v31 Então teremos 16 vértices pendentes 8 vértices internos na primeira camada 4 vértices internos na segunda camada e 2 vértices internos na terceira camada O jogo final é a raiz Esse cálculo nos permite escrever que ao todo temos 31n vértices e 30n 1 arestas MARINA VARGAS MARINA VARGAS MATEMÁTICA PARA COMPUTAÇÃO M AT E M ÁT I C A COMPUTAÇÃO PARA Código Logístico I000122 Fundação Biblioteca Nacional ISBN 9786558210719 9 7 8 6 5 5 8 2 1 0 7 1 9