Spezialisierung für Datenstrukturen und Algorithmen

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?

Sie werden auch erfahren, wie Dienste wie Dropbox es schaffen, große Dateien sofort hochzuladen und eine Menge Speicherplatz zu sparen!

Wenn Sie jemals einen Navigationsdienst genutzt haben, um die optimale Route zu finden und die Zeit bis zum Ziel abzuschätzen, haben Sie Algorithmen auf Graphen verwendet. Graphen kommen in verschiedenen realen Situationen vor, wie z.B. in Straßennetzen, Computernetzwerken und neuerdings auch in sozialen Netzwerken! Wenn Sie nach der schnellsten Zeit für den Weg zur Arbeit suchen, nach dem günstigsten Weg, eine Reihe von Computern zu einem Netzwerk zu verbinden oder nach einem effizienten Algorithmus, um automatisch Gemeinschaften und Meinungsführer in Facebook zu finden, werden Sie mit Graphen und Algorithmen auf Graphen arbeiten. In diesem Online-Kurs lernen Sie zunächst, was ein Graph ist und welches einige der wichtigsten Eigenschaften sind. Dann lernen Sie verschiedene Möglichkeiten kennen, Graphen zu durchlaufen und wie Sie nützliche Dinge tun können, während Sie den Graphen in einer bestimmten Reihenfolge durchlaufen. Anschließend werden wir über Algorithmen für kürzeste Wege sprechen - von den grundlegenden bis hin zu den Algorithmen, die die Tür für 1000000 Mal schnellere Algorithmen öffnen, die in Google Maps und anderen Navigationsdiensten verwendet werden. Sie werden diese Algorithmen verwenden, wenn Sie sich für die Arbeit an unserem Fast Shortest Routes industrial capstone project entscheiden. Den Abschluss bilden die Minimum Spanning Trees, die für die Planung von Straßen-, Telefon- und Computernetzen verwendet werden und auch bei Clustering- und Approximationsalgorithmen Anwendung finden.

Die Welt und das Internet sind voll von textlichen Informationen. Wir suchen nach Informationen mithilfe von Textabfragen, wir lesen Websites, Bücher, E-Mails. Aus der Sicht der Informatik sind das alles Strings. Um all diese Informationen sinnvoll zu nutzen und die Suche effizient zu gestalten, verwenden Suchmaschinen viele String-Algorithmen. Auch die aufkommende personalisierte Medizin verwendet viele Suchalgorithmen, um krankheitsverursachende Mutationen im menschlichen Genom zu finden. In diesem Online-Kurs lernen Sie die wichtigsten Konzepte des Mustervergleichs kennen: Tries, Suffixbäume, Suffix-Arrays und sogar die Burrows-Wheeler-Transformation.

In den vorangegangenen Kursen unserer Online-Spezialisierung haben Sie die grundlegenden Algorithmen erlernt. Jetzt sind Sie bereit, in den Bereich der komplexeren Probleme und Algorithmen zu deren Lösung vorzustoßen. Fortgeschrittene Algorithmen bauen auf den grundlegenden Algorithmen auf und verwenden neue Ideen. Wir beginnen mit Netzwerkflüssen, die in typischen Anwendungen wie optimalen Übereinstimmungen, der Suche nach disjunkten Pfaden und der Flugplanung verwendet werden, aber auch in eher überraschenden Anwendungen wie der Bildsegmentierung in der Computer Vision. Dann fahren wir mit der linearen Programmierung fort, die bei der Optimierung der Budgetzuweisung, der Portfolio-Optimierung, der Suche nach der billigsten Diät, die alle Anforderungen erfüllt, und vielen anderen Anwendungen zum Einsatz kommt. Als nächstes erörtern wir inhärent schwierige Probleme, für die keine exakten guten Lösungen bekannt sind (und wahrscheinlich auch nicht gefunden werden) und wie man sie in der Praxis löst. Wir schließen mit einer sanften Einführung in Streaming-Algorithmen, die bei der Verarbeitung von Big Data häufig verwendet werden. Solche Algorithmen sind in der Regel so konzipiert, dass sie riesige Datensätze verarbeiten können, ohne dass sie überhaupt einen Datensatz speichern können.

Im Frühjahr 2011 wurden Tausende von Menschen in Deutschland mit einer tödlichen Krankheit ins Krankenhaus eingeliefert, die als Lebensmittelvergiftung mit blutigem Durchfall begann und häufig zu Nierenversagen führte. Es war der Beginn des tödlichsten Ausbruchs in der jüngeren Geschichte, verursacht durch einen mysteriösen Bakterienstamm, den wir als E. coli X bezeichnen. Schon bald brachten deutsche Beamte den Ausbruch mit einem Restaurant in Lübeck in Verbindung, in dem fast 20% der Gäste innerhalb einer einzigen Woche blutigen Durchfall entwickelt hatten. Zu diesem Zeitpunkt wussten die Biologen, dass sie es mit einem bisher unbekannten Erreger zu tun hatten und dass herkömmliche Methoden nicht ausreichen würden - es würden Computerbiologen benötigt, um das Genom des neu aufgetauchten Erregers zusammenzusetzen und zu analysieren. Um den evolutionären Ursprung und das pathogene Potenzial des Ausbruchsstammes zu untersuchen, starteten die Forscher ein Crowdsourced Research Programm. Sie veröffentlichten die bakteriellen DNA-Sequenzierungsdaten eines Patienten, was eine Flut von Analysen auslöste, die von Computerbiologen auf vier Kontinenten durchgeführt wurden. Sie nutzten sogar GitHub für das Projekt: https://github.com/ehec-outbreak-crowdsourced/BGI-data-analysis/wiki Der Ausbruch in Deutschland 2011 war ein frühes Beispiel für die Zusammenarbeit von Epidemiologen mit Computerbiologen, um einen Ausbruch zu stoppen. In diesem Online-Kurs werden Sie in die Fußstapfen der Bioinformatiker treten, die den Ausbruch untersuchten, indem Sie ein Programm entwickeln, das das Genom von E. coli X aus Millionen von sich überschneidenden Teilstücken des E.coli X-Genoms zusammensetzt.