Computabilidade

Conceitos em Ciência da Computação

Pritesh Patel

Computer Scientist & Data Scientist for over 20 years

O que é computabilidade?

Problema Computável

  • Existência de algoritmo: Existe um procedimento claro.
  • Tempo finito: Produz saída em passos limitados.

Problema Não Computável

  • Não existe algoritmo: Não dá para resolver para todas as entradas.
  • Cálculo infinito: Pode nunca concluir.
1 Problemas não computáveis podem se tornar computáveis quando encontramos um algoritmo e/ou fazemos um algoritmo conhecido terminar em tempo finito.
Conceitos em Ciência da Computação

Autômatos

Definição de Autômatos

  • Máquinas imaginárias
  • Ajudam a entender como a computação funciona
  • Têm estados
  • Têm regras de transição entre estados

Imagem de um semáforo como analogia que representa autômatos

Conceitos em Ciência da Computação

Autômatos Finitos (FA)

Autômatos Finitos (FA)

  • Máquinas simples
  • Número fixo de estados
  • Sem memória além do estado atual

Imagem de um semáforo e estados como analogia para Autômatos Finitos

Conceitos em Ciência da Computação

Autômatos com Pilha (PDA)

Autômatos com Pilha (PDA)

  • Mais poderosos
  • Têm estados
  • Usam uma pilha como memória para decisões mais complexas

Imagem de um semáforo e estados como analogia para Autômatos com Pilha

Conceitos em Ciência da Computação

Resumo

Autômatos Finitos (FA)

  • Úteis para tarefas simples

Autômatos com Pilha (PDA)

  • Mais poderosos para problemas mais complexos

Importância

  • Se um problema pode ser modelado por autômatos, PODEMOS implementar um algoritmo para resolvê-lo
Conceitos em Ciência da Computação

Vamos praticar!

Conceitos em Ciência da Computação

Preparing Video For Download...