AULA 4 - Modelagem Matemática, Máquinas de Estado, Autômatos, Máquinas de Mealy e Turing

Prévia do material em texto

MATEMÁTICA 
COMPUTACIONAL 
AULA 4 
 
 
 
 
 
 
 
 
 
Prof. Luis Gonzaga de Paulo 
 
 
2 
CONVERSA INICIAL 
Muitos dos conceitos que estudamos em matemática tem aplicação direta 
e prática, não apenas em ambientes complexos e requintados, mas também em 
coisas simples, do dia a dia. As máquinas e os autômatos que estudaremos 
nesta aula são um exemplo: são frequentemente usadas para a modelagem 
matemática dos mais diferentes tipos de problemas, desde analisadores de 
linguagem a engines de busca, mecanismos de inferência, robôs e máquinas 
dos mais diversos tipos. 
Porém, em sua essência tais máquinas são fundamentais para os 
ambientes de computação, pois em síntese o próprio computador é uma dessas 
máquinas. O conhecimento do funcionamento dessas máquinas em nossos 
estudos tem o propósito de possibilitar o uso intenso dessas ferramentas, quer 
seja para a modelagem e o desenvolvimento de solução para os diversos 
problemas que se apresentam para os profissionais da tecnologia, quer seja para 
o estudo de questões relativas à computação, para a revisão de conceitos e o 
desenvolvimento tecnológico e científico. 
TEMA 1 – MÁQUINA DE ESTADOS 
As máquinas de estado são uma forma matemática de abstrair 
processos ou o funcionamento de equipamentos reais, sejam eletrônicos ou 
mecânicos, e ainda dos softwares. Em outras palavras, as máquinas de estado 
são um modelo matemático de sistemas que possuem entradas e saídas 
discretas e a capacidade de representar, em um certo momento, um estado pré-
estabelecido. 
As máquinas de estado também são chamadas autômatos, ou máquinas 
de estado finito (FSM – Finite State Machine, em inglês). O tipo de abstração 
propiciado por essas máquinas nos permite a modelagem matemática de um 
vasto número de problemas. Apesar de possuir a capacidade de representar 
múltiplos estados, uma FSM só pode apresentar-se em um estado por vez, 
denominado estado atual, sendo esta é principal característica de uma máquina 
de estados. O estado atual representa a informação relativa às entradas 
passadas, e isso é necessário para que se possa determinar o comportamento 
do sistema perante as próximas entradas. 
Uma FSM pode ser representada por uma quíntupla (Q, ∑, δ, q0, F): 
 
 
3 
 Q é um conjunto finito de estados; 
 ∑ é conjunto finito de símbolos, chamado de alfabeto da FSM; 
 δ é a função de transição; 
 q0 é o estado inicial no qual qualquer entrada é processada (q0 ∈ Q); 
 F é um conjunto de estado/estados finais de Q (F ⊆ Q). 
Figura 1 – Diagrama de representação de uma máquina de estados 
 
A terminologia aplicada às FSM inclui os seguintes termos: 
 Alfabeto é um conjunto finito de símbolos. Por exemplo: ∑ = {a, b, c, d} 
é um conjunto do alfabeto no qual ‘a’, ‘b’, ‘c’, e ‘d’ são símbolos. 
 String é uma sequência finita de símbolos obtidos de ∑. Por exemplo, a 
string ‘cabcad’ é uma string válida do conjunto do alfabeto ∑ = {a, b, c, 
d}. 
 Comprimento de uma string é o número de elementos presentes na 
string, denotado por |S|. Por exemplo, se S = ‘cabcad’, |S|= 6. Se |S|= 0, 
então a string é chamada string vazia, denotada por λ or ε). 
 Fecho de Kleene ou Operador de Kleene, ∑*, é um operador unário ou 
um conjunto de símbolos ou strings ∑, dado um infinito conjunto de todas 
as possíveis strings de todos os possíveis comprimentos sobre ∑ incluindo 
λ. A representação: ∑* = ∑0 ∪ ∑1 ∪ ∑2 ∪……. ∑p é o conjunto de todas 
as strings possíveis de comprimento p. Por exemplo, se ∑ = {a, b}, ∑* = 
{λ, a, b, aa, ab, ba, bb, ………..}. 
 
 
4 
 Fecho de Kleene / Mais, ∑+ é um conjunto infinito de possíveis strings 
de todos os possíveis comprimentos sobre ∑ excluindo λ. A 
representação é: ∑+ = ∑1 ∪ ∑2 ∪ ∑3 ∪……. ∑+ = ∑* − { λ }. Por exemplo, 
se ∑ = { a, b }, então ∑+ = { a, b, aa, ab, ba, bb, ………..}. 
 Linguagem é um subconjunto de ∑* para algum alfabeto ∑, que pode ser 
finito ou infinito. Por exemplo, se a linguagem L compreende todas as 
strings possíveis de comprimento 2 sobre ∑ = {a, b}, então L = { ab, aa, 
ba, bb}. 
A base do funcionamento de uma FSM é justamente isso: considerar que 
um estado armazena informações sobre as etapas anteriores, isto é, o passado 
do processo. Além disso, o estado reflete as mudanças ocorridas desde a 
entrada neste estado até o momento presente. Uma mudança de estado - 
geralmente descrita ou especificada por uma condição que precisa ser atendida 
ou ocorrer – refere-se à uma transição. Uma ação refere-se à uma atividade a 
ser realizada para gerar a transição, ou mesmo à uma atividade que ocorre em 
função de uma transição. 
Figura 2 – Um semáforo (farol ou sinal): exemplo de uma FSM 
 
 
 
5 
Figura 2 – Um diagrama de estado de FSM de um elevador 
 
Um diagrama de estado é a forma gráfica que utilizamos para 
representar o funcionamento de uma máquina de estado, como mostrado na 
Figura 3. As tabelas de transição de estado também podem representar as 
FSM - máquinas de estado. Uma máquina de estados finita pode ser descrita por 
uma tabela de transição de estados, que contém as informações completas 
sobre as ações e os estados, para cada um dos estados, e também todas as 
transições registradas ou previstas. 
Tabela 1 – Estados de uma FSM 
 
As máquinas de estado podem ser de dois tipos: as do tipo aceitadoras 
(ou reconhecedoras), como mostrado na Figura 4, que produzem uma saída 
binária, restrita a sim ou não, para informar se a entrada é aceita pela máquina 
ou não, e as do tipos transdutoras, como visto na Figura 5, que produzem uma 
informação na saída baseada em um estímulo ou informação de entrada e/ou 
um estado utilizando ações, e que geralmente são utilizadas para aplicações de 
controle. 
 
Condição Estado A Estado B Estado C
1 ... ... ...
2 ... Estado C ...
3 ... ... ...
Estado
Tabela de Transição de Estados
 
 
6 
Figura 4 – FSM do tipo aceitadores 
 
Do ponto de vista matemático, uma FSM é função da relação de conjuntos 
pré-determinados, e tem a seguinte definição (Gersting, 2015): 
Máquina de Estado Finito M = [E, I, O, fE, fO] é uma máquina de estado 
finito se E é um conjunto finito de estados, I é um conjunto finito de 
símbolos de entrada (o alfabeto de entrada), O é um conjunto finito 
de símbolos de saída (o alfabeto de saída) e fE, fO são funções, onde: 
fE: E x I →E 
e 
fO : E → O 
A máquina sempre começa inicializada por um estado inicial fixo e0 . 
Figura 5 – FSM do tipo transdutores 
 
As figuras apresentadas e os exemplos utilizados até aqui tratam de um 
tipo de FSM que denominamos AFD – Autômato Finito Determinístico, ou 
seja, uma estrutura matemática constituída por três tipos de elementos: um 
conjunto de estados, um alfabeto (com os símbolos reconhecidos como 
Efeitos 
Físicos
Efeitos 
Mecânicos
Luz
Calor
Som
Posição
Força
Velocidade
Sinal de
Saída
Sensor
 
 
7 
entrada e saída) e um conjunto de transições. Entre os estados destacamos 
um único estado inicial e um subconjunto composto dos estados finais. 
Um AFD - Autômato Finito Determinístico é representado por uma 
quíntupla (Q, ∑, δ, q0, F), na qual: 
 Q é um conjunto finito de estados; 
 ∑ é um conjunto finito de símbolos chamado alfabeto; 
 δ é a função de transição, na qual δ: Q × ∑ → Q; 
 q0 é o estado inicial a partir do qual qualquer entrada é processada (q0 ∈ 
Q); 
 F é um conjunto de estado/estados finais de Q (F ⊆ Q). 
Como já vimos, um AFD – Autômato Finito Determinístico é representado 
por um dígrafo denominado diagrama de estado. Nesse dígrafo, os vértices 
representam os estados, as arestas nomeadas com o alfabeto de entrada 
mostram as transições, o estado inicial é definido por uma única aresta vazia, e 
o estado final é indicado por um círculo duplo. Por exemplo, consideremos um 
AFD como segue: 
 Q = {a, b, c}; 
 ∑ = {0, 1}; 
 q0 = {a}; 
 F = {c}. 
A função de transição δ é apresentada no quadro a seguir. 
Quadro 1 – Funçãode transição para o AFD 
Estado atual 
Próximo estado para 
uma entrada 0 
Próximo estado para uma 
entrada 1 
a a b 
b c a 
c b c 
Podemos representar graficamente esse AFD da seguinte forma. 
 
 
 
8 
Figura 6 – Estado do AFD proposto 
 
Em um AFD, para cada par (estado, símbolo) há uma transição para um 
único estado, o que confere um caráter determinístico ao funcionamento deste 
autômato. Caso eliminemos essa restrição, ou seja, se para um determinado par 
(estado, símbolo) for possível haver transições para dois ou mais estados, 
passamos a denominar a FSM como AFN – Autômato Finito não 
Determinístico. Ou seja, em um AFN é possível haver um conjunto com várias 
operações possíveis para a mesma palavra ou símbolo de entrada em um 
estado. Os componentes de um AFN são basicamente os mesmos de um AFD, 
porém um AFN contempla as seguintes definições: 
 Um AFN pode ter mais que um estado inicial; 
 A função de transição apresenta, para cada par (estado, símbolo), um 
conjunto de estados. 
Um AFN - Autômato Finito Não-Determinístico é representado por uma 
quíntupla (Q, ∑, δ, q0, F), na qual: 
 Q é um conjunto finito de estados; 
 ∑ é um conjunto finito de símbolos chamado alfabeto; 
 δ é a função de transição, na qual δ: Q × ∑ → 2Q (2 elevado a Q deve-se 
ao fato de que a transição de um estado pode para qualquer combinação 
de Q); 
 q0 é o estado inicial a partir do qual qualquer entrada é processada (q0 ∈ 
Q); 
 F é um conjunto de estado/estados finais de Q (F ⊆ Q). 
Um AFN também pode ser representado por um dígrafo, um diagrama de 
estado, da mesma forma que um AFD. Para exemplificar, vamos considerar um 
AFN com as seguintes características: 
 
 
 
9 
 Q = {a, b, c}; 
 ∑ = {0, 1}; 
 q0 = {a}; 
 F = {c}; 
A função de transição δ é apresentada no quadro a seguir. 
Quadro 2 – Função de transição para o AFD. 
Estado Atual 
Próximo Estado para 
uma Entrada 0 
Próximo Estado para 
uma Entrada 1 
a a,b b 
b c a,c 
c b,c c 
A representação gráfica desse AF pode ser a seguinte. 
Figura 7 – Gráfico do AFN proposto 
 
O Quadro 3 apresenta um comparativo entre um AFD e um AFN. 
Quadro 1 – Comparativo entre um AFD e um AFN 
AFD AFN 
A transição de um estado ocorre para um único 
estado próximo particular, para cada símbolo 
de entrada. Por isso, é chamado 
determinístico. 
A transição de um estado pode ocorrer para 
vários estados seguintes, para cada símbolo de 
entrada. Por isso, é chamado de não-
determinístico. 
Transições de strings vazias não existem. Transições de strings vazias podem ocorrer. 
O retrocesso é permitido. O retrocesso nem sempre é possível. 
Requer mais espaço. Requer menos espaço. 
Uma string é aceita se passar para um estado 
final. 
Uma string é aceita se pelo menos uma das 
transições possíveis terminar em um estado 
final. 
 
 
10 
Figura 8 – Arquitetura de um AFD 
 
Um AFD pode ser representado pela arquitetura mostrada na Figura 9: 
uma máquina que opera com uma leitura sequencial – em uma fita – e em 
apenas uma direção: para a direita. Esta fita contém os símbolos distribuídos em 
células, sendo um único símbolo em cada célula. A máquina também tem um 
registrador para armazenar o estado atual, um conjunto de instruções – a função 
de transição do AFD – e uma unidade de controle. 
É possível também que se possa fazer a leitura bidirecional da fita, 
permitindo que a transição possa avançar ou retroceder na leitura dos símbolos. 
Nesse caso, para evitar que a leitura avança para além do final, ou retroceda 
para antes do começo, é necessário que existam mais duas células com 
símbolos especiais < e >, que, na prática, limitam as transições: uma transição 
de avanço (ou leitura da fita para a direita) para a condição < e uma transição 
de retrocesso (ou leitura da fita para a esquerda) para a condição >. A Figura 9 
apresenta a arquitetura dessa variação de AFD. 
Figura 9 – AFD com fita bidirecional 
 
 
controle
+
ᵟ
a1 a2 ai an
e
... ...
fita de somente leitura
unidirecional
registrador com
estado atual
controle
+
ᵟ
e
fita de somente leitura
bidirecional
registrador com
estado atual
a1 a2 ai an... ...
 
 
11 
Na aula prática sobre FSM, são apresentados problemas para os quais a 
solução emprega os dois tipos de autômatos, e a solução proposta para eles, 
assim como exercícios resolvidos que reforçam os conceitos apresentados. 
Além de seu uso na matemática, na engenharia e nas tecnologias em geral, as 
Máquinas de Estado são largamente empregadas na computação, quer seja na 
modelagem do funcionamento de softwares (sistema ou aplicativos), quer seja 
para projetar sistemas digitais compostos de hardware e software, na 
Engenharia de Software, nos projetos de compiladores e de protocolos de rede, 
e também no estudo da computação e das linguagens. 
TEMA 2 – AUTÔMATOS DE PILHA 
Apesar da sua extensa aplicação, as máquinas de estado finito – FSM, ou 
autômatos finitos, não atendem à totalidade dos problemas. É o caso, por 
exemplo, de aplicações para as quais é necessário usar expressões aritméticas. 
Nesses casos, falta aos autômatos uma memória que permita registrar todos os 
valores – ou as ocorrências dos símbolos. Para atender à essa necessidade são 
utilizados os AP – Autômatos de Pilha (pushdown automata, em inglês). 
Figura 10 – A arquitetura de um AP 
 
Estes são mecanismos de grande importância para a computação, como, 
por exemplo, nos compiladores de linguagem de programação, na etapa de 
análise sintática de um código. Ainda, diferentemente dos autômatos finitos, um 
autômato de pilha não determinístico tem uma abrangência muito superior a dos 
controle
+
ᵟ
e
fita de somente leitura
bidirecional
registrador com
estado atual
a1 a2 ai an... ...
b1
b2
bn
.
.
.
topo da pilha
 
 
12 
AP determinísticos. Um autômato de pilha é uma máquina de estados bastante 
semelhante à um AFD, porém com o adicional de uma pilha. A Figura 10 
apresenta a arquitetura de um AP. 
A pilha, tal como uma fita, compõe-se de células que são capazes de 
receber apenas um símbolo por vez. A leitura, porém, é feita apenas na célula 
do topo da pilha. No início do processo, o registrador contém o estado inicial do 
AP. A fita então recebe a palavra de entrada da sua primeira célula, pois o 
cabeçote de leitura está posicionado na primeira célula da fita. Neste momento, 
a pilha está vazia. À medida em que a leitura da fita prossegue e as transições 
resultam em um uso da pilha, um símbolo de fim de pilha (F) é inserido na pilha, 
de modo a identificar esse status novamente quando a pilha for lida. 
A principal diferença entre um APD – Autômato de Pilha Determinístico e 
um APN – Autômato de Pilha Não-Determinístico reside no fato de que o APN 
pode contemplar transições compatíveis entre si. 
TEMA 3 – MÁQUINA DE MEALY 
Uma máquina de Mealy é uma FSM cuja saída depende do estado atual, 
bem como da entrada. Pode ser descrita por uma sêxtupla (Q, ∑, O, δ, X, q0) em 
que: 
 Q: conjunto finito de estados; 
 ∑: conjunto finito de símbolos denominado alfabeto de entrada; 
 O: conjunto finito de símbolos denominado alfabeto de saída; 
 δ: função de entrada de transição em que δ: Q × ∑ → Q; 
 X: função de saída da transição em que X: Q × ∑ → O; 
 q0: estado inicial a partir do qual qualquer entrada é processada (q0 ∈ Q). 
Os estados de uma máquina de Mealy são mostrados no quadro a seguir. 
 
 
 
13 
Quadro 4 – Estados de uma máquina de Mealy 
Estado atual 
Próximo estado 
entrada = 0 entrada = 1 
Estado Saída Estado Saída 
→ a b x1 c x1 
b b x2 d x3 
c d x3 c x1 
d d x3 d x2 
O diagrama de estados dessa máquina é o seguinte. 
Figura 11 – Diagrama de estados de uma máquina de Mealy 
 
TEMA 4 – MÁQUINA DE MOORE 
Uma máquina de Moore é uma FSM cujas saídas dependem apenas do 
estado atual. Pode ser descrita por uma sêxtupla (Q, ∑, O, δ, X, q0) em que: 
 Q: conjunto finito de estados; ∑: conjunto finito de símbolos denominado alfabeto de entrada; 
 O: conjunto finito de símbolos denominado alfabeto de saída; 
 δ: função de entrada de transição em que δ: Q × ∑ → Q; 
 X: função de saída da transição em que X: Q → O; 
 q0: estado inicial a partir do qual qualquer entrada é processada (q0 ∈ Q). 
Os estados de uma máquina de Moore são mostrados no quadro a seguir. 
 
 
 
14 
Quadro 5 – Estados de uma máquina de Moore 
Estado atual 
Próximo estado 
Saída 
Entrada = 0 Entrada = 1 
→ a b c x2 
b b d x1 
c c d x2 
d d d x3 
O diagrama de estados de uma máquina de Moore é o seguinte. 
Figura 12 – Diagrama de estados de uma máquina de Moore 
 
TEMA 5 – MÁQUINA DE TURING 
A Máquina de Turing é um dispositivo inventado em 1936 por Alan Turing, 
matemático inglês, que aceita as linguagens (conjunto recursivamente 
enumerável) geradas por gramáticas tipo 0. Uma máquina de Turing é um 
modelo matemático que consiste em uma fita de comprimento infinito, dividida 
em células, pelas quais a entrada é dada, e de uma cabeça de leitura que lê a 
fita de entrada. Um registrador de estado armazena o estado da máquina de 
Turing. Depois de ler um símbolo de entrada, este é substituído por outro 
símbolo, o estado interno da máquina é alterado, e a cabeça de leitura se move 
uma célula, para a direita ou para a esquerda. Se a máquina atingir o estado 
final, a string de entrada será aceita; caso contrário, será rejeitada. 
Uma máquina de Turing pode ser formalmente descrita com uma sétupla 
(Q, X, ∑, δ, q0, B, F), em que: 
 Q é um conjunto finito de estados; 
 X é o alfabeto da fita; 
 
 
15 
 ∑ é o alfabeto de entrada 
 δ é a função de transição δ: Q × X → Q × X × {deslocamento à esquerda, 
deslocamento à direita}. 
 q0 é o estado inicial; 
 B é o símbolo de ‘Espaço em Branco’; 
 F é o conjunto de estados finais. 
Uma comparação da máquina de Turing com outros modelos de 
autômatos é bastante útil, como mostrando no quadro a seguir. 
Quadro 2 – Máquina de Turing x outros autômatos 
Tipo de Máquina Estrutura de Pilha de Dados Determinística? 
Autômatos Finitos N/A Sim 
Autômato de Pilha Último a entrar, primeiro a sair (LIFO) Não 
Máquina de Turing Fita infinita Sim 
Vamos à um exemplo da máquina de Turing M = (Q, X, ∑, δ, q0, B, F), 
com: 
 Q = {q0, q1, q2, qf} 
 X = {a, b} 
 ∑ = {1} 
 q0 = {q0} 
 B = espaço em branco 
 F = {qf } 
A transição de estados δ é dada por: 
Simbolo do Alfabeto 
da Fita 
Estado atual ‘q0’ Estado atual ‘q1’ Estado atual ‘q2’ 
a 1Rq1 1Lq0 1Lqf 
b 1Lq2 1Rq1 1Rqf 
Em uma máquina de Turing, a complexidade do tempo refere-se à medida 
do número de vezes que a fita se move quando a máquina é inicializada para 
alguns símbolos de entrada, e a complexidade do espaço é o número de células 
da fita gravadas. A complexidade do tempo pode ser representada por T (n) = O 
 
 
16 
(n log n). A complexidade do espaço da máquina de Turing pode ser 
representada por S (n) = O (n). 
Quanto à linguagem, uma máquina de Turing aceita uma linguagem se 
entrar em um estado final para qualquer string de entrada escrita. Uma 
linguagem é dita recursivamente enumerável (gerada pela gramática Tipo 0) se 
for aceita por uma máquina de Turing. Uma MT decide por uma linguagem se o 
aceita e entra em um estado de rejeição para qualquer entrada que não esteja 
nessa linguagem. Uma linguagem é recursiva se for decidida por uma máquina 
de Turing. Podem haver alguns casos em que uma máquina de Turing não para. 
Então essa máquina de Turing aceita a linguagem, mas não a decide. 
Vamos ver questões elementares da máquina de Turing com o auxílio dos 
dois exemplos a seguir. Primeiramente, vamos tratar de uma máquina de Turing 
que possa reconhecer todas as entradas com uma string na qual o número de 
letras ‘a’ seja par. Essa máquina de Turing M pode ser construída com os 
seguintes passos: 
 Seja q1 o estado inicial; 
 Se M está em q1; ao ler ‘a’, entra no estado q2 e escreve B (espaço em 
branco); 
 Se M está em q2; ao ler ‘a’, entra no estado q1 e escreve B (espaço em 
branco); 
 Dos movimentos apresentados, nós podemos verificar que M entra no 
estado q1 se ler um número par de ‘a’s, e entra no estado q2 se ler um 
número ímpar de ‘a’s. Portanto q2 é o único estado de aceitação. 
Deste modo: 
M = {{q1, q2}, {1}, {1, B}, δ, q1, B, {q2}} 
Em que δ é dado por: 
Símbolo do 
alfabeto da fita 
Estado atual ‘q1’ Estado atual ‘q2’ 
a BRq2 BRq1 
No segundo exemplo, projetamos uma máquina de Turing que lê uma 
string representando um número binário e apaga todos os 0s iniciais da string. 
No entanto, se a string for composta apenas por 0s, ela manterá um 0. Vamos 
supor que a string de entrada seja delimitada por um espaço em branco, B, em 
 
 
17 
cada extremidade da cadeia. Então nossa máquina de Turing M pode ser 
construída pelos seguintes movimentos: 
 Seja q0 o estado inicial; 
 Se M está em q0, ao ler 0, move à direita, entra no estado q1 e apaga o 0. 
Ao ler 1, entra no estado q2 e move à direita. 
 Se M está em q1,ao ler 0, move à direita 0, ou seja, troca os 0’s por B’s. 
Ao atingir o 1 mais à esquerda, entra em q2 e move à direita. Se encontra 
B, ou seja, a string é composta apenas de 0’s, move à esquerda e entra 
no estado q3. 
 Se M está em q2, lendo tanto 0 ou 1, move à direita. Se encontrar B, move 
à esquerda e entra em q4. Isto valida que a string contém apenas 0’s e 
1’s. 
 Se M está em q3, troca ‘B’ por ‘0’, move à esquerda e atinge o estado 
final qf. 
 Se M está em q4, ao ler tanto 0 ou 1, move à esquerda. Ao alcançar o 
início da string, ou seja, ler ‘B’, atinge o estado final qf. 
Portanto: 
M = {{q0, q1, q2, q3, q4, qf}, {0,1, B}, {1, B}, δ, q0, B, {qf}} 
Em que δ é dado por: 
Símbolo do 
alfabeto da fita 
Estado 
atual ‘q0’ 
Estado 
atual ‘q1’ 
Estado 
atual ‘q2’ 
Estado 
atual ‘q3’ 
Estado 
atual ‘q4’ 
0 BRq1 BRq1 ORq2 - OLq4 
1 1Rq2 1Rq2 1Rq2 - 1Lq4 
B BRq1 BLq3 BLq4 OLqf BRqf 
FINALIZANDO 
As máquinas de estado fazem parte de um poderoso arsenal para o 
desenvolvimento de soluções com base na formulação matemática do problema 
e suas possíveis soluções. Por serem processos empregados desde a origem 
da computação, com um forte embasamento matemático, podem causar uma 
primeira impressão de complexidade. Entretanto, o uso constante e a sua 
equiparação aos componentes essenciais dos computadores – os circuitos 
 
 
18 
digitais de lógica e aritmética binária – fornece um precioso conhecimento para 
o estudo de problemas e o projeto de soluções computacionais, com a vantagem 
de poder-se utilizar a modelagem matemática em sua plenitude, valendo-se 
principalmente das provas dos modelos formais, o que, em termos de otimização 
do uso de tempo e de recursos escassos, pode ser a diferença entre o sucesso 
e o fracasso do projeto. 
 
 
 
19 
REFERÊNCIAS 
BONAFINI, F. C. Matemática e estatística. São Paulo: Pearson Education do 
Brasil, 2014. 
GERSTING, J. L. Fundamentos matemáticos para a ciência da computação: 
um tratamento moderno de matemática discreta. Rio de Janeiro: LTC, 2015. 
MACEDO, L. R. D.; CASTANHEIRA, N. P.; ROCHA, A. Tópicos de matemática 
aplicada. Curitiba: InterSaberes, 2013. 
STEIN, C.; DRYSDALE R. L.; BOGART, K. Matemática discreta para ciência 
da computação. São Paulo: Pearson Education do Brasil, 2013. 
VIEIRA, M. J. Introdução aos Fundamentos da computação: linguagens e 
máquinas. São Paulo: Pioneira Thomson Learning, 2005. 
WALPOLE, R. E. et al. Probabilidade & estatística para engenharia e 
ciências. São Paulo: Pearson Prentice Hall, 2009.