Semantik eines applikativen Algorithmus



  • Hallo zusammen!

    Habe dieses Semester mein Info-Studium begonnen und schlage mich gerade mit der letzen Übungsaufgabe von aktuellen Blatt zu Algorithmen und Datenstrukturen herum. Eine Aufgabenstellung erschließt sich mir irgendwie nicht so ganz:

    Gegeben sei der folgende applikative Algorithmus für ganze Zahlen x und y (// bedeutet ganzzahlige Division):

    f(x , y) = if y = 0 then 1
    else if(x < 2 * y) then f(x, x - y)
    else x * f(x - 1, y - 1) // y
    fi
    fi

    Erläutern Sie anhand der Beispiele f(4,2) und f(8,5), welche Berechnungen der Algorithmus ausführt.
    Für welche x und y terminiert der Algorithmus nicht?
    Was ist die Semantik des Algorithmus?

    Die ersten beiden Fragen waren ja kein Problem... Aber was ist denn bitte die Semantik des Algorithmus? Ich denke mal, man will von mir wissen, was der Alg. da berechnet.. Aber da tut sich für mich nicht wirklich ein Muster auf, die Berechnungen erscheinen mir irgendwie mal total zusammenhangslos und willkürlich! Oder ist vielleicht was ganz anderes gefragt?!

    Vielleicht kann mir ja jemand von euch weiterhelfen... 🙂

    Gruß,
    Matthias



  • Matthias S. schrieb:

    Aber was ist denn bitte die Semantik des Algorithmus? Ich denke mal, man will von mir wissen, was der Alg. da berechnet..

    jop, genau das ist gefragt.
    also wenn ich überhaupt keine ahnung hätte was da berechnet wird, würde ich das einfach mal in einer programmiersprache meiner wahl programmieren und mit ganz vielen wertepaaren aufrufen.
    kleiner tip: die funktion braucht man oft in der kombinatorik, vielleicht kennst du sieh noch gar nicht.



  • Ahhh....... Der Groschen fällt glaube ich gerade... Binomialkoeffizient? 🙂



  • exakt 🤡



  • Witzig... Ich hab das bestimmt mit 6 Wertepaaren berechnet und hatte das gerade Donnerstag in der Mathe-Vorlesung, aber irgendwie hatte ich wohl ein etwas größeres Brettchen vom Kopf... 😉

    Dank dir auf alle Fälle! 😃



  • Ähm wenns sich um Binomialdingsda handeln würde, wär doch laut dem Algo 4 über 2 12 anstatt von richigen 6, oder hab ich was flasch aufgeschnappt?


Log in to reply