BuK/IIm14/Studenten/s3ankrau1

Wiki-Quelltext dieser Seite.

<language>Scheme</language>
==Übungsaufgaben==

===Vorlesung 1===

'''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:'''
Ein Beispiel aus der Landwirtschaft soll die eingeführten Begriffe verdeutlichen. Betrachtet sei eine Menge $M$ von Nutztieren in einem landwirtschaftlichen Betrieb. Wir definieren die folgende zweistellige Relation $\sim$ auf $M$:

Für je zwei Nutztiere $x$ und $y$ aus $M$ soll $x\sim y$ genau dann gelten, wenn $x$ und $y$ Tiere derselben Art sind.
Für die Kuh $K$ und den Ochsen $O$ gilt $K\sim O$. Für das Huhn $H$ gilt aber nicht $H\sim K$. Die Relation $\sim$ erfüllt die drei Forderungen für Äquivalenzrelationen:

* Reflexivität
Jedes Tier ist von derselben Art wie es selbst.

*Symmetrie
Ist ein Tier von derselben Art wie ein zweites, dann ist das zweite auch von derselben Art wie das erste.

*Transitivität
Wenn $K$ und $O$ Tiere derselben Art sind und ebenso $O$ und $L$ von derselben Art sind, dann sind auch $K$ und $L$ von derselben Art (nämlich von der Art, zu der dann jedes der drei Tiere gehört).


----


'''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="552a585b6f006">
(define function
 (lambda()
  (function)))

(define f
 (lambda(x)
  (if (= x 3)
   (function)
   (/ 35 (- x 3)))))
</code>

<run id="552a585b6f006">(f 5)</run>


----


'''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}
$$


----


'''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]] 
|-
|}


----


'''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 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}
$$

<code id="552a60656d8aa">
(define zn
 (lambda(z)
  (if (z<0)
   (- (* -2 z) 1)
   (* 2 z))))
</code>
<run id="552a60656d93d">(zn 6)</run>

----

'''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(\{a,b,c\}) $


$ \wp(\{\})=\{\{\emptyset\}\} $<br />
$   \wp(\{c\})=\{\{\emptyset\},\{c\}\} $<br />
$   \wp(\{b,c\})=\{\{\emptyset\},\{c\},\{b\},\{b,c\}\} $<br />
$   \wp(\{a,b,c\})=\{\{\emptyset\},\{c\},\{b\},\{b,c\},\{a\},\{a,b\},\{a,c\},\{a,b,c\}\} $<br />

<language>Scheme</language>
<language>Scheme</language>
===Vorlesung 2===

'''Kommentieren Sie. Nennen Sie Beispiele.'''
*Unzugängliches (wenigstens) für Computer
**Keine Beschreibungssprache vorhanden, daher nicht formalisierbar/maschinell beschreibbar
**Probleme zu vielschichtig und mit mehreren abhängigen Parametern
**Beispiel: "Wird es morgen regnen?", "Wer gewinnt das WM-Finale?"

*Praktisch Unmögliches
**Problem zwar maschinell beschreibbar, doch kann es aufgrund von Ressourcen-Problemen praktisch nicht gelöst werden
**Beispiele sind das n-Damen-Problem oder TSM für sehr große Probleminstanzen


----


'''Warum ist es so schwierig ein leistungsfähiges Schachprogramm zu entwerfen?'''


----


'''Zeigen Sie, dass die folgenden Mengen abzählbar unendlich sind: $\Z$, $\Q$, die Menge der Primzahlen, die geraden Zahlen.'''

*Für $\Z$: 

{| border="1" cellpadding="5" cellspacing="0"
|-
|| 0 || 1 || 2 || 3 || 4 || 5 || ...
|-
|| 0 || 1 || -1 || 2 || -2 || 3 || ...
|-
|}

$$f(z)=\begin{cases}
  −(2z+1),  & \text{wenn }z < 0 \text{;}\\
  2z, & \text{wenn } z \geq 0
\end{cases}
$$

*Für $\Q$:

$\Q=\{\frac{a}{b} | a \in \Z, b\in \N\}$

Beweis mit Cantors erstem Diagonalargument:

{| border="1" cellpadding="5" cellspacing="0"
!$b$\$a$
!$0$
!$1$
!$-1$
!$2$
!$-2$
!...
|-
|| 1 || 0 || 1 || -1 || 2 || -2 || ...
|-
|| 2 || 0 || 1/2 || -1/2 || 2/2 || -2/2 || ...
|-
|| 3 || 0 || 1/3 || -1/3 || 2/3 || -2/3 || ...
|-
|| 4|| 0 || 1/4 || -1/4 || 2/4 || -2/4 || ...
|-
|| 5 || 0 || 1/5 || -1/5 || 2/5 || -2/5 || ...
|-
|| ... || ... || ... || ... || ... || ... || ...
|-
|}


*Für Primzahlen:
** Nach dem Satz von Euklid unendlich
** Als Teilmenge der natürlichen Zahlen auch abzählbar, es gilt $P \subset \N$

*Gerade Zahlen:
** Als Teilmenge der natürlichen Zahlen abzählbar unendlich, es gilt $G \subset \Z$


----


'''Beweisen Sie den folgenden Satz: Wenn M1,M2,M3,... abzählbare Mengen sind, dann ist auch die Menge $\bigcup_{n=1}^\infty {M_{n}}$ abzählbar.'''

'''Verifizieren Sie, dass die folgende Funktion $f : \N+ \to \Q+$ eine bijektive Funktion ist und implementieren Sie eine Prozedur, die die zugehörige Umkehrfunktion $f^{-1}$ berechnet.'''

$$f(n) = \begin{cases}
1, & \text{wenn } n=1;\\
f(\frac{n}{2})+1, & \text{wenn } n \text{ gerade};\\
\frac{1}{f(n-1)}, & \text{wenn } n \text{ ungerade}.
\end{cases}$$

Umkehrfunktion:

$$ f^{-1}(n) = \begin{cases}1, & n = 1 \\ f^{-1}(n-1) * 2, & n > 1 \\ f^{-1}(\frac{1}{n}) + 1, & sonst\end{cases} $$

*(1)
<code>
(define f
  (lambda(n)
    (if(= n 1)
       1
       (if (= (modulo n 2) 0)
           (+ (f(/ n 2)) 1)
           (/ 1 (f(- n 1)))))))
</code>

<run></run>

'''Zeigen Sie, dass die Menge der reellen Zahlen überabzählbar unendlich ist.'''

==Kreativaufgaben==