matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenAlgebraMathem. Definition verstehen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Geschichte • Erdkunde • Sozialwissenschaften • Politik/Wirtschaft
Forum "Algebra" - Mathem. Definition verstehen
Mathem. Definition verstehen < Algebra < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Algebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Mathem. Definition verstehen: Erklärung
Status: (Frage) beantwortet Status 
Datum: 22:03 So 03.08.2014
Autor: Vokabulator

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.

        
Bezug
Mathem. Definition verstehen: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                
Bezug
Mathem. Definition verstehen: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 19:44 Fr 22.08.2014
Autor: Vokabulator

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?

Bezug
                        
Bezug
Mathem. Definition verstehen: Antwort
Status: (Antwort) fertig Status 
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

Bezug
                                
Bezug
Mathem. Definition verstehen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 12:32 Sa 23.08.2014
Autor: Vokabulator

super, vielen Dank! Hat mir sehr geholfen!

Bezug
        
Bezug
Mathem. Definition verstehen: Antwort
Status: (Antwort) fertig Status 
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


Bezug
                
Bezug
Mathem. Definition verstehen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 11:46 Mo 04.08.2014
Autor: Vokabulator

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!

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Algebra"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]