Sistemas Operacional 5 (Gabriel)

Prefácio

A matemática discreta continua sendo um elemento importante no ensino da Ciência da Computação. Desejamos

oferecer aos estudantes os instrumentos para que desenvolvam um vocabulário preciso, recursos para notação,

abstrações úteis e raciocínio formal — e queremos fazê-lo logo, desde o início de sua formação. Explicações

claras e exatas são mais importantes do que nunca. Portanto, foi mantido o estilo simples que caracterizou

as versões anteriores. Em termos de conteúdo, as "mudanças mínimas" previstas para esta terceira edição

acabaram evoluindo para o que resultou nesta revisão maior. Assim, a primeira metade da segunda edição

foi bastante ampliada, enquanto na segunda metade houve uma boa redução. A ampliação da primeira metade

do livro se dá de duas maneiras: pela introdução de novos tópicos e por um maior detalhamento na apresentação

dos tópicos já existentes, como por exemplo os referentes à lógica formal. Mesmo o estudante sem base

em cálculo vai achar o material acessível, especialmente com a ajuda dos exercícios práticos e os inúmeros

exemplos e exercícios novos. Por outro lado, a fim de manter o livro compatível com um curso de um semestre,

alguma coisa tinha que ser eliminada. Atualmente, a maioria dos alunos de graduação tem acesso, através

de cursos de teoria de computação, à maior parte do material que figurava no trecho final da segunda edição;

de modo que, por enquanto, uma introdução é o suficiente.

As mudanças com relação à segunda edição são mostradas a seguir com mais detalhes.

Capítulo 1: A Seção 1.1 da edição anterior, sobre sentenças e quantificadores, foi desmembrada em duas seções,

1.1 e 1.2. Incluímos exemplos de uso de tautologias para simplificar expressões condicionais de programas.

Fizemos uma nova introdução aos predicados e quantificadores e uma caracterização mais formal do que

são "wff" e "sentenças". Da mesma forma, a antiga Seção 1.2 sobre lógica proposicional e lógica predicada foi

dividida em duas seções, 1.3 e 1.4, nas quais o leitor irá encontrar uma explicação intuitiva e adequada dos

axiomas, que muito esclarece sobre o raciocínio envolvido nas demonstrações formais. Na Seção 1.5, o material

sobre programação em lógica é totalmente novo e a seção sobre a verificação de programas foi ampliada.

Capítulo 2: A Seção 2.2 inclui uma discussão sobre indução completa, enquanto na edição anterior ela era

apresentada apenas como exercício. A Seção 2.3 contém uma ampla discussão sobre definições recursivas —

de seqüências, conjuntos, operações — e algoritmos recursivos, bem como um tratamento mais completo das

técnicas para resolver relações de recorrência. A Seção 2.4 apresenta uma discussão explícita de algoritmos

dividir-para-conquistar e de técnicas para resolver relações de recorrência. Também fornece uma descrição

mais completa de invariantes de laços.

Capítulo 3: A Seção 3.1 examina o tipo de dados set das linguagens Pascal e SETL, e implementações possíveis

para um tipo de dados abstrato "set" para conjuntos. A noção de "herança" da programação orientada para

objeto se relaciona com a idéia de subconjuntos. A Seção 3.2 ilustra o uso de árvores de decisão como mecanismos

de contagem. A Seção 3.3 é uma nova seção que trata do Princípio da Inclusão e Exclusão e do Princípio

da Casa do Pombo. A Seção 3.4 mostra como contar o número de permutações de n objetos não necessariamente

distintos e o número de combinações de r dentre n objetos com repetições. A Seção 3.5 usa o triângulo

de Pascal (antes apresentado apenas como exercício) como uma introdução ao teorema binomial; também

inclui uma demonstração completa do teorema binomial, que antes era tratado apenas como exercício e

problema prático.

Viii Prefácio

Capítulo 4: A Seção 4.1 fornece uma explicação melhor que a da segunda edição sobre como testar as várias

propriedades de relações. São discutidos os fechos reflexivo, simétrico e transitivo. A Seção 4.2 é inteiramente

nova (e opcional) e fornece uma introdução a bancos de dados, apresentando bancos de dados relacionais

como conjuntos de relações matemáticas. As pesquisas são formuladas em termos das operações select, project

e join, ou em termos da teoria de conjuntos ou da lógica de predicados. Diagramas PERT, caminhos críticos

e ordenação topológica também são abordados pela Seção 4.2. A Seção 4.3, sobre funções, agora inclui

uma breve referência a linguagens de programação e suas funções, e mostra como contar o número de funções,

funções injetivas e funções sobrejetivas de um conjunto finito a outro. A contagem do número de permutações

sem pontos fixos em um conjunto finito também é abordada. O tópico sobre ordem de grandeza de funções

foi antecipado e recebeu novos exemplos e uma interpretação gráfica. A Seção 4.4, sobre matrizes, passou

a incluir matrizes booleanas e multiplicação de matrizes booleanas.