BuK/IIm18/Vorlesung6

Wiki-Quelltext dieser Seite.

== Übungsaufgabe 1 ==
Eine TM soll überprüfen ob $w$ die Form $uu$ besitzt. Für $u$ gilt $a^ib^ic^i$, bei Korrektheit von w soll u auf dem Band hinterlassen werden.

== Übungsaufgabe 2 ==
Beweisen sie mittels Aussagenlogik $A \wedge B \rightarrow C \Leftrightarrow \neg C \wedge B \rightarrow \neg A$.

Der Beweis kann in Form einer Wahrheitstabelle erbracht werden. Dabei werden die folgenden Variabeln genutzt:

$A: P'$  ist entscheidbar

$B: P$  ist reduzierbar auf $P'$

$C: P$  ist entscheidbar


Als gegeben kann dabei nach Satz 1 betrachtet werden dass:

$A \wedge B \Rightarrow C$

zu beweisen ist:

$\neg C \wedge B \Rightarrow \neg A$


Beweis:

{| border="1" cellpadding="5" cellspacing="0"
!$Zeile$
!$A$
!$B$
!$C$
!$E=A \wedge B$
!$F=E\Rightarrow C$
!$G=\neg C \wedge B$
!$H = G \Rightarrow \neg A$
!$I = F \Leftrightarrow H$
!$Kommentar$
|-
|| 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 ||style="background-color:#fedcba" | 0 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | gegeben durch Satz 1
|-
|| 2 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 0 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 0 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | 0 || style="background-color:#fedcba" | 1 || style="background-color:#fedcba" | falsch nach Satz 1
|-
|| 3 ||1 || 0 || 1 || 0 || 1 || 0 || 1 || 1 || ...
|-
|| 4 ||1 || 0 || 0 || 0 || 1 || 0 || 1 || 1 || ...
|-
|| 5 ||0 || 1 || 1 || 0 || 1 || 0 || 1 || 1 || ...
|-
|| 6 || style="background-color:#9FF781" | 0 || style="background-color:#9FF781" | 1 || style="background-color:#9FF781" | 0 || style="background-color:#9FF781" | 0 || style="background-color:#9FF781" | 1 || style="background-color:#9FF781" | 1 || style="background-color:#9FF781" | 1 || style="background-color:#9FF781" | 1 || style="background-color:#9FF781" | Einzig verbleibende Möglichkeit für $\neg C \wedge B$
|-
|| 7 ||0 || 0 || 1 || 0 || 1 || 0 || 1 || 1 || ...
|-
|| 8 ||0 || 0 || 0 || 0 || 1 || 0 || 1 || 1 || ...

|-

|}

<table border=1>
    <tr>
        <th width=50%>1. Fall</th>
        <th width=50%>2. Fall</th>
    </tr>
    <tr>
        <td>Es gibt eine exakte Lösung des Problems.</td>
        <td>Es gibt keine exakte Lösung des Problems.</td>
    </tr>
    <tr>
        <td>Anwendung eines Verfahrens/Algorithmus, welches das Optimalitätskriterium für ein bestimmtes Problem erfüllt.</td>
        <td>Das Optimalitätskriterium wird nicht immer erfüllt.</td>
    </tr>
    <tr>
        <td>Hier spricht man von einem <b>Algorithmus</b>.</td>
        <td>Diese Verfahren können <b>Heuristiken</b> sein.</td>
    </tr>
<tr>
        <td>Hier spricht man von einem <b>Algorithmus</b>.</td>
        <td>Diese Verfahren können <b>Heuristiken</b> sein.</td>
    </tr>
<tr>
        <td>Hier spricht man von einem <b>Algorithmus</b>.</td>
        <td>Diese Verfahren können <b>Heuristiken</b> sein.</td>
    </tr>
<tr>
        <td>Hier spricht man von einem <b>Algorithmus</b>.</td>
        <td>Diese Verfahren können <b>Heuristiken</b> sein.</td>
    </tr>
<tr>
        <td>Hier spricht man von einem <b>Algorithmus</b>.</td>
        <td>Diese Verfahren können <b>Heuristiken</b> sein.</td>
    </tr>

</table>