BuK/IIm11/Studenten/simawiel/ue2

Wiki-Quelltext dieser Seite.

== Aufgabe 1 ==
Beispiele für nicht effizient lösbare Probleme:
Springer-Problem, Golomb-Lineal, JSSP, n-Damen, TSP, ...
----
== Aufgabe 2 ==
Es ist zu zeigen, dass die folgenden Mengen abzählbar unendlich sind: $\Z, \Q,$ die Menge der Primzahlen, die geraden Zahlen
=== Zu $\Z$ ===
Einige Zahlen aus $\Z$ sind folgend dargestellt:

$\ldots -5, -4, -3, -2, -1, 0, 1, 2, 3, 4, 5, \ldots$

z.z.: $\Z$ ist abzählbar unendlich.

Um Zahlen der Menge $\Z$ abzählen zu können, muss man sie so darstellen, dass es ein erstes Element gibt, bei dem die Zählung beginnt. Man benötigt dafür eine Funktion $f(x) : \Z \mapsto \N$ , die jede ganze Zahl auf eine natürliche abbildet.

<math>\begin{tabular}{l l l l l l l l l l}
  $\N$ & 1 & 2 & 3 & 4 & 5 & 6 &7 & 8 & 9 \\
  $\Z$ & 0 & -1 & 1 & -2 & 2 & -3 & 3 & -4 & 4\\
\end{tabular}</math>

Dadurch erhält jede ganze Zahl aus $\Z$ eine eindeutige Position in dieser Darstellung, somit ist jede Zahl aus $\Z$ bzw. $\Z$ selbst abzählbar unendlich. $\Box$
=== Zu $\Q$ ===
z.z.: $\Q$ ist abzählbar unendlich.

Um dies zu zeigen wird das <math>\textsc{Cantorsche}</math> Diagonalisierungsverfahren 1. Art verwendet.

Eine Eigenschaft rationaler Zahlen ist, dass sie als Bruch dargestellt werden können. In der nachfolgenden Tabelle sind die rationalen Zahlen durch Nenner (N) und Zähler (Z) eingetragen.

<math>
\begin{tabular}{l | l l l l l l l l l l}
  Z / N & 1 & & 2 & & 3 & & 4 & & \ldots\\
  \hline
  \tabularnewline
  1 & $\frac{1}{1}$ & $\rightarrow$ & $\frac{1}{2}$ & & $\frac{1}{3}$ & $\rightarrow$ & $\frac{1}{4}$ & & \ldots\\
    & & $\swarrow$ & & $\nearrow$ & & $\swarrow$ &\\
  2 & $\frac{2}{1}$ & & $\frac{2}{2}$ & & $\frac{2}{3}$ & & $\frac{2}{4}$ & & \ldots\\
    & $\downarrow$ & $\nearrow$ & & $\swarrow$ & & \\
  3 & $\frac{3}{1}$ & & $\frac{3}{2}$ & & $\frac{3}{3}$ & & $\frac{3}{4}$ & & \ldots\\
    & & $\swarrow$ & & & & & &\\
  4 & $\frac{4}{1}$ & & $\frac{4}{2}$ & & $\frac{4}{3}$ & & $\frac{4}{5}$ & & \ldots\\
  \tabularnewline
  \vdots & \vdots & & \vdots & & \vdots & & \vdots & &\\
\end{tabular}
</math>

Entsprechend der Richtung der eingezeichneten Pfeile können die darin dargestellten Zahlen aus $\Q$ gezählt werden. Somit ist $\Q$ abzählbar unendlich. $\Box$

=== Zur Menge der Primzahlen ===
z.z.: Die Menge der Primzahlen ($P$) ist abzählbar unendlich.

Es gilt $P \subset \N$