Frage zu Relationen in Bezug auf Sortierverfahren

[titus]

Ich muss das Forum meines Vertrauens mal wieder bezüglich einer Problematik konsultieren.

Ich habe hier eine Übungsaufgabe (Keine Hausaufgabe/Hausarbeit oder ähnliches), die zwar einerseits recht einfach klingt, bei der ich mich aber andererseits doch ziemlich doof anstelle. Die Aufgabe lautet:

Kreuzen Sie an, welche der nachfolgenden Relationen für das Sortieren geeignet sind und welche zu einem stabilen Sortierverfahren führen.

Relationen:
1. ist kleiner als
2. ist Vater von
3. ist Teilmenge von
4. ist größer oder gleich
5. ist so groß wie

Ich hätte jetzt auf folgendes getippt:

für das Sortieren geeignet: 1 und 4 ist meint Tipp (Habs mir nochmal überlegt und editiert).
führt zum stabilen Sortieren: 1 würde ich sagen.

Ist das richtig? Na vermutlich nicht.

 

[bygones]

hae - ist meine uni schon so lange her ... aber ein Algorithmus kann ein stablies Sortierverfahren implementieren (oder ein instabiles) - aber eine Relation ?

stabil heisst wenn bei einem Element die zu sortierende Eigenschaft gleich ist er die Datensatzreihenfolge beibehaelt (oder so)...

d.h. es gibt eine Reihe von algorithmen die stabile bzw instabil "sind"... alle koennen aber mit einer Relation arbeiten

zum ersten... ich wage mal die Behauptung 1 - 4 sind zum sortieren geeignet

 

[Landei]

Die Frage zielt offenbar darauf ab, ob die Relation eine totale Ordnung herstellt oder nicht. 1 und 4 erfüllen diese Bedingung, der Rest nicht. Bei 2 kann z.B. sein, dass Klaus nicht der Vater von Dieter ist und Dieter nicht der Vater von Klaus ist, bei 3. kann A keine Teilmenge von B und gleichzeitig B keine Teilmenge von A sein. Damit kann man logischerweise keine eindeutige Sortierung herstellen.

 

[bygones]

Die Frage zielt offenbar darauf ab, ob die Relation eine totale Ordnung herstellt oder nicht. 1 und 4 erfüllen diese Bedingung, der Rest nicht. Bei 2 kann z.B. sein, dass Klaus nicht der Vater von Dieter ist und Dieter nicht der Vater von Klaus ist, bei 3. kann A keine Teilmenge von B und gleichzeitig B keine Teilmenge von A sein. Damit kann man logischerweise keine eindeutige Sortierung herstellen.

ist dann 1 auch eine totale Ordnung ?
2 ist nicht kleiner als 2 und vice versa ?!

 

[Landei]

Wikipedia sagt, dass <= eine Totalordnung ist. Wenn du eine Relation < gegeben hast, kannst du a <= b definieren als ! b < a

 

[titus]

Danke schon mal vielmals für die Antworten!

Ist "größer oder gleich" (>=) dann auch eine Lage eine totale Ordnung herzustellen?

 

[SlaterB]

unterscheidet sich > von < ?

 

[titus]

Ja, ok. Danke!