Algorithmen: Sortierverfahren

Algorithmen und Datenstrukturen

Sortieren: Einfache Verfahren

• Grundidee ist die Unterteilung in einen sortierten und einen unsortierten Teil.
• Pro Schritt wird ein Element vom unsortierten zum sortierten Teil verschoben.
• Der sortierte Teil ist stets sortiert.
• Alle Elemente im sortierten Teil sind kleiner oder grösser als die im unsortierten Teil (Invariante).
• Beispiele hierfür sind Selection Sort, Insertion Sort und Bubble Sort.

Sortieren: Divide and Conquer

• Das Problem wird in kleinere Teilprobleme zerlegt.
• Die Teilprobleme werden rekursiv gelöst.
• Die Teillösungen werden zur Gesamtlösung zusammengefügt.
• Mergesort und Quicksort sind gängige Beispiele.

Mergesort

• Die Eingabe wird in zwei gleich grosse Hälften geteilt.
• Jede Hälfte wird rekursiv sortiert.
• Die sortierten Hälften werden zusammen gemischt.
• Am Beispiel der Eingabe [8, 3, 1, 7, 0, 10, 2, 6]:
  • Teilung: [8, 3, 1, 7] und [0, 10, 2, 6].
  • Rekursive Sortierung: [1, 3, 7, 8] und [0, 2, 6, 10].
  • Mischen: [0, 1, 2, 3, 6, 7, 8, 10].

Neuronale Netze – Grundlagen und Architekturen

Einführung

• Neuronale Netze haben in den letzten Jahren grosse Erfolge in verschiedenen Bereichen der künstlichen Intelligenz erzielt.
• Durchbrüche wurden insbesondere in der Bilderkennung, der Sprachverarbeitung und dem maschinellen Übersetzen erzielt.
• Ziel ist es, die Grundlagen neuronaler Netze zu erläutern und verschiedene Architekturen vorzustellen - mathematische Grundlagen und Anwendungsbereiche werden dabei betrachtet.
• Die Arbeit gliedert sich in Einleitung, Grundlagen, Architekturen, Anwendungen, Zusammenfassung und Ausblick.

Neuron

• Das Neuron ist die grundlegende Baueinheit eines neuronalen Netzes, welches Eingaben empfängt, verarbeitet und ein Ausgangssignal ausgibt.
• Das Neuron besteht aus Eingängen ($x_1, x_2,..., x_n$), Gewichten ($w_1, w_2,..., w_n$), einer Aktivierungsfunktion ($f$) und einem Ausgang ($y$).
• Die Verarbeitung der Eingänge erfolgt mittels einer gewichteten Summe und der Anwendung der Aktivierungsfunktion: $y = f(\sum_{i=1}^{n} w_i * x_i)$.

Aktivierungsfunktionen

• Aktivierungsfunktionen führen eine nichtlineare Transformation der gewichteten Summe der Eingänge durch.
• Gängige Aktivierungsfunktionen sind Sigmoid ($\sigma(x) = \frac{1}{1 + e^{-x}}$), Tangens Hyperbolicus ($\tanh(x) = \frac{e^x - e^{-x}}{e^x + e^{-x}}$) und ReLU ($ReLU(x) = max(0, x)$).

Netzwerkarchitektur

• Neuronale Netze bestehen aus mehreren Schichten von Neuronen; die Neuronen einer Schicht sind mit denen der nächsten Schicht verbunden.
• Es gibt Feedforward-Netze, bei denen Informationen nur in eine Richtung fliessen, und rekurrente Netze, bei denen Informationen auch in die entgegengesetzte Richtung fliessen können.

Architekturen neuronaler Netze

• Feedforward-Netze bestehen aus einer Eingangs-, einer oder mehreren versteckten Schichten und einer Ausgabeschicht.
• Convolutional Neural Networks (CNNs) sind speziell für die Verarbeitung von Bildern entwickelt worden und verwenden Faltungsoperationen, um lokale Muster zu erkennen.
• Recurrent Neural Networks (RNNs) sind für die Verarbeitung sequentieller Daten geeignet und verwenden rekurrente Verbindungen, um Informationen über die Zeit zu speichern.
• Long Short-Term Memory Networks (LSTMs) können besser lange Abhängigkeiten in den Daten lernen und verwenden spezielle Gedächtniszellen.

Anwendungen neuronaler Netze

• In der Bilderkennung werden neuronale Netze zur Erkennung von Objekten, Gesichtern oder zur Klassifizierung von Bildern eingesetzt.
• In der Sprachverarbeitung werden neuronale Netze z.B. zur Spracherkennung, zur Textanalyse oder zur maschinellen Übersetzung eingesetzt.
• Weitere Anwendungen sind die Vorhersage von Aktienkursen, die Steuerung von Robotern oder die Diagnose von Krankheiten.

Zusammenfassung und Ausblick

• Die Forschung im Bereich neuronaler Netze ist noch nicht abgeschlossen.
• Zukünftige Forschung wird sich auf Erklärbarkeit, Robustheit und Effizienz konzentrieren.

Vibration

Einführung

• Beispiele für Vibrationen sind der Herzschlag, das Pendel einer Uhr und die Vibration von Atomen in Festkörpern.
• Vibration ist die Bewegung eines Teilchens oder Körpers, die sich nach einer bestimmten Zeit wiederholt.
• Die einfachste periodische Bewegung ist die harmonische Bewegung.
• Das Kapitel behandelt die Grundlagen der Vibration und die Analyse freier Schwingungen von Systemen mit einem Freiheitsgrad.
• Zu den Lernzielen gehört es, Beispiele für Vibrationen zu geben, Freiheitsgrade zu definieren, zwischen gedämpften und ungedämpften Schwingungen zu unterscheiden usw.

Grundlegende Konzepte der Vibration

• Der Freiheitsgrad ist die Anzahl der unabhängigen Koordinaten, die zur Beschreibung der Bewegung eines Systems erforderlich sind.
• Ein System, dessen Bewegung durch nur eine Koordinate beschrieben werden kann, ist ein System mit einem Freiheitsgrad (SDOF).
• Ein Beispiel hierfür ist eine Masse, die an einer Feder befestigt ist und sich in eine Richtung bewegen kann.
• Ein System, dessen Bewegung durch zwei unabhängige Koordinaten beschrieben werden kann, ist ein System mit zwei Freiheitsgraden.
• Ein Beispiel hierfür ist ein Doppelpendel.
  • Ein System, dessen Bewegung mehr als zwei unabhängige Koordinaten benötigt, ist ein System mit mehreren Freiheitsgraden.
  • Ein Beispiel hierfür sind die Flügel eines Flugzeugs.
• Freie Schwingung ist die Schwingung eines Systems unter Einwirkung von Kräften, die dem System selbst innewohnen, wie z.B. Federkraft, Dämpfungskraft, Schwerkraft.
• Erzwungene Schwingung ist die Schwingung eines Systems unter Einwirkung einer äusseren Kraft.
• Ungedämpfte Schwingung ist die Schwingung, wenn keine Energie durch Reibung usw. verloren geht.
• Gedämpfte Schwingung, wenn Energie durch Reibung usw. verloren geht.

Schritte für die Vibrationsanalyse

1. Mathematische Modellierung: Bestimmung der Freiheitsgrade und Ableitung der Bewegungsgleichung.
2. Ableitung der massgebenden Gleichungen: Anwendung des zweiten Newtonschen Gesetzes.
3. Lösung der massgebenden Gleichungen: Anwendung von Standardlösungstechniken.
4. Interpretation der Ergebnisse: Ableitung nützlicher Konstruktionsfolgerungen.

Bewegungsgleichung

• Anwenden von Newtons zweitem Gesetz: $\sum F = ma$.
  • Für ein Masse-Feder-System gilt:
  • Federkraft: $-kx$.
  • Trägheitskraft: $-m\ddot{x}$.
    • Die Bewegungsgleichung ist $m\ddot{x} + kx = 0$.

Ungedämpfte freie Schwingung

• Die allgemeine Lösung für $m\ddot{x} + kx = 0$ ist: $x(t) = A \cos(\omega_n t) + B \sin(\omega_n t)$.
  • $A$ und $B$ sind Konstanten, die aus den Anfangsbedingungen bestimmt werden können.
  • Die Eigenfrequenz beträgt: $\omega_n = \sqrt{\frac{k}{m}}$.
    • Die Lösung kann auch geschrieben werden als: $x(t) = X \cos (\omega_n t - \phi)$.
    • $X$ ist die Amplitude und $\phi$ der Phasenwinkel.
      • Weitere Parameter sind die Periode $T = \frac{2\pi}{\omega_n}$ und die Frequenz $f_n = \frac{1}{T} = \frac{\omega_n}{2\pi}$.

Probleme

• Ein Feder-Masse-System mit $m = 10 \mathrm{~kg}$ und $k = 4000 \mathrm{~N} / \mathrm{m}$ hat eine Eigenfrequenz von $\omega_n = 20 \mathrm{rad} / \mathrm{s}$ und eine Schwingungsdauer von $T = 0.3142 \mathrm{s}$.
• Für ein Feder-Masse-System mit $m = 5 \mathrm{~kg}$ und $\omega_n = 10 \mathrm{rad} / \mathrm{s}$ beträgt die Federsteifigkeit $k = 500 \mathrm{~N} / \mathrm{m}$.
• Für ein Feder-Masse-System mit $k = 5000 \mathrm{~N} / \mathrm{m}$ und $T = 0.25 \mathrm{~s}$ beträgt die Masse $m = 7.958 \mathrm{~kg}$.

Grenzwerte

Intuitiver Begriff des Grenzwerts

• Für eine Funktion $y = f(x)$ bedeutet $\lim_{x \to a} f(x) = L$, dass $f(x)$ sich $L$ annähert, wenn sich $x$ dem Wert $a$ annähert.
• Für eine Funktion $y = f(x)$ bedeutet $\lim_{x \to \infty} f(x) = L$, dass sich $f(x)$ dem Wert $L$ annähert, wenn $x$ sehr gross wird.

Berechnung von Grenzwerten

• Sind $\lim_{x \to a} f(x) = L$ und $\lim_{x \to a} g(x) = M$, so gilt:
  • $\lim_{x \to a} [f(x) \pm g(x)] = L \pm M$
  • $\lim_{x \to a} [k \cdot f(x)] = k \cdot L$
  • $\lim_{x \to a} [f(x) \cdot g(x)] = L \cdot M$
  • $\lim_{x \to a} \frac{f(x)}{g(x)} = \frac{L}{M}$ falls $M \neq 0$
  • $\lim_{x \to a} [f(x)]^n = L^n$
  • $\lim_{x \to a} \sqrt[n]{f(x)} = \sqrt[n]{L}$
• Unbestimmte Ausdrücke: $\frac{0}{0}$, $\frac{\infty}{\infty}$, $0 \cdot \infty$, $\infty - \infty$, $1^{\infty}$, $0^0$, $\infty^0$.

Auflösung unbestimmter Ausdrücke

• Für $\frac{0}{0}$ werden Zähler und Nenner faktorisiert und vereinfacht.
• Beispiel: $\lim_{x \to 2} \frac{x^2 - 4}{x - 2} = 4$.
• Für $\frac{\infty}{\infty}$ werden Zähler und Nenner durch die höchste Potenz von $x$ geteilt.
• Beispiel: $\lim_{x \to \infty} \frac{3x^2 - 5x + 2}{5x^2 + 4x - 3} = \frac{3}{5}$.
• Für $\infty - \infty$ wird die Subtraktion in einen Bruch umgewandelt.
• Beispiel: $\lim_{x \to \infty} (\sqrt{x^2 + x} - x) = \frac{1}{2}$.

Asymptoten

• Eine senkrechte Asymptote von $f(x)$ ist die Gerade $x = a$, falls $\lim_{x \to a} f(x) = \pm \infty$ gilt.
• Eine waagerechte Asymptote von $f(x)$ ist die Gerade $y = b$, falls $\lim_{x \to \infty} f(x) = b$ gilt.
• Eine schiefe Asymptote von $f(x)$ ist die Gerade $y = mx + n$, wobei $m = \lim_{x \to \infty} \frac{f(x)}{x}$ und $n = \lim_{x \to \infty} [f(x) - mx]$ ist.

Physik

Vektoren und Koordinatensysteme

• Zur Beschreibung eines Vektors ist ein Koordinatensystem erforderlich:
  • Kartesische Koordinaten nutzen senkrechte Achsen ($x$ und $y$).
  • Polarkoordinaten nutzen einen Radius $r$ und einen Winkel $\theta$.
• Ein Vektor kann in seine Komponenten zerlegt werden:
  • $A_x = A \cos \theta$
  • $A_y = A \sin \theta$
• Die Summe von Vektoren erfolgt durch Addition ihrer Komponenten:
  • $\overrightarrow{A} + \overrightarrow{B} = (A_x + B_x, A_y + B_y)$
• Das Skalarprodukt ergibt einen Skalar:
  • $\overrightarrow{A} \cdot \overrightarrow{B} = |\overrightarrow{A}| |\overrightarrow{B}| \cos \theta$
  • $\overrightarrow{A} \cdot \overrightarrow{B} = A_x B_x + A_y B_y$
• Das Vektorprodukt ergibt einen Vektor:
  • $\overrightarrow{A} \times \overrightarrow{B} = |\overrightarrow{A}| |\overrightarrow{B}| \sin \theta \hat{n}$
  • $\overrightarrow{A} \times \overrightarrow{B} = (A_y B_z - A_z B_y, A_z B_x - A_x B_z, A_x B_y - A_y B_x)$ wobei $\hat{n}$ der Normalenvektor ist.

Statistische Tests

Definition und Ziele

• Statistische Tests sind Verfahren der Inferenzstatistik zur Entscheidungsfindung über eine Population auf Basis von Stichprobendaten.
• Ziel ist die Validierung oder Ablehnung statistischer Hypothesen sowie die Unterstützung von Entscheidungsprozessen.

Allgemeine Vorgehensweise

1. Formulierung von Nullhypothese ($H_0$) und Alternativhypothese ($H_1$).
2. Wahl des statistischen Tests anhand der Art der Variablen, Anzahl der Stichproben und Verteilung der Daten.
3. Bestimmung des Ablehnungsbereichs basierend auf dem Signifikanzniveau $\alpha$.
4. Berechnung der Teststatistik aus den Stichprobendaten.
5. Entscheidung: Ablehnung von $H_0$ zugunsten von $H_1$, wenn die Teststatistik im Ablehnungsbereich liegt.

Fehlerrisiken

• Risiko 1. Art ($\alpha$): $H_0$ ablehnen, obwohl sie wahr ist (falsch-positiv).
• Risiko 2. Art ($\beta$): $H_0$ nicht ablehnen, obwohl sie falsch ist (falsch-negativ).

Beispiele für statistische Tests

• T-Test, ANOVA, Chi-Quadrat-Test, Wilcoxon-Mann-Whitney-Test, Kruskal-Wallis-Test, Pearson-Korrelation, Spearman-Korrelation, Fishers exakter Test, McNemar-Test.

Anmerkungen

• Der p-Wert ist die Wahrscheinlichkeit, bei Gültigkeit von $H_0$ eine mindestens so extreme Teststatistik zu erhalten wie die beobachtete. $H_0$ wird abgelehnt, wenn der p-Wert < $\alpha$ ist.
• Die Teststärke ist die Wahrscheinlichkeit, $H_0$ abzulehnen, wenn sie falsch ist (1 - $\beta$).
• Die Wahl des geeigneten Tests ist entscheidend.

Vektorräume

Definition

• Ein Vektorraum ist eine nichtleere Menge $V$ von Objekten, genannt Vektoren, auf der zwei Operationen definiert sind: Addition und Skalarmultiplikation, die zehn unten aufgeführten Axiome erfüllen.

Axiome

1. Die Summe von $\mathbf{u}$ und $\mathbf{v}$, bezeichnet mit $\mathbf{u} + \mathbf{v}$, liegt in $V$.
2. $\mathbf{u} + \mathbf{v} = \mathbf{v} + \mathbf{u}$
3. $(\mathbf{u} + \mathbf{v}) + \mathbf{w} = \mathbf{u} + (\mathbf{v} + \mathbf{w})$
4. Es gibt einen Nullvektor $\mathbf{0}$ in $V$, so dass $\mathbf{u} + \mathbf{0} = \mathbf{u}$
5. Für jedes $\mathbf{u}$ in $V$ gibt es einen Vektor $-\mathbf{u}$ in $V$, so dass $\mathbf{u} + (-\mathbf{u}) = \mathbf{0}$
6. Das Vielfache von $\mathbf{u}$ mit dem Skalar $c$, bezeichnet mit $c\mathbf{u}$, liegt in $V$.
7. $c(\mathbf{u} + \mathbf{v}) = c\mathbf{u} + c\mathbf{v}$
8. $(c + d)\mathbf{u} = c\mathbf{u} + d\mathbf{u}$
9. $c(d\mathbf{u}) = (cd)\mathbf{u}$
10. $1\mathbf{u} = \mathbf{u}$

Beispiele

• $\mathbb{R}^n$: Vektoren sind $n \times 1$ Matrizen.
• $\mathbb{R}$: Vektoren sind reelle Zahlen.
• $\mathbb{C}$: Vektoren sind komplexe Zahlen.
• $\mathbb{P}$: Vektoren sind Polynome.
• $M_{m \times n}$: Vektoren sind $m \times n$ Matrizen.
• Die Menge aller stetigen Funktionen, die auf der reellen Zahlengeraden definiert sind.

Unterräume

• Ein Unterraum eines Vektorraums $V$ ist eine Teilmenge $H$ von $V$, die die folgenden Eigenschaften hat:
  • Der Nullvektor $\mathbf{0}$ ist in $H$.
  • Für alle $\mathbf{u}$ und $\mathbf{v}$ in $H$ ist $\mathbf{u} + \mathbf{v}$ in $H$.
  • Für alle $\mathbf{u}$ in $H$ und jeden Skalar $c$ ist $c\mathbf{u}$ in $H$.

Beispiele

• $H = { \begin{bmatrix} x \ y \end{bmatrix} : x - 3y = 0 }$ ist ein Unterraum von $\mathbb{R}^2$, da $H = \text{Span} { \begin{bmatrix} 3 \ 1 \end{bmatrix} }$.
• $H = { \begin{bmatrix} x \ y \end{bmatrix} : x - 3y = 1 }$ ist kein Unterraum von $\mathbb{R}^2$, da $\mathbf{0} \notin H$.
• $H = { \begin{bmatrix} x \ y \end{bmatrix} : x \geq 0, y \geq 0 }$ ist kein Unterraum von $\mathbb{R}^2$, da $c\mathbf{u} \notin H$ für $c < 0$.
• $H = { \begin{bmatrix} x \ y \end{bmatrix} : x^2 + y^2 \leq 1 }$ ist kein Unterraum von $\mathbb{R}^2$, da $\mathbf{u} + \mathbf{v} \notin H$.

Taylors Theorem

Theorem

• Wenn $f: I \to \mathbb{R}$ ist $(n+1)$ mal differenzierbar auf dem Intervall $I$ und $a \in I$, dann gilt für $x \in I$: $$ f(x) = \underbrace{f(a) + f'(a)(x-a) + \frac{f''(a)}{2!}(x-a)^2 + \dots + \frac{f^{(n)}(a)}{n!}(x-a)^n}_{T_n(x)} + R_n(x) $$ wobei $T_n(x)$ das Taylor-Polynom vom Grad $n$ ist, zentriert bei $a$, und $R_n(x)$ das Restglied ist. $$ R_n(x) = \frac{f^{(n+1)}(c)}{(n+1)!}(x-a)^{n+1} $$ für ein $c$ zwischen $a$ und $x$.

Beispiele Taylorreihen

• $e^x = 1 + x + \frac{x^2}{2!} + \frac{x^3}{3!} + \dots = \sum_{n=0}^{\infty} \frac{x^n}{n!}$
• $\sin x = x - \frac{x^3}{3!} + \frac{x^5}{5!} - \dots = \sum_{n=0}^{\infty} (-1)^n \frac{x^{2n+1}}{(2n+1)!}$
• $\cos x = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} - \dots = \sum_{n=0}^{\infty} (-1)^n \frac{x^{2n}}{(2n)!}$
• $\ln(1+x) = x - \frac{x^2}{2} + \frac{x^3}{3} - \dots = \sum_{n=1}^{\infty} (-1)^{n+1} \frac{x^n}{n}$
• $(1+x)^{\alpha} = 1 + \alpha x + \frac{\alpha(\alpha-1)}{2!}x^2 + \dots = \sum_{n=0}^{\infty} \binom{\alpha}{n} x^n$, wobei $\binom{\alpha}{n} = \frac{\alpha(\alpha-1) \dots (\alpha-n+1)}{n!}$

Bernoullis Prinzip

• Besagt, dass eine Erhöhung der Geschwindigkeit eines Fluids gleichzeitig mit einer Abnahme des Drucks oder einer Abnahme der potentiellen Energie des Fluids einhergeht. $\bf{P + \frac{1}{2} \rho V^2 + \rho gh = constant}$
  • P ist der absolute Druck des Fluids
  • $\rho$ ist die Dichte des Fluids
  • V ist die Geschwindigkeit des Fluids
  • g ist die Erdbeschleunigung
  • h ist die Höhe

Anwendungen

• Flugzeuge: Die Form der Tragfläche ist so konstruiert, dass die Luft über der Oberseite der Tragfläche schneller strömt als unter der Unterseite, wodurch der Druck über der Fläche geringer ist als der darunter, was zu einer Auftriebskraft führt.
• Rennwagen: Spoiler erzeugen einen Bereich niedrigen Drucks über dem Auto, was dazu beiträgt, das Auto auf die Strecke zu saugen.
• Sprühflaschen: Durch das Zusammendrücken des Griffs wird Luft durch ein Rohr gezwungen, welche schnell über ein zweites, mit der Flüssigkeit verbundenes Rohr strömt. Die schnelle Luft erzeugt einen Bereich niedrigen Drucks, der die Flüssigkeit nach oben in den Luftstrom saugt, wo sie als Spray verteilt wird.