Wiki: Simple String Matching

Bei Postings zu Vorlesungsthema X lassen Sie Ihr Betreff bitte mit "X: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!

Moderator: Algorithmen und Datenstrukturen

Forumsregeln
Bei Postings zu Vorlesungsthema X lassen Sie Ihr Betreff bitte mit "X: " beginnen, gefolgt von einer möglichst präzisen Überschrift, danke!
Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 201
Registriert: 12. Apr 2015 11:35

Wiki: Simple String Matching

Beitrag von sqrt(2) » 23. Apr 2016 17:59

Quelle: https://wiki.algo.informatik.tu-darmsta ... ction_step

Hallo,

ich verstehe beim Induktionsschritt den Punkt 2.2 der Abstrakten Sicht nicht ganz. Meine Fragen:

a. Warum hat man hier die Bedingung eingeführt das I nicht die leere Menge sein darf?
b. "and i-m+1 is the head element of I" -> Ist meine Auffassung richtig, dass man hier prüft ob vom aktuellen Laufindex i geschaut wird, ob die Gleichung [i-m+1] mit dem ersten Element der Sequenz I überein stimmt? Wenn ja hat man aufgrund von 1. einen vollständigen und gültigen Kandidaten. Ungültige Kandidaten wurden ja dank 1. Satz 2 entfernt.
c. Warum ist I nur eine ordered Sequence und keine sorted Sequence? (Weil wir keinen Vergleich c direkt auf I anwenden, sondern nur Elemente in I reinpacken die "zufällig" aufgrund der Nummerierung der einzelnen Positionen i sortiert ist?)

Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 201
Registriert: 12. Apr 2015 11:35

Re: Wiki: Simple String Matching

Beitrag von sqrt(2) » 23. Apr 2016 18:10

b hat sich durch Correctness 1. geklärt.

Prof. Karsten Weihe
Moderator
Moderator
Beiträge: 1824
Registriert: 21. Feb 2005 16:33

Re: Wiki: Simple String Matching

Beitrag von Prof. Karsten Weihe » 24. Apr 2016 09:22

sqrt(2) hat geschrieben: ich verstehe beim Induktionsschritt den Punkt 2.2 der Abstrakten Sicht nicht ganz. Meine Fragen:
a. Warum hat man hier die Bedingung eingeführt das I nicht die leere Menge sein darf?
Weil danach in 2.2 sofort auf das "head element" von I zugegriffen wird, dass ja im Falle einer leeren Menge I nicht existiert.

Da Sie in einem Follow-Up geschrieben haben, dasss Ihre Frage b sich geklärt hat, gehe ich darauf also nicht ein.

KW

Benutzeravatar
sqrt(2)
Sonntagsinformatiker
Sonntagsinformatiker
Beiträge: 201
Registriert: 12. Apr 2015 11:35

Re: Wiki: Simple String Matching

Beitrag von sqrt(2) » 24. Apr 2016 14:52

Okay, danke :)

Antworten

Zurück zu „AuD: Vorlesung“