p2

Prévia do material em texto

UNIVERSIDADE FEDERAL DO ESPÍRITO SANTO
DEPARTAMENTO DE INFORMÁTICA
Curso de Engenharia de Computação
2a. Avaliação de Algoritmos e Fundamentos da Teoria de Computação (INF09268) – 19/08/2021
Prof. Eduardo Zambon
Instruções:
• Esta avaliação parcial vale 3.0 pontos na média parcial da disciplina.
• Esta avaliação deve ser feita obrigatoriamente em dupla.
• Por se tratar de uma avaliação, assume-se que você só vai discutir as soluções com a sua dupla.
Obviamente, o formato deste semestre não facilita a aplicação dessa regra; esse ponto fica para a
ética e consciência de cada um.
• Envie um arquivo PDF com as suas respostas na tarefa do Classrom até o prazo limite.
• Faça um envio por dupla.
Q1 (1.0 ponto) Construa um Autômato de Pilha (Pushdown Automata – PDA) que aceita a linguagem livre de
contexto L = {aibjck | i+ k = j}, com i, j, k > 0.
Q2 (1.0 ponto) Seja N o conjunto de todos os números naturais e seja A ⊆ N um subconjunto dos naturais.
O conjunto A é dito computável se existe um algoritmo que recebe como entrada um elemento n ∈ N e
decide se n ∈ A ou não. Por outro lado, o conjunto A é dito listável se existe um algoritmo que enumera
exatamente os elementos de A. (Note que não há garantia de alguma ordenação nesta enumeração.) Por
definição, qualquer conjunto computável também é listável.
Considere o problema de decisão abaixo.
Pertinência em um conjunto listável.
Input: um algoritmo EA que enumera os elementos do conjunto listável A; e um natural n ∈ N.
Output: sim; se n ∈ A.
não; caso contrário.
Este problema é decidı́vel, semi-decidı́vel ou indecidı́vel? Justifique adequadamente sua resposta.
Q3 (1.0 ponto) Projete uma Máquina de Turing duas-fitas que transforma números em notação binária em
números equivalentes em notação unária. O número binário de entrada fica na Fita 1 e a saı́da em notação
unária deve ser escrita na Fita 2.
Obs. 1: Se você preferir, você pode descrever a máquina de Turing como um algoritmo, isto é, não é
necessário apresentar o diagrama completo da máquina, só descrever como ela funciona.
A seguir, determine a complexidade de tempo da máquina, justificando adequadamente a sua resposta.
Obs. 2: Não é necessário determinar a fórmula completa da função tcM , somente o seu comportamento
assintótico.
1