Definição de problemas e algoritmos

1. Um robô está na posição da seta. Existe um tesouro escondido em um caixote amarelo, mas no outro há uma armadilha que o deixa preso para sempre. Para saber em que caixote está, pode-se verificar a chave marrom e ler o valor de X. Se X = -1, então o tesouro está em A, mas se X = 1, então o tesouro está em B. Escreva um algoritmo para pegar o tesouro. O robô só entende os seguintes comandos

   • virar à direita
   • virar à esquerda
   • abrir um caixote
   • andar N quadrados
   • ler um valor e
   • pegar o tesouro
   

   a) Identifique todas as partes relacionadas (problema, entrada, saída etc.).

   b) Concorde ou discorde: um algoritmo que abre um caixote antes de ler a chave está bem definido.

2. Escreva um algoritmo para somar dois números decimais inteiros usando somente a tabuada.

3. Execute:

   • Pegue papel em branco e lápis;

   • Desenhe um semicírculo na esquerda;

   • Desenhe outro semicírculo na direita;

   • Desenhe um círculo menor em baixo de de cada semicírculo;

   • Desenhe um semicírculo maior sobre os semicírculos;

   • Pinte os semicírculos pequenos de verde;

   • Pinte o semicírculo grande de laranja;

   a) Que figura você obteve? O procedimento acima é um algoritmo? Explique.

   b) Reescreva o procedimento como um algoritmo bem definido que obtenha o desenho disponível aqui. Atente-se para tamanho, ordem etc.

4. Ana dá uma volta no percurso de corrida do Lago a cada 15 min. Suponha que um amigo comece a correr X minutos mais tarde em um ritmo de Y min por volta. Dados X e Y, Ana e seu amigo irão se encontrar no início da volta antes de uma hora? Quando? Escreva um algoritmo para o problema. Lembre-se de sempre especificar claramente todas as partes relacionadas (problema, entrada, saída etc.)!

5. Em um hospital, é preciso escalar um médico para plantão em cada dia do mês. Sabendo-se que medico é um vetor de dimensão $N$, onde $N$ é o número de médicos e medico[i] é a matrícula do $i$-ésimo médico, queremos construir um novo vetor plantao com 30 posições, onde plantao[j] contém a matrícula do médico escalado para o dia $j$. O objetivo é obter uma escala mais justa possível.

   plantao[1] = medico[1];
   dia = 2;
   enquanto (dia ≤ 30) faça {
       plantao[dia] = plantao[dia - 1];
       dia = dia + 1;
   }
   

   a) Como você descreveria uma escala justa? Descreva a entrada e a saída usando uma linguagem mais formal do que na descrição do problema.

   b) No algoritmo escrito acima, descreva as configurações inicial, após a execução das linhas 1, 2, após a $i$-ésima execução da linha 4, e a configuração final.

   c) Argumente (informalmente ou formalmente) que o algoritmo acima não está correto de acordo com a especificação de saída que você descreveu.

6. Você tem três baldes, identificados como $A$, $B$ e $C$ com capacidades $2$, $7$ e $4$ litros respectivamente. Os baldes $A$ e $C$ estão vazios, enquanto o balde $B$ está cheio de água. Um amigo gostaria de, sem desperdiçar água, separar um litro, mas não há indicadores de medida nos baldes. Ele sugeriu o procedimento abaixo:

   • Despeje água do balde $B$ no balde $A$ até a borda;
   • Despeje metade da água do balde $A$ no balde $C$;
   • Entregue o balde $A$.

   a) Argumente que este procedimento não é um algoritmo; para isso, dê a definição de um algoritmo e descreva suas características.

   b) Depois escreva um algoritmo para o problema.

Decidibilidade

Atenção: as questões abaixo tratam de conteúdos que não discutimos em sala e estão disponíveis apenas para referência.

1. Leia:

   Como regra básica que dominou a computação, a lei de Moore afirma que o número de transístores de um chip de microprocessador irá dobrar a cada dois anos — o que em geral significa que a velocidade também irá dobrar. (...) Não por muito tempo. Esse ritmo já começou a decair, graças ao aquecimento que é inevitável quando mais e mais circuitos de silícios são espremidos em uma pequena área. (...)

   The chips are down for Moore’s law, Nature, 9 de fevereiro de 2016 (adaptado).

   Considerando o excerto, disserte brevemente sobre: “mesmo que a lei de Moore não chegasse ao fim, ainda há problemas que não poderíamos resolver”. No seu texto, defina problemas indecidíveis e problemas intratáveis, explicando a diferença entre eles.

2. Concorde ou discorde: “O problema de decidir se dois números racionais são iguais é indecidível, já que existem infinitas formas de escrever um mesmo número.”

   Justifique considerando a seguinte questão: como podemos mostrar que um problema é decidível (resolvível)?