Vorlesung6
Aus ProgrammingWiki
Archivierte Version vom 2019-05-05T19:04:11+00:00. Aktuelle Version
Ü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 Czu beweisen ist:
\neg C \wedge B \Rightarrow \neg ABeweis:
| 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 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | gegeben durch Satz 1 |
| | 2 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 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 | 0 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 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 | ... |
| 1. Fall | 2. Fall |
|---|---|
| Es gibt eine exakte Lösung des Problems. | Es gibt keine exakte Lösung des Problems. |
| Anwendung eines Verfahrens/Algorithmus, welches das Optimalitätskriterium für ein bestimmtes Problem erfüllt. | Das Optimalitätskriterium wird nicht immer erfüllt. |
| Hier spricht man von einem Algorithmus. | Diese Verfahren können Heuristiken sein. |