Aula Prática Análise de computabilidade e complexidade de algoritmos
ROTEIRO DE AULA PRÁTICA
NOME DA DISCIPLINA: Análise de Computabilidade e Complexidade de Algoritmos
Unidade: 1 – Teoria da Computabilidade – Programas e Máquinas
Aula: 3 -Máquinas de Registradores – Norma
OBJETIVOS
Definição dos objetivos da aula prática:
Compreender os conceitos e características de uma máquina de Turing e entender a relação de
uma máquina e a aceitação de uma linguagem
SOLUÇÃO DIGITAL:
Não se aplica
PROCEDIMENTOS PRÁTICOS E APLICAÇÕES
Procedimento/Atividade nº 1
Desenvolver uma Máquina de Turing a partir do problema proposto.
Atividade proposta:
A Máquina de Turing (MT) é um dispositivo imaginário que criou a base para a ciência da
computação contemporânea. Pode ser definida como um modelo abstrato de um computador,
que se limita apenas aos aspectos lógicos do seu funcionamento, e não à sua implementação
física. Numa Máquina de Turing é possível modelar qualquer máquina digital. Apesar de a
Máquina de Turing ser um modelo abstrato, sua aplicação prática pode ser vista em diversas
áreas, como (Tiarajú, 2011):
• Estudar a capacidade computacional dos algoritmos, permitindo a definição formal,
apresentando se um problema é computável ou não.
• A MT é usada como base teórica para projetar e analisar linguagens de programação. Ela
auxilia na identificação dos limites da computação e na compreensão da expressividade
e da capacidade de diferentes linguagens.
Público3
• Analisar problemas computacionais e classifica-os de acordo com sua dificuldade. Ela é
usada para estudar classes de complexidade, como P, NP, NP-completo, dentre outras.
• Pode ser utilizada no campo da Inteligência Artificial, sobretudo no que diz respeito à
computação universal e à capacidade de sistemas artificiais de executar tarefas
inteligentes.
Apesar de a Máquina de Turing ser um modelo teórico, sua aplicação prática é ampla e influencia
diversas áreas da computação e da teoria da informação. Ela é uma referência para o estudo e
compreensão da computação e da complexidade computacional.
Uma Máquina de Turing é composta por uma fita que é dividida em células. As células são
utilizadas para armazenar elementos do alfabeto. O cabeçote é o elemento da Máquina de Turing
que realizar a escrita e a leitura dos símbolos da fita, este se movimenta para a esquerda e para
a direita. Os registradores armazenam o estado da MT, ressalta-se que o número de estados
deve ser finito. A função transição indica para a MT qual símbolo escrever, qual direção será
movido o cabeçote (direita ou esquerda) e qual será seu novo estado, dado o símbolo lido e o
estado em que se encontra (Tiarajú, 2011).
Sabendo disso, desenvolva uma Máquina de Turing Determinística para a seguinte Linguagem:
L = {anbn | n>=0}
.
Procedimentos para a realização da atividade:
Analisar as características da Máquina de Turing;
Criar a Máquina de Turing que aceita a linguagem passada (lembrando que é um modelo teórico
baseado em estados e transições);
Testar a Máquina criada com palavras que pertencem a linguagem (Ex: aaabbb);
Testar a Máquina criada com palavras que não pertencem a linguagem (Ex: aabbb, abb, aab;)
Avaliando os resultados:
O desenvolvimento da máquina de Turing para o problema apresentado envolve a definição
precisa de seus componentes: estados, alfabeto da fita, transições, e critérios de aceitação. Os
Público4
estados representam as etapas distintas do processamento da entrada. Cada estado
desempenha uma função específica no reconhecimento ou transformação dos símbolos. O
alfabeto é composto por símbolos de entrada (a, b), símbolos transformados (A, B) e o espaço
vazio (beta).
A criação das regras de transição é importante para garantir que a máquina realize o
balanceamento duplo corretamente. O estado inicial é configurado para identificar o começo da
sequência e transformar os símbolos conforme necessário, movendo o cabeçote para o próximo
símbolo. Estados intermediários são projetados para processar e transformar os símbolos de
entrada, garantindo que a máquina verifique a consistência dos padrões e trate corretamente os
espaços vazios. O estado final sinaliza que a fita foi processada com sucesso. A implementação
dessas transições requer um mapeamento cuidadoso entre os estados e suas respectivas ações,
garantindo que a lógica definida no grafo seja traduzida para o comportamento da máquina.
Checklist:
ü Criar a máquina de Turing;
ü Verificar se é determinística;
ü Testar com valores que pertencem a linguagem;
ü Testar com valores que não pertencem a linguagem.
RESULTADOS
Resultados do experimento:
Ao final dessa aula prática, você deverá enviar um arquivo em pdf contendo a imagem da
Máquina de Turing desenvolvida. O arquivo não pode exceder o tamanho de 2Mb.
Resultados de Aprendizagem:
Como resultados dessa prática será possível compreender como um modelo computacional pode
resolver problemas complexos por meio de operações simples e sequenciais.
Aula Prática Análise de computabilidade e complexidade de algoritmos
