Algorithmen und Datenstrukturen | Crashkurs für Anfänger
Fabian Rappert | Data Science Institute
https://www.youtube.com/watch?v=Zk6UifZ1P-M

Transkript (automatisch erstellt)

0:00 Heute wirst du die Grundlagen in Algorithmen und Datenstrukturen lernen. Diese Themen sind super wichtig in der Informatik und in dem Bereich Data
0:08 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
0:17 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
0:25 in diesem Bereich finden können. Wir schauen uns heute zuerst an. Erstens, was genau sind Algorithmen und Datenstrukturen? Zweitens, dann reden
0:33 wir darüber, was macht eigentlich einen effizienten Algorithmus aus? Und dann vergleichen wir noch die wichtigsten Datenstrukturen und Algorithmen. Also,
0:41 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
0:48 über Produkte, Nutzer und Filialen skalerbar und sicher abspeichern können. Datenstrukturen helfen genau dabei. Wenn du schon mal einige Zahlen Code
0:57 geschrieben hast, wirst du Datenstrukturen wie z.B. Listen oder auch Wörterbücher vielleicht schon kennen. Algorithmen auf der anderen
1:04 Seite sind Schritt für Schritt Anweisungen zur Lösung von Problemen. Du kannst den Algorithmus wie einen Rezept vorstellen. Es gibt eine Eingabe,
1:12 nämlich die Zutaten. Es folgen klar definierte Anweisungen und die erzeugen am Ende eine Ausgabe, nämlich das Gericht. Datenstrukturen definieren
1:20 also, wo und wie Daten gespeichert werden und Algorithmen entscheiden dann, was mit diesen Daten geschieht. Algorithmen und Datenstrukturen sind
1:28 dabei zwei unterschiedliche Themen, gehören aber häufig zusammen. Und der relevante Punkt, um diese Themen wirklich zu verstehen, ist Effizienz.
1:36 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,
1:43 wie wenn du zehn Aufgaben in einer Stunde schaffst. Und genauso bei Algorithmen und Datenstrukturen gibt die Effizienz an, wie viel Ressourcen, wie
1:51 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
1:58 vorkommen, so verarbeiten Algorithmen oft 100000ende Datenpunkte. Und zu sagen, wie effizient dein Algorithmus ist, benutzen wir die sogenannte Big
2:06 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
2:15 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
2:25 Elemente enthält. Es wird immer eine Operation sein. Das wäre daher der maximal effiziente Algorithmus. Diesen einfachen Algorithmus markiert man mit
2:35 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
2:44 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.
2:52 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
3:01 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
3:09 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
3:17 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
3:27 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,
3:37 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
3:45 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.
3:57 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
4:05 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
4:13 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
4:27 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.
4:36 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
4:49 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
4:56 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
5:03 hier noch einen Video explizit dazu machen, weil es einfach ein super spannendes und wichtiges Thema ist. Jetzt wissen wir, wie wir Operation und
5:11 Algorithmen miteinander vergleichen können und können daher über Datenstrukturen reden. Und wir fangen direkt mit der ersten an, Arrays.
5:18 Arrays, manchmal auch Listen genannt, speichern Elemente über einen Index. Wichtig dabei ist das sogenannte Zero based Numbering. Das heißt, die Zahl 0
5:27 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
5:36 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
5:45 vorstellen. Der Compiler muss daher schon beim Initialisieren der Liste wissen, wie viel Speicherplatz erforderlich ist, um alle Elemente in
5:52 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
5:59 freihalten. Da beides die Adresse der Liste, also die Startposition und der Index des abgefragten Elementes schon bekannt sind, kann ein Array Elemente
6:09 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
6:18 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
6:26 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
6:34 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
6:42 gespeichert wurde. Deshalb müssen wir die Liste mit der neuen Menge komplett auf einen neuen Speicherorto übertragen. Das gleiche gilt aber auch beim
6:49 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
6:57 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.
7:06 Listen sind super und total praktisch. Allerdings können diese häufig ineffizient sein. Verlinkte Listen erlauben uns Elemente flexibler
7:14 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
7:24 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
7:32 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
7:41 wir auch super effizient Elemente hinzufügen oder auch entfernen oder aber auch die Reihenfolge der Elemente anpassen. Nun können wir mit einer
7:49 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
7:59 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
8:06 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
8:15 als Dictionary kennen, nutzen ein Schlüsselwertpaar, um auf Daten zuzugreifen. Mit Hilfe einer sogenannten Hashfunktion wird ein Schlüssel, wie
8:23 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
8:33 Falle effizient abzulegen oder wiederzufinden. Dadurch brauchen wir, egal wie groß unser Dictionary ist, immer die gleiche Anzahl an Operationen.
8:41 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
8:51 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
9:00 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
9:09 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
9:18 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
9:27 oder im Callstack eines Programms verwendet, um die Reihenfolge der Funktionsaufrufe zu sichern. Eine Queue dagegen folgt dem First in First Out
9:35 Prinzip. Das bedeutet, dass das als allererstes eingefügte Element auch zuerst entfernt wird, wie bei einer Warteschlange im Supermarkt. Wer zuerst
9:44 ansteht, wird auch zuerst bedient oder auf einer Musikapp, wo du ein Lied zur Warteschlange hinzufügst. Die grundlegenden Operationen einer Q
9:54 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.
10:04 Beide Datenstrukturen kann man auch mit einem Array darstellen. Graphs. Häufig brauchen wir aber nicht die Daten selbst, sondern wollen auch deren
10:12 Beziehung darstellen. Ein Graf stellt eine Menge von Knoten und deren Beziehung zueinander dar. Er eignet sich besonders gut zur Modellierung von
10:21 Netzwerken, wie z.B. Google Maps und den besten Weg vorzuschlagen oder soziale Netzwerke, um Person in Beziehung zueinander zuetzen. In einem gerichteten
10:29 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
10:38 Verbindung für eine wechselseitige Beziehung steht, z.B. eine Freundschaft. Zusätzlich können wir Grafen mit einem Zahlenwert gewichten, etwa die
10:46 Entfernung, Kosten und Zeit. Diese Art von Grafen wird oft in Routenplanern oder Optimierungsproblemen eingesetzt. Zum Schluss gibt es den Baum, eine
10:54 spezielle Form eines Grafen, bei dem es keine Zyklen gibt und die Knoten in einer hierarchischen Struktur organisiert sind. Er eignet sich
11:02 hervorragend für die Darstellung von Entscheidungsprozessen oder organisierten Daten, z.B. in Dateisystem, wie du es z.B. auf deinem
11:09 Laptop hast, Stammbaumstrukturen oder Suchalgorithmen. Eine besonders häufig verwendete Baumstruktur ist der binäre Baum, bei dem jeder Knoten höchstens
11:18 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
11:28 zum Suchen, Einfügen und auch Löschen. Algorithmen. Es gibt viele verschiedene grundlegende Arten von Algorithmen, die sich sowohl durch ihre Funktionsweise
11:36 als auch durch den Bereich, wo sie angewendet werden, unterscheiden. Erstens, Sortieralgorithmen. Stell dir vor, du arbeitest in der Bibliothek und
11:43 du wirst beauftragt, alle Bücher alphabetisch zu sortieren. Wie kannst du diese Aufgabe so effizient wie nur möglicht erledigen? Sortieralgorithmen
11:52 dienen dazu, Elemente in einer Liste in eine vordefinierte Reihenfolge zu sortieren, z.B. Bücher alphabetisch zu sortieren. Es gibt unterschiedlichste
12:02 Sortierealgorithmen und die haben eben alle ihre Vor und aber auch Nachteile. Z.B. der Bubbles Sort, der vergleicht immer zwei benachbarte Elemente und
12:10 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
12:17 lange wiederholt, bis tatsächlich die Elemente in der richtigen Reihenfolge sind. Der Insertion Sort baut eine sortierte Teilliste auf, in neue
12:26 Elemente direkt an die richtigen Stellen eingefügt werden. Ähnlich wenn du beispielsweise Spielkarten in der Hand hast und du die manuell sortieren
12:34 müsstest. Diese Sortieralgorithmen sind einfach zu verstehen, aber ziemlich ineffizient gerade bei vielen Elementen, da sie im Durchschnitt eine quadratische
12:42 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
12:52 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
13:01 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
13:11 werden im Schnitt weniger Operationen ausgeführt. Schließlich wählt der Quicksort ein Pivotelement und dann alle kleineren Elemente nach links und alle
13:21 größeren Elemente nach rechts und sortiert dann die Teillisten rekursiv, bis alle Elemente sortiert sind. Suchchalgorithmen. Succhalgorithmen
13:29 werden verwendet, um ein bestimmtes Element in einer Datenliste zu finden. Die einfachste Variante ist hierbei die lineare Such, bei der alle Elemente der
13:38 Reihe nach durchsucht werden. Mit einer durchschnittlichen Laufzeit kannst ihr vielleicht denken, O von N. Wesentlich schneller ist dann die binäre Suche.
13:45 Diese funktioniert jedoch nur auf sortierten Listen. Sie durchsucht das mittlere Element und vergleicht das dann mit dem gesuchten Wert und entscheidet
13:54 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
14:03 Logarithmus n. Suchagorithmen werden im täglichen Leben ziemlich häufig verwendet, ohne dass wir wahrscheinlich darüber nachdenken. Sie spielen eine
14:10 zentrale Rolle in vielen Bereichen der Informatik, wie z.B. bei Datenbanksystem, Textverarbeitung, KI und vieles weitere. Grafenalgorithmen
14:19 kommen zum Einsatz, wenn Daten als Netzwerke organisiert sind. Ein sozialer Netzwerkgraf soll Freundeskreise und Verbindungswege analysieren. Wenn man
14:27 also einen Grafen durchlaufen möchte, gibt es zwei ziemlich bekannte Algorithmen. Tiefensuche und die Breitensuche. Die Tiefensuche beginnt an
14:36 einem Startknoten und verzweigt sich dann so tief wie möglich, bevor sie zurückkehrt. Die Breitensuche erkundet den nächstgelegenen Nachbarn zuerst und
14:44 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
14:53 und A Sternchen am weitesten verbreitet. Das klassische Beispiel hierfür ist Navigation und Routenplanung, wobei diese beiden Algorithmen Entfernung zu
15:02 beiden Zielen minimieren können. Auch Algorithmen wie Grußgral oder PRIM zur Berechnung minimaler Spannbäume sind Teile dieser Kategorie, um die
15:12 Gesamtkosten eines Grafen zu minimieren und ein effizientes Netzwerk aufzubauen. Rekursive Algorithmen. Schließlich zeichnen sich rekursive Algorithmen
15:21 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
15:29 organisieren lassen, wie z.B. das Berechnen der Fibonacci Zahlen oder das Durchlaufen von Baumstrukturen. Hier rechnet man immer tiefer und tiefer. Ein
15:37 gutes Beispiel, um das einfach zu verstehen, ist die Fakultät. Die Fakultät von 4 ist ausgerechnet 4* 3* 2* 1geschrieben
15:47 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
15:58 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
16:06 eine kleine Einführung in die wichtigsten Begriffe. Zu diesen Themen wird es wahrscheinlich bald noch einen längeren Kurs auf diesem YouTube-Kanal
16:13 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,
16:21 sind diese Weiterbildung übrigens komplett kostenlos für dich mit einem sogenannten Bildungsgutschein. Auch manche Personen im Job können diese
16:27 Weiterbildungen komplett finanziert bekommen durch das sogenannte Qualifizierungs- und Chancengesetz. Gerade für Arbeitslose, die Lust haben,
16:34 in die IT einzusteigen, aber vielleicht noch ein paar Qualifikulationen brauchen, ist das eine super Gelegenheit, denn wir begleiten dich
16:40 100% ortsunabhängig von keiner Erfahrung bis zu deinem ersten ITJob. Mehr Informationen findest du auf unserer Webseite, die verlinke ich dir einfach
16:48 mal in der Videobeschreibung. Ansonsten hoffe ich, das Video konnte dir einiges beibringen zu Algorithmen und Datenstrukturen und ich würde sagen, wir
16:54 sehen uns bald.