Видео 99
Просмотров 284 343

22:07

Approximative Stringsuche

19:58

Repeats in Strings

27:13

String Alignment Varianten

26:06

Lokale Stringalignments

37:47

Suffix Tree: Aufbau in Linearzeit

18:59

Kellerautomaten

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:00 Endliche Automaten
2:12 Grenzen endlicher Automaten
4:42 Automat mit "Keller"
7:40 Übergangsfunktion eines Kellerautomaten
12:03 Keller = String
14:41 Beispiel Kellerautomat
21:22 Kontextfreie Grammatiken (CFG)
22:19 CFG ⇒ Kellerautomat
25:26 Beispiel
32:28 CFG = (nicht-deterministische) Kellerautomat
34:10 ...

Видео

22:07

k-Means Clustering

Просмотров 2585 месяцев назад

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 (...

19:58

Approximative Stringsuche

Просмотров 1346 месяцев назад

_(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...

27:13

Repeats in Strings

Просмотров 846 месяцев назад

_(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 ...

26:06

String Alignment Varianten

Просмотров 1716 месяцев назад

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...

37:47

Lokale Stringalignments

Просмотров 1136 месяцев назад

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...

18:59

Suffix Tree: Aufbau in Linearzeit

Просмотров 1678 месяцев назад

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...

24:56

Suffix Arrays

Просмотров 1438 месяцев назад

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...

22:32

Suffix Trees

Просмотров 1888 месяцев назад

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...

19:34

Suffix Tries

Просмотров 1819 месяцев назад

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...

14:24

Exakte Stringsuche

Просмотров 1939 месяцев назад

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...

8:02

Was ist Bioinformatik?

Просмотров 1,3 тыс.10 месяцев назад

Bioinformatik kann man an der THM studieren. Infos unter: www.thm.de

21:36

Der Barbier und die Unberechenbarkeit

Просмотров 27010 месяцев назад

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...

31:53

While kann mehr als Loop

Просмотров 50611 месяцев назад

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....

1:06:15

Die Loop-Sprache

Просмотров 607Год назад

Eine Programmiersprache, die mit nur 4 Befehlen auskommt. Der wichtigste davon ist loop, eine Schleife mit fester Anzahl an Durchläufen. Damit ist dafür gesorgt, dass ein Loop-Programm niemals unendlich lange laufen kann. Wir fügen der Sprache nach und nach neue Ausdrucksmöglichkeiten hinzu, die sich immer in die ursprünglichen 4 Befehle übersetzen lassen, und erhalten am Schluss mit "extended ...