Wie finde ich das maximale und minimale Element in einer Menge, vereinfacht gesagt und wie finde ich das Maximum, sowie Minimum?

Gibt es da einen TRick oder so?

Answer 1

[iqKleinerDrache]

na du gehst die Liste von links nach rechts durch. Initial ist das erste Element dein Minimum. Ist dann das nächste kleiner so wird es dies. Usw
Maximumsuche analog. Die Menge muss natürlich aufzählbar und endlich sein. Das versteht sich von selbst. Wie solltest du sonst links anfangen und beim weitergehen wissen wann Schluss ist ja.

Comments

[DerRoll]

Abzählbar reicht nicht, die Menge muss entscheibar sein (selbst rekursiv wie ich es bei J0T4T4 geschrieben habe reicht nicht). Endlich reicht immer, endliche Mengen sind immer aufzählbar.

Answer 2

[DerRoll]

Wie soll das gehen da nicht mal jede Menge beschränkt ist und nicht mal jede beschränkte Menge ein Maximum hat.

Woher ich das weiß: Studium / Ausbildung – Dipl.Math.

Comments

[jqiow2]

Ich mein natürlich für die Relationen, die geordnet sind!

[DerRoll]

@jqiow2

Die Eigenschaft beschränkt zu sein oder ein Maximum zu haben erfordert zwar eine Ordnungsrelation, aber umgekehrt gilt das nicht. R zum Beispiel ist geordnet, hat aber kein Maximum und kein Minimum.

[jqiow2]

@DerRoll

O.o

Answer 3

[J0T4T4]

Der normale Algorithmus für soetwas ist folgend:

Du gehst alle Elemente der Menge durch und vergleicht alle mit dem bisherigen Maximum. Wenn irgendwas größer als das bisherige Maximum sein sollte, dann passt du das bisherige Maximum an.

Am Ende hast du dann das maximale Element der Menge. Das ergibt aber natürlich nur Sinn, wenn sich die Menge überhaupt ordnen lässt.

Comments

[DerRoll]

Das klappt nur wenn due Menge wenigstens rekursiv aufzählbar ist. Denn sonst gibt rs kein Verfahren das "alle Elemente der Menge durch geht". Und selbst dann kann die fragliche Menge noch unbeschränkt sein oder es existiert kein Maximum bzw Minimum.

[J0T4T4]

@DerRoll

Ja, das Verfahren eignet sich nur wirklich für endliche Mengen.

Wenn kein Maximum existiert wäre es aber auch nicht so verwerflich, wenn das Verfahren scheitert. So allgemein ist es aber auch schwierig, was anderes sinnvolles zu antworten.

[DerRoll]

@J0T4T4

Endlich muss nicht sein, entscheidbar dürfte genügen.

[J0T4T4]

@DerRoll

Was gebau macht eine Menge entscheidbar?

Außerdem nochmal ein Beispiel:

Nehmen wir die Menge aller reellen Zahlen zwischen einschließlich 0 und 1. Das Maximum der Menge ist 1. Grundsätzlich existiert also das Maximum und ich (als Mensch) kann sehen, dass alle anderen Zahlen dort kleiner sind (außer vielleicht 0.999 periode). Ein Algorithmus kann aber nicht in endlicher Zeit diese unendliche Menge durchgehen, d.h. er würde scheitern. Kannst du mir sagen, woran das liegt?

[DerRoll]

@J0T4T4

Der Begriff "Entscheidbar" kommt aus der theoretischen Informatik. Es gilt

Entscheidbar TM rekursiv Aufzählbar TM abzählbar.

R ist überabzählbar, d.h. einen auf abzählbaren Methoden beruhenden Algorithmus einen Wert zu finden (außer als Grenzwert) ist nicht möglich. Nebenbei ist 0,9 periode identisch mit 1.