Algorithmus Vorstellungsgespräch



  • 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.



  • Bashar schrieb:

    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.

    Oh shit, ja da hast du Recht 😉
    Total vergessen. Zum Glück ist das hier keine Prüfung...

    Aber wo wir grad bei einem halbwegs theoretischen Thema sind (blurrys OP wird ja nicht ernst weiter verfolgt). Wie kann ich zeigen/beweisen/begründen, dass eine Sprache turingvollständig ist - also alles berechenbare auch berechnen kann?
    Ich denke mal nicht, dass Beispiele für WHILE- und LOOP- Berechenbarkeit reichen, oder?!



  • Skym0sh0 schrieb:

    Wie kann ich zeigen/beweisen/begründen, dass eine Sprache turingvollständig ist - also alles berechenbare auch berechnen kann?

    Kannst du das nicht tun, indem du sie auf eine Turingmaschine abbildest?

    Wenn wir annehmen können, dass Turingmaschinen alles berechnen können und deine Sprache als Turingmaschine funktionieren kann, können wir doch den entsprechenden Schluss ziehen.



  • Skym0sh0 schrieb:

    Aber wo wir grad bei einem halbwegs theoretischen Thema sind (blurrys OP wird ja nicht ernst weiter verfolgt). Wie kann ich zeigen/beweisen/begründen, dass eine Sprache turingvollständig ist - also alles berechenbare auch berechnen kann?

    Durch Simulation, d.h. durch Implementation einer Turingmaschine.



  • Ok, ich frage konkreter.
    Mir geht es weniger um den formalen, universellen Beweis, sondern ich möchte einem Kollegen klar machen, dass die Templates (und damit das Typsystem) von C++ turingvollständig sind.

    Nur wie?



  • Skym0sh0 schrieb:

    Ok, ich frage konkreter.
    Mir geht es weniger um den formalen, universellen Beweis, sondern ich möchte einem Kollegen klar machen, dass die Templates (und damit das Typsystem) von C++ turingvollständig sind.

    Nur wie?

    Und dir muss ich Beweise, dass das Typesystem im C++ nicht turingvollständig ist, weil ein Template kein Type ist, sonder nur ihre Instanzierung.

    Implementiere eine Funktion als Template?



  • Ich spreche von sowas hier:

    #include <iostream>
    
    int ack(unsigned int n, unsigned int m)
    {
    	if ( n == 0 )
    		return m + 1;
    	else if ( m == 0 )
    		return ack(n - 1, 1);
    	else
    		return ack(n - 1, ack(n, m - 1));
    }
    
    template<unsigned int N, unsigned int M>
    struct Ack
    {
    	static const unsigned int value = Ack<N - 1, Ack<N, M - 1>::value>::value;
    };
    
    template<unsigned int M>
    struct Ack<0, M>
    {
    	static const unsigned int value = M + 1;
    };
    
    template<unsigned int N>
    struct Ack<N, 0>
    {
    	static const unsigned int value = Ack<N-1, 1>::value;
    };
    
    int main()
    {
    	const unsigned int N = 3;
    	const unsigned int M = 4;
    
    	std::cout << "Ack(" << N << ", " << M << ") = " << ack(N, M) << std::endl; // 125
    	std::cout << "Ack<" << N << ", " << M << ">::value = " << Ack<N, M>::value << std::endl; // 125
    	return 0x0;
    }
    

Anmelden zum Antworten