Mathem. Definition verstehen < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Definition: Sei n ∈ N und a = a0, ..., an−1 eine endliche Folge mit ai ∈ N
(i = 0, ..., n − 1).
Das Sortierproblem besteht darin, eine Folge aφ(0), ..., aφ(n−1) zu finden, derart
dass aφ(i) ≤ aφ(j) ist f¨ur alle i, j ∈ {0, ..., n − 1} mit i < j und derart dass die
Abbildung φ eine Permutation der Indexmenge {0, ..., n − 1} ist.
Beispiel: Es seien n = 8 und a = 3 8 1 4 3 3 2 6.
i : 0 1 2 3 4 5 6 7
ai : 3 8 1 4 3 3 2 6
φ(i) : 2 6 5 0 4 3 7 1
aφ(i) : 1 2 3 3 3 4 6 8 |
Hallo!
Hier wird "Sortierung" im Informatik-Sinne, also bei Sortieralgorithmen, formal definiert.
Ich versteh hier nicht ganz, was φ(i) für eine Bewandtnis hat.
aφ(i) ist ja die sortierte Folge. Aber φ(i) verstehe ich nicht. Was trägt das zur Definition bei?
Danke für Tipps und Hilfen.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:40 So 03.08.2014 | | Autor: | Marcel |
Hallo,
> Definition: Sei n ∈ N und a = a0, ..., an−1 eine
> endliche Folge mit ai ∈ N
> (i = 0, ..., n − 1).
> Das Sortierproblem besteht darin, eine Folge aφ(0), ...,
> aφ(n−1) zu finden, derart
> dass aφ(i) ≤ aφ(j) ist f¨ur alle i, j ∈ {0, ..., n
> − 1} mit i < j und derart dass die
> Abbildung φ eine Permutation der Indexmenge {0, ..., n
> − 1} ist.
> Beispiel: Es seien n = 8 und a = 3 8 1 4 3 3 2 6.
> i : 0 1 2 3 4 5 6 7
> ai : 3 8 1 4 3 3 2 6
> φ(i) : 2 6 5 0 4 3 7 1
> aφ(i) : 1 2 3 3 3 4 6 8
> Hallo!
>
> Hier wird "Sortierung" im Informatik-Sinne, also bei
> Sortieralgorithmen, formal definiert.
>
> Ich versteh hier nicht ganz, was φ(i) für eine Bewandtnis
> hat.
>
> aφ(i) ist ja die sortierte Folge. Aber φ(i) verstehe ich
> nicht. Was trägt das zur Definition bei?
[mm] $\varphi \colon \{0,...,n-1\} \to \{0,...,n-1\}$ [/mm] ist eine Bijektion (Idee: kein Index geht
verloren und keiner kommt mehrmals vor) so, dass die durch
[mm] $b_{k}:=a_{\varphi(k)}$ [/mm] für $k=0,...,n-1$
definierte Folge
[mm] $b_0 \le b_1 \le b_2 \le [/mm] ... [mm] \le b_{n-2} \le b_{n-1}$
[/mm]
erfüllt.
Oben hast Du
[mm] $a_0=3,$ $a_1=8,$ $a_2=1,$ $a_3=4,$ $a_4=3,$ $a_5=3,$ $a_6=2,$ $a_7=6\,.$
[/mm]
"Sortiert" siehst Du sofort:
[mm] $b_0=1,$ $b_1=2,$ $b_2=3,$ $b_3=3,$ $b_4=3,$ $b_5=4,$ $b_6=6,$ $b_7=8$ [/mm]
Wenn Du jetzt hinschaust:
[mm] $b_0=a_2\,,$ [/mm] also muss hier [mm] $\varphi(0)=2$ [/mm] sein. Denn: Es gibt keinen anderen(!) Index
aus $k [mm] \in \{0,...,7\}$ [/mm] mit [mm] $a_k=1\,.$
[/mm]
[mm] $b_1=a_6\,,$ [/mm] dann muss [mm] $\varphi(1)=6\,$ [/mm] sein, denn: ...?
[mm] $b_2=a_0=a_4=a_5\,.$ [/mm] Hier kann [mm] $\varphi(2) \in \{0,4,5\}$ [/mm] gewählt werden.
Würdest Du nun [mm] $\varphi(2)=5$ [/mm] wählen, so siehst Du
[mm] $b_3=a_0=a_4=a_5\,,$ [/mm] aber [mm] $5\,$ [/mm] wurde schon benutzt: [mm] $\varphi(3) \in \{0,4\}$ [/mm] wäre wählbar etc..
Im Prinzip sagt die Funktion [mm] $\varphi$ [/mm] "nur": Wie muss ich die Indizes "tauschen",
so dass nach dem Tausch die Folgeglieder in der richtigen Reihenfolge stehen.
Oben siehst Du, dass es dafür mehr als eine bijektive Funktion
[mm] $\varphi \colon \{0,...,n-1\} \to \{0,...,n-1\}$ [/mm] geben kann.
Mit Eurem [mm] $\varphi$ [/mm] von oben:
Wenn
[mm] $a_0=3,$ $a_1=8,$ $a_2=1,$ $a_3=4,$ $a_4=3,$ $a_5=3,$ $a_6=2,$ $a_7=6\,$
[/mm]
ist, und wenn
[mm] $\varphi(0):=2,$ $\varphi(1):=6,$ $\varphi(2):=5,$ $\varphi(3):=0,$ $\varphi(4):=4,$ $\varphi(5):=3,$ $\varphi(6):=7,$ $\varphi(7):=1$
[/mm]
(siehe Deine Tabelle: $i [mm] \mapsto \varphi(i)$!)
[/mm]
ist, dann ist
[mm] $\varphi \colon \{0,...,7\} \to \{0,...,7\}$
[/mm]
bijektiv (warum?), und mit [mm] $b_k:=a_{\varphi(k)}$ [/mm] ($k=0,...,7$) folgt
[mm] $b_0=a_{\varphi(0)}=a_2=1\,,$ [/mm]
[mm] $b_1=a_{\varphi(1)}=a_6=2\,,$ [/mm]
[mm] $b_2=a_{\varphi(2)}=a_5=3\,,$ [/mm]
[mm] $b_3=a_{\varphi(3)}=a_0=3\,,$ [/mm]
[mm] $b_4=a_{\varphi(4)}=a_4=3\,,$ [/mm]
[mm] $b_5=a_{\varphi(5)}=a_3=4\,,$ [/mm]
[mm] $b_6=a_{\varphi(6)}=a_7=6\,,$ [/mm]
[mm] $b_7=a_{\varphi(7)}=a_1=8\,.$
[/mm]
Du siehst hier: Weil [mm] $\{0,...,7\} \ni [/mm] k [mm] \mapsto a_k$ [/mm] nicht injektiv ist, haben wir die
Möglichkeit zur Erstellung mehrer Funktionen [mm] $\varphi$ [/mm] wie gewünscht. Bspw.
wäre durch
[mm] $\varphi(0):=2,$ $\varphi(1):=6,$ $\red{\varphi(2):=0},$ $\red{\varphi(3):=5},$ $\varphi(4):=4,$ $\varphi(5):=3,$ $\varphi(6):=7,$ $\varphi(7):=1$
[/mm]
ein "anderes" bijektives [mm] $\varphi \colon \{0,...,7\} \to \{0,...,7\}$ [/mm] wie gewünscht gefunden.
(Das "neue" sollte man dann auch vielleicht besser bspw. [mm] $\tilde{\varphi}$ [/mm] nennen!)
Gruß,
Marcel
|
|
|
| |
|
Hallo!
Ich muss doch noch mal nachfragen: Habe mir das Ganze jetzt noch mal angeschaut und bin grad wieder am Stolpern:
Die Zahlenfolge 6 1 4 3 3 2 3 8 ist keine richtige Sortierung.
Begründung: Zwar sind die Indizes der beiden Folgen eine Bijektion aufeinander, aber:
Bei dieser Sortierung wäre [mm] \varphi(0) [/mm] = 7 (also der siebte Index der Ausgangsfolge, die Zahl 6), was aber falsch ist, weil z. B. [mm] \varphi(1) [/mm] = 2 (die Zahl 1), was ja dem Kriterium [mm] a_\varphi_(i) \le a_\varphi_(j) [/mm] widerspricht, wobei i als [mm] \le [/mm] j definiert wurde
Ist das richtig argumentiert? Habe ich da alles in Betracht gezogen?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:35 Fr 22.08.2014 | | Autor: | Marcel |
Hallo,
> Hallo!
>
> Ich muss doch noch mal nachfragen: Habe mir das Ganze jetzt
> noch mal angeschaut und bin grad wieder am Stolpern:
>
> Die Zahlenfolge 6 1 4 3 3 2 3 8 ist keine richtige
> Sortierung.
naja, Du hast hier die Bijektion [mm] $\varphi \colon \{0,...,7\} \to \{0,...,7\}$ [/mm] nicht angegeben.
> Begründung: Zwar sind die Indizes der beiden Folgen eine
> Bijektion aufeinander,
Wenn Du [mm] $\varphi$ [/mm] gar nicht angibst, ist das hier so nicht klar. Du hattest
> i : 0 1 2 3 4 5 6 7
> [mm] a_i [/mm] : 3 8 1 4 3 3 2 6
Warum ist das nicht klar? Um
> 6 1 4 3 3 2 3 8
zu kreieren, könntest Du ja auch
[mm] $\varphi(0):=7\,,$
[/mm]
[mm] $\varphi(1):=2\,,$
[/mm]
[mm] $\varphi(2):=3\,,$
[/mm]
[mm] $\varphi(3):=\varphi(4):=4\,,$
[/mm]
... (Rest auch irgendwie passend)
definiert haben. Dann wäre [mm] $\varphi \colon \{0,...,7\} \to \{0,...,7\}$ [/mm] nicht bijektiv - denn
diese Funktion wäre nicht surjektiv!
Aber nehmen wir mal an, Du hast schon diese Umsortierung mit einer
bijektiven Funktion [mm] $\varphi$ [/mm] (diese ist hier auch nicht eindeutig!) gefunden.
> aber:
>
> Bei dieser Sortierung wäre [mm]\varphi(0)[/mm] = 7 (also der
> siebte Index der Ausgangsfolge, die Zahl 6),
Vorsicht in der Sprechweise: Die Indexzählung fängt bei 0 an, der erste
Index ist also 0. Der achte Index der Ausgangsfolge ist 7, und der Wert
des Folgeglieds mit diesem Index ist eben [mm] $a_7=6\,.$
[/mm]
> was aber
> falsch ist, weil z. B. [mm]\varphi(1)[/mm] = 2 (die Zahl 1), was ja
> dem Kriterium [mm]a_\varphi_(i) \le a_\varphi_(j)[/mm] widerspricht,
> wobei i als [mm]\le[/mm] j definiert wurde
Auch das ist schlecht gesagt. Ich weiß, was Du meinst, aber wenn etwas
gilt, ist es nicht falsch. Verkürzt gesagt sagst Du für obige Folge [mm] $a\,:$
[/mm]
Wäre [mm] $\varphi \colon \{0,...,7\} \to \{0,...,7\}$ [/mm] eine Bijektion, so dass [mm] "$(a_{\varphi(j)})_{j=0}^7$ [/mm] sortiert" ist, dann
kann nicht [mm] $\varphi(0)=7$ [/mm] und [mm] $\varphi(1)=2$ [/mm] gelten.
Denn dann wäre
[mm] $a_{\varphi(0)}=6$ $\red{\textbf{>}}$ $a_{\varphi(1)}=1\,,$
[/mm]
obwohl
$0 < [mm] 1\,$
[/mm]
gilt.
(Aus $0 < [mm] 1\,$ [/mm] müßte doch [mm] $a_{\varphi(0)} \le a_{\varphi(1)}$ [/mm] folgen.)
> Ist das richtig argumentiert? Habe ich da alles in Betracht gezogen?
Du meinst es sicher richtig, aber an Deiner Ausdrucksweise musst Du
arbeiten.
P.S. Ich würde das Sortierproblem auch ein wenig anders formulieren,
vielleicht hilft Dir das beim Verständnis. Du kannst es in äquivalenter
Form auch so formulieren:
Sei [mm] $a=(a_i)_{i=0}^{n-1}$ [/mm] eine endl. Zahlenfolge. Wir sagen, dass [mm] $b=(b_j)_{j=0}^{n-1}$ [/mm] eine Sortierung
der Folge [mm] $a\,$ [/mm] ist, wenn es eine Bijektion (was hier gleichbedeutend mit Injektion
und auch gleichbedeutend mit Surjektion ist)
[mm] $\varphi \colon \{0,...,n-1\} \to \{0,...,n-1\}$
[/mm]
so gibt, dass
für alle $i [mm] \in \{0,...,n-1\}$ [/mm] gilt [mm] $b_i=a_{\varphi(i)}$ [/mm] und für alle $j [mm] \in \{0,...,\red{n-2}\}$ [/mm] gilt [mm] $b_j$ $\le$ $b_{j+1}$ [/mm]
(d.h. [mm] $a_{\varphi(j)}$ $\le$ $a_{\varphi(j+1)}$).
[/mm]
In Deinem obigen Fall wäre [mm] $b_0 [/mm] > [mm] b_1$ [/mm] wegen [mm] $b_0=a_{\varphi(0)}=a_7=6 [/mm] > [mm] 1=b_1=a_{\varphi(1)}=a_2=1$ [/mm] und
somit [mm] $b\,$ [/mm] KEINE Sortierung der Folge [mm] $a\,.$
[/mm]
Beachte dabei: Der Begriff "Sortierung" wird hier von mir sehr lasch benutzt.
Etwas besser würde man "Sortierung von klein nach groß" oder so etwas
dazu sagen.
Gruß,
Marcel
|
|
|
| |
|
super, vielen Dank! Hat mir sehr geholfen!
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 23:17 So 03.08.2014 | | Autor: | rmix22 |
> Definition: Sei n ∈ N und a = a0, ..., an−1 eine
> endliche Folge mit ai ∈ N
> (i = 0, ..., n − 1).
> Das Sortierproblem besteht darin, eine Folge aφ(0), ...,
> aφ(n−1) zu finden, derart
> dass aφ(i) ≤ aφ(j) ist f¨ur alle i, j ∈ {0, ..., n
> − 1} mit i < j und derart dass die
> Abbildung φ eine Permutation der Indexmenge {0, ..., n
> − 1} ist.
> Beispiel: Es seien n = 8 und a = 3 8 1 4 3 3 2 6.
> i : 0 1 2 3 4 5 6 7
> ai : 3 8 1 4 3 3 2 6
> φ(i) : 2 6 5 0 4 3 7 1
> aφ(i) : 1 2 3 3 3 4 6 8
> Hallo!
>
> Hier wird "Sortierung" im Informatik-Sinne, also bei
> Sortieralgorithmen, formal definiert.
>
> Ich versteh hier nicht ganz, was φ(i) für eine Bewandtnis
> hat.
>
> aφ(i) ist ja die sortierte Folge. Aber φ(i) verstehe ich
> nicht. Was trägt das zur Definition bei?
>
> Danke für Tipps und Hilfen.
Was genau ist dir unklar? Ohne [mm] $\varphi(i)$ [/mm] gibst doch auch keine Folge [mm] $a_{\varphi(i)}$.
[/mm]
Oder meintest du, dass aφ einfach der Name der sortierten Folge ist? Leider verwendest du die hier angebotene Möglichkeit für den Formelsatz nicht, sodass das nicht klar ersichtlich ist.
Oder ist dir unklar, warum [mm] $\varphi(i)$ [/mm] eine Permutation der Indexmenge sein muss? Das hat dir Marcel gerade versucht zu erklären, warum [mm] \varphi [/mm] bijektiv sein muss - damit keine Folgenelemente verloren gehen oder mehrfach verwendet werden.
Nimm dazu [mm] $\;n=3$ [/mm] und die Folge $a=<30;50;20>$
Und nun nehmen wir eine Abbildung [mm] $\varphi$, [/mm] welche keine Permutation von [mm] $\{0;1;2\}$ [/mm] ist, etwa [mm] $\varphi{(i)}=1\text{ für }i\in\{0;1;2\}.
[/mm]
Die "sortierte" Folge wäre nun $<50;50;50>$ und erfüllt die übrigen Anforderungen der Definition. Es mach also durchaus Sinn zu fordern, dass alle Indizes genau einmal vorkommen sollen, denn nur das stellt sicher, dass die neue Folge eine bloße Umordnung der alten Folge ist. Die restliche Definition stellt eine Sortierung in aufsteigender Reihenfolge sicher.
RMIx
|
|
|
| |
|
Super, vielen Dank für die ausführlichen Antworten! Ich hatte nicht verstanden, was das φ(i) genau bewirkt, also wie genau das φ(i) zur Sortierung beiträgt. Aber jetzt ist es mir klar!
|
|
|
|
