Introdução - teoria da computação - Apresentação

Prévia do material em texto

TEORIA DA COMPUTAÇÃO
AULA 0 - APRESENTAÇÃO
Cristiane Yanase Hirabara de Castro
O QUE É A TEORIA DA COMPUTAÇÃO ??
| Classes de problemas
y Problemas Indecidíveis 
y Problemas Intratáveis
y Problemas Tratáveis
| … o que pode e o que não pode ser computável, 
explicando porque, de que forma e com que 
complexidade.
PROBLEMAS ??
1. Existe programa para solucionar um determinado problema ?
2. Qual o poder de expressão de um determinado modelo de 
especificação ?
3. Dado um programa qualquer, ele sempre tem parada garantida ?
4. Dois programas P1 e P2 são equivalentes entre si ?
5. Uma determinada solução é a melhor solução para um dado 
problema ?
6. Qual o significado de um determinado problema ?
7. Dado um programa qualquer, este programa está correto ?
8. …
9. …
TEORIA DAS LINGUAGENS FORMAIS E 
AUTÔMATOS
y …modelos formais (juntamente com suas propriedades ) 
que fundamentam a ciência da computação. 
y … gramáticas e máquinas abstratas .
y Teoria da computação segundo a ótica da Teoria das 
Linguagens Formais e Autômatos.
TEORIA DA COMPUTAÇÃO ???
| Problema: definir um conjunto de cadeias de símbolos;
| Exemplo: conjunto M dos números binários que têm 2 
dígitos • M={00,01,10,11}
| Porém, se fosse o conjunto N de todas as combinações 
de dígitos binários, poderíamos tentar o seguinte:
y N={0,1,00,01,10,11,000,...}
| Percebe-se que este conjunto é infinito;
TEORIA DAS LINGUAGENS FORMAIS E 
AUTÔMATOS
y …modelos formais (juntamente com suas propriedades ) 
que fundamentam a ciência da computação. 
y … gramáticas e máquinas abstratas .
y Teoria da computação segundo a ótica da Teoria das 
Linguagens Formais e Autômatos.
PORQUE ESTUDAR TEORIA DA 
COMPUTAÇÃO ??
| Procedimento e Algoritmos 
| Representação clara:
y humanos x computador
| Representação Formal X Computador;
| Um objetivo de LFA é estudar uma maneira precisa e 
formal de descrever seqüências de símbolos 
pertencentes à um determinado conjunto;
TEORIA DA COMPUTAÇÃO ???
| Em especial conjuntos que não podem ser trivialmente 
enumerados;
| Os estudos iniciais foram em torno de Linguagens 
Naturais (LN);
| Insucesso: LN é extensa, complexa, não tem sintaxe 
rígida e semântica bem determinada (rica em 
ambigüidade);
TEORIA DA COMPUTAÇÃO ???
| Assim, ela não permite o tratamento computacional;
| Resultados significativos na descrição de linguagens 
computacionais;
|
| Linguagens Computacionais são muito mais simples;
TEORIA DA COMPUTAÇÃO ???
| As maneiras sistemáticas de descrever uma linguagem de 
programação são:
y um método que permite construir programas sintaticamente 
corretos - geração (Gramática);
y um método que permite verificar se um programa escrito está
sintaticamente correto - reconhecimento (Autômatos);
TEORIA DA COMPUTAÇÃO ???
| Pesquisas já demonstraram o uso destas técnicas em: 
y análise de linguagens de programação 
| léxica;
| sintática;
y modelos de sistemas biológicos; 
y desenho de hardware;
TEORIA DA COMPUTAÇÃO ???
| Pesquisas já demonstraram o uso destas técnicas em: 
y análise de linguagens de programação 
| léxica;
| sintática;
y modelos de sistemas biológicos; 
y desenho de hardware;
y relacionamentos com linguagens naturais (sem muito 
sucesso);
CONCLUSÃO
| ENADE
| Tecnologias Bancárias
| Pesquisas Operacionais 
EMENTA
| Estudo das Linguagens Formais e Autômatos, através do 
estudos dos formalismos pertencentes a cada uma das 
linguagens formais. Esses formalismos incluem o estudo 
de gramáticas e máquinas abstratas.
CONTEÚDO PROGRAMÁTICO
| Introdução à Linguagens Formais e Autômatos
| Linguagens Regulares
y Gramática Regular
y Expressão Regular
y Autômatos Finitos
| Linguagens Livre de Contexto
y Gramática Livre de Contexto
y Simplificação de GLC’s
y Ambiguidade em GLC’s
y Autômatos com Pilha
| Linguagens Sensíveis ao Contexto
y Máquinas de Turing
| Linguagens Enumeráveis Recursivamente
y Máquinas de Turing
CRONOGRAMA
| Aula 1 – Conceitos Básicos + Lista 1
| Aula 2 – Autômatos Finitos
| Aula 3 – Expressões Regulares + Lista 3
| Aula 4 – Gramáticas Regulares + Lista 4
| Aula 5 – Dúvidas – Listas 1,2,3 e 4
| Aula 6 – Avaliação 1 
| Aula 7 – Árvores de Derivação + ambiguidade
| Aula 8 – Simplificação + Lista 5 
| Aula 9 – Formas Canônicas + Lista 5
| Aula 10 – Dúvidas - Lista 5 
| Aula 11 – Avaliação 2
| Aula 12 – Autômatos com Pilha
| Aula 13 – Máquinas de Turing
| Aula 14 – Lista 6
| Aula 15 – Dúvidas - Lista 6
| Aula 16 – Avaliação 3
CRITÉRIO DE AVALIAÇÃO
| 3 Avaliações Individuais, 
| Sem consulta
| Pesos: 
y Avaliação 1 – Peso 3,5
y Avaliação 2 – Peso 3,5
y Avaliação 3 – Peso 3
BIBLIOGRAFIA – LIVRO TEXTO
|MENEZES, Paulo Blauth. Linguagens Formais e 
Autômatos. Porto Alegre: Editora Sagra-Luzzatto, 1998;