Um livro texto para Álgebra Aplicada à Computação

Prévia do material em texto

Um livro texto para Álgebra Aplicada à Computação 
 
Jaime Evaristo 
Departamento de Tecnologia da Informação 
Universidade Federal de Alagoas 
jaime@ccen.ufal.br 
 
 
Resumo 
 
 O ensino de matemática discreta (ou álgebra abstrata) para os cursos da área de 
computação e informática é recomendado por todas as versões do Currículo de Referência da 
Sociedade Brasileira de Computação e fortemente sugerido pelas Diretrizes Curriculares para 
os Cursos da Área de Computação e Informática, da Comissão de Especialistas de Ensino de 
Computação e Informática-CCEInf. O artigo a seguir apresenta o livro de nossa autoria 
Introdução à Álgebra (com aplicações à Ciência da Computação), livro texto para uma 
disciplina que contemple a recomendação do Currículo de Referência e das Diretrizes 
Curriculares a respeito da matemática discreta. 
 
 
Abstract 
 
 The teaching of discrete mathematics (or abstract algebra) for the courses of the 
computing and informatic area is recommended by all the versions of the Reference’s 
Curriculum of the Brazilian Computer Society and strongly suggested by the Curriculum’s 
Guidelines for the Computing and Informatic Courses of the Specialist Teaching Comission on 
Computing and Informatics-CCEInf. The following article presents the book, written by us: 
Introdução à Álgebra (com aplicações à Ciência da Computação), class book for a discipline 
that observes the recommendation of the Reference’s Curriculum and of the Curriculum’s 
Guidelines regarding the discrete mathematics. 
 
Palavras-chave: matemática discreta, álgebra abstrata, aplicações à Ciência da Computação, 
números inteiros. 
 
 
 1. Introdução 
 Segundo as Diretrizes Curriculares para os Cursos da Área de Computação e 
Informática apresentadas pela Comissão de Especialistas de Ensino de Computação e 
Informática-CCEInf ao Conselho Nacional de Educação, “... a matemática, para a área de 
computação, deve ser vista como uma ferramenta a ser usada na definição formal de conceitos 
computacionais (linguagens, autômatos, métodos etc.). Os modelos formais permitem definir 
suas propriedades e dimensionar suas instâncias, dadas suas condições de contorno. 
Considerando que a maioria dos conceitos computacionais pertencem ao domínio do discreto, 
a matemática discreta (ou também chamada álgebra abstrata) é fortemente empregada”. 
 No nosso entendimento, a necessidade de que um curso de graduação contemple o 
estudo da álgebra abstrata não se restringe apenas ao fato de que “a maioria dos conceitos 
computacionais pertencem ao domínio do discreto” e sim, sobretudo, pelo fato de que o 
desenvolvimento desta parte da matemática contempla o exercício da linguagem matemática 
que é, sem sombra de dúvidas, a linguagem mais apropriada para a ciência, em particular a 
Ciência da Computação. Ou seja, ao se estudar álgebra abstrata aprende-se a ler matemática 
(e, portanto, aprende-se a ler ciência); aprende-se a escrever matemática (e, portanto, 
aprende-se a escrever ciência). Além disto, o estudo da álgebra abstrata permite o 
desenvolvimento de várias técnicas de demonstrações de fatos científicos, técnicas estas que 
são utilizadas fortemente nas disciplinas que estudam os aspectos formais da Ciência da 
Computação. Além disto, ainda, o estudo da álgebra abstrata propicia, de forma bastante 
natural, que se apresentem formas de estabelecimento de novas teorias científicas, o que, sem 
nenhuma dúvida, irá facilitar os egressos dos cursos da área de Computação e Informática que 
ingressarem no campo da pesquisa. 
 2. A ementa 
 O Currículo de Referência 99 (CR99), aprovado no Congresso da Sociedade Brasileira 
de Computação realizado na Cidade do Rio de Janeiro em 1999, sugere a seguinte ementa para 
a disciplina Álgebra Abstrata, como parte da matéria Matemática. 
 
Conjuntos. Funções. Relações sobre conjuntos: relações de equivalência 
e de ordem. Indução matemática. Recursão. Sistemas algébricos. Lógica 
e circuitos lógicos: linguagens simbólicas, tabelas-verdade, equivalência 
lógica, funções booleanas, diagramas de Karnaugh. Reticulados. 
Monóides. Grupos. Anéis. Teoria dos códigos: canal binário simétrico, 
código de blocos, matrizes geradoras e checadoras, códigos de grupo, 
códigos de Hamming. Teoria dos domínios: ordens parciais completas, 
continuidade, ponto fixo, domínios, espaço das funções. 
 No nosso entendimento, e enfatizando o que foi dito na seção anterior, uma primeira 
disciplina para o estudo da matemática discreta para alunos da área de computação e 
informática deveria contemplar o mínimo de conceitos algébricos para que a maior parte do 
seu desenvolvimento seja destinado: 
· à ênfase da necessidade da conceituação formal dos elementos básicos de 
uma ciência e de que todo conceito formal só pode conter elementos 
conceituados anteriormente; 
· à ênfase da necessidade de que as assertivas científicas sejam devidamente 
provadas (ou fixadas axiomaticamente); 
· ao estudo de técnicas de demonstração; 
· à leitura de textos matemáticos; 
· ao estudo de técnicas de resolução de problemas com a possibilidade 
consequente do desenvolvimento de raciocínios abstratos; 
· ao realce de aspectos históricos da ciência; 
· às aplicações dos conceitos matemáticos à Ciência da Computação. 
 Nesta perspectiva, propomos uma primeira disciplina (sessenta horas, no máximo no 
terceiro semestre do curso) que contemple apenas cinco entes algébricos: conjuntos, relações 
binárias, funções, anéis (restrito aos anéis dos inteiros e aos anéis inteiros módulo n) e 
corpos (restrito ao corpo de frações de um domínio de integridade, em particular o corpo dos 
números racionais). Conjuntos pelo fato de que sua linguagem é a base da linguagem da 
álgebra, além do que permite o estabelecimento da necessidade de fixação de entes e conceitos 
primitivos de uma ciência; relações binárias para que se possa, entre outras coisas, se definir 
os inteiros módulo n e o corpo de frações de um domínio de integridade; funções para que se 
possa, por exemplo estabelecer igualdade entre estruturas algébricas; anéis para que se possa 
construir axiomaticamente o anel dos inteiros, apresentando o método da construção 
axiomática de uma teoria científica e, a partir do anel dos inteiros, se estude teoria dos 
números, discutindo divisibilidade, máximo divisor comum, números primos, etc., conceitos 
que permitem aplicações importantes para a Ciência da Computação; e corpos para que se 
apresente os números racionais a partir de definições, em contraposição à apresentação dos 
números inteiros que seria feita de forma axiomática. 
 Em relação aos outros importantes conceitos algébricos listados na ementa proposta 
pelo CR99, propomos que eles sejam apresentados quando da necessidade de sua aplicação 
(por exemplo, reticulados em computação gráfica). Tendo nos semestres iniciais visto a 
necessidade de conceituasses formais e apreendido diversas definições abstratas, o aluno, 
diante da aplicação imediata, terá mais condições de absorver os novos conceitos. 
 3. O livro 
 Focando os pontos discutidos acima, o livro Introdução à Álgebra (com aplicações à 
Ciência da Computação) contém nove capítulos. O primeiro deles trata de Conjunto e 
Funções que trás a preocupação de que nada seja utilizado sem que houvesse sido definido ou 
concebido como conceito primitivo anteriormente. Por exemplo, função é definida antes que 
sejam definidas as operações com conjuntos (isto para que se possa definir operações em 
conjuntos); para que se possa definir operações com conjuntos, definem-se antes funções 
boleanas (aqui chamadas predicados) e operações lógicas; o conjunto vazio só é definido 
após a definição de contradição em um conjunto. Neste sentido, o capítulo contém as 
seguintes seções: 1.1 Conceitos e entes primitivos; 1.2 Subconjuntos; 1.3 Uma representação 
de conjuntos;1.4 Igualdade de conjuntos; 1.5 Par ordenado e produto cartesiano de dois 
conjuntos; 1.6 Relações Binárias; 1.7 Funções; 1.8 Outra representação de conjuntos; 1.9 
Operações em conjuntos; 1.11 Operações com conjuntos; 1.12 Uma operação com funções; 
1.13 Funções inversas; 1.14 Conjuntos finitos; 1.15 Exercícios. 
 O capítulo 2 trata da construção axiomática dos números inteiros. Na verdade, houve 
uma grande dúvida na concepção do livro entre tratar os inteiros como conhecidos ou 
construí-los axiomaticamente, definindo-o como o "único" domínio bem ordenado. Optamos 
pela segunda possibilidade para que o aluno seja defrontado com uma forma de se conceber 
uma teoria científica (no caso uma teoria axiomática) e para que o aluno seja devidamente 
instruído sobre a necessidade de que os entes científicos sejam formalmente concebidos. Com 
este objetivo o capítulo estuda basicamente os anéis e, para tal, contém as seguintes seções: 
2.1 Teoria axiomática; 2.2 Anéis; 2.3 Elementos inversíveis; 2.4 Anéis isomorfos; 2.5 Domínio 
de integridade; 2.6 Anéis ordenados; 2.7 Domínio bem ordenado; 2.8 Exercício. 
 O capítulo 3 apresenta algumas propriedades básicas dos inteiros (por exemplo, não 
existe inteiro entre 0 e 1) e o Princípio da Indução Matemática, importante método para 
demonstrações de assertivas envolvendo os inteiros. O capítulo contém as seguintes seções: 
3.1 Duas propriedades básicas; 3.2 Valor absoluto; 3.3 Indução matemática; 3.4 Múltiplos de 
um elemento de um anel; 3.5 Exercícios. 
 Para que sejam utilizados em demonstrações dos capítulos seguintes (inclusive em 
aplicações da álgebra à Ciência da Computação) e considerando que o livro se destina também 
a alunos de outras áreas do conhecimento (Matemática, principalmente), o capítulo 4 
apresenta, informalmente, algoritmos e estabelece uma linguagem algorítmica básica (seis 
comandos apenas) que permitem (nos capítulos seguintes) o desenvolvimento de algoritmos 
que demonstram a existência de inteiros que verificam alguma propriedade. 
 O capítulo 5 trata da representação dos números inteiros. Nele é discutida a divisão 
euclidiana e, a partir dela, se mostra que os inteiros podem ser representados a partir de um 
número finito deles. São os sistemas de numeração. Apresenta, também, a representação 
interna dos nos computadores e discute as razões pelas quais existe uma diferença de 32 entre 
os códigos ASCII de uma letra maiúscula e da sua minúscula correspondente; pelas quais o 
código ASCII de A é 65 (e não 1, ou 10, ou 20). Apresenta, ainda, utilizando a representação 
do inteiro no sistema binário, um algoritmo para o cálculo de potências mais rápido do que 
aquele obtido diretamente da definição de potência. Para atingir estes objetivos, o capítulo 
contém as seções 5.1 Divisão euclidiana; 5.2 Sistemas de numeração; 5.3 Representação em 
computadores; 5.4 Potências Parte II; 5.5 Exercícios. 
 O Teorema Fundamental da Aritmética é o objeto de estudo do capítulo 6. Para tal é 
discutido o conceito de máximo divisor comum e apresentado, com as devidas justificativas, o 
algoritmo de Euclides. É discutido, também, o importante conceito de número primo e são 
apresentados alguns algoritmos (entre eles o Crivo de Eratóstenes) para obtenção de números 
deste tipo. Apresenta, ainda, a ineficiência dos algoritmos para fatoração de inteiros e alguns 
aspectos históricos sobre a busca de uma fórmula para obtenção de números primos. Isto, e 
algumas coisas mais, é obtido através das seções 6.1 Máximo divisor comum; 6.2 Números 
primos; 6.3 Divisor primo de um inteiro; 6.4 Números primos - Parte II; 6.5 Fatoração única; 
6.6 Números primos - Parte III; 6.7 Exercícios. 
 O capítulo 7 discute a aritmética modular. É discutido então a relação de equivalência 
congruência módulo n, cujas classes de equivalência geram o anel dos inteiros módulo n, o 
que permite a apresentação de anéis diferentes, intrinsecamente, do anel dos inteiros. Como 
aplicação da congruência módulo n, o capítulo apresenta formalmente fatos matemáticos que 
nos são ensinados (sem nenhuma justificativa) nas séries iniciais do ensino fundamental como 
critérios de divisibilidade e a famosa “prova dos nove". O capítulo contém ainda um estudo 
das congruências lineares que permite a obtenção de inversos de elementos de anéis Zn, uma 
apresentação da função F de Euler e, como não podia deixar de conter, uma apresentação 
breve dos aspectos históricos envolvendo o Último Teorema de Fermat. As seções deste 
capítulo são: 7.1 Congruências; 7.2 Aplicações: critérios de divisibilidade; 7.3 Aplicação: 
prova dos nove; 7.4 Potências módulo n; 7.5 Os anéis Zn; 7.6 Congruências lineares; 7.7 A 
função F de Euler; 7.8 O Último Teorema de Fermat; 7.9 Exercícios. 
 O capítulo que segue apresenta uma maravilhosa aplicação da álgebra abstrata à 
Ciência da Computação: o método de criptografia RSA. Aí todas as etapas para aplicação 
deste método (codificação, decodificação, assinaturas eletrônicas) são apresentadas e 
algebricamente justificadas pela aplicação de teoremas e conceitos discutidos nos capítulos 
anteriores. 
 Finalmente, o capítulo 9 trata de corpos, em particular do corpo dos números 
racionais. São apresentados números que não são racionais e alguns fatos a respeito do 
quociente e do resto da divisão euclidiana de dois inteiros. Além disto, para estimar a 
eficiência do algoritmo de Euclides (mantendo a máxima de que nada que não foi definido 
antes pode ser utilizado) é apresentado uma "pesquisa" em matemática, onde "novas" funções 
são definidas, com "novos" conceitos sendo estabelecidos. Isto tudo é discutido nas seções 9.1 
Introdução; 9.2 O corpo de frações de um domínio de integridade; 9.3 Os números racionais; 
9.4 "Números" não racionais; 9.5 Divisão euclidiana - Parte II; 9.6 O algoritmo de Euclides - 
Parte II; 9.7 Exercícios. 
 
4. Exercícios e Manual de Soluções 
 Para que o aluno possa sedimentar os conceitos apresentados, exercitar técnicas de 
demonstração e aprender a escrever matemática, o livro contém (sem a contabilização de 
itens) 126 exercícios, a maioria do tipo "mostre que". As soluções dos exercícios estão 
reunidas num exemplar denominado Manual de Soluções, disponível via mensagem eletrônica 
encaminhada ao autor (jaime@ccen.ufal.br). 
 
 5. Considerações finais 
 Naturalmente, um novo livro não pode ser simplesmente mais um livro. Um novo livro 
deve ter uma identidade própria que o diferencie dos demais livros existentes. Neste sentido, 
entendemos que o livro aqui apresentado se diferencia dos livros existentes nos seguintes 
pontos: 1. Ordenação própria na apresentação dos tópicos normalmente estudados em 
Conjuntos e Funções, com o objetivo de que nenhum conceito não fixado anteriormente seja 
utilizado; 2. Maior detalhamento das demonstrações das proposições matemática, com o 
objetivo de que o leitor aprenda a ler matemática e desenvolva técnicas de demonstração de 
fatos científicos; 3. Justificativas de fatos introdutórios interessantes da Ciência da 
Computação, geralmente, não discutidos pela literatura desta Ciência; 4. Apresentação de uma 
aplicação prática toda baseada em fatos fundamentais da matemática; 5. Apresentação dos 
resultados de uma “pesquisa” (aspas devido ao nível de profundidade) matemática, com 
estabelecimento de novos conceitos e de proposições decorrentes destes novo conceitos; 
6. Disponibilização das soluções de todos os exercícios propostos. 
 As idéias postas no livro vêm sendo aplicadas acerca de três anos, estando o mesmo 
sendo utilizado no corrente semestre com alunos do terceiro semestre do Curso de Ciência da 
Computação da Universidade Federal de Alagoas com resultados, em relação aos seus 
objetivos, bastante satisfatórios, melhores do que os resultados obtidos quando as idéias eram 
aplicadas baseadas em outros livros textos. 
Bibliografia 
Evaristo, J, Introduçãoà Informática (com aplicações à Ciência da Computação). EDUFAL, 
 Maceió, 1999. 
Currículo de Referência da SBC para os Cursos de Graduação em Computação, versão 1999, 
 www.sbc.org.br/educação. 
Diretrizes Curriculares de Cursos da Área de Computação e Informática, 
 http://www.mec.gov.br/nivemod/educsupe/diretriz.shtm#diretrizes