Das Video kommt von YouTube: erst beim Abspielen verbindet sich die Seite mit YouTube (Google).
Algorithmen und Datenstrukturen | Crashkurs für Anfänger
Das Wichtigste aus dem Video
Tipp auf eine Zeit – das Video springt genau dorthin.
Transkriptautomatisch erstellt · 120 Zeilen
- Heute wirst du die Grundlagen in Algorithmen und Datenstrukturen lernen. Diese Themen sind super wichtig in der Informatik und in dem Bereich Data
- Science und werden auch häufig in IT Bewerbungsgesprächen abgefragt. Deshalb erkläre ich dir die wichtigsten Konzepte so für den nächsten IT-SJob richtig gut
- vorbereitet bist. Mein Name ist Fabian Rappert und mein Job ist es seit Jahren Themen im Bereich Data Science so beizubringen, dass Leute einen guten Job
- in diesem Bereich finden können. Wir schauen uns heute zuerst an. Erstens, was genau sind Algorithmen und Datenstrukturen? Zweitens, dann reden
- wir darüber, was macht eigentlich einen effizienten Algorithmus aus? Und dann vergleichen wir noch die wichtigsten Datenstrukturen und Algorithmen. Also,
- legen wir los. In den meisten Anwendungen arbeiten wir mit großen Mengen von Daten. Z.B. Wenn wir ein Onlineshop haben, dann müssen wir Daten
- über Produkte, Nutzer und Filialen skalerbar und sicher abspeichern können. Datenstrukturen helfen genau dabei. Wenn du schon mal einige Zahlen Code
- geschrieben hast, wirst du Datenstrukturen wie z.B. Listen oder auch Wörterbücher vielleicht schon kennen. Algorithmen auf der anderen
- Seite sind Schritt für Schritt Anweisungen zur Lösung von Problemen. Du kannst den Algorithmus wie einen Rezept vorstellen. Es gibt eine Eingabe,
- nämlich die Zutaten. Es folgen klar definierte Anweisungen und die erzeugen am Ende eine Ausgabe, nämlich das Gericht. Datenstrukturen definieren
- also, wo und wie Daten gespeichert werden und Algorithmen entscheiden dann, was mit diesen Daten geschieht. Algorithmen und Datenstrukturen sind
- dabei zwei unterschiedliche Themen, gehören aber häufig zusammen. Und der relevante Punkt, um diese Themen wirklich zu verstehen, ist Effizienz.
- Das Thema Effizienz kannst du dir vorstellen wie bei dir selbst. Wenn du zehn Aufgaben in 5 Stunden schaffst, hast du nicht so effizient gearbeitet,
- wie wenn du zehn Aufgaben in einer Stunde schaffst. Und genauso bei Algorithmen und Datenstrukturen gibt die Effizienz an, wie viel Ressourcen, wie
- viel Arbeitsschritte und wie viel Zeit du benötigst. Während du in diesem Beispiel nur zehn Aufgaben hattest oder in deinem Kochrezept nur fünf Zutaten
- vorkommen, so verarbeiten Algorithmen oft 100000ende Datenpunkte. Und zu sagen, wie effizient dein Algorithmus ist, benutzen wir die sogenannte Big
- Onotation. Lass uns das mal am Beispiel erklären. O von 1. Wir haben eine Einkaufsliste mit fünf Artikeln und wollen den ersten kaufen. Der Zugriff
- auf das erste Element der Liste ist konstant schnell, denn er fordert nur eine Operation. Dabei ist es komplett egal, ob die Liste 5, 20 oder 10.000
- Elemente enthält. Es wird immer eine Operation sein. Das wäre daher der maximal effiziente Algorithmus. Diesen einfachen Algorithmus markiert man mit
- der Notation O von 1. Wichtig ist hier, dass die Zahl von der Operation nicht genau berechnet wird. Es geht hier einfach nur ganz abstrakt um den
- langfristigen Trend, nämlich, dass die Anzahl an Arbeitsschritten gleich bleibt. Egal wie lang diese Liste ist, egal ob es O von 1 oder O von 5 ist.
- Immer wenn wir eine konstante Anzahl von Arbeitsschritten haben, sprechen wir von O von 1. Häufig ist aber so, dass die Operation proportional zur Eingabemenge
- wachsen. Wenn du beispielsweise alle Mangos auf der Liste suchen möchtest, dann bräuchtest du nicht nur einen Arbeitsschritt, sondern wir müssten uns
- ja jedes einzelne Element in der Liste anschauen und fragen, ist das eine Mango? In diesem Fall ist die Anzahl einer forderlichen Operation gleich der
- Anzahl an Elementen n. Und deshalb wird es mit der Notation O von N beschrieben. Auch wenn die Operationen halb so viel oder zehn mal so viel wären, wie es
- Elemente in der Liste gibt, ist es egal, wie steil die gerade Linie nach oben geht. Es wäre trotzdem O von N. O von N². Hätten wir jetzt einen Algorithmus,
- der alle mehrfach vorkommenden Elemente aus der Liste löschen soll, dann müsste sich dieser für jeden zusätzlichen Artikel auf der Liste alle anderen
- vorgehenden Artikel auf der Liste anschauen. Das wäre damit O von N². Es gibt dann noch weitere Notationen sowie O von Logarithmus n oder o von 2 hoch n.
- Es bleibt aber gleich. Je flacher die Linie ist, desto effizienter ist er. Solange wir jetzt zehn Artikel haben, sieht man das noch nicht so gut. Aber
- wenn wir jetzt die Eingabemenge stark erhöhen, dann wird sofort klar, warum das so wichtig ist. Das heißt, wir haben hier bei einer Eingabemenge von 10, da
- ist O von 1 1. O von Logarithm n auch 1. O von N ist dann 10. O von N hoch 2= 100, O von 2 hoch n= 1024 und O von N Fakultät ist über 3 Millionen. Aber wenn
- wir jetzt nur eine Spalte weitergehen und die Eingabemenge 50 ist, dann sind wir bei O von 1, also einem Konstantenalgorithmus, immer noch bei 1.
- von Logarithmus n sind wir bei 1,7, bei Linearen schon bei 50, bei quadratisch bei 2500 und bei Exponential oder der Fakultät so viel mehr als Millionen oder
- Milliarden, dass wir diese Zahl hier gar nicht auf dem Computer kriegen. Das heißt, es geht hierbei vor allem um den Trend, wie dieser sich entwickelt, vor
- allem bei sehr, sehr großen Eingabemengen. Das ist nur ein grober Überblick über die Notatation und wir werden demnächst auf dem YouTube-Kanal
- hier noch einen Video explizit dazu machen, weil es einfach ein super spannendes und wichtiges Thema ist. Jetzt wissen wir, wie wir Operation und
- Algorithmen miteinander vergleichen können und können daher über Datenstrukturen reden. Und wir fangen direkt mit der ersten an, Arrays.
- Arrays, manchmal auch Listen genannt, speichern Elemente über einen Index. Wichtig dabei ist das sogenannte Zero based Numbering. Das heißt, die Zahl 0
- ist immer der erste Index. Das heißt, in einer Liste mit Apfel, Banane und Kirschen liefert der Zugriff auf das Element mit dem Index 1, die Ausgabe
- Banane. Die Elemente in der Liste müssen daher auch im physischen Memory nacheinander abgespeichert werden. Diese können wir uns wie eine riesige Matrix
- vorstellen. Der Compiler muss daher schon beim Initialisieren der Liste wissen, wie viel Speicherplatz erforderlich ist, um alle Elemente in
- der Liste auf der gleichen Reihe abspeichern zu können. In diesem Fall haben wir fünf Elemente und wir müssen in der Matrix auch fünf Kästchen
- freihalten. Da beides die Adresse der Liste, also die Startposition und der Index des abgefragten Elementes schon bekannt sind, kann ein Array Elemente
- sehr effizient abfragen. Um jetzt hier in dem Beispiel die Zahl 8 zu bekommen, müssen wir einfach die Startposition mit dem Index 2 addieren, um so den
- Speicherort rauszubekommen. Das heißt, wenn wir auf ein Element zugreifen wollen, ist es uns egal, wie groß die Liste ist. Diese Operation wird daher
- mit O von 1 beschrieben, denn wir haben eine konstante Anzahl Operation unabhängig von der Listengröße. Wenn wir jetzt aber eine Zahl am Ende des Arrays
- hinzufügen wollen, müssen wir sicherstellen, dass wir Werte nicht aus Versehen überschreiben, wie z.B. wir hier die Variable, die nach dem Array
- gespeichert wurde. Deshalb müssen wir die Liste mit der neuen Menge komplett auf einen neuen Speicherorto übertragen. Das gleiche gilt aber auch beim
- Entfernen. Wenn wir jetzt die Zahl 8 löschen, wird die neue Liste mit den neuen Indes auf einen neuen Speicherort dupliziert. Insgesamt brauchen wir dann
- dafür N Operation. Je größer die Liste ist, desto mehr Operation brauchen wir. Also haben wir hier eine O von N. Der nächste Datentyp sind Linked Lists.
- Listen sind super und total praktisch. Allerdings können diese häufig ineffizient sein. Verlinkte Listen erlauben uns Elemente flexibler
- anzulegen. Hier wird jedes Element als ein Node dargestellt und es besitzt keinen Index, sondern den Speicherplatz vom nächsten Element. Somit können wir
- Elemente einzeln auf der Memory abspeichern. Die Liste fängt mit der zwei an, diese zeigt auf den Speicherort der 7, diese auf den Speicherort der 8
- und so weiter. Die fünf ist in diesem Beispiel das letzte Element und zeigt auf kein weiteres Element. Da nun jedes Element den Nachfolger besitzt, können
- wir auch super effizient Elemente hinzufügen oder auch entfernen oder aber auch die Reihenfolge der Elemente anpassen. Nun können wir mit einer
- Komplexität von O von 1 Elemente hinzufügen oder entfernen. Wir haben aber den Tradeoff, dass der Zugäuf auf ein bestimmtes Element O von N ist, da
- wir durch die einzelnen Notes durchgehen müssen. Es ist also komplett umgedreht wie bei einem Array. Wichtig ist ja auch, dass die Pfeile gerichtet sind und
- wir nur von vorne navigieren können. Eine Dubly Linkless ist natürlich auch möglich, um das Element davorzubekommen. Hashmaps. Hashmaps, die wir in Python
- als Dictionary kennen, nutzen ein Schlüsselwertpaar, um auf Daten zuzugreifen. Mit Hilfe einer sogenannten Hashfunktion wird ein Schlüssel, wie
- z.B. hier der Name, intern in eine ganze Zahl umgewandelt. Und diese Zahl wird dann als Index verwendet, um den dazugehörigen Wert Kräutert in diesem
- Falle effizient abzulegen oder wiederzufinden. Dadurch brauchen wir, egal wie groß unser Dictionary ist, immer die gleiche Anzahl an Operationen.
- Das wäre dann, du ahnst das schon, die Operation O von 1. Sowohl fürs Durchsuchen als auch fürs entfernen und hinzufügen. Also super effizient. Stacks
- undes. Zwei weitere Datenstrukturen, die in der Informatik häufig verwendet werden, sind der Stack und die Queue. Ein Stack funktioniert nach dem Last in
- First Out Prinzip. Das bedeutet, dass das zuletzt hinzugefügte Element als erstes wieder entfernt wird. Ähnlich wie bei einem Stapel von Tellern. Man legt
- neue Teller oben drauf und nimmt sie dann auch wieder von oben runter. Die beiden wichtigsten Operationen eines Stacks sind Push, ein Element oben drauf
- legen und Pop, das oberste Element, entfernen. Stacks werden z.B. bei rückgängig Operationen, z.B. wenn du Steuerung Z auf dein Programm drückst
- oder im Callstack eines Programms verwendet, um die Reihenfolge der Funktionsaufrufe zu sichern. Eine Queue dagegen folgt dem First in First Out
- Prinzip. Das bedeutet, dass das als allererstes eingefügte Element auch zuerst entfernt wird, wie bei einer Warteschlange im Supermarkt. Wer zuerst
- ansteht, wird auch zuerst bedient oder auf einer Musikapp, wo du ein Lied zur Warteschlange hinzufügst. Die grundlegenden Operationen einer Q
- ein Element hinten ranstellen und DQ ein Element von vorne entfernen. Qes kommen häufig zum Einsatz bei Druckaufträgen, Datenübertragung oder Task Scheduling.
- Beide Datenstrukturen kann man auch mit einem Array darstellen. Graphs. Häufig brauchen wir aber nicht die Daten selbst, sondern wollen auch deren
- Beziehung darstellen. Ein Graf stellt eine Menge von Knoten und deren Beziehung zueinander dar. Er eignet sich besonders gut zur Modellierung von
- Netzwerken, wie z.B. Google Maps und den besten Weg vorzuschlagen oder soziale Netzwerke, um Person in Beziehung zueinander zuetzen. In einem gerichteten
- Graf spielt die Richtung der Verbindung eine Rolle, z.B. bei einem Link von einer Webseite zu einer anderen, während bei einem ungerichteten Graf die
- Verbindung für eine wechselseitige Beziehung steht, z.B. eine Freundschaft. Zusätzlich können wir Grafen mit einem Zahlenwert gewichten, etwa die
- Entfernung, Kosten und Zeit. Diese Art von Grafen wird oft in Routenplanern oder Optimierungsproblemen eingesetzt. Zum Schluss gibt es den Baum, eine
- spezielle Form eines Grafen, bei dem es keine Zyklen gibt und die Knoten in einer hierarchischen Struktur organisiert sind. Er eignet sich
- hervorragend für die Darstellung von Entscheidungsprozessen oder organisierten Daten, z.B. in Dateisystem, wie du es z.B. auf deinem
- Laptop hast, Stammbaumstrukturen oder Suchalgorithmen. Eine besonders häufig verwendete Baumstruktur ist der binäre Baum, bei dem jeder Knoten höchstens
- zwei Kinder hat. Ein Binary Tree, bei dem alle Werte links kleiner und alle Werte rechts größer als die der Knoten sind. Ermöglicht effiziente Operationen
- zum Suchen, Einfügen und auch Löschen. Algorithmen. Es gibt viele verschiedene grundlegende Arten von Algorithmen, die sich sowohl durch ihre Funktionsweise
- als auch durch den Bereich, wo sie angewendet werden, unterscheiden. Erstens, Sortieralgorithmen. Stell dir vor, du arbeitest in der Bibliothek und
- du wirst beauftragt, alle Bücher alphabetisch zu sortieren. Wie kannst du diese Aufgabe so effizient wie nur möglicht erledigen? Sortieralgorithmen
- dienen dazu, Elemente in einer Liste in eine vordefinierte Reihenfolge zu sortieren, z.B. Bücher alphabetisch zu sortieren. Es gibt unterschiedlichste
- Sortierealgorithmen und die haben eben alle ihre Vor und aber auch Nachteile. Z.B. der Bubbles Sort, der vergleicht immer zwei benachbarte Elemente und
- vertauscht sie. Also natürlich nur, wenn sie davor in der falschen Reihenfolge sind. Dieser Vorgang wird dann für alle Elemente automatisch ausgeführt und so
- lange wiederholt, bis tatsächlich die Elemente in der richtigen Reihenfolge sind. Der Insertion Sort baut eine sortierte Teilliste auf, in neue
- Elemente direkt an die richtigen Stellen eingefügt werden. Ähnlich wenn du beispielsweise Spielkarten in der Hand hast und du die manuell sortieren
- müsstest. Diese Sortieralgorithmen sind einfach zu verstehen, aber ziemlich ineffizient gerade bei vielen Elementen, da sie im Durchschnitt eine quadratische
- Laufzeit von O von N² haben, da wir häufig sehr viel miteinander vergleichen müssen. Effizienter sind hier der Merch Sort und auch Quicksort, die im
- Durchschnitt mit O von N Logarithmus N arbeiten. Das ist deutlich schneller und wird deshalb sehr sehr häufig in der Praxis verwendet. Der Merchsort teilt
- die Liste rekursiv in zwei Hälften, sortiert jede Hälfte und führt sie dann anschließend zusammen. Durch diese Aufteilungen kleine vortierte Listen
- werden im Schnitt weniger Operationen ausgeführt. Schließlich wählt der Quicksort ein Pivotelement und dann alle kleineren Elemente nach links und alle
- größeren Elemente nach rechts und sortiert dann die Teillisten rekursiv, bis alle Elemente sortiert sind. Suchchalgorithmen. Succhalgorithmen
- werden verwendet, um ein bestimmtes Element in einer Datenliste zu finden. Die einfachste Variante ist hierbei die lineare Such, bei der alle Elemente der
- Reihe nach durchsucht werden. Mit einer durchschnittlichen Laufzeit kannst ihr vielleicht denken, O von N. Wesentlich schneller ist dann die binäre Suche.
- Diese funktioniert jedoch nur auf sortierten Listen. Sie durchsucht das mittlere Element und vergleicht das dann mit dem gesuchten Wert und entscheidet
- dann, ob sie im linken oder rechten Teil weiter. Sie halbiert hierbei bei jedem Schritt den Suchbereich und so erreicht sie dann eine Laufzeit von O von
- Logarithmus n. Suchagorithmen werden im täglichen Leben ziemlich häufig verwendet, ohne dass wir wahrscheinlich darüber nachdenken. Sie spielen eine
- zentrale Rolle in vielen Bereichen der Informatik, wie z.B. bei Datenbanksystem, Textverarbeitung, KI und vieles weitere. Grafenalgorithmen
- kommen zum Einsatz, wenn Daten als Netzwerke organisiert sind. Ein sozialer Netzwerkgraf soll Freundeskreise und Verbindungswege analysieren. Wenn man
- also einen Grafen durchlaufen möchte, gibt es zwei ziemlich bekannte Algorithmen. Tiefensuche und die Breitensuche. Die Tiefensuche beginnt an
- einem Startknoten und verzweigt sich dann so tief wie möglich, bevor sie zurückkehrt. Die Breitensuche erkundet den nächstgelegenen Nachbarn zuerst und
- geht dann Ebene für Ebene weiter, bis sie schließlich das Ziel erreicht. Weiterhin sind für Algorithmen für die kürzeste Suche die Algorithmen Jigstra
- und A Sternchen am weitesten verbreitet. Das klassische Beispiel hierfür ist Navigation und Routenplanung, wobei diese beiden Algorithmen Entfernung zu
- beiden Zielen minimieren können. Auch Algorithmen wie Grußgral oder PRIM zur Berechnung minimaler Spannbäume sind Teile dieser Kategorie, um die
- Gesamtkosten eines Grafen zu minimieren und ein effizientes Netzwerk aufzubauen. Rekursive Algorithmen. Schließlich zeichnen sich rekursive Algorithmen
- dadurch aus, dass sie sich selbst immer und immer wieder aufrufen. Sie eignen sich besonders gut für Probleme, die sich natürlich in Teilprobleme
- organisieren lassen, wie z.B. das Berechnen der Fibonacci Zahlen oder das Durchlaufen von Baumstrukturen. Hier rechnet man immer tiefer und tiefer. Ein
- gutes Beispiel, um das einfach zu verstehen, ist die Fakultät. Die Fakultät von 4 ist ausgerechnet 4* 3* 2* 1geschrieben
- 4* 3 Fakultät oder 4* 3* 2 Fakultät. Das heißt, wir müssen hier rekursiv die Fakultät zunächst von 3 ausrechnen, welche wiederum die Fakultät von 2
- braucht und so weiter, bis wir ans finale Ergebnis kommen. Insgesamt sind Algorithmen und Datenstrukturen sehr große Themen. In diesem Video gab es nun
- eine kleine Einführung in die wichtigsten Begriffe. Zu diesen Themen wird es wahrscheinlich bald noch einen längeren Kurs auf diesem YouTube-Kanal
- geben und sonst würdest du sie natürlich auch ausführlich lernen in eine unserer Weiterbildung zum Data Scientist oder Date Analyst. Wenn du arbeitslos bist,
- sind diese Weiterbildung übrigens komplett kostenlos für dich mit einem sogenannten Bildungsgutschein. Auch manche Personen im Job können diese
- Weiterbildungen komplett finanziert bekommen durch das sogenannte Qualifizierungs- und Chancengesetz. Gerade für Arbeitslose, die Lust haben,
- in die IT einzusteigen, aber vielleicht noch ein paar Qualifikulationen brauchen, ist das eine super Gelegenheit, denn wir begleiten dich
- 100% ortsunabhängig von keiner Erfahrung bis zu deinem ersten ITJob. Mehr Informationen findest du auf unserer Webseite, die verlinke ich dir einfach
- mal in der Videobeschreibung. Ansonsten hoffe ich, das Video konnte dir einiges beibringen zu Algorithmen und Datenstrukturen und ich würde sagen, wir
- sehen uns bald.