BuK/IIm14/Studenten/s3mamich
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Java</language>
== Übungsaufgaben ==
====Vollständige Induktion - Seite 14====
'''Mathematische Beweismethode''', nach der eine Aussage für alle natürlichen Zahlen bewiesen wird. Da es sich um unendlich viele Zahlen handelt, kann ein Beweis nicht für alle Einzelfälle durchgeführt werden.
Er wird daher in zwei Etappen durchgeführt: als '''Induktionsanfang''' für eine kleinste Zahl, für die man die Aussage zeigen will, (meist 1 oder 0) und als '''Induktionsschritt''', der aus der Aussage für eine variable Zahl die entsprechende Aussage für '''die nächste Zahl''' logisch ableitet.
Beweisverfahren:
'''Induktionsanfang (IA)''' z.z.: Es gilt $A(0)$.
'''Induktionsschritt (IS)''' z.z.: Wenn $A(i)$ gilt '''(Induktionsvoraussetzung, IV)''' , dann gilt auch $A(i+1)$ '''(Induktionsbehauptung, IB)'''
====Übungsaufgabe 1.3 - Seite 15====
Beweisen Sie die folgenden Beziehungen für Fibonacci-Zahlen mittels vollständiger Induktion für $ n \in \N$ und $n \geq 1$
====Erste Beziehung für Fibonacci-Zahlen====
$$ \sum\limits_{k=1}^{n} F_{k} = F_{n+2} - 1$$
''' Fibonacci-Zahlenfolge:
$F_{1}$ = 1, $F_{2}$ = 1, $F_{3}$ = 2
''' Induktionsanfang (IA):
z.z. Für $n = 1$ ergibt sich für die linke Seite und rechte Seite:
$F_{k}$ = $F_{n+2} - 1$
$F_{1}$ = $F_{1+2}-1$
$F_{1}$ = $F_{3}-1$
$1 = 2-1$
$1 = 1$ $\Rightarrow$ OK
''' Induktionsschritt (IS):
Wenn $ \sum\limits_{k=1}^{i} F_{k} = F_{i+2} - 1$ (Induktionsvoraussetzung, '''IV'''), dann gilt auch: $ \sum\limits_{k=1}^{i+1} F_{k} = F_{i+3} - 1$ (Induktionsbehauptung, '''IB''').
$ \sum\limits_{k=1}^{i+1} F_{k} = \sum\limits_{k=1}^{i} F_{k} + F_{i+1}$ $\quad \stackrel{IV}{=}$ $ F_{i+2} -1 + F_{i+1}$ $ = F_{i+3} - 1$ (Ergebnis = IB)
<div align="right">$\square $</div>
====Zweite Beziehung für Fibonacci-Zahlen====
$$ \sum\limits_{k=1}^{n} F_{2k} = F_{2n+1} - 1$$
''' Fibonacci-Zahlenfolge:
$F_{1}$ = 1, $F_{2}$ = 1, $F_{3}$ = 2
''' Induktionsanfang (IA):
z.z. Für $n = 1$ ergibt sich für die linke Seite und rechte Seite:
$ F_{2k} = F_{2n+1} - 1$
$ F_2 = F_{2*1+1} - 1$
$ F_2 = F_{3} - 1$
$ 1 = 2 - 1 $
$ 1 = 1 \Rightarrow OK $
''' Induktionsschritt (IS):
Wenn $ \sum\limits_{k=1}^{i} F_{2k} = F_{2i+1} - 1$ (Induktionsvoraussetzung, '''IV'''), dann gilt auch $ \sum\limits_{k=1}^{i+1} F_{2k} = F_{2(i+1)+1} - 1 = F_{2i+3} -1$ (Induktionsbehauptung, '''IB''').
$ \sum\limits_{k=1}^{i+1} F_{2k} = \sum\limits_{k=1}^{i} F_{2k} + F_{2(i+1)} \quad \stackrel{IV}{=} \quad F_{2i+1} - 1 + F_{2i+2} \quad = \quad F_{2i+3} - 1 $ (Ergebnis = IB)
<div align="right">$\square $</div>
====Dritte Beziehung für Fibonacci-Zahlen====
$$ \sum\limits_{k=1}^{n} F_{2k-1} = F_{2n}$$
''' Fibonacci-Zahlenfolge:
$F_{1}$ = 1, $F_{2}$ = 1, $F_{3}$ = 2
''' Induktionsanfang (IA):
z.z. Für $n = 1$ ergibt sich für die linke Seite und rechte Seite:
$ \sum\limits_{k=1}^{1} F_{2k-1} = F_{2}$
$ 1 = 1 \Rightarrow OK$
''' Induktionsschritt (IS):
Wenn $\sum\limits_{k=1}^{n} F_{2k-1} = F_{2n}$ '''(Induktionsvoraussetzung, IV)''', dann gilt auch $\sum\limits_{k=1}^{n+1} F_{2k-1} = F_{2(n+1)} = F_{2n+2}$ '''(Induktionsbehauptung, IB)'''
$ \sum\limits_{k=1}^{n+1} F_{2k-1} = \sum\limits_{k=1}^{i} F_{2k-1} + F_{2(i+1)-1} \quad \stackrel{IV}{=} \quad F_{2i} + F_{2(i+1)-1} \quad = \quad F_{2i} + F_{2i+2-1} \quad = \quad F_{2i} + F_{2i+1} \quad = \quad F_{2i+2}$ (Ergebnis = IB)
<div align="right">$\square$</div>
----
====Übungsaufgabe 1.4 - Seite 16====
'''Wiederholen Sie die Eigenschaften von Äquivalenzrelationen und geben Sie ein Beispiel an.'''
* Reflexivität: $a\sim a$
Jedes Objekt ist zu sich selbst äquivalent.
*Symmetrie: $a\sim b \ \Rightarrow\ b\sim a$
Wenn $a$ zu $b$ äquivalent ist, dann ist auch $b$ äquivalent zu $a$ (und umgekehrt).
*Transitivität: $a\sim b\ \mathrm{und}\ b\sim c\ \Rightarrow\ a\sim c$
Wenn $a$ zu $b$ äquivalent und $b$ zu $c$ äquivalent ist, dann ist $a$ äquivalent zu $c$.
'''Beispiel:'''
TODO
----
====Übungsaufgabe 1.5 - Seite 17====
'''Schreiben Sie ein Programm, das q berechnet.'''
Die im Folg. definierte Funktion $q : \R \mapsto \R$ ist an der Stelle $x=3$ undefiniert. Hierfür verwenden wir das Symbol $\bot$.
$$q(x)=\begin{cases}
\dfrac{35}{x-3}, & \text{wenn }x \neq 3\text{;}\\
\bot, & \text{sonst.}
\end{cases}
$$
<code id="552ea4ca18eb8">public double q(x){
if(x=3){
while(true){<run id="552ea484e355a"></run>
}
}else{
double result = 35/(x-3);
}
return result;
}</code>
<run id="552eabb7d6af4">q(2);</run>
----
====Übungsaufgabe 1.6 - Seite 17====
'''Geben Sie sich einige Definitionsbeispiele selbstgewählter Funktionen vor. Achten Sie darauf, dass es sich auch um (echte) partielle Funktionen handeln kann. Außerdem sollten Sie einige abschnittsweise definierte Funktionen, z.B. Briefporto, Zuzahlungen für Medikamente usw., aufnehmen.'''
Funktion für die Berechnung des Portos von Briefen anhand des Gewichts $x$ in Gramm:
$$p(x)=\begin{cases}
0.62 , & \text{wenn }0 < x \leq 20 \text{;}\\
0.85 , & \text{wenn }20 < x \leq 50 \text{;}\\
1.45 , & \text{wenn }50 < x \leq 500 \text{;}\\
2.40 , & \text{sonst.}
\end{cases}
$$
----
====Übungsaufgabe 1.7 - Seite 17====
'''Wiederholen Sie die folgenden Eigenschaften von Funktionen: injektiv, surjektiv und bijektiv. Geben Sie aussagekräftige Beispiele an. Skizzieren Sie folgende Funktionen mittels Abbildungspfeilen aus X in Y : injektiv und surjektiv; injektiv, nicht surjektiv; nicht injektiv, surjektiv; nicht injektiv, nicht surjektiv.'''
{| border="1" cellpadding="5" cellspacing="0"
!Eigenschaft
!Beschreibung
!Beispiele
|-
||injektiv || Jedes Element aus Y hat höchstens einen Partner in X || $ \N \Rightarrow \N, x \rightarrow x^2 $
|-
||surjektiv || Jedes Element aus Y hat mindestens einen Partner in X || $ \R \Rightarrow \R_{+}, x \rightarrow x^2 $
|-
||bijektiv || Jedes Element aus Y hat genau einen Partner in X (muss injektiv und surjektiv sein) || $ \R_{+} \Rightarrow \R_{+}, x \rightarrow x^2 $
|-
|}
<br>
{| border="1" cellpadding="5" cellspacing="0"
!Funktion $X \Rightarrow Y$
!Darstellung
|-
||injektiv,surjektiv ||[[Bild:Stefanscheumann_Injektivsurjektiv.jpg|250px]]
|-
||injektiv,nicht surjektiv || [[Bild:Sirorose_Injektivnichtsurjektiv.jpg|250px]]
|-
||nicht injektiv,surjektiv || [[Bild:Stefanscheumann_Nichtinjetktivsurjektiv.jpg|250px]]
|-
||nicht injektiv,nicht surjektiv ||[[Bild:Stefanscheumann_Nichtinjektivnichtsurjektiv.jpg|250px]]
|-
|}
----
====Übungsaufgabe Folie 22/25====
'''Zeigen Sie, dass die Menge $\Z$ eine abzählbar unendliche Menge ist und setzen Sie sich mit der Aussage auseinander, wonach doch $\Z$ eigentlich doppelt so viele Elemente besitzt, wie $\N$.'''
Eine abzählbar unendliche Menge ist dadurch definiert, dass sie die selbe Mächtigkeit wie die Menge der natürlichen Zahlen hat. Man kann also jedes Element der Menge auf ein Element der natürlichen Zahlen bijektiv abbilden. Man definiert $f : \Z \to \N$:
$$f(z)=\begin{cases}
−(2z+1), & \text{wenn }z < 0 \text{;}\\
2z, & \text{wenn } z \geq 0
\end{cases}
$$
----
====Übungsaufgabe 1.8 - Seite 20====
'''Entwerfen Sie ein Aufbauschema zur systematischen Erzeugung aller Elemente aus ℘(M) für eine gegebene endliche Menge M und wenden Sie es auf einige selbstgewählte Beispiele an.'''
# Leere Menge aufnehmen
# Nimm ein Element aus der Menge und füge es jedem Element der vorher gebildeten Menge Hinzu und übernimm die vorher gebildetetn Elemente
''' Beispiel '''
für $ \wp(\{x,y,z\}) $
$ \wp(\{\})=\{\{\emptyset\}\} $<br />
$ \wp(\{x\})=\{\{\emptyset\},\{x\}\} $<br />
$ \wp(\{x,y\})=\{\{\emptyset\},\{x\},\{y\},\{x,y\}\} $<br />
$ \wp(\{x,y,z\})=\{\{\emptyset\},\{x\},\{y\},\{z\},\{x,y\},\{x,z\},\{y,z\},\{x,y,z\}\} $<br />
== Übungsaufgaben 2te Präsentation ==
=== Turing-Maschine als Akzeptator ===
Geben Sie Trichterbilder für den Einsatz einer TM als Akzeptator an:
* für semi-entscheidbare Sprachen:
[[Bild:Maria Michel-Suarez Semi entscheidbar2.png|250px]]
* für entscheidbare Sprachen:
[[Bild:Maria Michel-Suarez Entscheidbar.png|250px]]
=== Turing-Aufzählbarkeit, Turing-Entscheidbarkeit ===
Definieren Sie die Begriffe Turing-aufzählbar und Turing-entscheidbar analog zur Turing-Berechenbarkeit.
Sei A ein Alphabet, $M \subseteq A^*$.
* M heißt Turing-entscheidbar, wenn die charakteristische Funktion $\chi_M$
$$ \chi_M(w) = \begin{cases}
wahr, & \text{wenn} w \in M;\\
falsch, & \text{wenn} w \in A^* \setminus \{M\};\\
\end{cases}
$$
Turing-berechenbar ist.
* M heißt Turing-aufzählbar, wenn es eine Funktion $f: \N \rightarrow M$ gibt, die surjektiv und Turing-berechenbar ist.
Eine Funktion $f: A^* \rightarrow A^*$ heißt Turing-berechenbar, wenn es eine Turing Maschine M gibt, so dass für alle \[ w, y \in A^*\] gilt: $f (w) = y$ genau dann, wenn das Eingabewort vom Anfangszustand, nach beliebige viele Schritte stoppt in einem Endzustand mit einer Final Konfiguration.
=== Unentscheidbarkeitsbeweis ===
Zeigen Sie die Unentscheidbarkeit (Semi-Entscheidbarkeit) von \[ L_{\Sigma^{*}}:=\{\left\langle M \right\rangle | L(M) = \Sigma^{*} \} \] durch Reduktion der Sprache LΣ^* auf das Halteproblem.
Schreibe für alle Eingabewörter aus $\Sigma^{*}$ die Kodierung der Maschine M, also <M>, sowie w $\in$ $\Sigma^{*}$ auf das Band einer Maschine $M_2$. Die Maschine $M_2$ ist so konstruiert, dass sie aus ihrer Eingabe <M> und w die Kodierung einer Maschine M', d.h. <M'>, mit einem Eingabewort $y$ auf ihr Band als Ausgabe schreibt.
Die Besonderheit von M' ist, dass diese Maschine mit dem Eingabewort $y$ stoppt, wenn M(w) stoppen würde. Dabei ist $y$ nur ein Platzhalter, denn $y$ hat auf die Terminierung von M' keinen Einfluss. Als nächstes wird <M'> und $y$ auf das Band einer UTM $M_1$ geschrieben. $M_1$ führt die Kodierung der Maschine M' mit dem Wort $y$ aus. Dabei verwirft die Maschine M' als erstes ihr Eingabewort $y$, so dass ihr Band leer ist. Wenn die durch $M_1$ ausgeführte Maschine M' mit ihrem leeren Band hält, so heißt das, dass auch die Maschine M mit dem Wort w akzeptieren würde. Wenn die durch die Maschine $M_1$ ausgeführte Maschine M' auf dem anfangs leeren Band nicht in einem Endzustand hält, dann stoppt auch die Maschine M mit dem Wort w nicht in einem Endzustand. <M> ist $\in$ $L_{\Sigma^{*}}$ genau dann, wenn M' termiert.
Da das Halteproblem jedoch nicht lösbar ist, ist auch $L_{\Sigma^{*}}$ unentscheidbar.
[[Bild:Maria Michel-Suarez Unentscheidbar.png]]
Das Halteproblem ist das Problem bei einer gegebenen Programm und einer Eingaben entscheiden zu können, ob das Programm mit dieser Eingabe hält oder nicht, also entscheidet ob ein Problem hält oder nicht. In der theoretische Informatik, ob es möglich algorithmisch festzustellen, ob ein Programm bei einer Eingabe endet oder nicht, also hält.
Das Halteproblem ist nicht entscheidbar.
=== Zusammenhang der Begriffe===
[[Bild:Maria Michel-Suarez Berechenbarkeit.png|800px]]
===Funktionsklassen ===
* Vorlesung 9, Folie 46/46
[[Bild:Maria Michel-Suarez Funktionsklassen1.png|400px]]
* Vorlesung 11, Folie 22/39
[[Bild:Maria Michel-Suarez Funktionsklassen2.png|400px]]
* Kreativität
[[Bild:Maria Michel-Suarez Funktionsklassen3.png|500px]]