FTC 22/03/2011

// Lembrete pessoal: perdi a ultima aula de conversa com o maciel. Por isso não há anotações do dia 17.

// Revisão da aula passada: (que sorte a minha o professor ter feito isso né?)
CONCEITO
Gramatica:
Uma gramatica é um conjunto de regras para a geração de palavras de uma linguagem.
Cada gramatica possui:
Um alfabeto
Um conjunto de variaveis e,
Um conjunto de regras de substituição.

Esse conjunto de regras, indica que pode-se substituir uma variavel/simbolo ou conjunto destes por outra variavel/simbolo ou conjunto deles.

A notação que expressa estas trocas é:

P => A                    indicando que P pode ser substituido por A (sendo P e A ou uma variavel ou um simbolo)
P => AB                   indicando que P pode ser substituido pela concatenação de A com B (idem para B)
P => 0 | AB | <lambida>   indicando que P pode ser substituido por 0, pela concatenação de AB ou pela palavra <lambida>.
// No caso <lambida> é uma palavra e esta sendo usado aqui por abuso de notação. // Eu acho xP

Tambem pode existir o seguinte caso:

PA => B ou AB => PPA etc, porem esses casos com duas variaveis a esquerda são extremamente confusos e não usaremos eles quase nunca.

A notação para expressar o alfabeto, conjunto de variaveis e variavel inicial de uma gramatica é a seguinte:

G = {{Vari,Aveis},{alfa,beto},NomeDoConjunto de Regras,Variavel de inicio}
// A variavel de inicio pertence ao conjunto de variaveis ja descrito.

// Nota: Para toda linguagem para qual existe um compilador existe uma gramatica.

 * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

CONCEITO:

Problemas de Decisão:

São problemas cuja a resposta final é sim, ou não.
É uma simplificação da amplitude total dos programas possiveis, e pode vir a ser útil em teoremas e coisas do tipo.
Vale notar que todo programa computavel pode ser convertido, sem muita dificuldade para um programa de resposta sim ou não,
basta perguntar esse programa x tem resposta y para tal parametro? resposta: sim ou não.
// Sim é um conceito muito bobo e é perda de tempo definir ele formalmente . . . .
// Imagino que ele deve acabar sendo útil quando o professor quiser usar um teorema, ou uma dessas doideras de matematica.

// O professor enfatizou que nem todos os problemas podem ser adaptados como problemas de decisão, mas é bestera dele. . .
// para qualquer efeito que seja pratico aposto que agente se vira e adapta.

CONCEITO:

Instancia de um problema de decisão é o total de variedades de entradas que se pode receber, tipo, se a entrada é um numero natural teremos tantas instancias quanto numeros naturais, ou seja infinitas instancias.
// Mais um conceito bobo..

CONCEITO:

Solução é um meio pelo qual se encontra uma resposta correta para um problema de decisão (PD), pode-se pensar nisso como um algoritimo.

CONCEITO:

Problema Decidível é aquele que possuí uma solução.
Sendo Indecidível um que não a possua.

// O professor comecou a falar uma boberas a respeito do numero de algoritimos que existem para cada PD,
// de modo que se existem 4 instancias tenho 2^4 algoritimos para solucionar. ja que cada resposta pode ser sim, ou nao.
// e basta pensar q cada algoritimo desse é besta e é tipo uma tabela de respostas, e não algoritimo no conceito coloquial.
// e tambem vale lembrar que apenas um desses algoritimos é a solução do problema né, é tipo tentativa e erro.

CONCEITO:

Restrição de um PD, é gerar um PD a partir de outro restrigindo os valores possiveis dos parametros do primeiro.

Por exemplo o numero N é primo? Nesse caso temos infinitas instancias.
Mas se eu restringir que N é um numero menor que 100, tenho um numero finito de instancias.