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.

• 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 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.