Artigos

O número Alcuíno de um gráfico

O número Alcuíno de um gráfico



We are searching data for your request:

Forums and discussions:
Manuals and reference books:
Data from registers:
Wait the end of the search in all databases.
Upon completion, a link will appear to access the found materials.

O número Alcuíno de um gráfico

Por Péter Csorba, Cor Hurkens e Gerhard Woeginger

Anais do 16º Simpósio Europeu de Algoritmos (2008)

Resumo: Consideramos um problema de planejamento que generaliza o problema de travessia do rio de Alcuin (também conhecido como: O quebra-cabeça do lobo, da cabra e do repolho) para cenários com gráficos de conflito arbitrários. Derivamos uma variedade de resultados teóricos combinatórios, estruturais, algorítmicos e de complexidade em torno deste problema.

Introdução: O monge anglo-saxão Alcuin (735–804 d.C.) foi um dos principais estudiosos de seu tempo. Ele serviu como chefe da Escola do Palácio de Carlos Magno em Aachen, desenvolveu o minúsculo carolíngio (uma escrita que se tornou a base da forma como as letras do atual alfabeto romano são escritas) e escreveu uma série de textos elementares sobre aritmética, geometria e astronomia. Seu livro “Propositiones ad acuendos iuvenes” (Problemas para aguçar os jovens) é talvez a coleção mais antiga de problemas matemáticos escritos em latim. Ele contém o seguinte problema conhecido.

Um homem teve que transportar para o outro lado de um rio um lobo, uma cabra e um feixe de repolhos. Que ele, que é capaz, diga como é possível transportá-los com segurança?

Em um plano de transporte seguro, nem lobo e cabra, nem cabra e repolho podem ser deixados sozinhos. O problema da travessia do rio de Alcuíno difere significativamente de outros quebra-cabeças medievais, uma vez que não é geométrico nem aritmético, mas puramente combinatório. Biggs o menciona como um dos quebra-cabeças combinatórios mais antigos da história da matemática. Ascher afirma que o problema também aparece no folclore gaélico, dinamarquês, russo, etíope, suaheli e zambiano. Borndorfer, Grotschel & Lobel usam o problema de Alcuin para fornecer ao leitor uma introdução agradável à programação inteira.


Assista o vídeo: GRÁFICOS A PUNTO DE CRUZ. ABECEDARIOS (Agosto 2022).