Aula Prática Análise de computabilidade e complexidade de algoritmos

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