Teoria da Computação

Máquina de Turing
1. Componentes
  1. Cabeçote
    1. Pode ler e escrever na fita
  2. Tabela de ação
    1. Diz qual símbolo escrever, como mover o cabeçote e qual será seu novo estado
  3. Fita
    1. Arbitrariamente extensível para a esquerda e para a direita
  4. Registrador de estados
    1. Armazena o estado da máquina; há um estado especial denominado estado inicial
2. Definição
  1. Modelo de uma máquina universal capaz de operar com uma sequência de instruções e dados entremeados em uma fita de comprimento infinito
Autômato
1. Autômato finito determinístico
  1. É uma máquina de estados finita onde o próximo estado possível é univocamente determinado
2. Autômato finito não-determinístico
  1. É uma máquina de estados finita onde para cada par de estados e símbolo de entrada pode haver vários próximos estados possíveis.
3. Autômato de pilha
  1. LIFO - Last in, first out - Último a entrar primeiro a sair
Tese de Turing-Church
1. Definição
  1. É uma hipótese sobre a natureza de artefatos mecânicos de cálculos, como computadores, e sobre que tipo de algoritmos eles podem executar
2. Requisitos do algoritmo
  1. Consiste de um conjunto finito de instruções, que são descritas com um número finito de símbolos
  2. Sempre produz resultado em um número finito de passos
  3. Pode, a princípio, ser executado por um ser humano com apenas papel e lápis
  4. A execução não requer inteligência do ser humano
3. Limites da computação
  1. Problemas que jamais poderão ser resolvidos por um computador, independemente da sua velocidade ou memória
    1. Problema da parada, problema da correspondência de Post
  2. Problemas que podem ser resolvidos por um computador, mas requerem um período tão extenso de tempo para completar a ponto de tornar a solução impraticável
    1. Aritimética de Presburger
  3. Casos em que pode ser mais difícil resolver um problema do que verificar cada uma das soluções manualmente
    1. Classes P e NP
Recursão
1. É um método comum de simplificação, onde um problema maior é divido em subproblemas do mesmo tipo e resolvidos dessa forma. Quando o resultado dos subproblemas são unidos o mesmo deverá representar o resultado do problema maior
Definição
1. É um subcampo da ciência da computação e matemática que busca determinar quais problemas podem ser computados em um modelo de computação. Teve início nos primeiros anos do século XX, onde os matemáticos buscavam por um modelo formal da computação.

Nächster

Teoria da Computação

Beschreibung

Zusammenfassung der Ressource

ähnlicher Inhalt

	Erstellt von Alisson Foratto vor etwa 8 Jahre