![Algorithmen und Datenstrukturen](/img/default-banner.jpg)
- 100
- 297 527
Algorithmen und Datenstrukturen
Germany
Приєднався 3 бер 2021
Auf diesem Kanal gibt es Videos aus Lehrveranstaltungen der Technischen Hochschule Mittelhessen (THM) von Prof. Dr. Andreas Gogol-Döring zum Thema Algorithmen und Datenstrukturen.
Das Buch zum Kanal heißt "Algorithmen und Datenstrukturen für Dummies" und ist bei Wiley erschienen (ISBN: 978-3-527-71432-2).
Implementierungen zu (einigen) Algorithmen finden Sie auf algorithmendummies.de/
Das Buch zum Kanal heißt "Algorithmen und Datenstrukturen für Dummies" und ist bei Wiley erschienen (ISBN: 978-3-527-71432-2).
Implementierungen zu (einigen) Algorithmen finden Sie auf algorithmendummies.de/
Reterna: Rekursive Funktionen mit Ternary Conditional Operator
Reterna ist eine didaktische Programmiersprache, die auf Rekursion basiert und keine Schleifen kennt und in der es auch keine Variablen gibt. Neben Rekursion verfügt sie über einen Ternary Conditional Operator der Form "a ? b : c", mit denen sich Bedingungen abprüfen lassen. Die Sprache dient dazu, die Prinzipien rekursiver Programmierung zu verstehen und einzuüben.
0:00 Was ist Reterna?
2:08 Die Syntax von Reterna
11:07 Einfache Beispiele
13:41 Ternary Conditional Operator
16:29 Beispiel Fibonaccy Zahlen
19:37 Rechenoperationen
32:57 Logische Operationen
34:12 Vergleiche
35:59 Strings
42:24 Sprachen akzeptieren
49:24 Ackermann-Funktion
Querverweise
ua-cam.com/video/pdIjMOmxMWM/v-deo.html (Kodierung von Strings)
ua-cam.com/video/dpjITLtwDvA/v-deo.html (Ackermann-Funktion)
0:00 Was ist Reterna?
2:08 Die Syntax von Reterna
11:07 Einfache Beispiele
13:41 Ternary Conditional Operator
16:29 Beispiel Fibonaccy Zahlen
19:37 Rechenoperationen
32:57 Logische Operationen
34:12 Vergleiche
35:59 Strings
42:24 Sprachen akzeptieren
49:24 Ackermann-Funktion
Querverweise
ua-cam.com/video/pdIjMOmxMWM/v-deo.html (Kodierung von Strings)
ua-cam.com/video/dpjITLtwDvA/v-deo.html (Ackermann-Funktion)
Переглядів: 314
Відео
Kellerautomaten
Переглядів 4352 місяці тому
Gibt man einem endlichen Automaten die Möglichkeit, Daten auf einem Stapel (auch "Stack" oder "Keller" genannt) zu speichern, so erhält man einen Kellerautomaten. Die Sprachen, die (nicht-deterministische) Kellerautomaten akzeptieren können, sind genau die kontextfreien Sprachen. Im Video wird gezeigt, wie man zu jeder kontextfreien Grammatik einen passenden Kellerautomaten definieren kann. 0:0...
k-Means Clustering
Переглядів 2857 місяців тому
Clustering bedeutet, dass eine Menge von Objekten so in Gruppen eingeteilt werden sollen, dass ähnliche Objekte in derselben Gruppe landen. Eines der wichtigsten Clustering-Verfahren ist das k-Means-Clustering, bei dem die Cluster durch Mittelpunkte (englisch: "means") definiert werden. Im Video wird der heuristische k-Means-Algorithmus von Lloyd vorgestellt. 0:00 Clustering 1:49 Mittelpunkte (...
Approximative Stringsuche
Переглядів 1428 місяців тому
_(Dieses Video stammt noch aus der Coronazeit)_ Bei der approximativen Stringsuche möchte man alle Vorkommen eines Patterns p in einem Text t finden, wobei man eine begrenzte Anzahl von Fehlern zulässt. Fehler können dabei einfach falsche Buchstaben sein ("Mismatch"); oder man kann zusätzlich auch Einfügungen ("Insertions") und Löschungen ("Deletions") einzelner Buchstaben zulassen. Letzteres k...
Repeats in Strings
Переглядів 928 місяців тому
_(dieses Video stammt noch aus der Coronazeit)_ Ein Repeat ist ein Teilstring, der mehrfach in einem Text vorkommt. Wir schauen uns im Video verschiedene Algorithmen an, mit denen man möglichst lange Repeats finden kann. Mit einem Suffixbaum gelingt dass sogar in Linearzeit. 0:00 Repeats und maximale Repeats 7:44 Longest Repeats: Brute Force Algorithmus 15:52 Suffix Trees 20:59 Longest Repeats ...
String Alignment Varianten
Переглядів 1818 місяців тому
Man kann mit einer Reihe von sehr ähnlichen Algorithmen diverse Alignmentprobleme auf Strings lösen. In diesem Video schauen wir uns davon verschiedene an, unter anderem: - globale Alignments - lokale Alignments - glokale Alignments - Overlap-Alignments _dieses Video stammt noch aus der Coronazeit_ 0:00 Needleman-Wunsch vs. Smith-Waterman 2:40 Distanz vs. Score 6:30 lineares Scoring-Schema 11:1...
Lokale Stringalignments
Переглядів 1268 місяців тому
Bei einem lokalen Stringalignment geht es darum, Teile in zwei Strings zu finden, die möglichst gut zueinander passen. Je nachdem, ob man dabei auch Einfügungen ("Inserts") und Löschungen ("Deletions") von Zeichen zulässt oder nicht, ergeben sich unterschiedliche lokale Stringalignmentprobleme, die man elegant mit Algorithmen lösen kann, die nach dem Prinzip des _dynamischen Programmierens_ arb...
Suffix Tree: Aufbau in Linearzeit
Переглядів 17510 місяців тому
Der Suffix Tree ist ein Datenstruktur, mit der man viele Probleme im Bereich Stringsuche effizient lösen kann. Wie man Suffix Trees in Linearzeit aufbauen kann, zeigen wir hier am Beispiel von Ukkonens Algorithmus. 0:00 Suffix Trees aufbauen in quadratischer Zeit 2:10 Ukkonens Algorithmus 6:30 End-of-String-Zeichen $ 7:32 Schritte beim Aufbau 9:25 Kantenbeschriftungen verlängern in O(1) 11:51 M...
Suffix Arrays
Переглядів 15610 місяців тому
Eine sehr einfache aber dennoch effiziente Datenstruktur zur schnellen Suche in Strings (also ein Stringindex) ist das Suffix Array. Es enthält die Anfangspositionen aller Suffixe des Textes in ihrer lexikographischen Reihenfolge. 0:00 Stringindices 2:07 Präfixe und Suffixe 3:37 Teilstrings = Präfix eines Suffix 6:01 Sortierte Suffix Liste 9:37 Suffix Array 12:19 Suche im Suffix Array Video übe...
Suffix Trees
Переглядів 21810 місяців тому
Der Suffix Tree ist eine speichereffiziente Variante des Suffix Tries. Abgesehen von einer schnellen Suche kann man mit diesem Stringindex noch allerhand weitere Probleme effizient lösen, zum Beispiel die Suche nach längsten Repeats. 0:00 Trie 2:02 Trefferlisten im Suffix Array 9:29 Knoten einsparen 13:11 Kantenbeschriftungen effizient speichern 15:32 Speicherbedarf Suffix Tree 18:53 Repeats im...
Suffix Tries
Переглядів 19610 місяців тому
Die Suche nach Teilstrings in einem Text t lässt sich ungemein beschleunigen, wenn man zuvor für t einen Stringindex aufgebaut hat. Der Trie ist ein solcher Stringindex: Er entspricht einem baumförmigen endlichen Automaten, der alle Teilstrings von t akzeptiert. Die Laufzeit einer Suche im Trie hängt nur von der Länge des Suchworts ab und ist unabhängig von der Textlänge (jedenfalls theoretisch...
Exakte Stringsuche
Переглядів 22911 місяців тому
Wir suchen alle Vorkommen eines Strings p in einem Text t. Eine naheliegende Lösung benötigt dafür die Zeit O(n * m), wobei n und m die Längen der beiden Strings sind. Mit einem kleinen Trick kann man diesen Algorithmus so verbessern, dass er in der Praxis mit weitaus komplizierten Verfahren mithalten kann. Der Horspool-Algorithmus ist ein Beispiel dafür, dass auch einfache algorithmische Ideen...
Was ist Bioinformatik?
Переглядів 1,4 тис.11 місяців тому
Bioinformatik kann man an der THM studieren. Infos unter: www.thm.de
Der Barbier und die Unberechenbarkeit
Переглядів 353Рік тому
In dem Satz "der Barbier rasiert genau die Leute, die sich nicht selbst rasieren" steckt ein Widerspruch, denn: Wer rasiert den Barbier? Nach diesem Muster lässt sich zu jedem Berechnungsmodell und jeder Programmiersprache eine Aufgabe formulieren, die sich damit nicht lösen lässt. Wo dabei jedoch im Einzelnen das Problem liegt, hängt vom jeweiligen Berechnungsmodell ab. Wir schauen uns in dies...
While kann mehr als Loop
Переглядів 612Рік тому
Die Schleife, der die Loop-Sprache ihren Namen verdankt, zeichnet sich dadurch aus, dass sie stets nur endlich oft durchlaufen wird. Anders als bei while-Schleifen, bei denen es passieren kann, dass sie sich aufhängen und niemals enden, kommt darum ein Loop-Programm immer zu seinem Ende. Leider bedeutet das auch, dass Loop in ihren Möglichkeiten stärker eingeschränkt ist, als die Sprache While....
Endliche Automaten = Reguläre Ausdrücke
Переглядів 976Рік тому
Endliche Automaten = Reguläre Ausdrücke
Wave Function Collapse: PCG mit Constraints
Переглядів 184Рік тому
Wave Function Collapse: PCG mit Constraints
Rätsel: In begrenzten Texten eindeutig definierbare Zahlen
Переглядів 289Рік тому
Rätsel: In begrenzten Texten eindeutig definierbare Zahlen
Sprünge und Verzweigungen (Rechnerbau Teil 11)
Переглядів 327Рік тому
Sprünge und Verzweigungen (Rechnerbau Teil 11)
Programmierbare Computer (Rechnerbau Teil 9)
Переглядів 8202 роки тому
Programmierbare Computer (Rechnerbau Teil 9)
Großartig, hab es auf Anhieb verstanden! Vielen Dank!
Bist du bruda von kuppinger abi?
Mega die Erklärung! War erst abgeschreckt von der länge aber lohnt sich absolut! Danke!
So jemanden wie Sie hätte ich mir als Dozent gewünscht!
Sie sind der Beste. Vielen Dank
🙏🙏🙏🙏
Vielen Dank :)
Sehr gutes Video, du hast definitiv mehr Aufmerksamkeit verdient.
Vielen Dank für die tolle Erklärung
Was ich mir aus dem Video gemerkt habe: Rehashen = "An den Knöpfen spielen" 20:12
Vielen Dank für das sehr nützliche und ausführliche Video. Ich bin Studentin der THM Gießen und hatte GDI bei Ihnen besucht. Ich kann nur sagen, Sie sind der Beste👌 .
Vielen Dank für deine Videos. Genau so eine Videoreihe hab ich gesucht.😊
Hast du schon ein Video zu Algorithmen für einen dynamischen Binärbaum? Knotenobjekte, Verlinkung, Durchsuchung sind klar. Aber wenn wir den Baum einfach nur dynamisch erweitern, hängen auf einer Seite eines Knotens mehr Nachfahren als auf der anderen. Es müßte also irgendwie alles umgelinkt werden, und ein anderer Knoten wird die Wurzel. Klassisches Beispiel: Eine Menge an Zahlen der größe nach anordnen. (Klar könnte man auch ein geordnetes Array binär durchsuchen, aber wir wollen ja einen Baum.) Wenn ich bei den natürlichen Zahlen mit der 1 anfange, hängen alle Nachfahren auf einer Seite (größer als 1).
Hm, ich wollte wissen, ob es einen effizienteren Algorithmus für Bitcount gibt. Akademisch-theoretisch anscheinend ja. Daß man zu vielen Problemen Nachschlagemaps erstellen kann, ist auch klar. Die Optimierungen sind aus theoretischer Sicht auch spannend nachzuvollziehen. Ich frage mich nur, ob das auf heutigen Systemen noch Relevanz hat - vielleicht auf embedded systems mit rudimentären Mikrocontrollern, aber da sind die Speicherkapazitäten wahrscheinlich das Problem. Bitshift verarbeitet ein Prozessor extrem schnell, ein Register-Increment ebenso. Beim Shift kann man auch noch das Overflow-Flag nutzen. Das Laden aus dem RAM kostet dagegen verhältnismäßig viel Zeit. Ich bezweifele, daß die Optimierung in der Praxis eine echte Beschleunigung bringt. Wenn ich von Berlin nach Hamburg will und zu Fuß 1x ausreicht, aber mit dem Auto müßte ich 100x fahren, dann würde ich das Auto nehmen. :) Aber schöne theoretische Auseinandersetzung! Danke!
Behämmertes Video
Vielen Dank für dieses ausgezeichnete Video👍🏾
Toll! Danke für das Video!!!
26:28 man startet ja immer mit einem leeren Keller richtig? Brauchen wir also zum Anfang immer eine Regel wie epsilon:epsilon->s damit der Keller entsprechend gefüllt ist?
20:38 wir haben also die Regel epsilon: x -> x genommen. Wurde dann dafür ein x aus unserem Keller entfernt und dann wieder neu hinzugefügt?
super!!! danke
Super erklärt :)
Was ist der Unterschied zwischen Breitensuche und Dijkstra?
16:31 Warum werden die Epsilon Übergänge jetzt auch entfernt? Mit welcher Eingabe kommt man denn jetzt vom Startzustand in einen anderen Zustand?
16:57 Wenn ich von meinem Startzustand in den Automaten rübergehe der nur die Zeichen x akzeptiert können dann in diesem Automaten blieb viele x folgen? In der Skizze sind nämlich zwei Kanten eingezeichnet. Ich verstehe das so das, wenn man ein x eingibt, man dann in den dritten Zustand kommt und von diesem aus entweder dann in den Endzustand gelangen kann oder wieder zurück in den zweiten Zustand wechseln kann und erneut ein x eingeben kann. Falls es so ist, musste dann der reguläre Ausdruck nicht (x|y)* lauten?
Super Video, vielen Dank
23:33 müsste es nicht anderesherum sein? Also haben wir nicht aus einem nicht deterministischen automaten einen deterministischen gemacht?
Finde das du das wirklich toll erklärst. Schade das, dass Video so wenig Views hat, war ja sicher aufwendig das Video zu machen. Ich gucks mir jedenfalls grad bis zum Ende an und es hilft mir sehr fürs Studium. Danke dir für die Arbeit!
Sie haben an der Stelle 4:17 den falschen Unterbaum abgeschnitten
Vielen Dank für das Video, war lange auf der Suche nach gutem Material. Sie haben mir damit sehr gut weitergeholfen.
danke
Eine fantastische Serie, die einen vom Detail durch sämtliche Abstraktionsstufen führt!
Kann mich nur wiederholen, anschaulich, nachvollziehbar und voller Leidenschaft erklärt :)
Eine fantastische Art zu Erklären! Gefällt mir sehr gut und hat mir schon wieder ein paar Grundlegende Dinge verdeutlicht. Vielen Dank :)
Klasse erklärt
Danke für das Video, mega sympathische Stimme! :)
beste Vorlesung zu Algorithmen und Datenstrukturen, die ich bisher gesehen habe. Vielen Dank!
Richtig gut erklärt! Danke
schön verständlich erklärt, danke sehr :)
Die Barbiere rasieren sich gegenseitig. Könnte nicht das die Lösung sein?
Mega das gute Video!
In welchem Video finde ich die Erklärung wieso die Laufzeit O(n * log n ) ist? Tolle Arbeit die sie hier hochladen, die Videos sind eine riesige Hilfe!
Erst einmal vielen Dank für ihre hilfreichen Videos. :) mir ist bei der AlgoDat Playliste aufgefallen, dass der Heap Sort gar nicht erwähnt wurde, hat das einen bestimmten Grund? ..
Leider habe ich (noch) kein Video zu Heapsort aufgenommen, da ich den Algorithmus nicht in meiner Vorlesung bespreche. Bei der Auswahl der Themen für eine Vorlesung muss man ja immer abwägen, was man nimmt und was man weg lässt. Entscheidend ist dann immer, was man an grundsätzlichen Ideen und Fertigkeiten an einem Thema erwerben oder demonstrieren kann. Heapsort ist meiner Meinung nach kein Algorithmus, an dem man besonders viel lernen kann - aber vielleicht irre ich mich da?
10:35 hab ich nicht schon a.last in el.prev reingeschoben? Also waere object(a.last) dann nicht die falsche Stelle? Oder is deshalb das next dran
Nein, a.last wird erst später umgesetzt, ab 10:59
@@Gogol-Doering Dankeschön!
Vielen Dank für die guten und verständlichen Videos🙌
Vielen Dank
aber 19:32 rechts regular wurde mit links regulaer vertauscht oder?
vielen Dank🙏
Wow so eine Super Erklärung! Könnten Sie mehr videos zu diesem Thema machen, in denen Sie auch die Korrektheit von komplexeren Algorithmen beweisen?
Genial. So einen Prof hätte ich gerne..
Großartig, danke!