Aspectos Formais da Computação CCO 410 Prof. Dr. Sérgio Donizetti Zorzo UFSCar –2006

Aspectos Formais da Computação

CCO 410

Prof. Dr. Sérgio Donizetti Zorzo

UFSCar –2006


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 loucuraAutômatos FinitosExpressões Regulares e LinguagensPropriedades das Linguagens RegularesGramáticas e Linguagens Livre de ContextoAutômatos de PilhaPropriedades de linguagens livres de contextoIntrodução às Máquinas de TuringIndecidibilidadeProblemas IntratáveisOutras classes de problemas


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

BibliografiaHopcroft, J. E.; Ullman, J.D. & Motwani, R. - Introdução à Teoria de Autômatos,

Linguagens e Computação. Editora Campus, 2003. 560p.


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)


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


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.


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


1- Provas DedutivasSequê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.


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

2x ≥ x2 somente se x ≥ 4

2x ≥ x2 se x ≥ 4

Sempre que x ≥ 4, segue-se que 2x ≥ x2

USO DE → PARA INDICAR ENTÃO


Afirmações com quantificadores

para todo

existe

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)

A ordem em que esses quantificadores aparecem afeta o significado da afirmaçã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.


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 inteiroProva1- (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.


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”


2- Provas sobre conjuntosProvas por contradiçãoProvas por contra-exemplo

Provas sobre conjuntosusar 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 F2- 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 )


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


2- Provas sobre conjuntosProvas por contradiçãoProvas por contra-exemplo

Provas por contradição ou contrapositivaToda 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 verdadeiros2) H é verdadeiro e C é falso => a afirmação “Se H então C” é falsa3) H é falso e C é verdadeiro4) H e C são falsos


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


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”


2- Provas sobre conjuntos

Provas por contradição

Provas por contra-exemploServem 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 ”


3- Provas Indutivas

induções sobre inteiros

formas mais gerais de induções sobre inteiros

induções estruturais

induções mútuas


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)”


induções sobre inteirosSuponha 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


Teorema 7: “Σi2 = n ( n+1) (2n+1) / 6, para i variando de 1 a n”

Prova:

1 (base)

2 (etapa de induçã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


3- Provas Indutivas




induções mútuas

formas mais gerais de induções sobre inteiros1- (base) pode-se usar vários casos de base. Isto é, provamos S(i),

S(i+1), ... S(j), para algum j>i


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)


3- Provas Indutivas




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.


3- Provas Indutivas




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.


Conceitos Centrais da Teoria de AutômatosAlfabetoConjunto 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 – cadeiaSequê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


Potência de um AlfabetoConjunto 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 = 01011111Observar que |xy| = |x| + |y|


LinguagensConjunto 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 = Σ*


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 primoL = { 1, 10, 11, 101, 111, 1011, .....}


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 conjuntosL = { 0n1n | n ≥ 1 }L = { 0i1j | 0 ≤ i ≤n j }

Linguagem ou Problema ? é a mesma coisa......

Documents

Aspectos Formais da Computação CCO 410 Prof. Dr. Sérgio Donizetti Zorzo UFSCar –2006