Projeto 1: exercícios validados

Situação atual: este projeto está em construção. Novos problemas serão propostos conforme os conteúdos correspondentes forem apresentados nas aulas. Neste momento, somente as opções 1, 2, 3, 7, 8 e 9 estão liberadas.

Escolha do problema

• Cada grupo escolhe somente um problema e desenvolve apenas a opção escolhida.
• Dois grupos não podem escolher o mesmo problema. A escolha será registrada com o professor durante a apresentação das opções à turma.

Use a tabela para localizar a opção escolhida e leia sua seção completa. A linguagem e as bibliotecas são livres. As estruturas e técnicas indicadas devem participar efetivamente da solução, mas o grupo pode adaptar implementações estudadas nas aulas. Uma coleção baseada em vetor não substitui uma estrutura encadeada quando o enunciado exigir encadeamento.

Opção	Problema	Conteúdo central
1	Robô de inspeção em um armazém	Fila encadeada e expansão por distância
2	Colorização automática de regiões	Pilha encadeada e uma cor por região
3	Colorização automática por camadas	Fila encadeada e lista circular de cores com representação livre
7	Redução de uma suíte de testes	Força bruta e estratégia gulosa
8	Substituição em cache com acessos conhecidos	Estratégia gulosa e comparação com fila FIFO
9	Equivalência de regras booleanas	Força bruta e pilha encadeada

Boa prática interna: recomenda-se que cada grupo registre como compilar e executar seu programa. Essa documentação serve somente para a organização dos integrantes e não precisa ser apresentada nem entregue ao professor.

Opção 1: robô de inspeção em um armazém

Objetivo

Implemente uma simulação que encontre uma rota com a menor quantidade de movimentos entre a posição inicial de um robô e um ponto de inspeção. Prateleiras e áreas interditadas impedem a passagem.

O projeto simula o deslocamento em software. Não é necessário construir ou controlar um robô físico.

Modelagem do problema

Represente o armazém por uma matriz com L linhas e C colunas. Cada posição (l, c) contém uma célula livre ou um obstáculo.

Duas células são vizinhas quando compartilham um lado. Portanto, a partir de (l, c), os únicos movimentos possíveis são (l - 1, c), (l + 1, c), (l, c - 1) e (l, c + 1), desde que a nova posição permaneça dentro da matriz e esteja livre.

Uma rota válida é uma sequência de células livres que começa na origem, termina no destino e usa somente movimentos entre células vizinhas. O custo da rota é a quantidade de movimentos, equivalente à quantidade de transições entre células consecutivas. O programa deve minimizar esse custo.

Use uma fila encadeada para organizar as posições pendentes em ordem não decrescente de distância à origem. Cada posição deve entrar na fila no máximo uma vez.

Entrada

Use, no mínimo, o seguinte modelo de dados:

• L e C, com valores entre 1 e 30;
• uma matriz com L linhas e C colunas;
• uma coordenada de origem;
• uma coordenada de destino.

No formato textual de referência, . representa uma célula livre e # representa um obstáculo. As coordenadas começam em zero, (0, 0) identifica o canto superior esquerdo, a linha aumenta para baixo e a coluna aumenta para a direita.

5 7
.......
...#...
...#...
...#...
.......
2 0
2 6

A origem e o destino devem estar dentro da matriz e sobre células livres.

Regras essenciais

• O robô pode mover uma célula para cima, para baixo, para a esquerda ou para a direita. Movimentos diagonais são proibidos.
• Cada movimento custa uma unidade. O robô não pode atravessar obstáculos nem sair da matriz.
• O mapa permanece fixo durante a busca.
• A fila usada na expansão deve ser explicitamente encadeada.
• A solução pode apresentar qualquer rota mínima quando houver empate.
• Quando origem e destino coincidirem, a rota possui zero movimentos.
• Quando não existir rota, o programa deve informar essa condição sem apresentar um percurso parcial como resposta.

Saída obrigatória

Mostre o mapa com a rota identificada e informe a quantidade de movimentos. A exibição pode usar caracteres no terminal, desde que origem, destino, obstáculos, rota e posições livres permaneçam distinguíveis.

Para a entrada de referência, uma saída válida contém uma rota com 10 movimentos. Outra rota também será aceita se respeitar o mapa e possuir o mesmo custo mínimo.

Exemplo visual de entrada e saída

No exemplo, S identifica a origem (2, 0), D identifica o destino (2, 6) e os blocos escuros representam obstáculos. A saída destaca uma das rotas mínimas: o robô contorna os obstáculos pela parte superior e chega ao destino após 10 movimentos.

Casos para verificar

• Um mapa com obstáculos, desvios e mais de uma rota possível: confira que o percurso escolhido é mínimo.
• Um destino separado da origem por obstáculos: confira a indicação de ausência de rota.
• Origem e destino iguais: confira o resultado com zero movimentos.

Limite do projeto

Considere um robô e um destino por execução. Não são exigidos múltiplos pontos de visita, obstáculos em movimento, custos variáveis, animação ou representação explícita do mapa como grafo.

Opção 2: colorização automática de regiões

Objetivo

Implemente um programa que pinte automaticamente as regiões brancas de um desenho. Cada região inteira deve receber uma única cor pseudoaleatória. Use uma pilha encadeada para controlar a expansão da pintura.

Modelagem do problema

Represente a imagem por uma matriz de pixels. Cada pixel de entrada é exatamente preto ou branco.

Considere dois pixels brancos conectados quando existe entre eles uma sequência formada somente por pixels brancos e movimentos para cima, para baixo, para a esquerda ou para a direita. Pixels que se tocam apenas pela diagonal não estão conectados por esse contato.

Uma região é um conjunto máximo de pixels brancos conectados. A palavra máximo significa que nenhum outro pixel branco pode ser acrescentado ao conjunto pelas regras de conexão. A saída deve manter os pixels pretos e substituir todos os pixels brancos de uma mesma região por uma única cor válida.

Use uma pilha encadeada para armazenar os pixels pendentes da região atual. A próxima posição processada deve ser a última inserida. Termine uma região antes de iniciar a seguinte.

Entrada

O programa deve receber o caminho de um arquivo PNG de entrada e o caminho do arquivo PNG de saída. A imagem deve ser opaca, possuir dimensões positivas e conter somente pixels pretos ou brancos.

Verifique essas propriedades depois de decodificar a imagem. A codificação interna do PNG pode usar, por exemplo, escala de cinza, RGB, RGBA ou paleta indexada. Não rejeite um arquivo somente pela forma como o PNG armazena as cores. Ele é válido para este problema quando os pixels decodificados são opacos e cada pixel resulta exatamente em preto ou branco. Qualquer transparência torna a entrada inválida, inclusive quando ela estiver definida na paleta, em vez de aparecer em um canal alfa separado.

O formato de execução de referência é:

programa entrada.png saida.png [semente]

A semente pseudoaleatória é opcional e, quando usada, deve ser um inteiro entre 0 e 4.294.967.295. Repetir a execução com a mesma imagem e a mesma semente deve produzir as mesmas cores.

Cada cor pode ser representada por três componentes RGB inteiros entre 0 e 255. Preto corresponde a (0, 0, 0) e branco corresponde a (255, 255, 255). Para os testes iniciais, o programa deve aceitar imagens de até 128 por 128 pixels.

Apoio opcional: o exemplo de leitura, alteração de pixels e gravação recebe uma imagem, altera seus pixels e salva um arquivo PNG. Baixe também os demais arquivos da pasta de suporte de imagens, incluindo a pasta vendor. O exemplo está em C, mas a linguagem da solução permanece livre.

Regras essenciais

• Preserve todos os pixels pretos.
• Pinte todos os pixels brancos, inclusive os localizados nos limites da imagem.
• Todos os pixels da mesma região devem receber a mesma cor.
• A cor deve ser diferente de preto e branco.
• Regiões diferentes podem receber a mesma cor.
• Ao consultar vizinhos, considere somente coordenadas existentes na matriz.
• Cada pixel deve entrar na pilha no máximo uma vez.
• A pilha deve ser explícita e encadeada. Usar somente chamadas recursivas não atende a esta opção.
• Se o arquivo não cumprir o contrato de entrada, informe o motivo e não produza uma imagem parcial como resultado.

Saída obrigatória

Salve no caminho solicitado uma imagem PNG colorida com as mesmas dimensões da entrada. Informe no terminal a quantidade total de regiões pintadas e preserve todos os pixels pretos.

Como as cores podem ser pseudoaleatórias, duas execuções podem produzir cores diferentes. O número de regiões, a separação entre elas e os pixels preservados devem permanecer iguais.

Casos para verificar

• Uma região com formato irregular: confira que toda a região recebe uma única cor e que a pintura não atravessa pixels pretos.
• Várias regiões, incluindo pixels que se tocam apenas pela diagonal: confira a separação correta.
• Uma região que alcança algum limite da imagem: confira que todos os pixels brancos conectados são pintados sem acessar posições externas à matriz.

Exemplos de entrada e saída

As cores das saídas são ilustrativas. Outra saída é válida se preservar os pixels pretos, pintar cada região inteira com uma única cor permitida e informar a mesma quantidade de regiões.

Caso	Entrada binária	Exemplo de saída válida
Região irregular
Contato diagonal
Região na borda

Limite do projeto

Use imagens binárias preparadas, sem pixels cinza e sem transparência. Não são exigidos reconhecimento de objetos, classificação de fundo ou cores diferentes entre regiões vizinhas.

Opção 3: colorização automática por camadas

Objetivo

Implemente um programa que pinte as regiões brancas de um desenho com camadas de cores que se repetem conforme a distância ao início da região. Use uma fila encadeada para expandir a pintura e uma lista circular de cores, com representação livre, para organizar a paleta.

Modelagem do problema

Represente a imagem por uma matriz de pixels pretos e brancos. Dois pixels brancos são vizinhos quando compartilham um lado, isto é, quando um está imediatamente acima, abaixo, à esquerda ou à direita do outro. Cada conjunto máximo de pixels brancos conectados por esses movimentos forma uma região. Contato apenas diagonal não conecta pixels.

Localize as regiões percorrendo as linhas de cima para baixo e, em cada linha, as colunas da esquerda para a direita. O primeiro pixel branco ainda não pintado encontrado nessa varredura será o início s da região.

Para cada pixel p da região, defina d(p) como a menor quantidade de movimentos válidos entre s e p, sem sair da região. Se a paleta ordenada contém m cores, numere suas posições de 0 a m - 1. Escolha a posição da cor por d(p) mod m.

mod significa resto da divisão inteira. Com três cores, os restos possíveis da divisão por 3 são 0, 1 e 2. Por isso, as distâncias 0, 1 e 2 usam as três cores, a distância 3 volta à posição 0, a distância 4 usa a posição 1 e o ciclo continua.

Use uma fila encadeada para processar os pixels por distância. A paleta deve se comportar como uma lista circular: depois da última cor, volte à primeira. Sua representação interna é livre e não precisa ser encadeada. Reinicie o uso da paleta na primeira cor ao começar cada região.

Entrada

O programa deve receber, nesta ordem:

• o caminho de um arquivo PNG de entrada, opaco, com dimensões positivas e pixels somente pretos ou brancos;
• o caminho do arquivo PNG de saída;
• uma sequência ordenada com pelo menos duas entradas de cor no formato R,G,B.

Cada componente R, G e B deve ser um inteiro entre 0 e 255. Nenhuma entrada da paleta pode ser preta (0,0,0) nem branca (255,255,255). Entradas iguais na paleta são permitidas, embora produzam camadas visualmente iguais. Para os testes iniciais, o programa deve aceitar imagens de até 128 por 128 pixels.

O formato de execução de referência é:

programa entrada.png saida.png R1,G1,B1 R2,G2,B2 [outras cores]

O apoio de leitura e gravação de imagens indicado na opção 2 também pode ser usado nesta opção.

Regras essenciais

• Preserve todos os pixels pretos e pinte todos os pixels brancos.
• Considere apenas vizinhos por cima, por baixo, pela esquerda e pela direita.
• Use a menor distância dentro da própria região.
• Troque a cor ao avançar de uma camada de distância, não a cada pixel processado.
• Marque cada pixel para impedir inserções repetidas e ciclos de processamento.
• A fila deve ser explícita e encadeada.
• A paleta deve preservar a ordem recebida e repetir as cores circularmente. Ela pode ser representada por um vetor e um índice.
• Cada nova região deve começar na primeira cor da paleta.
• Se o arquivo ou a paleta não cumprir o contrato de entrada, informe o motivo e não produza uma imagem parcial como resultado.

Saída obrigatória

Salve no caminho solicitado uma imagem PNG colorida com as mesmas dimensões da entrada. Informe a quantidade de regiões pintadas e liste uma vez a paleta recebida, na ordem original. Preserve todos os pixels pretos.

O resultado apresenta faixas discretas de cor. Não é necessário suavizar a transição entre as camadas.

Casos para verificar

• Uma região com mais camadas do que cores: confira o retorno à primeira cor e a uniformidade de cada camada.
• Várias regiões separadas: confira a pintura independente e o reinício da paleta.
• Uma região que alcança algum limite da imagem: confira a pintura completa sem acessar posições externas à matriz.

Exemplo visual do módulo e da pintura

A figura mostra uma região branca de 4 por 4 pixels, uma paleta circular com três cores e a correspondência entre distância, resto da divisão e cor. A grade, os números e o contorno são anotações didáticas e não fazem parte da imagem processada.

Limite do projeto

Use imagens binárias preparadas, sem pixels cinza e sem transparência. Não são exigidos reconhecimento de objetos, cores aleatórias, transições suaves ou cores diferentes entre regiões vizinhas.

Opção 7: redução de uma suíte de testes

Contexto

Em software, um requisito descreve um comportamento ou uma condição que o sistema deve atender. Um caso de teste, chamado de teste neste projeto, descreve uma situação usada para verificar um ou mais requisitos. Uma suíte de testes é o conjunto de testes já disponível para verificar o sistema.

A relação entre testes e requisitos pode ocorrer em ambas as direções. Um teste pode cobrir vários requisitos, e um requisito pode ser coberto por vários testes. Quando dois ou mais testes cobrem o mesmo requisito, existe redundância de cobertura.

Suítes grandes podem exigir mais tempo para serem executadas e analisadas. A redução busca selecionar uma parte dos testes existentes que mantenha todos os requisitos cobertos. Neste projeto, os testes são considerados previamente definidos. O programa não decide quais testes devem ser implementados nem executa testes reais. Ele recebe a relação de cobertura e decide quais testes selecionar.

O modelo usa uma simplificação: um valor 1 na matriz informa que o teste fornece a cobertura necessária para considerar aquele requisito coberto. Na prática, essa informação isolada não comprova que o requisito foi completamente validado nem garante a detecção de defeitos.

Objetivo

Implemente duas estratégias para reduzir uma suíte de testes já existente. A estratégia exata por força bruta deve encontrar uma seleção válida com a menor quantidade possível de testes. A estratégia gulosa deve construir uma seleção conforme a regra definida neste enunciado. Compare os resultados obtidos pelas duas estratégias.

O programa processa uma relação de cobertura fornecida na entrada. Não é necessário executar testes de um software real nem medir cobertura de código.

Modelagem do problema

Considere o conjunto de requisitos $R = \{r_1, r_2, \ldots, r_m\}$ e o conjunto de testes $T = \{t_1, t_2, \ldots, t_n\}$. O índice $i$, entre $1$ e $n$, identifica a posição de cada teste no conjunto $T$.

Para cada teste $t_i$, a função $C(t_i)$ indica o subconjunto de requisitos cobertos por esse teste. Por exemplo, $C(t_2) = \{r_1, r_3\}$ significa que o teste $t_2$ cobre os requisitos $r_1$ e $r_3$.

Uma seleção $S \subseteq T$ é válida quando as coberturas dos testes escolhidos, consideradas em conjunto, incluem todos os requisitos:

$$\bigcup_{t_i \in S} C(t_i) = R$$

Em palavras, a expressão afirma que, para cada requisito de $R$, existe pelo menos um teste selecionado em $S$ que o cobre. Como $C(t_i)$ contém somente requisitos pertencentes a $R$, a união é igual a $R$ quando nenhum requisito fica descoberto.

Cada teste possui custo igual a uma unidade. Portanto, o custo de $S$ é sua quantidade de testes, indicada por $|S|$. Uma solução ótima é uma seleção válida com o menor $|S|$ possível, isto é, o menor número de testes que, em conjunto, cobrem todos os requisitos.

Represente a relação de cobertura por uma matriz binária. Cada linha corresponde a um teste, cada coluna corresponde a um requisito, 1 significa que o teste cobre o requisito e 0 significa que não cobre.

Entrada

Use obrigatoriamente o seguinte formato textual, recebido pela entrada padrão ou por um arquivo de texto:

1. primeira linha: quantidade n de testes e quantidade m de requisitos;
2. segunda linha: os m identificadores dos requisitos, na ordem das colunas;
3. próximas n linhas: identificador do teste seguido por m valores binários.

Considere de 1 a 15 testes e de 1 a 20 requisitos. Identificadores não podem conter espaços nem se repetir dentro do próprio conjunto.

4 5
R1 R2 R3 R4 R5
T1 1 1 0 0 0
T2 0 0 1 1 0
T3 0 0 0 0 1
T4 1 0 1 0 1

Nesse exemplo, T1 cobre R1 e R2, enquanto T4 cobre R1, R3 e R5. A matriz fornece toda a informação necessária sobre abrangência. O programa não precisa descobrir o que cada teste cobre.

Exemplo visual de seleções candidatas

A figura compara três seleções para a matriz de referência. A primeira cobre todos os requisitos, mas usa um teste desnecessário. A segunda deixa R4 descoberto e, por isso, é inválida. A terceira cobre todos os requisitos com três testes e é ótima, pois nenhuma seleção com apenas dois testes cobre as cinco colunas. A figura não associa as seleções às estratégias e não antecipa uma conclusão geral sobre a estratégia gulosa.

Regras essenciais

• Um requisito está coberto quando pelo menos um teste selecionado possui 1 na coluna correspondente.
• Cobrir o mesmo requisito várias vezes não reduz o custo nem fornece benefício adicional.
• Cada teste pode ser selecionado no máximo uma vez.
• A força bruta deve examinar os subconjuntos de testes e garantir uma solução com quantidade mínima quando a cobertura completa for possível.
• A estratégia gulosa deve escolher, a cada passo, o teste que cobre a maior quantidade de requisitos ainda não cobertos.
• A contribuição gulosa deve ser recalculada depois de cada escolha.
• Em empate na estratégia gulosa, escolha o primeiro teste na ordem da entrada.
• Antes de executar as estratégias, verifique se cada requisito aparece em pelo menos um teste. Quando uma coluna possui somente zeros, a cobertura completa é impossível.
• Em empate entre soluções exatas mínimas, qualquer uma será aceita.
• Se a entrada violar quantidades, identificadores ou valores definidos no contrato, informe o motivo e não execute as estratégias.

Saída obrigatória

Mostre, separadamente, os testes escolhidos e a quantidade usada por cada estratégia. Na solução exata, apresente os identificadores na ordem em que aparecem na entrada. Na solução gulosa, apresente os identificadores na ordem em que foram escolhidos. Compare a quantidade da seleção gulosa com a quantidade mínima encontrada por força bruta. Se houver diferença, informe quantos testes adicionais foram selecionados.

Para a entrada de referência, uma saída semanticamente equivalente a esta é esperada:

Forca bruta: 3 testes, T1 T2 T3
Guloso: 3 testes, T4 T1 T2
Quantidade do guloso igual ao minimo: sim
Testes adicionais: 0

Se a cobertura completa for impossível, não execute as duas estratégias. Liste, na ordem da entrada, todos os requisitos que não aparecem em teste algum. Não mostre nem classifique uma seleção parcial como solução.

Análise obrigatória

Determine se a regra gulosa definida neste enunciado sempre garante uma seleção com quantidade mínima. Justifique a conclusão com uma demonstração válida ou com uma entrada que funcione como contraexemplo. Se usar um contraexemplo, apresente a matriz e as saídas das duas estratégias. Uma única entrada em que as quantidades coincidem não demonstra o comportamento para todas as entradas possíveis.

Casos para verificar

Além da entrada de referência, crie e execute no mínimo três entradas próprias:

• uma suíte com sobreposição e redundância entre as coberturas;
• uma suíte com pelo menos um requisito impossível de cobrir;
• um caso-limite válido, como uma suíte com um teste e um requisito.

Para cada entrada criada, registre a entrada, a saída obtida e uma verificação manual curta dos requisitos cobertos pela seleção. Compare o resultado esperado antes da execução com o resultado produzido pelo programa. Crie outras entradas quando forem necessárias para sustentar a análise obrigatória.

Limite do projeto

O núcleo do projeto inclui ler e validar a matriz, executar as duas estratégias, comparar os resultados e verificar o programa com entradas criadas pelo grupo. Use somente a matriz como fonte da relação de cobertura.

Não são exigidos análise do código-fonte de outro software, implementação ou execução de testes reais, medição automática de cobertura, prioridades, custos diferentes entre testes ou garantia de detecção de defeitos. Os casos criados pelo grupo podem ser arquivos de texto simples. Não é necessário implementar um framework de testes automatizados.

Opção 8: substituição em cache com acessos conhecidos

Contexto

Uma memória cache é um armazenamento pequeno e de acesso rápido que mantém cópias de itens usados pelo sistema. Quando um item solicitado já está na cache, o acesso pode ser atendido sem buscar novamente esse item em um armazenamento mais lento.

Neste projeto, a cache é apenas uma simulação. Ela possui c posições, também chamadas de espaços. Cada item ocupa exatamente uma posição, independentemente de seu identificador. Carregar um item significa colocar uma cópia dele em uma posição da cache. Remover um item apaga somente essa cópia simulada. O item continua disponível fora da cache e pode ser carregado novamente em um acesso posterior.

Um acesso é uma solicitação por um item. O acesso produz um acerto quando o item já está na cache e uma falta quando ele não está. Em um sistema real, uma falta tende a exigir uma busca mais lenta. O modelo representa esse trabalho atribuindo custo de uma unidade a cada falta e custo zero a cada acerto. Portanto, minimizar as faltas representa reduzir as buscas no armazenamento mais lento.

Uma política de substituição define qual item deve ser removido quando ocorre uma falta e todas as posições da cache já estão ocupadas. As duas políticas comparadas neste projeto são a ótima offline e a FIFO. A sigla FIFO significa first in, first out, ou primeiro a entrar, primeiro a sair.

Objetivo

Implemente duas simulações independentes para a mesma sequência de acessos. A primeira deve usar a política ótima offline, baseada em uma estratégia gulosa. A segunda deve usar a política FIFO, implementada com uma fila encadeada. Compare as quantidades de acertos e faltas.

No modelo offline, a sequência completa de acessos é conhecida antes do início da simulação. Por isso, a política ótima offline pode consultar os acessos futuros ao escolher um item para remoção. Essa possibilidade serve como referência teórica e não representa uma cache real capaz de prever o futuro.

Modelagem do problema

Considere a sequência $A = (a_1, a_2, \ldots, a_n)$, formada por n acessos, e uma cache com capacidade c. O símbolo $a_i$ identifica o item solicitado no acesso de índice $i$, entre 1 e n. Um mesmo identificador pode aparecer várias vezes na sequência.

Antes do primeiro acesso, a cache está vazia. Ao processar $a_i$:

• ocorre um acerto quando $a_i$ já está na cache. O estado permanece inalterado;
• ocorre uma falta quando $a_i$ não está na cache. Uma cópia de $a_i$ deve ser carregada;
• quando existe uma posição livre, $a_i$ entra nessa posição sem remover outro item;
• quando as c posições estão ocupadas, a política escolhe um item para remoção antes da entrada de $a_i$.

Depois de cada acesso, o item solicitado deve estar na cache. As políticas ótima offline e FIFO devem receber a mesma sequência, mas cada simulação começa novamente com a cache vazia. Os estados das duas simulações são independentes.

Entrada

Use obrigatoriamente o seguinte formato textual, recebido pela entrada padrão ou por um arquivo de texto:

1. primeira linha: capacidade c e quantidade n de acessos;
2. segunda linha: os n identificadores inteiros, na ordem dos acessos.

Considere 1 <= c <= 5 e 10 <= n <= 30.

3 12
1 2 3 4 1 2 5 1 2 3 4 5

Considere inválida uma entrada cuja capacidade ou quantidade de acessos esteja fora dos limites, que contenha um valor não inteiro ou cuja segunda linha não possua exatamente n identificadores. Por exemplo, declarar n = 12 e fornecer somente 11 identificadores viola o contrato. Informe o motivo e não inicie nenhuma simulação.

Regras essenciais

Política ótima offline. Em uma falta com a cache cheia, consulte somente o trecho da sequência posterior ao acesso atual:

1. se algum item da cache não aparecer novamente, remova um desses itens;
2. se todos reaparecerem, remova aquele cujo próximo acesso estiver mais distante no futuro.

Essa regra é uma estratégia gulosa porque toma, em cada substituição, a decisão que preserva por mais tempo os itens que serão necessários primeiro. Nas condições do modelo offline, ela produz a menor quantidade possível de faltas. Não é necessário demonstrar formalmente essa propriedade.

Represente essa cache por c posições lógicas numeradas de 0 a c - 1. Um item novo ocupa a posição livre de menor índice. Quando vários itens armazenados não aparecerem novamente, remova aquele que estiver na posição lógica de menor índice. O item solicitado ocupa a mesma posição do item removido. Essas regras de desempate tornam o traço reproduzível.

Política FIFO. Mantenha os itens em uma fila encadeada, do item armazenado há mais tempo para o item armazenado há menos tempo. Em uma falta:

• se existir espaço livre, insira o item solicitado no final da fila sem remover outro item;
• se a cache estiver cheia, remova o item da frente e insira no final o item que produziu a falta.

O item removido deixa de fazer parte da cache e não assume outro papel na simulação. Se ele for solicitado novamente, ocorrerá uma nova falta. Um acerto não move o item nem altera sua posição na fila.

Em ambas as políticas:

• cada acesso deve ser classificado uma única vez como acerto ou falta, portanto a soma do total de acertos + total de faltas deve ser igual a n;
• um acerto não cria outra cópia do item;
• a quantidade de itens nunca pode superar c;
• o item solicitado deve estar na cache depois de cada acesso;
• uma remoção ocorre somente quando existe uma falta e a cache já contém c itens;
• identificadores podem se repetir na sequência, mas a cache não pode conter duas cópias do mesmo item;
• entradas inválidas devem produzir somente uma mensagem com o motivo do erro.

A fila encadeada é obrigatória na política FIFO. A representação da cache ótima pode usar as posições lógicas descritas acima.

Saída obrigatória

Mostre os totais de acertos e faltas de cada política. Para sequências com até 15 acessos, mostre também, depois de cada acesso, o item solicitado, se ocorreu acerto ou falta, o item removido quando houver remoção e o estado resultante da cache. Mostre a cache ótima pela ordem crescente das posições lógicas. Mostre a FIFO do item mais antigo para o mais recente. Para sequências maiores, somente os totais são obrigatórios.

Para a entrada de referência, uma saída resumida semanticamente equivalente a esta é esperada:

Otima offline: 5 acertos, 7 faltas
FIFO: 3 acertos, 9 faltas

Exemplo visual do traço das duas políticas

A figura mostra os 12 acessos da entrada de referência. Na cache ótima offline, o estado apresenta as posições lógicas 0, 1 e 2. Na FIFO, o estado apresenta os itens do mais antigo para o mais recente. O símbolo - indica que nenhum item foi removido, e o símbolo · indica uma posição ainda vazia.

Casos para verificar

Os casos abaixo são verificações obrigatórias do programa. A entrada de referência já verifica uma sequência em que a política ótima offline produz menos faltas que a FIFO. Além dela, crie e execute no mínimo três entradas próprias:

• Capacidade suficiente: use no máximo c identificadores distintos e repita os acessos até alcançar o mínimo de 10. Confira que somente a primeira ocorrência de cada identificador produz falta e que nenhuma remoção ocorre. Esse caso artificial verifica o comportamento quando a cache nunca fica sem espaço para um item novo.
• Um único item: use c = 1 e repita o mesmo identificador pelo menos 10 vezes. Confira uma falta inicial seguida somente por acertos. Esse caso verifica que um acerto não cria duplicatas, não remove o item e não altera o estado.
• Entrada inválida: crie uma entrada que viole uma das quantidades declaradas. Confira que o programa informa o motivo e não apresenta resultados parciais de nenhuma política.

Para cada entrada criada, registre a entrada, a saída obtida e uma verificação manual curta do estado esperado. Compare essa previsão com o resultado produzido pelo programa.

Limite do projeto

O núcleo do projeto inclui ler e validar a sequência, simular separadamente as duas políticas, manter a fila encadeada da FIFO, produzir os traços exigidos e verificar o programa com entradas criadas pelo grupo.

O modelo contém uma única cache inicialmente vazia por política. Não se exigem cache física, medição de tempo real, itens de tamanhos diferentes, operações de escrita, vários níveis de memória, previsão de acessos, processamento online ou otimizações para entradas grandes.

Opção 9: equivalência de regras booleanas

Contexto

Uma regra booleana combina condições que podem assumir somente os valores falso, representado por 0, e verdadeiro, representado por 1. O resultado da regra também é 0 ou 1. Regras desse tipo podem representar, por exemplo, critérios de acesso, filtros ou condições de decisão de um programa.

Duas regras são equivalentes quando produzem o mesmo resultado para toda atribuição possível de valores às suas variáveis. Em uma tabela verdade completa, isso significa que as colunas de resultado das duas regras são iguais em todas as linhas. As expressões podem ter textos diferentes e ainda serem equivalentes.

Verificar equivalência permite confirmar que uma regra reescrita preserva o comportamento da original. Uma única atribuição com resultados diferentes comprova que as regras não são equivalentes. Essa atribuição recebe o nome de contraexemplo. Para confirmar a equivalência, todas as atribuições precisam produzir resultados iguais.

Objetivo

Implemente um programa que verifique se duas regras booleanas são equivalentes. Use força bruta para gerar todas as atribuições possíveis das variáveis. Para cada atribuição, use uma pilha encadeada para calcular separadamente o resultado de cada expressão.

Essas operações cumprem funções diferentes. A força bruta determina quais valores serão atribuídos às variáveis em cada tentativa. A pilha processa os tokens de uma expressão e calcula um único resultado para a atribuição atual. Depois das duas avaliações, o programa compara os resultados.

Quando as regras não forem equivalentes, apresente uma combinação de valores que comprove a diferença.

Modelagem do problema

Cada variável representa uma condição falsa, indicada por 0, ou verdadeira, indicada por 1. Uma atribuição associa exatamente um desses valores a cada variável declarada. Com n variáveis, existem $2^n$ atribuições possíveis.

Cada expressão é formada por tokens, isto é, unidades separadas por espaços. Em A B AND, os tokens são A, B e AND. Os tokens permitidos são:

• variáveis declaradas por letras maiúsculas de A a Z;
• constantes booleanas 0 e 1, que mantêm seus valores em todas as atribuições;
• operador unário NOT;
• operadores binários AND e OR.

Variáveis e constantes são operandos, pois fornecem valores. NOT, AND e OR são operadores, pois transformam esses valores.

A entrada usa notação pós-fixa, na qual o operador aparece depois de seus operandos. Por exemplo, a expressão usual (A AND B) OR (NOT A) é escrita como A B AND A NOT OR. A notação pós-fixa não é universalmente melhor que a notação usual. Ela foi escolhida porque determina a ordem das operações sem parênteses ou regras de precedência e permite uma avaliação direta com pilha.

Avalie cada expressão da esquerda para a direita e inicie cada avaliação com uma pilha vazia:

• ao encontrar uma variável, consulte o valor dela na atribuição atual e empilhe esse valor, não a letra;
• ao encontrar 0 ou 1, empilhe diretamente o valor da constante;
• ao encontrar NOT, desempilhe um valor, negue esse valor e empilhe o resultado;
• ao encontrar AND ou OR, desempilhe o operando da direita e depois o da esquerda, aplique o operador e empilhe o resultado.

Uma expressão válida termina com exatamente um valor na pilha. Esse valor é o resultado da expressão para a atribuição atual.

Entrada

Use obrigatoriamente o seguinte formato textual, recebido pela entrada padrão ou por um arquivo de texto:

1. primeira linha: quantidade n de variáveis, entre 0 e 10;
2. segunda linha: n variáveis distintas separadas por espaços;
3. terceira linha: primeira expressão pós-fixa;
4. quarta linha: segunda expressão pós-fixa.

Cada expressão pode conter até 50 tokens, contados pelas unidades separadas por espaços. Por exemplo, A B AND possui três tokens.

Quando n for zero, represente a lista vazia de variáveis por uma linha vazia ou por -. Nesse caso, existe $2^0 = 1$ atribuição, a atribuição vazia, e as expressões podem usar somente as constantes 0 e 1 e os operadores permitidos.

2
A B
A B AND
A B OR

Regras essenciais

• Use a mesma atribuição nas duas expressões durante cada comparação. Se A = 1 na atribuição atual, toda ocorrência de A nas duas expressões fornece o valor 1.
• Dentro de uma atribuição, todas as ocorrências da mesma variável possuem o mesmo valor.
• Inicie cada avaliação com uma pilha vazia. As duas expressões não podem compartilhar nós nem valores residuais de pilha.
• A força bruta pode encerrar na primeira divergência encontrada.
• Declare equivalência somente depois de avaliar as duas expressões em todas as $2^n$ atribuições sem encontrar resultados diferentes.
• A pilha usada na avaliação deve ser explícita e encadeada.
• Uma entrada inválida deve ser informada como erro, não como regras não equivalentes.
• Qualquer atribuição divergente será aceita como contraexemplo.

Considere inválida uma expressão vazia, com mais de 50 tokens, com token desconhecido, com variável não declarada, com operador sem valores suficientes ou que deixe mais de um valor na pilha. Considere também inválida uma entrada cuja quantidade de variáveis esteja fora do limite, não corresponda à lista ou contenha variável repetida ou fora do intervalo de A a Z.

Saída obrigatória

Informe se as expressões são equivalentes. Quando não forem, mostre os valores de todas as variáveis no contraexemplo e o resultado de cada expressão para essa atribuição. Quando n = 0, não existe variável para listar.

Para a entrada de referência, uma saída válida é:

Nao equivalentes
A=1 B=0
Expressao 1: 0
Expressao 2: 1

Outra atribuição também será aceita se realmente produzir resultados diferentes. Para uma entrada inválida, informe o motivo sem apresentar uma conclusão de equivalência.

Exemplo visual da pilha e de um contraexemplo

A figura possui dois exemplos independentes. À esquerda, ela avalia A B AND A NOT OR para A = 1 e B = 0, mostrando que a pilha armazena valores booleanos e termina com um único resultado. À direita, ela compara A B AND com A B OR e destaca uma atribuição que produz resultados diferentes. O topo da pilha aparece à direita de cada estado. A tabela verdade completa possui finalidade didática; o programa pode encerrar na primeira divergência encontrada.

Casos de teste fornecidos

Execute todos os casos abaixo. Eles fornecem entradas e resultados esperados para verificar comportamentos diferentes do programa.

Caso 1: divergência com contraexemplo

Use a entrada de referência apresentada anteriormente. A saída deve informar que as expressões não são equivalentes, mostrar uma atribuição divergente e apresentar os dois resultados. A = 1 e B = 0 é um contraexemplo válido, mas não é o único.

Caso 2: textos diferentes e regras equivalentes

2
A B
A B AND
B A AND

Saída esperada:

Equivalentes

Caso 3: uso de NOT em regras equivalentes

2
A B
A B AND A NOT OR
A NOT B OR

Saída esperada:

Equivalentes

Caso 4: expressões constantes sem variáveis

0
-
1 0 OR
1

Saída esperada:

Equivalentes

Caso 5: variável não declarada

1
A
A B AND
A

Saída semanticamente esperada:

Entrada invalida: uma expressao usa uma variavel nao declarada

Neste último caso, não informe equivalência nem apresente contraexemplo.

Limite do projeto

O núcleo do projeto inclui validar a entrada, gerar as atribuições por força bruta, avaliar cada expressão com uma pilha encadeada independente, comparar os resultados e executar os casos de teste fornecidos.

Use somente os operadores e a notação pós-fixa definidos acima. Não se exigem conversão de expressões usuais para pós-fixas, parênteses na entrada, regras de precedência, simplificação algébrica, impressão da tabela verdade completa, circuitos eletrônicos ou métodos avançados de verificação lógica.