Aspectos Formais da Computação
CCO 410
Prof. Dr. Sérgio Donizetti Zorzo
UFSCar –2006
Aspectos Formais da Computação
Objetivos
- Apresentar aos alunos modelos computacionais e respectivas classes de conjuntos que
podem ser tratados. Capacitar o aluno a identificar num dado conjunto as suas
características computacionais e construir o modelo computacional apropriado,
ajustando-o para um modelo computacional eficiente, com o rigor matemático
necessário.
Ementa / Plano de Aula
Autômatos: os Métodos e a loucura
Autômatos Finitos
Expressões Regulares e Linguagens
Propriedades das Linguagens Regulares
Gramáticas e Linguagens Livre de Contexto
Autômatos de Pilha
Propriedades de linguagens livres de contexto
Introdução às Máquinas de Turing
Indecidibilidade
Problemas Intratáveis
Outras classes de problemas
Aspectos Formais da Computação
Avaliação
-
Exercícios semanais – média aritmética, descartando 2 piores notas.
-
Provas Formais - 05/05/2006 e 28/06/2006
Nota Final = (P1 + P2 + Exercicios) / 3
Prova de Suficiência
22/março/2006 - 4a. Feira – 8h / Sala de Seminários – DC
Bibliografia
Hopcroft, J. E.; Ullman, J.D. & Motwani, R. - Introdução à Teoria de Autômatos,
Linguagens e Computação. Editora Campus, 2003. 560p.
Aspectos Formais da Computação
Teoria dos Autômatos
-
Estudo dos dispositivos de computação abstratos, ou “máquinas”.
década de 30 – Alan Turing
estudo de uma máquina abstrata que tinha todas as características dos computadores
atuais, pelo menos no que se refere ao que eles poderiam calcular.
Objetivo
- descrever com exatidão o que podia ou não podia fazer
- aplicável até hoje.
década de 40 e 50 – máquinas de Turing mais simples = “autômatos finitos”
Objetivo
- modelar funções do cérebro, estudo de gramáticas formais (Chomsky)
em 1969 – Cook estendeu o estudo de Turing a respeito da computabilidade dos problemas
- problemas que podem ser resolvidos de forma eficiente e
- problemas intratáveis que em princípio podem ser resolvidos mas que, na prática,
levam tanto tempo que os computadores são inúteis para solucionar todas as instâncias
(NP-difícies)
Aspectos Formais da Computação
Teoria dos Autômatos
-
Estudos teóricos dessa área tem relação direta com o que fazemos hoje.....
Autômatos finitos e certas classes de gramáticas formais
..........
tem relação direta com a construção de componentes de software.
Máquinas de Turing
..........
o que esperar de nosso software.
Teoria de Problemas Intratáveis
...........
nos permite detectar a situação e encontrar soluções aproximadas, por alguma
heurística ou método para limitar o período de tempo da computação.
e o que os computadores podem fazer ????
problemas decidíveis / indecidíveis
os computadores podem computar de forma eficiente ????
problemas tratáveis / intratáveis
Aspectos Formais da Computação
Representações de Conjuntos
-
Para cada classe de conjunto (de acordo com a Hierarquia de Chomsky) há
uma maneira finita de representá-los. Para os conjuntos regulares, temos :
Autômatos finitos
.......... Conjunto finito de estados, onde cada estado “memoriza” alguma
informação, e ações que podem representar influências externas e que faz com
o estado “atual” seja atualizado por um novo estado.
Gramáticas
.......... São sistemas de reescrita onde cada cadeia de símbolos pode ser
definida em termos de novas cadeias de símbolos.
Expressões Regulares
........... São expressões (finitas) que, utilizando um número fínito de
metasímbolos, permitem representar conjuntos regulares.
Aspectos Formais da Computação
Provas Formais
É útil ? Onde ?
...... testes de programas – como? dedução,
TIPOS DE PROVAS FORMAIS:
- Provas Dedutivas
...... uma sequência de etapas justificadas
- Provas por Contradição, Contra-Exemplo, e sobre Conjuntos
........ uso de resultados de teoria já estabelecida, exemplos absurdos
- Provas por indução
........ provas recursivas de uma afirmação parametrizada
Aspectos Formais da Computação
1- Provas Dedutivas
Sequência de afirmações cuja verdade nos leva de alguma afirmação inicial, chamada de
hipótese ou declaração dada, a uma afirmação de conclusão.
Cada etapa da prova deve se seguir, por algum princípio lógico aceito, dos fatos dados, de
algumas afirmações anteriores na prova dedutiva, ou de uma combinação desses
elementos.
O teorema que é provado quando vamos de uma hipótese H até uma conclusão C é a
afirmação “Se H então C” - dizemos que C é deduzido de H.
Teorema 1:
Se x ≥ 4, então 2x ≥ x2
- Informalmente é fácil convencermos que o Teorema 1 é verdadeiro
-
a hipótese “x ≥ 4” tem o parâmetro x – não é verdade nem falsa/ depende de x
-
A conclusão “2x ≥ x2” tem o parâmetro x , e substituindo x vamos achar que a
conclusão é verdadeira
Mas temos infinitos valores de x, e não poderemos testar todos....
Essa é uma prova informal, pois utilizamos nossa intuição apenas.
Aspectos Formais da Computação
Maneiras distintas de dizer “Se H então C”
H implica C
H somente se C
C se H
Sempre que H é verdadeira, segue-se C
no exemplo Teorema 1 - Se x ≥ 4, então 2x ≥ x2 teríamos...
2x ≥ x2 implica x ≥ 4
USO DE
2x ≥ x2 somente se x ≥ 4
2x ≥ x2 se x ≥ 4
Sempre que x ≥ 4, segue-se que 2x ≥ x2
→ PARA INDICAR ENTÃO
Aspectos Formais da Computação
Afirmações com quantificadores
para todo
existe
A ordem em que esses
quantificadores aparecem afeta o
significado da afirmação.
para cada
combinação de para-todo / existe
Para-todo - deve considerar todas as opções possíveis
existe - só tem que escolher um valor (que pode depender dos valores anteriores)
Conjunto Infinito
“O conjunto S é infinito se e somente se, para todo inteiro n, existe um
subconjunto T de S com exatamente n elementos”.
(OK)
“O conjunto S é infinito se e somente se, existe um subconjunto T de S tal que
para todo inteiro n, o conjunto T tem exatamente n elementos”. (INCORRETO)
Aspectos Formais da Computação
Afirmações se-e-somente-se
“A se e somente se B”
“A iff B “( iff - if and only if / notação matemática)
“A é equivalente a B”
“A exatamente quando B”
Querem dizer........
“se A então B” e “se B então A”
1- a parte se: “se B então A”
2- a parte somente-se “se A então B”, que pode ser enunciada por
“A somente se B “ (forma equivalente)
...... As provas podem ser apresentadas em qualquer ordem.
Aspectos Formais da Computação
Afirmações se-e-somente-se
Seja a notação
1. └x┘- piso do número real x – é o maior inteiro igual ou menor que x
2. ┌x┐- teto do número real x – é o menor inteiro igual ou maior que x
Teorema 3 – Seja x um número real. Então └x┘ = ┌x┐ se e somente se x é um inteiro
Prova
1- (somente-se) Suponha que └x┘=┌x┐e tentaremos mostrar que x é um inteiro.
Usando as definições de de piso e teto, notamos que └x┘ ≤ x e ┌x┐≥ x.
Porém foi dado que └x┘=┌x┐e assim podemos substituir o teto pelo piso na
primeira igualdade para concluir que ┌x┐ ≤ x.
Tendo em vista que ┌x┐≤ x e ┌x┐≥ x são válidas, podemos concluir pelas
propriedades das desigualdades aritméticas que ┌x┐= x.
Como ┌x┐ sempre é um inteiro, x também que que ser um inteiro nesse caso.
2- (parte se) Suponha que x é um inteiro e tentamos provar que └x┘=┌x┐. Isso é fácil,
pois pelas definições de teto e piso, quando x é um inteiro temos que └x┘e ┌x┐são
iguais a x, e portanto, são iguais entre si.
Aspectos Formais da Computação
Teoremas que parecem não ter hipótese
As vezes a hipótese está subentendida como no exemplo de trigonometria que
admite que se θ é um ângulo e que o significado de sen e cos são os de
seno e cosseno da trigonometria, então
Teorema 4 – sen2 θ + cos2 θ = 1
......ou “Se θ é um ângulo então sen2 θ + cos2 θ = 1”
Aspectos Formais da Computação
2- Provas sobre conjuntos
Provas por contradição
Provas por contra-exemplo
Provas sobre conjuntos
usar a correspondência com a teoria de conjuntos e todos os resultados
dessa teoria.
A igualdade E = F consiste em
1- se x está em E, então x está em F
2- se x está em F, então x está em E
Teorema 5:
R U ( S Π T ) = ( R U S) Π ( R U T )
Nesse caso E = R U ( S Π T )
e
F = ( R U S) Π ( R U T )
Aspectos Formais da Computação
Teorema 5:
R U ( S Π T ) = ( R U S) Π ( R U T )
1) (Parte se )
Afirmação
Justificativa
1.
x está em R U ( S Π T )
dado
2.
x está em R ou x está em ( S Π T )
1) e definição de união
3.
x está em R ou x está em S e T
2) e definição de intersecção
4.
x está em R ou S
3) e definição de união
5.
x está em R ou T
3) e definição de união
6.
x está em ( R U S) Π ( R U T )
4) e 5) e definição de intersecção
2) (parte somente-se)
Afirmação
Justificativa
1.
x está em ( R U S) Π ( R U T )
dado
2.
x está em ( R U S)
1) e definição de intersecção
3.
x está em ( R U T)
1) e definição de intersecção
4.
x está em R ou x está em S e T
2) e 3) e raciocínio sobre uniões
5.
x está em R ou x está em ( S Π T )
4) e definição de intersecção
6.
x está em R U ( S Π T )
5) e definição de união
Aspectos Formais da Computação
2- Provas sobre conjuntos
Provas por contradição
Provas por contra-exemplo
Provas por contradição ou contrapositiva
Toda afirmação se-então tem uma forma equivalente que, em algumas
circunstâncias, é mais fácil de provar.
A contrapositiva da afirmação “se H então C” é “se não C então não H”
=> Uma afirmação e sua antítese são ambas verdadeiras ou ambas falsas,
e assim podemos provar qualquer uma delas para provar a outra.
Há 4 casos a considerar:
1) H e C são verdadeiros
2) H é verdadeiro e C é falso => a afirmação “Se H então C” é falsa
3) H é falso e C é verdadeiro
4) H e C são falsos
Aspectos Formais da Computação
A contrapositiva da afirmação “se H então C” é “se não C então não H”
Há 4 casos a considerar para a afirmação contrapositiva “se não C então não H”:
1) H e C são verdadeiros
2) H é verdadeiro e C é falso => a afirmação “Se não C então não H ” é falsa
3) H é falso e C é verdadeiro
4) H e C são falsos
Exemplo:
A igualdade E = F consiste em
1- se x está em E, então x está em F
2- se x está em F, então x está em E
Ou (usando a contrapositiva)
A igualdade E = F consiste em
1- se x não está em E, então x não está em F
2- se x não está em F, então x não está em E
Aspectos Formais da Computação
2- Provas sobre conjuntos
Provas por contradição
Provas por contra-exemplo
Outra forma de provar uma afirmação da forma “Se H então C” é provar a
afirmação
“H e não C implica falsidade”
Aspectos Formais da Computação
2- Provas sobre conjuntos
Provas por contradição
Provas por contra-exemplo
Servem para provar que determinada afirmação não é um teorema
Suposto Teorema: “Todos os primos são impares”
(ou, se o inteiro x é um número primo, então x é impar)
O número 2 é primo, mas é par
Suposto Teorema: “Não existe par de inteiros a e b tais que a mod b = b
mod a”
Se acharmos a= b = 2 o teorema funciona
Teorema 6: “a mod b = b mod a se e somente se a = b ”
Aspectos Formais da Computação
3- Provas Indutivas
induções sobre inteiros
formas mais gerais de induções sobre inteiros
induções estruturais
induções mútuas
induções sobre inteiros
Suponha que temos que provar a afirmação S(n) sobre um
inteiro n
1- (base) mostramos que S(i) é verdade para um inteiro i
específico . Em geral i=0 ou i=1
2- (etapa indutiva) Supondo n>i, onde i é o inteiro da base,
mostramos que “se S(n) então S(n+1)”
Aspectos Formais da Computação
induções sobre inteiros
Suponha que temos que provar a afirmação S(n) sobre um inteiro n
1- (base) mostramos que S(i) é verdade para um inteiro i específico . Em
geral i=0 ou i=1
2- (etapa indutiva) Supondo n>i, onde i é o inteiro da base, mostramos
que “se S(n) então S(n+1)”
Teorema 7: “
Σi2
= n ( n+1) (2n+1) / 6, para i variando de 1 a n”
Prova:
1 (base)
2 (etapa de indução)
Aspectos Formais da Computação
Teorema 7: “Σi2 = n ( n+1) (2n+1) / 6, para i variando de 1 a n”
Prova:
1 (base) provar que S(0) é verdadeiro
0 = 0. (0+1).(2.0+1)
 0=0
OK (provado)
2
2 (etapa de indução ) Supondo que S(n) é verdadeiro, temos que provar
que S(n+1) também é verdadeiro
Aspectos Formais da Computação
3- Provas Indutivas
induções sobre inteiros
formas mais gerais de induções sobre inteiros
induções estruturais
induções mútuas
formas mais gerais de induções sobre inteiros
1- (base) pode-se usar vários casos de base. Isto é, provamos S(i), S(i+1),
... S(j), para algum j>i
2- (etapa indutiva) Supondo n>i, onde i é o inteiro da base, mostramos
que “se S(n) então S(n+1)”
Na prova de S(n+1) pode-se usar a verdade de todas as afirmações S(i),
S(i+1), ... , S(j) em vez de usar apenas S(n)
Aspectos Formais da Computação
3- Provas Indutivas
induções sobre inteiros
formas mais gerais de induções sobre inteiros
induções estruturais
induções mútuas
induções estruturais
Usada na teoria de autômatos em caso de árvores e sub-árvores e
expressões,que possuem definição recursiva.
Aspectos Formais da Computação
3- Provas Indutivas
induções sobre inteiros
formas mais gerais de induções sobre inteiros
induções estruturais
induções mútuas
As vezes temos que provar um grupo de afirmações S1(n), S2(n) S3(n) ....
Sk(n) e tais afirmações devem ser induzidas em n no seu conjunto.
Aspectos Formais da Computação
Conceitos Centrais da Teoria de Autômatos
Alfabeto
Conjunto de símbolos finito e não vazio.
Convencionalmente, usamos o símbolo Σ para um alfabeto
Σ1 = { 0, 1 } alfabeto binário
Σ2 = { a,b,c,d,e } alfabeto das cinco primeiros letras do alfabeto latino
Strings – palavra – cadeia
Sequência finita de símbolos de um alfabeto
0110 é uma cadeia do alfabeto Σ1 = { 0, 1 }
Cadeia Vazia – cadeia formada por zero símbolos e representada por ε
Comprimento de uma cadeia é o número de símbolos do alfabeto que a cadeia contém.
A cadeia 0110 do alfabeto Σ1 = { 0, 1 } tem comprimento 4 , pois contém 4
símbolos |0110| = 4
A cadeia 010101 do alfabeto Σ2 = { 01, 02 } tem comprimento 3, ou seja |010101| =3
|ε| = 0
Aspectos Formais da Computação
Potência de um Alfabeto
Conjunto de todas as cadeias de certo comprimento.
Convencionalmente, Σk denota todas as cadeias de comprimento k do alfabeto Σ
Se Σ = { 0, 1 }
Σ0 = {ε } Σ1 = Σ = { 0,1 } Σ2 = { 00,01,10,11} Σ3 = {000,001,010,011,100,101,110,111}
Conjunto de todas as cadeias sobre um alfabeto Σ ( FECHO - Σ* )
Σ* = Σ0 U Σ1 U Σ2 U ..... (Fecho de Σ)
Σ+ = Σ1 U Σ2 U .....
(Fecho Positivo de Σ)
Concatenação de Cadeias –
Justaposição de seus símbolos – Sejam x e y denotando cadeias sobre um
alfabeto Σ então xy denota a concatenação, e representa a cadeia formada
pelos símbolos da cadeia x seguido (justapostos) pelos símbolos da cadeia y.
x= 0101 do alfabeto Σ = { 0, 1 } e y = 1111 do Σ = { 0, 1 } . xy = 01011111
Observar que |xy| = |x| + |y|
Aspectos Formais da Computação
Linguagens
Conjunto de cadeias de um determinado alfabeto
L C Σ*
Exemplos de linguagem sobre o alfabeto Σ = { 0, 1 } :
A linguagem de todas as cadeias que consistem de n 0’s seguidos de n 1’s, ou
seja, L = {ε, 01,0011, 000111, .....}
A linguagem descrita pelo conjunto de cadeias de 0’s e 1’s com nu número igual
de cada um deles, ou seja, L = {ε, 01,10, 0011, 0101, 1001,1010, .....}
A linguagem dos números binários, cujo valor é um número primo
L = { 1, 10, 11, 101, 111, 1011, .....}
A linguagem vazia, ou seja, sem nenhuma cadeia
L={}
A linguagem de cadeias vazias, ou seja cadeias sem símbolos
L = {ε }
A linguagem de todas as cadeias do alfabeto
L = Σ*
Aspectos Formais da Computação
Problemas
Na teoria de autômatos, um problema é decidir se uma dada cadeia é elemento de
alguma linguagem específica
Dado uma cadeia w em Σ* (formado por símbolos de Σ),
definir se w está ou não em L C Σ*
Exemplos de problemas sobre o alfabeto Σ = { 0, 1 } :
Dado um cadeia, verificar se está na linguagem dos números binários, cujo valor
é um número primo
L = { 1, 10, 11, 101, 111, 1011, .....}
Aspectos Formais da Computação
Descrição dos conjuntos
{ w | algo sobre w }
Exemplos de conjuntos :
L = { w | w consiste de igual número de 0’s e 1’s}
L = { w | w é um número inteiro binário primo}
L = { w | w é um programa em C sintaticamente correto}
Outros conjuntos
L = { 0n1n | n ≥ 1 }
L = { 0i1j | 0 ≤ i ≤n j }
Linguagem ou Problema ?
 é a mesma coisa......