BuK/IIm14/Studenten/s3mamich

Wiki-Quelltext dieser Seite.

<language>Java</language>
== Übungsaufgaben ==

====Vollständige Induktion - Seite 14====

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====

$$ \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>


=== Aufgabe 2 ===

$$ \sum\limits_{k=1}^{n} F_{2k} =  F_{2n+1} - 1$$

IA: 

Für $n = 1$ ergibt sich:

$ F_2 =  F_{2*1+1} - 1$

$ F_2 =  F_{3} - 1$

$ 1 =  2 - 1 $

$ 1 = 1 \Rightarrow OK $

IS:

Wenn $ \sum\limits_{k=1}^{i} F_{2k} =  F_{2i+1} - 1$ (IV), dann gilt auch:

$ \sum\limits_{k=1}^{i+1} F_{2k} =  F_{2(i+1)+1} - 1 =  F_{2i+3} -1$ (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_{2n+3} - 1 $

<div align="right">$\square $</div>

=== Aufgabe 3 ===

$$ \sum\limits_{k=1}^{n} F_{2k-1} =  F_{2n}$$

Wenn $\sum\limits_{k=1}^{n} F_{2k-1} =  F_{2n}$,

dann gilt auch $\sum\limits_{k=1}^{n+1} F_{2k-1} =  F_{2n+2}$

Für $ n = 1$:

$ \sum\limits_{k=1}^{1} F_{2k-1} =  F_{2}$

$ 1 = 1 \Rightarrow OK$

IS:

$ \sum\limits_{k=1}^{n+1} F_{2k-1} = \sum\limits_{k=1}^{n} F_{2k-1} + F_{2(n+1)-1}$

$ \Rightarrow F_{2n} + F_{2n+1}$

$ \Rightarrow F_{2n+2}$

<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 />