Puzzles clássicos de ciência da computação

Os desenvolvedores de software têm uma propensão para quebra-cabeças. Talvez seja por isso que livros como
To Mock a Mockingbird existe. Trata-se de uma coleção de quebra-cabeças lógicos que é considerada uma introdução ao
cálculo lambdaum dos conceitos centrais do
Lisp.

Essas perguntas de quebra-cabeça são
de rigueur para muitas entrevistas de programação, embora sejam
muitas vezes abusadas. Há uma desvantagem em pensar nas linguagens de programação como soluções
para quebra-cabeças matemáticos abstratos arbitrariamente difíceis. Provavelmente é por isso que o Lisp tem
uma rica reputação de ser poderoso, mas simultaneamente denso e impenetrável.

Prefiro pensar nas
linguagens de programação como ferramentas utilitárias para problemas do mundo real.
Eles me permitem atingir objetivos pragmáticos (e muitas vezes
prosaicos). O PHP é a linguagem menos sexy
uma linguagem que o senhor jamais encontrará, mas isso importa quando é a tecnologia que impulsiona o atual Boardwalk
e Park Place do mundo da Web? Não sou fã de perguntas do tipo quebra-cabeça em entrevistas;
Prefiro que os possíveis desenvolvedores
me façam uma apresentação ou
escrever um programa razoavelmente útil no ambiente de desenvolvimento real
que o senhor usará no trabalho. Resolva todos os quebra-cabeças que o senhor quiser, mas o único que estamos
recebendo pago para resolver é o problema do cliente.

Dito isso, muitos conceitos fundamentais da ciência da computação podem ser resumidos
bem em forma de quebra-cabeça, o que ajuda tremendamente no ensino e na aprendizagem desses
conceitos-chave. Aqui está uma lista rápida dos quebra-cabeças clássicos da ciência da computação
de que me lembro dos meus tempos de universidade:

Jantares filosóficos Concorrência e deadlocks	Cinco filósofos sentam-se ao redor de uma mesa circular. Na frente de cada filósofo há um prato grande de prato grande de arroz. Os filósofos alternam seu tempo entre comer e pensar. Há um pauzinho entre cada filósofo, à sua direita e esquerda imediatas. Para comer, um determinado filósofo precisa usar os dois pauzinhos. Como o senhor pode garantir que que todos os filósofos possam comer de forma confiável sem morrer de fome?
Caixeiro-viajante P=NP	Um vendedor tem uma rota de cidades que compõe sua rota. Qual é a rota de vendas mais eficiente que visita cada cidade exatamente uma vez e depois retorna à cidade de origem? cidade de origem?
Oito rainhas Projeto de Algoritmos	Dadas oito rainhas em um tabuleiro de xadrez padrão 8 x 8, quantas posições únicas – excluindo rotações e imagens espelhadas – essas oito rainhas podem ocupar sem atacar umas às outras?
Dois generais Protocolos de comunicação	Dois exércitos, cada um liderado por um general, estão se preparando para atacar uma cidade. Os exércitos estão acampados fora da cidade em duas montanhas separadas por um grande vale. Para Para capturar a cidade, os generais devem atacar exatamente ao mesmo tempo. A única A única maneira de os generais se comunicarem é enviando mensageiros pelo vale. Infelizmente, o vale está ocupado pelos defensores da cidade, portanto, há uma chance de qualquer de um determinado mensageiro ser capturado. Cada general não tem como saber se seu mensageiro chegou. mensageiro chegou. Como os generais coordenam seu ataque?
Torres de Hanói Recursão	O senhor tem uma pilha de discos, do maior para o menor, que deslizam para a primeira pino de um quadro de três pinos. Seu objetivo é mover toda a pilha de discos da primeira primeiro pino para o terceiro pino. Entretanto, o senhor só pode mover o disco mais alto de qualquer estaca, e os discos menores devem sempre ser colocados sobre os discos maiores. Quantas jogadas serão necessárias? serão necessários?

Considero este o “maior sucesso” dos quebra-cabeças clássicos da ciência da computação. Mas tenho certeza
tenho certeza de que esqueci alguns. Há algum outro enigma que eu tenha esquecido e que expresse conceitos fundamentais da ciência da computação, do tipo
conceitos fundamentais da ciência da computação, do tipo que seria ensinado em um curso típico de graduação em ciência da computação?
de ciência da computação?