Sandbox: Difference between revisions

From Alda
Jump to navigationJump to search
No edit summary
No edit summary
 
(20 intermediate revisions by 12 users not shown)
Line 1: Line 1:
Formel:
<math>
\Delta L_{sum} = \frac{\sqrt{L_R^4 \cdot \Delta L_B^2 + L_B^4 \cdot \Delta L_R^2}}{(L_B + L_R)^2}
</math>
---
<math>f(x)=\sqrt[4]{x}</math>
<math>f(x)=\sqrt[4]{x}</math>


Line 5: Line 10:
hallo'''
hallo'''


<math>L_{iij}</math>
<math>
X_{ij} = x_i x_j
</math>


There was a young lady from Riga,
There was a young lady from Riga,
Line 17: Line 27:


{| border="1" cellspacing="0" cellpadding="9" align="center"
{| border="1" cellspacing="0" cellpadding="9" align="center"
! hello
! hello
! is
! is
|-  
|-  
Line 24: Line 34:
|-
|-
|}
|}
          5


----
      /       \
3.Stunde am 16.04.2008
 
==Sortierverfahren==
 
=== Motivation ===
'''Def:'''
Ein Sortierverfahren ist ein Algorithmus, der dazu dient, eine Liste von Elementen zu sortieren.
 
'''Anwendungen'''
* Sortierte Daten sind häufig Vorbedingungen für Suchverfahren (Speziell für Algorithmen mit Log(N) Komplexität)
* Darstellung von Daten gemäß menschlicher Wahrnehmung
* Bemerkung: aus programmiertechnischer Anwenwendungssicht hat das Sortierproblem an Relevanz verloren, da
** Festplatten / Hauptspeicher heute weniger limitierenden Charakter haben, so dass komplizierte, speicher-sparende Sortieralgorithmen nur noch in wenigen Fällen benötigt werden.
** gängige Programmiersprachen heute typenabhängige Algorithmen zur Verfügung stellen. Der Programmierer braucht deshalb sich in den meisten Fällen nicht mehr um die Implementierung von Sortieralgorithmen kümmern. In C/C++ sorgen dafür beispielsweise Methoden aus der [http://de.wikipedia.org/wiki/Standard_Template_Library STL]
 
===  Vorraussetzungen/ Spielregeln ===
==== Mengentheoretische  Anforderungen====
;Definition Totale Ordnung/ Total gordnete Menge:
Eine Totale Ordnung / Total geordnete Menge ist eine binäre Relation   
<math>R \subseteq M \times M</math> über einer Menge <math>M</math>, die transitiv, antisymmetrisch und total ist.<br>
 
<math>R</math> sei  dargestellt als infix Notation <math>\le </math> dann, falls M total geordnet, gilt
<math> \forall a,b,c \ \epsilon M </math> <br/>
(1) <math>a \le b \bigwedge b \le a \Rightarrow a=b </math> (antisymmetrisch)<br/>
(2) <math>a \le b \bigwedge b \le c \Rightarrow a \le c </math> (transitiv)<br/>
(3) <math>a \le b \bigvee b \le a </math> (total) <br/>
Bemerkung: aus (3) folgt <math> a \le a </math> (reflexiv) <br/>
 
''Hab in der Wiki eine gute Seite dazu gefunden [http://de.wikipedia.org/wiki/Ordnungsrelation'' Ordnungsrelation]
 
==== Datenspeicherung ====
a) Array (Grafik folgt noch)
 
b) Vekettete Liste 
  Nachteil Adressierung bsp: 10 > 9
 
==== Charakterisierung der Effizienz von Algorithmen ====
 
:(a) Komplexität O(1), O(n), etc. wird in Kapitel [[Effizienz]] erklärt.
:(b) Zählen der notwendigen Vergleiche
:(c) Messen der Laufzeit mit 'timeit' (auf identischen Daten)


'''Rekursive Zerlegung'''
    2          8
zerlegt Ursprüngliche Probleme in kleinere Probleme und wendet sie auf die kleineren Probleme an;
daraufhin werden die Teilprobleme zur Lösung des Gesamtproblems verwendet.
'''Aufwand'''
für N  Eingaben, hängt ab vom Aufwand der Eingaben geringeren Umfangs ab. (Teilprobleme)


  /  \      /  \


1      4  7      9


----
This is a sentence.
----
4. Stunde, am 17.04.2008
<br/>
(Fortsetzung der Stunde vom 16.04.2008)
<br/>
 
 
=== 3.3 Mergesort ===
==== a) Algorithmus ====
 
# Zugrunde liegende Idee:
* "Teile und herrsche"-Prinzip (divide and conquer) zur Zerlegung in Teilprobleme
* Zusammenführen der Lösungen über Mischen (merging)
** two-way
** multi-way
==== a.1) Algorithmus <tt>c ← merge(a,b)</tt> ====
 
c = merge(a,b) ← {      # Kombination zweier sortierter Listen a_i und b_j
                        # zu einer sortierten Ausgabeliste c_k
    a[M+1] ← maxint
    b[N+1] ← maxint
    for k ← 1 to M+N
        if a[i] < b[j]
            c[k] > a[i]
            i ← i+1
        else
            c[k] ← b[j]
            j ← j+1
}
 
 
==== a.2)'''rekursiver Mergesort''' ====
 
  mergesort(m) ← {    #m ist ein Array
      if |m| > 1      #True, wenn m mehr als 1 Element hat.
          a ← mergesort(m[1:<|m|/2])
          b ← mergesort(m[(|m|/2)+1:|m|])
          c ← merge(a,b)
          return(c)
      else
          return(m)
}
 
(Eine In-place-Implementierung siehe bei Sedgewick.)
 
Bei der Sortierung mit Mergesort wird das Array immer in zwei Teile geteilt. → Es entsteht ein Binärbaum der Tiefe <math>lgN</math>.
 
Gegebene unsortierte Liste: [S,O,R,T,I,N,G]
Die Teile werden bei jedem Schritt paarweise gemischt.
 
Schritt 0:
  S 0 R T I N G        S    O R    T I    N    G    #Arraylänge: N/8
Schritt 1:            \  /  \  /  \  /    /
  OS RT IN G            OS    RT    IN    /      #Arraylänge: N/4        Vergleiche: N/4 * 4
Schritt 2:                \    /        \  /     
  ORST GIN                  ORST          GIN        #Arraylänge: N/2        Vergleiche: N/2 * 2
                              \        /
Schritt3:                      \      /
  GINORST                        GINORST            #Arraylänge: N          Vergleiche: N             
 
 
 
Zeitkomplexität: <math>C(N) - N \cdot lgN</math>
 
==== b) Komplexität ====
Komplexität: <math>C(N) = 2 \cdot \left( \frac{N}{2} \right) + N = N \cdot log_2 N
 
\cdot N</math>    (für N = <math>2^n</math> )
 
Erklärungen zur Formel:
* <math> C \left(\frac{N}{2}\right) </math>: für jede Hälfte des Arrays
* <math> + N </math>: für das Zusammenführen
 
==== c) Weitere Eigenschaften von MergeSort ====
* Mergesort ist '''stabil''', weil die Position gleicher Schlüssel im Algorithmus
 
<tt>merge(a,b)</tt> nicht verändert wird - wegen <tt>„<”</tt> hat das linke
 
Element Vorrang.
* Mergesort ist '''unempfindlich gegenüber der Reihenfolge der Eingabedaten'''.
 
Grund dafür ist die vollständige Aufteilung des Ausgangsarrays in Arrays der Länge
 
1.
* Diese Eigenschaft ist dann unerwünscht, wenn ein Teil des Arrays oder gar das
 
ganze Array schon sortiert ist. Es wird nämlich in jedem Fall das ganze Array neu
 
sortiert.
 
=== Quicksort ===
 
* Quicksort wurde in den 60er Jahren von Charles Antony Richard Hoare [http://de.wikipedia.org/wiki/C._A._R._Hoare] entwickelt. Es gibt viele Implementierungen von Quicksort, siehe  vgl. [http://de.wikipedia.org/wiki/Quicksort].
* Dieser Algorithmus gehört zu den "Teile und herrsche"-Algorithmen (divide-and-conquer) und ist der Standardalgorithmus für Sortieren.
 
==== Zugrunde liegender Algorithmus ====
 
  quicksort(l,r) ← {    #l: linke Grenze, r: rechte Grenze des Arrays
                      #Das Array läuft also von l bis r (a[l:r])
      if r > l
          i ← partition(l,r)    #i ist das Pivot-Element
          quicksort(l,i-1)    #quicksort auf beide Hälfte des Arrays anwenden
          quicksort(i+1,r)
  }
Dieser Algorithmus wird rekursiv für zwei Teilstücke links und rechts des Pivot-Elements aufgerufen. Das Pivot-Element ist nach diesem Schritt an der richtigen Position (d.h. links von der Stelle i stehen nur kleinere, rechts von i nur größere Elemente als das Pivot-Element).
Die Methode partition sorgt dafür, dass diese Bedingung erfüllt ist.
 
==== Algorithmus für <tt>partition</tt> ====
Aufgabe: Ordne <tt>a</tt> so um, dass nach der Wahl von <tt>i</tt> (Pivot-Element)
 
gilt:
# <math>a[i]</math> ist sortiert, d.h. dieses Element ist am endgültigen Platz.
# <math>\forall x \in \left\{ a \left[ l \right] , ... a \left[ i-1 \right]
 
\right\} : x \leq a \left[ i \right]</math>
# <math>\forall x \in \left\{ a \left[ i+1 \right], ... a \left[ r \right]
 
\right\} : x \geq a \left[ i \right]</math>
 
[[Abbildung fehlt noch]]  a[i] heißt Pivot-Element (p)
 
  i ← partition(l,r) ← {
      p ← a[r]    #p: Pivot-Element. Hier wird willkürlich das rechteste Element
                  #  als Pivot-Element genommen.
      i ← l-1    #i und j sind Laufvariablen
      j ← r
     
      repeat
          repeat
              i ← i+1    #Finde von links den ersten Eintrag >= p
          until a[i] >= p
     
          repeat
              j ← j+1    #Finde von rechts den ersten Eintrag <= p
          until a[j] <= p
          swap(a[i], a[j])
      until j <= i    #Nachteile: p steht noch rechts
      swap(a[i], a[j])    #Letzter Austausch zwischen i und j muss
                              #zurückgenommen werden
      swap(a[i], a[r])
      return(i)
  }
 
[[Abbildung fehlt noch]]
 
[[Beispiel fehlt noch]]
 
Bemerkungen zur gegebenen Implementierung:
#  Sie benötigt ein Dummy-Minimalelement.
#* Dieses Element ist durch zusätzliche <tt>if</tt>-Abfrage vermeidbar, aber die
 
<tt>if</tt>-Abfrage erhöht die Komplexität des Algorithmus (schlechte Performanz).
# Sie ist ineffizient für (weitgehend) sortierte Arrays, da sich folgende
 
Aufteilung für die Partitionen ergibt:
# Erste Partition: <tt>[l,i-1]</tt>, zweite Partition: <tt>[i+1,r]</tt>
# Die erste Partition umfasst <tt>N-1</tt> Elemente
# Die zweite Partition ist leer (bzw. sie existiert nicht), weil das Pivot-Element <tt>p = r</tt> gewählt wurde. Das Array wird also elementweise abgearbeitet.
# → <tt>N</tt> einzelne Aufrufe ⇒ Zeitkomplexität: <math>\approx
 
\frac{N^2}{2}</math> (siehe Berechnung vom 16.04.2008)
# Für identische Schlüssel sollten beide Laufvariablen stehen bleiben.
# Bei der gegebenen Implementierung tauscht auch gleiche Elemente aus.
# Für identische Schlüssel können die Abbruchbedingungen verbessert werden (siehe Sedgewick).
 
==== Komplexität ====
 
<math>C(N) = (N+1) + \frac{1}{N} \sum_{m=1}^{N} \left[ C(k-1) + C(N-k)
 
\right]</math> für <math> N>1;\, C_1 = C_0 =0 </math>
 
Anmerkungen zur Formel:
# <math>(N+1)</math>: Vergleiche für jeden Aufruf
# <math>k</math>: Teilungspunkt
<br/><br/><br/>
<math>
\frac{1}{N} \sum_{m=1}^{N} \left[ C(k-1) + C(N-k) \right] = 2 \frac{1}{N}
 
\sum_{k=1}^{N} C(k-1)
</math>
<br/><br/>
 
<math>
C(N) = (N+1) + \frac{1}{N} \sum_{m=1}^{N} \left[ C(k-1) + C(N-k) \right]
\overset{\cdot N}{\longleftrightarrow} </math>
<br/><br/>
 
<math>
N \cdot C(N) = N \left[ (N+1) + \frac{2}{N} \sum_{k=1}^{N} C(k-1) \right]
\overset{-\, (N-1) \cdot C(N-1)}{\longleftrightarrow} </math>
<br/><br/>
 
<math>
N \cdot C(N) - (N-1) \cdot C(N-1) = N(N+1) - (N-1) \cdot N + 2 \sum_{k=1}^{N}
 
C(k-1) - 2 \sum_{k=1}^{N} C(k-1) </math>
<br/><br/>
 
<math>
= N(N+1) - (N-1) \cdot N + 2 \cdot C(N-1) \longleftrightarrow </math>
<br/><br/>
 
<math>
N \cdot C(N) = N(N+1) - (N-1) \cdot N + 2 \cdot C(N-1) + (N-1) + (N-1) \cdot
 
C(N-1) = 2N + (N+1) \cdot C(N-1) \overset{/N(N+1)}{\longleftrightarrow} </math>
<br/><br/>
 
<math>
\frac{C(N)}{N+1} = \frac{C(N-1)}{N} + \frac{2}{N+1} </math>
<br/><br/>
 
<math>
= \frac{C(N-2)}{N-1} + \frac{2}{N} + \frac{2}{N+1} </math>
<br/><br/>
 
<math>
= \frac{C(N-3)}{N-2} + \frac{2}{N-1} + \frac{2}{N} + \frac{2}{N+1} </math>
<br/><br/>
 
<math>
= ... = </math>
<br/><br/>
 
<math>
= \frac{C(2)}{3} + 2 \sum_{k=3}^{N} \frac{1}{k+1} \approx 2 \sum_{k=3}^{N}
 
\frac{1}{k+1} \approx 2 \int_1^N \frac{1}{k} dk = 2 \cdot ln N
</math>
<br/><br/><br/>
Für sehr große N gilt:
<math>\approx 2 \sum_{k=1}^{N} \frac{1}{k}</math> beziehungsweise <math> \geq 2


\sum_{k=1}^{N} \frac{1}{k}</math>
This sentence is false.
<br/><br/>
And this one is unprovable!
Mittlere Komplexität:
<math>C(N) = 2(N+1) \cdot lnN \approx 2N \cdot lnN </math>
<br/><br/><br/>
==== Verbesserungen des Algorithmus ====
# Eine Verbesserung beseitigt die Rekursion durch Verwendung eines Stacks.
# "r" wird immer kleiner → Der rekursive Aufruf lohnt sich nicht mehr. → Explizites Sortieren einsetzen.
# Das Pivot-Element könnte geschickter gewählt werden: Median.
<br/>
[[Special:Contributions/147.142.207.188|147.142.207.188]] 19:31, 23 April 2008 (UTC)

Latest revision as of 09:29, 19 April 2012

Formel: <math> \Delta L_{sum} = \frac{\sqrt{L_R^4 \cdot \Delta L_B^2 + L_B^4 \cdot \Delta L_R^2}}{(L_B + L_R)^2} </math> --- <math>f(x)=\sqrt[4]{x}</math>

<math>f(x)=\frac{y}{x}</math>
hallo

<math>L_{iij}</math>

<math> X_{ij} = x_i x_j </math>

There was a young lady from Riga,

who smiled as she rode on a tiger.

they returned from the ride

with the lady inside

and the smile on the face of the tiger.

hello is
a table 
         5

      /       \

    2           8

  /   \       /   \

1       4   7       9

This is a sentence.

This sentence is false. And this one is unprovable!

Retrieved from "https://alda.iwr.uni-heidelberg.de/index.php?title=Sandbox&oldid=4881"