(31)994408961- RESOLVIDO-Relatorio de Aula Pratica - Analise de Computabilidade e Complexidade de Algoritmos

Prévia do material em texto

Roteiro Aula Prática
ANÁLISE DE COMPUTABILIDADE E COMPLEXIDADE DE ALGORITMOS
Público
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
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
Definição dos objetivos da aula prática:
OBJETIVOS
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úblic2o
· 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úblic3o
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.
Públic4o
image6.png
image7.png
image8.png
image9.png
image10.png
image1.png
image2.png
image3.png
image4.png
image5.png