Algorithmus Vorstellungsgespräch



  • Hallo,

    ich soll bei einem Vorstellunggespräch einen bekannten Algorithmus implementieren.
    Er ist iterativ. Welcher Algorithmus würde sich da mal als Übung anbieten ?



  • Alle Unterforen alphabetisch durchtrollen?

    <°))))><



  • Binary search würde sich anbieten, aber es kommt stark drauf an, wie schwer es sein muss?



  • was soll es bringen wenn du einen iterativen algorithmus als "übung" implementierst?

    aber bitte: euklidischer algorithmus

    edit: was ich mir als durchaus passable übung vorstelle ist das iterative implementieren eines eigentlich rekursiven algorithmuses. gutes beispiel dürfte backtracking sein.

    edit 2: grammatik...



  • Du?
    Vorstellungsgespräch?

    Ich will nen Mittschnitt 😃



  • DocShoe schrieb:

    Du?
    Vorstellungsgespräch?

    Einer muss ja Kaffee holen 😉



  • Ich hätte den Algorithmus genommen, der die Ackermann Funktion ausrechnet.



  • acki schrieb:

    Ich hätte den Algorithmus genommen, der die Ackermann Funktion ausrechnet.

    Ohne die Laufvariable zu ändern 😉



  • Caligulaminus schrieb:

    <°))))><

    Was drückt so ein Fisch aus?

    icarus2 schrieb:

    Einer muss ja Kaffee holen 😉

    Da werden wir leider auf blurry333 verzichten müssen, bei uns holt sich jeder selber einen Kaffee 🙂



  • Mechanics schrieb:

    Caligulaminus schrieb:

    <°))))><

    Was drückt so ein Fisch aus?

    Bezahlung für Trolle, damit sie einem aus dem Weg gehen?

    [Ackermann iterativ]Ohne die Laufvariable zu ändern

    Ich würd ihn sofort einstellen, wenn er den Scherz erklären kann. Bei Kenntnis seiner Postinghistorie.



  • Bashar schrieb:

    Ich würd ihn sofort einstellen, wenn er den Scherz erklären kann.

    👍



  • volkard schrieb:

    Bashar schrieb:

    Ich würd ihn sofort einstellen, wenn er den Scherz erklären kann.

    👍

    Ich kenne zwar die Ackermannfunktion und habe gerade noch mal den Wikipedia-Artikel gelesen, verstehe den Scherz aber trotzdem nicht. Eine Erklärung macht einen Witz zwar häufig weniger witzig ... dieses Risiko könnten wir aber doch mal eingehen 😉



  • Unwissender_ schrieb:

    Ich kenne zwar die Ackermannfunktion und habe gerade noch mal den Wikipedia-Artikel gelesen, verstehe den Scherz aber trotzdem nicht. Eine Erklärung macht einen Witz zwar häufig weniger witzig ... dieses Risiko könnten wir aber doch mal eingehen 😉

    Die Ackermann-Funktion ist nicht Loop-Berechenbar. Es sind nur Schleifen mit fester Anzahl an Iterationen möglich in der Form:
    LOOP k DO prog END

    Nur der initiale Wert von k spielt eine Rolle und durch eine Änderung kann die Anzahl der Iterationen nicht verändert werden. Müsste man aber für die Ackermann-Funktion



  • Mechanics schrieb:

    Caligulaminus schrieb:

    <°))))><

    Was drückt so ein Fisch aus?

    Häufig werden von Nutzern Troll-Beiträge mit einem ASCII-Art-Fisch, auch Roter Hering genannt, beantwortet (Beispiel: ><((((*> ). Dies soll die anderen Diskussionsteilnehmer dazu auffordern, den Beitrag des mutmaßlichen Trolls entsprechend zu prüfen und ggf. nicht weiter auf dessen Beiträge zu reagieren.

    http://de.wikipedia.org/wiki/Troll_(Netzkultur)



  • Ich habe die Ackermannfunktion eben iterativ mit Hilfe eines Stacks programmiert (Python):

    def ackermann(m, n):
        stack = [m, n]
        counter = 0
        while len(stack) > 1:
            counter += 1
            n = stack.pop()
            m = stack.pop()
            if m == 0:
                stack.append(n + 1)
            elif m > 0 and n == 0:
                stack.append(m-1)
                stack.append(1)
            else:
                stack.append(m-1)
                stack.append(m)
                stack.append(n-1)
        return stack.pop(), counter
    

    Ich frage mich nun, wie man die Funktion mit for-Schleifen (und ohne Stack) realisiert...vielleicht verstehe ich dann wovon ihr redet 🙂
    Würde mich freuen, wenn jemand das mal zeigen könnte. Eine Google-Suche hat mich noch nicht weiter gebracht.



  • es geht nicht.



  • Unwissender_ schrieb:

    Ich habe die Ackermannfunktion eben iterativ mit Hilfe eines Stacks programmiert (Python):

    Iteratives Schummeln mit künstlichem Stack zähle ich als rekursiv.



  • otze schrieb:

    es geht nicht.

    Wieso geht das nicht? Die Einschränkung, dass eine Schleife eine feste Anzahl von Iterationen hat (wie bei LOOP) gilt doch für bspw. C++ nicht.

    @Volkard
    Ich finde das auch mit dem Stack etwas tricksig, da es sich dabei um eine generische Lösung für das Umwandeln von rekursiven Algorithmen in iterative handelt. Daher auch mein Interesse an einer richtig echt wirklich nicht niemals rekursiven Variante.



  • Es geht dabei um Berechenbarkeit im Sinne der theoretischen Informatik.

    Klar, jede auch nur halbwegs aktuelle Programmiersprache kann auf die Zählvariable in einer For-Schleife (oder dem Sprachenäquivalent) zugreifen und dieses auch ändern (Ist ja technisch kein Problem).

    Die Fragestellung dahinter ist aber eine ganz andere:
    Turing, Church und Co haben sich damals gefragt: "Was bedeutet eigentlich Berechenbar und was ist berechenbar?"
    Und man fing an erste semantisch sauber definierte (theoretischen) Sprachen zu entwickeln. Und eine der Sprachen war halt LOOP.

    LOOP konnte ziemlich viel berechnen. Die Einschränkung oblag aber darin, dass von vornerein deterministisch gesagt werden konnte, wie viele Schleifendurchläufe für eine Eingabe X vollzogen würden.
    Einfache Beispiele für sowas wären die Normale Addition, Multiplikation, Potenzierung, factorial usw.

    Und man sah, es geht sehr viel. Aber die Frage kam danach auf, wo liegen denn die Grenzen. Ist mit Loop alles berechenbar?
    Und da kam der Herr Ackermann an und sagte: "Nein, sehet her, diese Funktion ist nicht berechenbar nur mit LOOP alleine." (Sie wächst schneller als man mit einer LOOP-Schleife berechnen kann).

    Dann kamen noch andere Berechenbarkeitsbegriffe, die dann mehr berechnen konnten als LOOP (und Äquivalente wie z.B. Primitive Rekursion). Beispiele sind da µ-Rekursion, WHILE- und GOTO-Programme oder Markov-Algorithmen.

    Zusamengefasst wird das unter anderem in der Church'schen These (oder Church Turing These). Ist ganz interessant und sollte jeder Informatiker mal was von gehört haben 😉



  • Da fehlt ein entscheidendes Detail. Ein LOOP-Programm terminiert ja immer, aber es gibt nicht-terminierende Programme, von daher war von Anfang an klar, dass LOOP nicht alles kann. Man könnte nun vermuten, dass jedes Programm, dass für jede Eingabe terminiert, in LOOP geschrieben werden kann. Die Ackermann-Funktion ist das klassische Gegenbeispiel.

    @Unwissender: Du hast die Lösung doch schon. Dein Stack ist deine Iterationsvariable (wenn du willst kannst du den Stack auch als Zahl codieren => Gödelisierung), und du veränderst sie in jedem Schleifendurchlauf. Was du nicht tust ist sie einfach nur "hochzuzählen". Deine Implementation ist ein klassisches WHILE-Programm. Und besser geht es nicht, aber man kann eine Unmöglichkeit ja nicht durch Angabe eines Beispiels zeigen, sondern nur durch einen universellen Beweis. Wie Skym0sh0 schon sagte, beruht der darauf, dass eine LOOP-berechenbare Funktion ein maximales Wachstum hat, das von der Ackermann-Funktion übertroffen wird.


Log in to reply