Ein guter Algorithmus geht in der Regel mit einer Reihe guter Datenstrukturen einher, die es dem Algorithmus ermöglichen, die Daten effizient zu manipulieren. In diesem Online-Kurs befassen wir uns mit den gängigen Datenstrukturen, die bei verschiedenen Berechnungsproblemen verwendet werden. Sie lernen, wie diese Datenstrukturen in verschiedenen Programmiersprachen implementiert werden und üben ihre Umsetzung in unseren Programmieraufgaben. Dies wird Ihnen helfen zu verstehen, was in einer bestimmten eingebauten Implementierung einer Datenstruktur vor sich geht und was Sie von ihr erwarten können. Sie werden auch typische Anwendungsfälle für diese Datenstrukturen kennen lernen. Einige Beispiele für Fragen, die wir in diesem Kurs behandeln werden, sind die folgenden: 1. Was ist eine gute Strategie für die Größenänderung eines dynamischen Arrays? 2. Wie werden Prioritätswarteschlangen in C++, Java und Python implementiert? 3. Wie implementiert man eine Hashtabelle so, dass die amortisierte Laufzeit aller Operationen im Durchschnitt O(1) ist? 4. Was sind gute Strategien, um einen Binärbaum im Gleichgewicht zu halten?
Datenstrukturen
Dieser Kurs ist Teil von Spezialisierung Datenstrukturen und Algorithmen
Dozenten: Neil Rhodes
284.637 bereits angemeldet
Bei enthalten
(5,470 Bewertungen)
Empfohlene Erfahrung
Kompetenzen, die Sie erwerben
- Kategorie: Prioritäts-Warteschlange
- Kategorie: Binärer Suchbaum
- Kategorie: Hash-Tabelle
- Kategorie: Liste
- Kategorie: Stack (Abstrakter Datentyp)
Wichtige Details
Zu Ihrem LinkedIn-Profil hinzufügen
9 Aufgaben
Erfahren Sie, wie Mitarbeiter führender Unternehmen gefragte Kompetenzen erwerben.
Erweitern Sie Ihre Fachkenntnisse
- Lernen Sie neue Konzepte von Branchenexperten
- Gewinnen Sie ein Grundverständnis bestimmter Themen oder Tools
- Erwerben Sie berufsrelevante Kompetenzen durch praktische Projekte
- Erwerben Sie ein Berufszertifikat zur Vorlage
Erwerben Sie ein Karrierezertifikat.
Fügen Sie diese Qualifikation zur Ihrem LinkedIn-Profil oder Ihrem Lebenslauf hinzu.
Teilen Sie es in den sozialen Medien und in Ihrer Leistungsbeurteilung.
In diesem Kurs gibt es 6 Module
In diesem Modul lernen Sie die grundlegenden Datenstrukturen kennen, die im weiteren Verlauf dieses Kurses verwendet werden. Wir beginnen dieses Modul mit einer detaillierten Betrachtung der grundlegenden Bausteine: Arrays und verknüpfte Listen. Von dort aus bauen wir zwei wichtige Datenstrukturen auf: Stapel und Warteschlangen. Als nächstes befassen wir uns mit Bäumen: Beispiele für ihre Verwendung in der Informatik, ihre Implementierung und die verschiedenen Möglichkeiten, sie zu durchlaufen. Wenn Sie dieses Modul abgeschlossen haben, werden Sie in der Lage sein, jede dieser Datenstrukturen zu implementieren und ein solides Verständnis für die Kosten der Operationen sowie für die Kompromisse bei der Verwendung jeder Datenstruktur haben.
Das ist alles enthalten
7 Videos7 Lektüren1 Aufgabe1 Programmieraufgabe
In diesem Modul besprechen wir Dynamische Arrays: eine Möglichkeit, Arrays zu verwenden, wenn im Voraus nicht bekannt ist, wie viele Elemente benötigt werden. Hier besprechen wir auch die amortisierte Analyse: eine Methode zur Bestimmung der amortisierten Kosten einer Operation über eine Folge von Operationen. Die amortisierte Analyse wird sehr häufig zur Analyse der Leistung von Algorithmen verwendet, wenn die direkte Analyse unbefriedigende Ergebnisse liefert, aber die amortisierte Analyse hilft zu zeigen, dass der Algorithmus tatsächlich effizient ist. Sie wird sowohl für die Analyse dynamischer Arrays als auch am Ende dieses Kurses für die Analyse von Splay-Bäumen verwendet.
Das ist alles enthalten
5 Videos1 Lektüre1 Aufgabe
Wir beginnen dieses Modul mit der Betrachtung von Prioritätswarteschlangen, die zur effizienten Planung von Aufträgen verwendet werden, entweder im Kontext eines Computerbetriebssystems oder im wirklichen Leben, zum Sortieren großer Dateien, was der wichtigste Baustein für jeden Big Data-Verarbeitungsalgorithmus ist, und zur effizienten Berechnung kürzester Pfade in Graphen, ein Thema, das wir in unserem nächsten Kurs behandeln werden. Aus diesem Grund gibt es für Prioritätswarteschlangen in vielen Programmiersprachen, darunter C++, Java und Python, integrierte Implementierungen. Wir werden sehen, dass diese Implementierungen auf der schönen Idee beruhen, einen kompletten Binärbaum in einem Array zu speichern, das es ermöglicht, alle Prioritätswarteschlangenmethoden in nur wenigen Zeilen Code zu implementieren. Anschließend werden wir zur Datenstruktur der disjunkten Mengen übergehen, die z.B. bei der dynamischen Graphenkonnektivität und der Bildverarbeitung verwendet wird. Wir werden wieder sehen, wie einfache und natürliche Ideen zu einer Implementierung führen, die sowohl einfach zu programmieren als auch sehr effizient ist. Nach Abschluss dieses Moduls werden Sie in der Lage sein, diese beiden Datenstrukturen von Grund auf effizient zu implementieren.
Das ist alles enthalten
15 Videos6 Lektüren3 Aufgaben1 Programmieraufgabe1 Plug-in
In diesem Modul lernen Sie eine sehr leistungsfähige und weit verbreitete Technik namens Hashing kennen. Zu seinen Anwendungen gehören die Implementierung von Programmiersprachen, Dateisystemen, Mustersuche, verteilte Schlüssel-Wert-Speicherung und vieles mehr. Sie lernen, wie man Datenstrukturen zum Speichern und Ändern von Objektmengen und Zuordnungen von einem Objekttyp zu einem anderen implementiert. Sie werden sehen, dass naive Implementierungen entweder riesige Mengen an Speicher verbrauchen oder langsam sind. Dann werden Sie lernen, wie man Hash-Tabellen implementiert, die linearen Speicher verbrauchen und im Durchschnitt in O(1) arbeiten! Schließlich werden Sie lernen, wie Hash-Funktionen in modernen verteilten Systemen eingesetzt werden und wie sie zur Optimierung der Speicherung von Diensten wie Dropbox, Google Drive und Yandex Disk verwendet werden!
Das ist alles enthalten
20 Videos4 Lektüren2 Aufgaben1 Programmieraufgabe
In diesem Modul befassen wir uns mit binären Suchbäumen, einer Datenstruktur für die Suche in sich dynamisch verändernden geordneten Mengen. Sie werden viele der Schwierigkeiten bei der Bewältigung dieser Aufgabe kennenlernen und erfahren, wie wir sie überwinden können. Dazu müssen Sie die Grundstruktur von binären Suchbäumen kennen, wissen, wie man einfügt und löscht, ohne diese Struktur zu zerstören, und wie man sicherstellt, dass der Baum ausgeglichen bleibt.
Das ist alles enthalten
7 Videos2 Lektüren1 Aufgabe
In diesem Modul setzen wir das Studium der binären Suchbäume fort. Wir studieren ein paar nicht-triviale Anwendungen. Anschließend untersuchen wir die neue Art von ausgewogenen Suchbäumen - Splay Trees. Sie passen sich dynamisch an die Abfragen an und sind in vielerlei Hinsicht optimal.
Das ist alles enthalten
4 Videos2 Lektüren1 Aufgabe1 Programmieraufgabe
Dozenten
Empfohlen, wenn Sie sich für Algorithmen interessieren
University of California San Diego
Tsinghua University
University of Illinois Urbana-Champaign
Warum entscheiden sich Menschen für Coursera für ihre Karriere?
Bewertungen von Lernenden
Zeigt 3 von 5470
5.470 Bewertungen
- 5 stars
73,55 %
- 4 stars
20,70 %
- 3 stars
3,59 %
- 2 stars
0,73 %
- 1 star
1,40 %
Geprüft am 22. Nov. 2019
Geprüft am 7. Feb. 2020
Geprüft am 26. Sep. 2020
Neue Karrieremöglichkeiten mit Coursera Plus
Unbegrenzter Zugang zu über 7.000 erstklassigen Kursen, praktischen Projekten und Zertifikatsprogrammen, die Sie auf den Beruf vorbereiten – alles in Ihrem Abonnement enthalten
Bringen Sie Ihre Karriere mit einem Online-Abschluss voran.
Erwerben Sie einen Abschluss von erstklassigen Universitäten – 100 % online
Schließen Sie sich mehr als 3.400 Unternehmen in aller Welt an, die sich für Coursera for Business entschieden haben.
Schulen Sie Ihre Mitarbeiter*innen, um sich in der digitalen Wirtschaft zu behaupten.
Häufig gestellte Fragen
Der Zugang zu Vorlesungen und Aufgaben hängt von der Art Ihrer Einschreibung ab. Wenn Sie einen Kurs im Prüfungsmodus belegen, können Sie die meisten Kursmaterialien kostenlos einsehen. Um auf benotete Aufgaben zuzugreifen und ein Zertifikat zu erwerben, müssen Sie die Zertifikatserfahrung während oder nach Ihrer Prüfung erwerben. Wenn Sie die Prüfungsoption nicht sehen:
Der Kurs bietet möglicherweise keine Prüfungsoption. Sie können stattdessen eine kostenlose Testversion ausprobieren oder finanzielle Unterstützung beantragen.
Der Kurs bietet möglicherweise stattdessen die Option 'Vollständiger Kurs, kein Zertifikat'. Mit dieser Option können Sie alle Kursmaterialien einsehen, die erforderlichen Bewertungen abgeben und eine Abschlussnote erhalten. Dies bedeutet auch, dass Sie kein Zertifikat erwerben können.
Wenn Sie sich für den Kurs einschreiben, erhalten Sie Zugang zu allen Kursen der Specializations, und Sie erhalten ein Zertifikat, wenn Sie die Arbeit abgeschlossen haben. Ihr elektronisches Zertifikat wird Ihrer Erfolgsseite hinzugefügt - von dort aus können Sie Ihr Zertifikat ausdrucken oder zu Ihrem LinkedIn-Profil hinzufügen. Wenn Sie die Kursinhalte nur lesen und ansehen möchten, können Sie den Kurs kostenlos besuchen.
Wenn Sie ein Abonnement abgeschlossen haben, erhalten Sie eine kostenlose 7-tägige Testphase, in der Sie kostenlos kündigen können. Danach gewähren wir keine Rückerstattung, aber Sie können Ihr Abonnement jederzeit kündigen. Siehe unsere vollständigen Rückerstattungsbedingungen.