Analise e complexidade de algoritmos

Disponível somente no TrabalhosFeitos
  • Páginas : 5 (1036 palavras )
  • Download(s) : 0
  • Publicado : 5 de junho de 2012
Ler documento completo
Amostra do texto
[LINGUAGENS FORMAIS E AUTÔMATOS]

Entendento a importância da matéria Linguagens Formais e Autômatos dentro do curso de Ciências da Computação. Buscando um conhecimento básico de Lógica Booleana e as definições para termos como “Palavras”, “Alfabeto” e “Gramática” dentro desse universo.

1. INTRODUÇÃO
A importância da Teoria das Linguagens Formais e dos Autômatos (LFA) está no estudo demodelos matemáticos que possibilitam a especificação e o reconhecimento de linguagens (no sentido amplo da palavra), suas classificações, estruturas, propriedades, características e inter-relacionamentos.
Essa teoria é de suma importância na Ciência da Computação pois ela ela tanto apoia outros aspectos teóricos da Ciência da Computação (decidibilidade, computabilidade, complexidade computacional,por exemplo), como fundamenta diversas aplicações computacionais tais como processamento de linguagens, reconhecimento de padrões, modelagem de sistemas.
2. LÓGICA BOOLEANA (CONCEITOS BÁSICOS)
Álgebra de Booleana é utilizada para exprimir os resultados ou saídas de circuitos lógicos e para manipular variáveis lógicas, com a finalidade de se obter o melhor circuito para uma determinada funçãológica. Chamamos de variável Booleana a uma variável que pode assumir só duas condições (dois valores).
Um exemplo de variável Booleana é uma chave, que só pode estar aberta ou fechada, não existe outra condição. Outro exemplo é uma lâmpada, que só pode estar acesa ou apagada. Em eletrônica digital costumamos associar a uma variável Booleana os símbolos “0“ e “1“ aos estados que a variável podeassumir. Desta forma lâmpada acesa poderia ser “1“ e conseqüentemente apagada “0“, mas poderia ser o contrário depende da convenção adotada.


Níveis Lógicos
0 (zero) 1 (um)
Falso Verdadeiro
Desligado Ligado
Baixo Alto
Não Sim
Chave aberta Chave fechada
Apagado Acesso

Operações em Álgebra Booleana
Adição Lógica = +, OU, OR
Multiplicação Lógica = ., E, AND
Complementação Lógica/Inversão =~, -, NOT, NÂO

E, AND, .
O E Lógico (AND), portanto, significa que o resultado SÓ É VERDADEIRO SE AMBAS AS CONDIÇÕES FOREM VERDADEIRAS.
1 º) 0• 0 = 0
2 º) 0• 1 = 0
3 º) 1• 0 = 0
4 º) 1• 1 = 1
1 º) A• 0 = 0: A pode ser 0 ou 1, então;

A = 0 _0• 0 = 0
A = 1 _1• 0 = 1
Obs: Notamos que todo número multiplicado por zero será zero

2 º) A• 1 = A : A pode ser 0 ou 1, então;
A = 0 _0• 1 =0



A = 1 _1• 1 = 1
Obs: Notamos que se multiplicarmos a variável por 1 o resultado será ela
Mesma

3 º) A• A = A : A pode ser 0 ou 1, então;
A = 0 _0• 0 = 0
A = 1 _1• 1 = 1
Obs: Notamos que se multiplicarmos a mesma variável, o resultado será ele
Mesma

4 º) A• A = 0 : A pode ser 0 ou 1, então;
A = 0 _ A = 1 _0• 1 = 0
A = 1 _ A = 0 _1• 0 = 0
Obs: Notamos que se multiplicarmos auma variável o seu complemento,
teremos como resultado zero
OU, OR, ~, -
O OU Lógico (OR), portanto, significa que o resultado SÓ É FALSO SE AMBAS AS CONDIÇÕES FOREM FALSAS. Note que o OU Lógico é exatamente o inverso do E Lógico.
1 º) 0 + 0 = 0
2 º) 0 + 1 = 1
3 º) 1 + 0 = 1
4 º) 1 + 1 = 1

1 º) A + 0 = A : A pode ser 0 ou 1, então;
A = 0 _0 + 0 = 0
A = 1 _1 + 0 = 1
Obs: Notamos que oresultado será sempre igual à variável

2 º) A + 1 = 1 : A pode ser 0 ou 1, então;
A = 0 _0 + 1 = 1
A = 1 _1 + 1 = 1


Obs: Notamos que sempre que somarmos 1 a uma variável, o resultado será
sempre 1

3 º) A + A = A : A pode ser 0 ou 1, então;
A = 0 _0 + 0 = 0
A = 1 _1 + 1 = 1
Obs: Notamos que se somarmos a mesma variável, o resultado será ela
Mesma

4 º) A + A = 1 : A pode ser 0ou 1, então;
A = 0 _ A = 1 _0 + 1 = 1
A = 1 _ A = 0 _1 + 0 = 1
Obs: Notamos que se somarmos a uma variável o seu complemento,
teremos como resultado 1
NOT, NÃO
Chamemos de A o complemento de A
1 º) Se A = 0 _ A= 1
2 º) Se A = 1 _ A= 0
Outra notação: A = A’

Através do postulado da complementação, podemos estabelecer a seguinte
identidade: A= A

Prova: Se A = 1, temos: A= 0 e se A=...
tracking img