Informatik (Fach) / A&D (Sortieren, Vergleichen) (Lektion)

In dieser Lektion befinden sich 22 Karteikarten

Sortierprogramme, BM, BMH, KMP

Diese Lektion wurde von scarvy erstellt.

Lektion lernen

Diese Lektion ist leider nicht zum lernen freigegeben.

zurück  |  weiter 1 / 1

  • Wie funktioniert die exakte Suche mit einem naiven ... = man vergleicht von Links an, bei Mismatch Pattern ein Zeichen nach Rechts - Das Problem der exakten Textsuche ist es, alle gültigenVerschiebungen zu finden.- Man kann aber z.B. auch sagen: Finde alle ...
  • Was sind die Vor- und Nachteile der exakten Suche ... Vorteile:- einfache Implementierung    -keine Vorverarbeitung- für natürliche Sprachen gut geeignet Nachteil:- vorherige Vergleiche werden nicht weiterverwendet- Untergrenze der worst-case Effizienz: ...
  • Was zeichnet den Boyer-Moore- Algorithmus aus? - Pattern wird von rechts nach links verglichen -nutzt bei Mismatch 2. Heuristiken:  Bad-Charakter-Heuristik                                                         ...
  • Wie funktioniert Good-suffix Heuristik? 2 Fälle:□ Mismatch nochmal im Pattern: verschieben bis zum letztenAuftreten□ Sonst: bis hinter den Mismatch schieben0 1 2 3 4 5 6 7 8 …A B A A B A D A C …E A B A C       E A B A C                       ...
  • Effizienz vom naiven, KMP und BM Algorithmus? Laufzeiten Naiver Algorithmus:□ Best: O(n) Avg: O(n*m) Worst: O(n*m)□ Schnell zu implementierenKMP-Algorithmus:□ Best: O(n) Avg: O(n) Worst: O(n)□ Der AllrounderBM-Algorithmus:□ Best: O(n/m) ...
  • Wie funktioniert der KMP? Der Algorithmus von Knuth, Morris und Pratt nutzt die bei Über­ein­stimmung von Zeichen gewonnene Information aus. So brauchen die Zeichen nach einem Mismatch nicht noch einmal alle wieder von vorn ...
  • KMP anhand von Beispiel. Beispiel:   0123456789... a b c a b c a b d a b c a b d a b c a b d Die Zeichen an den Positionen 0, ..., 4 haben über­ein­gestimmt. Der Vergleich c-d an Position 5 ergibt einen Mismatch. Das ...
  • Good-suffix-heuristik Beispiele: Beispiel:   0123456789... a b a a b a b a c b a c a b a b c a b a b Das Suffix ab hat bereits über­ein­gestimmt. Das Muster kann so weit geschoben werden, bis das nächste ...
  • Bad-Charakter heuristik Beispiel: Beispiel:   0123456789...a b b a b a b a c b a b a ba c b a b a c Der Vergleich b-c liefert einen Mismatch. Das Textzeichen b kommt im Muster an Position 0 und an Position 2 vor. Das Muster kann so ...
  • Welche Vorwerarbeitungsprozesse gibt es beim BM, BMH,KMP? ... Für die Good-suffix-heuristic wird ein Array s benötigt  um diese Schiebedistanz zu bestimmen, sind zwei unter­schied­liche Fälle zu betrachten. Fall 1:   Das über­einstimmende Suffix kommt noch ...
  • Wie funktioniert BMH? Von Horspool stammt die Idee, nur die Schlechtes-Zeichen-Strategie zu verwenden, jedoch nicht das Zeichen heranzuziehen, das zu einem Mismatch geführt hat, sondern stets das ganz rechte Zeichen des Textfensters. ...
  • Effizienz von BM-Algorithmus Analyse Unter der Bedingung, dass das Muster im Text nicht oder nur eine konstante Anzahl von Malen vorkommt, führt der Boyer-Moore-Algorithmus in der Suchphase im schlechtesten Fall O(nm) Vergleiche ...
  • Wie sortiert man am Besten? Man nimmt den Suchalgorithmus mit der besten Effizienz... - u.a. abhängig von der Länge der Liste und dem Grad der Sortiertheit
  • Definiere isort. > -- insertion sort: die Elemente werden nacheinander an die richtige Position "geschoben" (vgl. insert).> isort :: (Ord a) => [a] -> [a]> isort []     = []> isort (x:xs) = insert x (isort xs)   ...
  • Definiere quicksort. -Was ist der Unterschied verglichen ... > qsort :: (Ord a) => [a] -> [a]> qsort (x:xs) = qsort less ++ [x] ++ qsort more>  where >  less = filter (x >) xs>  more = filter (x <=) xs> qsort [] = []
  • Wie funktioniert mergesort? Funktionsweise Mergesort betrachtet die zu sortierenden Daten als Liste und zerlegt sie in kleinere Listen, die jede für sich sortiert werden. Die sortierten kleinen Listen werden dann im Reißverschlussverfahren ...
  • Wie ist mergesort definiert? Merge-Sort=Zusammenmischen zweier sortierter Listen. mergeSort :: [Int] -> [Int]mergeSort [] = []mergeSort [a] = [a]mergeSort x = merge (mergeSort links) (mergeSort rechts)where(links, rechts) = splitAt ...
  • Wie ist die Komplexität von mergesort? Mergesort ist im Gegensatz zu Quicksort stabil, wenn der Merge-Schritt richtig implementiert ist. Seine Komplexität (Worst-, Best- und Average-Case-Verhalten) beträgt in der Landau-Notation ausgedrückt ...
  • Wie ist die Effizienz von quicksort? Laufzeit Die Laufzeit des Algorithmus hängt im Wesentlichen von der Wahl des Pivotelementes ab. Im Worst Case (schlechtesten Fall) wird das Pivotelement stets so gewählt, dass es das größte oder das ...
  • Wie ist die Komplexität von isort? Komplexität Die Anzahl der Vergleiche und Verschiebungen des Algorithmus ist von der Anordnung der Elemente in der unsortierten Eingangsfolge abhängig. Für den Average Case ist eine genaue Abschätzung ...
  • Wie funktioniert isort? Insertion Sort (Sortieren durch Einfügen) ist einer der am einfachsten zu implementieren Sortieralgorithmen. Der Algorithmus funktioniert nach folgendem Prinzip: Betrachte alle Elemente der Reihe nach ...
  • Wie funktioniert countingsort? - man braucht ein Intervall- zählt alle Elemente mit Hilfe von Array -> schreibt sie wieder auf

zurück  |  weiter 1 / 1