Статии

Числото на Alcuin на графика

Числото на Alcuin на графика

Числото на Alcuin на графика

От Péter Csorba, Cor Hurkens и Gerhard Woeginger

Сборник от 16-ия Европейски симпозиум по алгоритми (2008)

Резюме: Ние разглеждаме проблем с планирането, който обобщава проблема за пресичане на река на Алкуин (известен също като: пъзел с вълк, коза и зеле) към сценарии с произволни конфликтни графики. Ние извличаме разнообразни комбинаторни, структурни, алгоритмични и теоретични резултати за сложността около този проблем.

Въведение: Англосаксонският монах Алкуин (735–804 г. сл. Н. Е.) Е един от водещите учени на своето време. Той служи като ръководител на Дворцовата школа на Карл Велики в Аахен, той разработва каролингския минускул (скрипт, който е основата на начина, по който се пишат буквите на настоящата римска азбука), и той пише редица елементарни текстове по аритметика, геометрия , и астрономия. Неговата книга „Propositiones ad acuendos iuvenes“ (Проблеми за изостряне на младите) е може би най-старата колекция от математически задачи, написана на латински. Той съдържа следния добре познат проблем.

Човек трябваше да транспортира в далечната страна на река вълк, коза и сноп зеле. Нека той, който може, да каже как би било възможно да ги транспортира безопасно?

В плана за безопасен транспорт нито вълк и коза, нито коза и зеле не могат да бъдат оставени сами заедно. Проблемът с пресичането на река на Алкуин се различава значително от други средновековни пъзели, тъй като той не е нито геометричен, нито аритметичен, а чисто комбинативен. Бигс го споменава като един от най-старите комбинаторни пъзели в историята на математиката. Ашер заявява, че проблемът се проявява и в галски, датски, руски, етиопски, суахелски и замбийски фолклор. Borndorfer, Grotschel & Lobel използват проблема на Alcuin, за да предоставят на читателя спокойно въведение в целочисленото програмиране.


Гледай видеото: ЧИСЛА В РИСУНКИ - ЧИСЛОТО 10 (Януари 2022).