www.vorhilfe.de
Vorhilfe

Kostenlose Kommunikationsplattform für gegenseitige Hilfestellungen.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Forenbaum
^ Forenbaum
Status Vorhilfe
  Status Geisteswiss.
    Status Erdkunde
    Status Geschichte
    Status Jura
    Status Musik/Kunst
    Status Pädagogik
    Status Philosophie
    Status Politik/Wirtschaft
    Status Psychologie
    Status Religion
    Status Sozialwissenschaften
  Status Informatik
    Status Schule
    Status Hochschule
    Status Info-Training
    Status Wettbewerbe
    Status Praxis
    Status Internes IR
  Status Ingenieurwiss.
    Status Bauingenieurwesen
    Status Elektrotechnik
    Status Maschinenbau
    Status Materialwissenschaft
    Status Regelungstechnik
    Status Signaltheorie
    Status Sonstiges
    Status Technik
  Status Mathe
    Status Schulmathe
    Status Hochschulmathe
    Status Mathe-Vorkurse
    Status Mathe-Software
  Status Naturwiss.
    Status Astronomie
    Status Biologie
    Status Chemie
    Status Geowissenschaften
    Status Medizin
    Status Physik
    Status Sport
  Status Sonstiges / Diverses
  Status Sprachen
    Status Deutsch
    Status Englisch
    Status Französisch
    Status Griechisch
    Status Latein
    Status Russisch
    Status Spanisch
    Status Vorkurse
    Status Sonstiges (Sprachen)
  Status Neuerdings
  Status Internes VH
    Status Café VH
    Status Verbesserungen
    Status Benutzerbetreuung
    Status Plenum
    Status Datenbank-Forum
    Status Test-Forum
    Status Fragwürdige Inhalte
    Status VH e.V.

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:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
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.vorhilfe.de