6480339
Description
Mind Map by Alisson Foratto, updated more than 1 year ago
|
Created by Alisson Foratto
about 8 years ago
|
|
Teoria da Computação
- Máquina de Turing
- Componentes
- Cabeçote
- Pode ler e escrever na fita
- Pode ler e escrever na fita
- Tabela de ação
- Diz qual símbolo escrever, como
mover o cabeçote e qual será seu novo
estado
- Diz qual símbolo escrever, como
mover o cabeçote e qual será seu novo
estado
- Fita
- Arbitrariamente extensível para
a esquerda e para a direita
- Arbitrariamente extensível para
a esquerda e para a direita
- Registrador
de estados
- Armazena o estado da máquina; há um
estado especial denominado estado
inicial
- Armazena o estado da máquina; há um
estado especial denominado estado
inicial
- Cabeçote
- Definição
- 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
- 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
- Componentes
- Autômato
- Autômato finito
determinístico
- É uma máquina de estados finita onde o próximo
estado possível é univocamente determinado
- É uma máquina de estados finita onde o próximo
estado possível é univocamente determinado
- Autômato finito
não-determinístico
- É 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.
- É 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.
- Autômato de pilha
- LIFO - Last in, first out - Último a entrar primeiro a
sair
- LIFO - Last in, first out - Último a entrar primeiro a
sair
- Autômato finito
determinístico
- Tese de Turing-Church
- Definição
- É uma hipótese sobre a natureza de artefatos
mecânicos de cálculos, como computadores, e
sobre que tipo de algoritmos eles podem
executar
- É uma hipótese sobre a natureza de artefatos
mecânicos de cálculos, como computadores, e
sobre que tipo de algoritmos eles podem
executar
- Requisitos do
algoritmo
- Consiste de um conjunto finito de instruções,
que são descritas com um número finito de
símbolos
- Sempre produz resultado
em um número finito de
passos
- Pode, a princípio, ser executado por
um ser humano com apenas papel e
lápis
- A execução não requer
inteligência do ser
humano
- Consiste de um conjunto finito de instruções,
que são descritas com um número finito de
símbolos
- Limites da
computação
- Problemas que jamais poderão ser resolvidos por um
computador, independemente da sua velocidade ou
memória
- Problema da parada, problema
da correspondência de Post
- Problema da parada, problema
da correspondência de Post
- 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
- Aritimética de
Presburger
- Aritimética de
Presburger
- Casos em que pode ser mais difícil resolver um problema do
que verificar cada uma das soluções manualmente
- Classes P e NP
- Classes P e NP
- Problemas que jamais poderão ser resolvidos por um
computador, independemente da sua velocidade ou
memória
- Definição
- Recursão
- É 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
- É 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
- É 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.
- É 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.
Want to create your own Mind Maps for free with GoConqr? Learn more.