Algorithmen Design und Komplexität - Wie kann man so denken?

15

Meine Frage ist allgemein: Wie fange ich an, in Bezug auf Algorithmusdesign und Komplexität zu denken? Ich werde einen Graduate Course in Algorithm Design belegen. Ich hatte mich früher angemeldet, ließ es aber später wieder fallen, weil ich nicht mithalten konnte. Ich muss diesen Kurs als Voraussetzung nehmen.

Gibt es einen Trick, um so zu denken? Ich weiß, dass dies ziemlich grob formuliert ist, aber manchmal hilft eine neue Perspektive, ein Thema anders zu denken.

Das Hauptproblem, das ich mit diesem Kurs (und ähnlichen theoretischen Kursen) habe, ist: Woher weiß ich, dass die von mir entwickelten Lösungen korrekt sind? Ich finde den theoretischen Teil willkürlich, besonders wenn ich nachweise, dass ein bestimmter Algorithmus auf eine bestimmte Weise handelt oder sich auf eine bestimmte Weise verhält?

In unserem Kurs wird der Standardtext verwendet: Einführung in Algorithmen von CLRS.

Gibt es Lehrbücher / Sites / Bücher / etc. das könnte einen Weg bieten, in diesem Bereich selbstbewusst zu werden?

Danke an alle,

Jason Dane

Jason Dane
quelle
2
Ich schlage vor, einen Blick auf diesen Beitrag zu werfen . Ich empfehle speziell das Buch von Udi Manber.
MS Dousti 31.12.10
1
Diese Diskussion zu StackOverflow bietet mehrere Vorschläge: stackoverflow.com/questions/2256721/…
Jeffs
2
Ich stimme der Manber-Empfehlung zu.
Lesen Sie
"Woher weiß ich, dass die von mir entwickelten Lösungen richtig sind?" Meinen Sie damit, dass (1) Sie einen Algorithmus gefunden haben, aber nicht wissen, wie Sie die Richtigkeit beweisen können, oder (2) Sie haben einen Beweis, sind sich aber nicht sicher, ob er richtig ist?
Jukka Suomela
Schritt eins: Geben Sie keine klaren Antworten mehr und beziehen Sie sich stattdessen auf die Lösungen anderer. ;)
Raphael

Antworten:

18

Ich denke, Kurse über Algorithmusdesign und Komplexität von Berechnungen sind für Studenten, die mit diesen Themen nicht vertraut sind, immer eine Herausforderung, da sie einen gewissen Grad an mathematischer Reife und Fähigkeiten zur Problemlösung erfordern. In meinem ersten Abschlusskurs über "Computational Complexity" erzählte mir ein Freund, der seinen Abschluss in reiner Mathematik gemacht hatte, wie überrascht er von der Tatsache war, dass dieser Kurs zwar nicht viel mathematischen Hintergrund benötigte (zumindest wurde dies in diesem Artikel erklärt) der Kursbeschreibung), es erforderte tatsächlich fast alle Fähigkeiten, die er durch all seine reinen Mathematik-Grundstudiengänge bekam!

Ich fand heraus, dass ich am meisten über "den Weg" Bescheid wusste (als ich mit dem Studium anfing), indem ich Übungen aus Sipsers Buch las und machte . Stellen Sie sicher, dass Sie die Übungen machen, da Sie nicht nur eine Reihe von Fakten oder Definitionen, sondern auch die Fähigkeit zur Problemlösung und die mathematische Reife erlernen möchten.

Das Buch von Sipser ist jedoch nur gut für Komplexität und NP-Vollständigkeit, es wird nicht ausreichen, um das CLRS-Buch zu ersetzen. Das einzige Problem mit CLRS-Büchern besteht darin, dass der Vorteil einer umfassenden Berichterstattung zu seiner Schwäche werden kann, da das Buch für die Schüler möglicherweise ziemlich beängstigend oder überwältigend wirkt. Mein Rat ist also, dass Sie wirklich in die Bibliothek gehen und nach Büchern über Algorithmen suchen, diese einzeln durchsuchen und diejenigen auswählen sollten, die Ihrem Denkmuster am besten entsprechen. Und wieder nicht vergessen, Übungen zu machen!

Für Algorithmen schlage ich persönlich die folgenden Bücher vor (zusätzlich zu den von Sadeq und JeffE vorgeschlagenen):

  • Das sehr lesenswerte und schöne Buch Algorithmen von S. Dasgupta, CH Papadimitriou und UV Vazirani.
  • Die Killer - Noten (oder Buch Entwurf) von Jeff Erickson. (Da JeffE zu bescheiden ist, um seine eigenen Notizen vorzuschlagen, muss ich es selbst tun.)

Wenn Sie sich mit einem bestimmten Algorithmus oder einer bestimmten Datenstruktur befassen und die Darstellung in Ihrem Lehrbuch für Sie nicht klar genug ist, ist es im Allgemeinen am besten, auf Google nach Vorlesungsskripten zu diesem bestimmten Thema zu suchen. In manchen Fällen erhalten Sie durch unterschiedliche Erklärungen des gleichen Sachverhalts schließlich ein vollständiges Bild. Zumindest funktioniert das bei mir so.

Dai Le
quelle
8
+1 für Jeffs Killernotizen. Ich lese sie immer gerne. Die arabische Kalligraphie des Wortes Algorithmus ist sehr schön.
Mohammad Al-Turkistany