Lexikographische Ordnung < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 15:43 Mi 20.10.2010 | | Autor: | roufthas |
| Aufgabe | In einem Alphabet A sei eine reflexive Ordnungsrelation ≤ gegeben. Definieren Sie(verbal oder formal)die zu ≤ gehörende lexikographische
reflexive Ordnungsrelation(die wieder wie üblich mit”≤”bezeichnet werden soll)in der Menge A+ der nicht leeren Zeichenketten über A!
(lexikographische reflexive Ordnung:Anordnung der Zeichenketten so,wie
sie in einem Lexikon vorgenommen wird; es ist zu definieren,wann genau
für zwei beliebige Zeichenketten s, t ∈A+ mit beispielsweise s = s0 ··· sm−1
und t = t0 ··· tn−1 gelten soll,dass s ≤ t ist,wobei die im Alphabet A vorhandene reflexive Ordnungsrelation ≤ zugrundegelegt wird.) |
Hallo,
dies ist eine Aufgabe eines Beleges. Ich glaubte zwar bisher in diesem Kurs alles verstanden zu haben, aber was diese Aufgabe betrifft, bin ich maßlos überfordert... Kann mir bitte jemand helfen?
mfg
|
|
| |
|
Hallo roufthas,
ein Beispiel. Es ist dafür besonders nützlich, wenn Du kein Japanisch kannst.
Neben zwei anderen Alphabeten gibt es im Japanischen auch die Silbenschrift Hiragana. Sie besteht aus 46 (früher 50) Zeichen, die auf drei verschiedene Weisen lexikographisch angeordnet werden können.
Nun bekommst Du sagen wir 300 Wörter in dieser Schrift. Sie bestehen aus ein bis vier Zeichen (könnten auch mehr sein...). Du sollst sie lexikalisch anordnen.
Die einzigen Informationen, die dir vorliegen, sind der Zeichenbestand und die Ordnungsrelation (hier z.B. ![[]](/images/popup.gif) I-ro-ha). Wie muss Dein Algorithmus aussehen, der die Daten ordnet? Genauer: wie entscheidest Du bei zwei vorliegenden Wörtern, welches weiter vorn in der lexikalischen (lexikographischen) Anordnung steht?
Falls Du lieber eine Dir bekannte Sprache nimmst, ordne diese Wörter:
altruistisch
Altar
alter
Altaisch
Altarabisch
alt
Altartisch
alta
Altan
Auch hier musst Du die Wörter ja nicht kennen, um sie zu ordnen. Sie existieren alle, eins allerdings ist kein deutsches Wort. Einzuordnen ist es trotzdem.
Wieder ist Dir nur das Alphabet bekannt und damit der Zeichenbestand und die alphabetische Anordnung, mithin die Ordnungsrelation, z.B. b<j<p.
Wie erweiterst Du das auf Wörter?
Grüße
reverend
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 16:40 Mi 20.10.2010 | | Autor: | roufthas |
Hi,
alt <
alta <
Altaisch <
Altan <
Altar <
Altarabisch <
Altartisch <
alter <
altruistisch
so würde ich die Ordnen, die, die mit einem Zeichen beginnen, was in dem Alphabet "weiter vorne" steht, setze ich nach vorn. Ich habe jetzt vorrausgesetzt, dass Groß und kleinschreibung keine Rolle spielt.
Aber trotzdem verstehe ich die gestellte Frage irgendwie nicht.
lg
Ps: Danke für die Mühe :)
|
|
|
| |
|
Hallo nochmal,
na, die Aufgabe war doch
> Definieren Sie(verbal oder formal)die zu ≤ gehörende lexikographische
> reflexive Ordnungsrelation(die wieder wie üblich mit”≤”bezeichnet werden
> soll)in der Menge A+ der nicht leeren Zeichenketten über A!
Das hast Du offenbar implizit getan, denn die Anordnung ist ja richtig. Und wie geht das allgemein, also z.B. für ein Dir vorliegendes "Alphabet" mit zugehöriger Ordnungsrelation?
Das ist die Aufgabe. Und Du darfst sie sogar ohne formale Formulierung lösen. Wie genau ist die Anordnung der Wörter definiert? Warum kommt alt vor alta, alta aber vor altaisch, und warum steht altarabisch zwischen altar und altartisch, was ja inhaltlich eher unsinnig ist?
Es gibt eigentlich nur zwei Dinge zu definieren, nämlich das Ende eines Worts (und damit dann den Umgang verschieden langer Wörter, wovon das kürzere zugleich der Beginn des längeren ist - alt,alta) und die signifante Stelle zweier Wörter, die darüber entscheidet, welches vorn und welches hinten steht.
Grüße
reverend
|
|
|
| |
|
Ich bin gerade völlig überfragt und verwerfe meine Idee,... Hilfe!
|
|
|
| |
|
Hallo Hendrik,
Deine Idee musst Du so schnell nicht verwerfen - damit meine ich die, die Du in den vorigen Fassungen Deiner Frage stehen hattest.
Definiere genauer, was m,n sind und überleg nochmal, ob wirklich beide Laufvariablen nötig sind.
Außerdem ist die lexikographische Anordnung von Wörtern nur zu lösen, wenn der Zeichensatz (das Alphabet) um das Zeichen "nicht vorhandenes Zeichen" erweitert wird und dieses lexikalisch richtig eingeordnet wird. Dann aber kommst Du mit Deinem Ansatz gut weiter.
Grüße
reverend
|
|
|
|
