Ich würde mich gerne als einen ziemlich erfahrenen Programmierer bezeichnen. Ich programmiere jetzt seit über 5 Jahren. Mein Schwachpunkt ist jedoch die Terminologie. Da ich Autodidakt bin, kenne ich einige der formaleren Aspekte der Informatik nicht, obwohl ich programmieren kann. Was sind also praktische Algorithmen / Datenstrukturen, die ich anhand des Namens erkennen und kennen könnte?
Hinweis: Ich bitte nicht um eine Buchempfehlung zur Implementierung von Algorithmen. Die Implementierung ist mir egal, ich möchte nur erkennen können, wann ein Algorithmus / eine Datenstruktur eine gute Lösung für ein Problem darstellt. Ich bitte mehr um eine Liste von Algorithmen / Datenstrukturen, die ich "erkennen" sollte. Zum Beispiel kenne ich die Lösung für ein Problem wie dieses:
Sie verwalten eine Reihe von Schließfächern mit der Bezeichnung 0-999. Die Leute kommen zu Ihnen, um das Schließfach zu mieten, und kommen dann zurück, um den Schließfachschlüssel zurückzugeben. Wie würden Sie eine Software entwickeln, um zu wissen, welche Schließfächer frei und welche in Gebrauch sind?
Die Lösung wäre eine Warteschlange oder ein Stapel.
Was ich suche, sind Dinge wie "In welcher Situation sollte ein B-Tree verwendet werden? Welcher Suchalgorithmus sollte hier verwendet werden?" Algorithmen funktionieren.
Ich habe versucht, in der Wikipedia-Liste der Datenstrukturen und Algorithmen nachzuschlagen, aber ich denke, das ist ein bisschen übertrieben. Also suche ich mehr nach den wesentlichen Dingen, die ich erkennen sollte?
Antworten:
Eine objektive Antwort:
Während meine anfängliche Antwort auf diese Frage auf meiner empirischen Erfahrung als angehender CS-Student und meiner projizierten Meinung über die Art von Menschen beruhte, mit denen ich im CS-Bereich zusammenarbeiten wollte. Es gibt tatsächlich eine objektive (in Bezug auf die subjektiven Meinungen der ACM SIGCSE und IEEE Computing Society) Antwort. Alle 10 Jahre arbeiten das ACM und die IEEE- Gremien an einer gemeinsamen Veröffentlichung zusammen, in der Vorschläge für ein Informatik-Curriculum für Grundstudenten auf der Grundlage von Fachkenntnissen über den Stand der Computerbranche aufgeführt sind. Weitere Informationen finden Sie unter cs2013.org . Das Komitee veröffentlicht einen Abschlussbericht, in dem die Lehrplanempfehlungen aufgeführt sind .
Trotzdem finde ich meine Liste immer noch ziemlich gut.
Ursprüngliche Antwort unten.
Was muss ich wissen?
Minimum
Ich denke, ein erfahrener Programmierer sollte mindestens Grundkenntnisse in Informatik haben. Sicher, Sie können bei vielen Jobs mit nur einem kleinen Teil der Informatik effektiv sein, da CS auf einer soliden Community basiert und der Fokus der meisten professionellen Positionen eingeschränkt ist. Außerdem werden sich viele Menschen nach dem Bachelor-Studium weiter spezialisieren. Ich denke jedoch auch nicht, dass dies eine Ausrede ist, um nicht mit grundlegenden CS-Kenntnissen vertraut zu sein.
Um die Titelfrage zu beantworten, sollte ein CS-Student (die Grundlage für einen erfahrenen Programmierer) nach seinem Abschluss Folgendes wissen:
Datenstrukturen
Algorithmen
Designmuster
Paradigmen
Komplexitätstheorie
Darüber hinaus
Um später in Ihrer Frage zu erfahren, worüber Sie Fragen haben, sollten Sie in der Lage sein, das entsprechende Muster, den Algorithmus und die Datenstruktur für ein bestimmtes Szenario zu identifizieren, sofern Sie mit dem oben Gesagten vertraut sind. Sie sollten jedoch erkennen, dass es oft keine beste Lösung gibt. Manchmal kann es erforderlich sein, das kleinere von zwei Übeln auszuwählen oder einfach zwischen zwei gleichermaßen realisierbaren Lösungen zu wählen. Aus diesem Grund benötigen Sie das allgemeine Wissen, um Ihre Wahl gegen Ihre Kollegen zu verteidigen.
Hier einige Tipps für Algorithmen und Datenstrukturen:
Einige der oben genannten Punkte scheinen keine Hirngespinste zu sein, andere scheinen vage zu sein. Wenn Sie wollen, dass ich näher darauf eingehen kann, kann ich. Ich hoffe jedoch, dass Sie bei einer konkreteren Frage wie "Entwerfen einer Funktion, die die Anzahl der Vorkommen jedes Zeichens in einer Zeichenfolge zählt" den Tipp zur ASCII-Tabelle und zu 128 Elementarrays lesen, die einen sauberen impliziten Hash bilden Tabellen für die Antwort.
Basierend auf diesen Ideen werde ich eine Antwort auf das in Ihrer Frage umrissene Schließfachproblem vorschlagen.
Beantworten Sie das in Ihrer Frage aufgeworfene Problem.
Dies ist möglicherweise nicht die beste Antwort auf Ihre Frage, aber ich denke, es ist eine interessante Frage, die nichts zu Komplexes erfordert. Und es wird sicherlich die zeitliche Komplexität der Verwendung einer Warteschlange oder eines Stapels übertreffen, die eine lineare Zeit benötigt, um zu bestimmen, ob ein Schließfach frei ist oder nicht.
Sie haben 0-999 Schließfächer. Da Sie nun eine feste Anzahl von Schließfächern haben, können Sie sich leicht eine Hash-Funktion ohne Kollisionen im Bereich von 0 bis 999 vorstellen. Diese Funktion ist einfach h (x) = x mod 1000. Konstruieren Sie nun [konzeptionell] eine Hash-Tabelle mit ganzzahligen Schlüsseln und dem Inhalt eines 1000-Elemente-Zeichen-Arrays als Ihre Werte. Wenn ein Kunde das Schließfach 78 für die Verwendung reservieren möchte, geben Sie einfach 78 in die Hash-Funktion ein (Rückgabe von 78) und fügen Sie diese Zahl zum Basiszeiger des Arrays hinzu. Dabei wird ein wahrer Wert an der Stelle gespeichert, auf die der Versatzwert zeigt . Wenn Sie überprüfen möchten, ob 78 verwendet wird, lesen Sie einfach den an diesem Ort gespeicherten Wert und vergleichen Sie ihn mit true.
Diese Lösung arbeitet für die Suche und Speicherung in konstanter Zeit, im Gegensatz zu einer Speicherung und Suche in Protokoll (n) für den Fall einer Prioritätswarteschlange, die durch einen Binärbaum gesichert ist. Die Beschreibung ist absichtlich ausführlich, damit Sie sehen können, wie die höheren Konzepte zu einem effizienten Algorithmus zusammengefasst werden.
Nun fragen Sie sich vielleicht, was wäre besser, wenn ich alle verfügbaren Schließfächer kennen müsste? Wenn in der Prioritätswarteschlange k verfügbare Schließfächer vorhanden sind, dauert das Iterieren über alle von ihnen k Schritte. Abhängig von Ihrer Prioritätswarteschlangenimplementierung müssen Sie möglicherweise Ihre Prioritätswarteschlange neu erstellen, wenn Sie sich alles ansehen. Dies würde k * log (k): (k <1000) Schritte erfordern. In der Array-Lösung müssen Sie nur ein 1000-Elemente-Array iterieren und prüfen, welche geöffnet sind. Sie können der Implementierung auch eine verfügbare oder verwendete Liste hinzufügen, um nur die Uhrzeit einzuchecken.
quelle
Das Algorithm Design Manual von Steven S. Skiena scheint die Quelle zu sein, nach der Sie suchen. Der zweite Teil ist eine klassifizierte Liste von Problemen mit einer Überprüfung der zugehörigen Algorithmen. Es gibt eine Webversion .
quelle
Es gibt kein "sollte". A. Machen Sie sich mit den grundlegenden Komplexitätsklassen (linear, logarithmisch usw.) vertraut. B. Stellen Sie fest, dass Sie mit einem einfachen Array so gut wie alles tun können, wie mit einer ausgefallenen Datenstruktur wie einem B-Baum. Der Trick bei der Auswahl der geeigneten Struktur / des geeigneten Algorithmus besteht darin, die Leistung, die erwartete Eingabegröße und die Komplexität der Implementierung in Einklang zu bringen.
Dann gibt es abstrakte, aber immens nützliche Dinge (obwohl die Nützlichkeit nicht sofort offensichtlich ist): Zustandsmaschinen, Graphentheorie, Konvexitätstheorie (lineare Programmierung usw.).
quelle
Das MIT veröffentlicht kostenlose Vorlesungsunterlagen, Videos, Aufgaben und Prüfungsunterlagen zur Einführung in Algorithmen . In den Vorlesungstiteln sind die behandelten Algorithmen / Datenstrukturen aufgeführt.
Dies ist ein von Experten überprüfter Konsens darüber, was Sie wissen sollten. Es ist wahrscheinlich auch eine großartige Lernressource.
quelle