Dykstra von Tim aus Stanford

    Entlang der schönen Coursera beginnt bald wieder der Algorithmenkurs von Tim aus Stanford. Und ich kann nicht über ihn schreiben. Und im Lichte dieses Beitrags über Fernunterricht ist dies umso mehr.

    Zunächst ist dies der interessanteste Kurs, den ich jemals absolviert habe. Und ich habe viele Jahre überhaupt nicht die schlechtesten Universitäten verbracht. Der Kurs heißt Algorithmen: Design und Analyse . Der Kurs beschreibt verschiedene Algorithmen für Graphen, diskutiert die entsprechenden Datenstrukturen für jeden Algorithmus, gibt es eine Theorie und kurze Beweise für diese Algorithmen. Der zweite Teil beschreibt unter anderem das P = NP-Problem und Algorithmen mit nichtpolynomieller Zeit.

    Warum mir dieser Kurs so gut gefallen hat. Weil der Dozent unglaublich cool ist! Er ist so involviert, er erzählt es auf diese Weise. Und dann müssen Sie jede Woche einen neuen Algorithmus programmieren (in der Sprache Ihrer Wahl) und anhand Ihrer Implementierung die Antwort auf die Frage finden. Senden Sie die Antwort auf die Frage auf der Website und erneut, bis Sie die richtige Antwort erhalten. Wie gesagt, jede Woche ein neuer Algorithmus. Und dementsprechend die Fristen. Es hat mich einfach verrückt gemacht: Ich bin von der Arbeit nach Hause gerannt und habe mich an den Wochenenden nicht von den Algorithmen getrennt. Ich bin in den Urlaub gefahren, habe mich auf den höchsten Punkt des Landes gesetzt und die Zusammenführungssortierung programmiert.

    Ich habe sechs Monate gewartet, bis es wieder angekündigt wurde, um es anderen Leuten zu empfehlen, denn für mich war es wie ein gefundener Schatz.


    Als Beispiel ist hier ein Bild, wie ich die Lösbarkeit des 2SAT-Problems mit einem Zufallsalgorithmus fand.

    2SAT-Problem: Es gibt eine Reihe von booleschen Variablen {X1, ..., Xn}, restriktive Bedingungen sind in der Form (X1 ODER X5), (¬X2 ODER X3), (X5 ODER X9), ... gegeben festzustellen, ob es möglich ist, alle diese Bedingungen gleichzeitig zu erfüllen.
    Der im Kurs vorgeschlagene Algorithmus nimmt den Wert einer der Variablen in einer der nicht erfüllten Bedingungen auf und ändert ihn zufällig.
    2SAT
    Auf dem Bild entlang der x-Achse ist die Anzahl der zufälligen Coups (pro Satzlauf) angegeben, entlang der y-Achse die Anzahl der nicht erfüllten Bedingungen. Es wurden sechs verschiedene Sätze solcher Bedingungen angegeben, und es musste bestimmt werden, welche von ihnen lösbar sind (erfüllt sind) und welche nicht. Wenn eine Reihe von Bedingungen erfüllt ist, findet eine solche zufällige Änderung eine Lösung. Wenn nicht, beginnt die Anzahl der nicht erfüllten Bedingungen um einen bestimmten Wert zu schwanken. Zum Beispiel ist in der zweiten linken Zeile des Bildes zu sehen, dass das System nach einiger Zeit zu einem Paar gegenseitig nicht erfüllter Bedingungen konvergierte und diese zufälligen Änderungen das System innerhalb mehrerer zufälliger Variationen in Schwingung versetzen.

    Nun scheint es mir, dass dies die Top 4 Monate meines Lebens in Bezug auf die Konzentration von interessanten Dingen waren, als dieser Kurs stattfand. Und ich denke immer noch, vielleicht geben Sie mir Ratschläge, welche Art von Planungsunternehmen und in welchen Positionen sie sich jeden Tag mit solchen Dingen befassen sollten.

    Jetzt auch beliebt: