Manden, geden, ulven og kålhovedet.

Hvis nogen skulle forledes til at tro, at datalogi kun handler om turingmaskiner og drivremme, kan de godt tro om igen. Man kan godt opgive at komme igennem studiet uden et solidt fundament indenfor så forskelligartede emner som biologi, ballistik, færgedrift og græsk.

For at demonstrere dette, præsenterer vi her et typisk eksamensspørgsmål. Vi vil også forsøge at give et svar. For at gøre det så realistisk som muligt, satte vi fire timer af til at finde svaret.

Spørgsmål

"En mand (m) er på udflugt med sine to "husdyr", en ged (g) og en ulv (u). Desuden medbringer han et stort, lækkert kålhovede (k). Undervejs kommer de til en flod, som de må krydse. De kan benytte en lille båd, som ligger ved bredden. Problemet er blot, at der kun er plads til manden og én af de andre (g,u,k). Samtidig ved manden, at ulven, hvis den lades alene med geden, helt sikkert vil æde denne. Ligeså vil geden, hvis den lades alene med kålhovedet, også fortære dette. Manden må altså sejle frem og tilbage over floden, medbringende ingen eller en af de andre hver gang, indtil han har fået alle sikkert over på den anden side, uden at nogen/noget er gået tabt.

Spørgsmål 1 Angiv en løsning til problemet, hvor alle parter overlever og kan fortsætte deres rejse.

Spørgsmål 2 Betragt strenge over alfabetet S = {m,u,g,k} og fortolk dem som følger: et symbol m betyder, at manden sejler alene over floden fra den side, han i øjeblikket er på, et u betyder, at manden har ulven med sig i båden, osv. Du skal nu lave en endelig automat, som accepterer præcis de strenge, der svarer til en transportsekvens, som overholder den regel, at alle overlever, samt at manden kun kan have noget med tilbage, der var der, hvor han startede fra (dvs. at hvis han vil sejle tilbage fra det sted, hvor ulven og geden står, så kan han medbringe en af disse, men ikke kålhovedet). For eksempel er gkmg en lovlig streng, men gk er ikke lovlig."

Løsning

Som det ses, er spørgsmål 2 dramatisk længere end spørgsmål 1, men de giver i en eksamenssituation samme antal points. Vi afsatte derfor al vor tid til det første spørgsmål og så bort fra det andet. Endnu en god grund til dette er, at spørgsmål 2 indeholder et græsk bogstav, nemlig bogstavet Store Ouzo, som vi ikke aner, hvad betyder.

Før vi kunne give mere end en overfladisk løsning på problemet, måtte vi først opnå en dybere forståelse. Ville det ikke være nemmere blot at sælge geden og købe en ny på den anden side af floden? Hvis geden ikke skal sulte, kunne den så ikke lige så godt få kålhovedet først som sidst? Svaret er indlysende: Græsset er grønnere på den anden side, og dette skyldes manglen på geder! Dermed lider geden ingen nød, men hvad motiverer ulven?

At medbringe en ulv til en flodbred uden geder er i bedste fald fjollet, medmindre:

a) At ulven er en attrap, lavet af papmaché, ligesom de fleste af de rottweilere, man ser i nærheden af parkbænke. Dette ville ikke ændre på det oprindelige problem, blot vil det være geden, der, hvis lejligheden bød sig, ville fortære ulven.

Eller

b) At ulven i virkeligheden er en gravhund. De to arter har flere fysiske ligheder, men gravhunden er i mange situationer, bl.a. rævejagt, langt mere praktisk. Derfor er det sandsynligt – men ikke godtgjort – at det overhovedet ikke drejer sig om en ulv.

Som det ses, kan en overvejelse af et kompliceret problem hurtigt føre til flere spørgsmål end svar. Lad os derfor tage afsæt i et simplere, men beslægtet, problem.

Vi antager, at manden skal krydse floden med tre fuldstændig identiske får. Dette synes umiddelbart at forenkle problemstillingen, da de alle lever af græs. Men skindet bedrager. Det egentlige problem ligger nu i at sikre sig, at fårene ikke i smug bytter plads, når man vender ryggen til. Hvis der var tale om to får, kunne man med en speedmarker sætte et kryds på maven af den ene, men tre får? Vi skifter simpelthen det ene får ud med en Mercedes. Voilá! Man kan nu sandsynliggøre situationen ved, at manden er quiz-vært og på vej til et TV-show med aftenens præmier. Og båden er selvfølgelig en bilfærge, hvilket ikke strider mod opgaveteksten.

I virkelighedens verden ville man nok vælge at sætte sig ned og vente på, at der ville blive bygget en bro, men i en eksamenssituation kan man ikke altid forvente, at dette vil ske indenfor fire timer. Dermed er spørgsmålet nu: Kan man fragte de to får og bilen over på et ti-turskort? Og kan det tidsmæssigt lade sig gøre uden også at erhverve sig et eksklusivkort? Vi vil lade det være op til læseren at besvare dette.

Og nu tilbage til det egentlige problem. En velkendt, og flittigt brugt, matematisk metode er indførsel af midlertidige variable, der sidenhen blot kan fjernes – dog må man selvfølgelig ikke herved skære dele væk af det oprindelige problem. Men vi genindfører altså ulven, geden og kålhovedet. Og da det ikke kan skade, beholder vi de tre oprindelige får og bilen. Desuden indfører vi en katapult.

Den oprindelige idé med katapulten var, at placere manden, geden, ulven og kålhovedet på katapulten og simpelthen kappe rebet. Desværre er der kun to, der kan gøre dette, og vedkommende kan ikke samtidig sidde på katapulten. Manden er én mulighed, men han må derefter ro særdeles hurtigt for at forhindre sine ejendele i at fortære hinanden. Den anden mulighed er, at geden gnaver rebet over. Dette har desværre den uheldige konsekvens, at manden fra den anden flodbred passivt må se til, mens geden fortærer først båden, og derefter katapulten (geder er jo altædende). Da vi arbejdede med problemet, syntes katapulten umiddelbart at være en blindgyde, og frustrationerne begyndte så småt at melde sig i vor gruppe. Indtil en indlysende idé meldte sig:

Vi sender simpelthen båden over med katapulten!

Eller omvendt:

Vi sender katapulten over med båden!

Specielt den første idé havde en fantastisk appel, og vi gik til arbejdet med fornyede kræfter. Snart måtte vi dog konstatere, at ingen af disse ideer bragte os nærmere målet, men snarere at de havde et vist potentiale for at forværre situationen. Humøret var lavt, og tiden løb.

På dette tidspunkt, ca. ti minutter før de normerede fire eksamenstimer udløber, må man gribe til et kunsttrick: Katapulten fjernes listigt, ligesom Mercedesen, båden, geden, ulven, kålhovedet, manden og floden. Og man går derefter videre til en anden eksamensopgave for dér at indhente nogle vitale points.

Fårene, katapulten og de albanske oprørere

Den næste opgave handlede i øvrigt, pudsigt nok, netop om en katapult, en hulens masse får og nogle albanske oprørere på en bjergside. Vi havde blot ti minutter til at løse denne opgave, hvilket vel godt kunne lade sig gøre, men fordrer stort overblik og viljestyrke.

Noget uklogt valgte vi istedet at panikke totalt og løbe rundt som høns uden hoveder.

Denne side er sidst ændret 07/01-2010 22:14