Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » Aufgabe 1
Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.
Beide Seiten, vorherige ÜberarbeitungVorherige ÜberarbeitungNächste Überarbeitung | Vorherige ÜberarbeitungNächste ÜberarbeitungBeide Seiten, nächste Überarbeitung | ||
pruefungen:bachelor:thprog-ws15-braindump [15.02.2016 13:13] – Cerox | pruefungen:bachelor:thprog-ws15-braindump [12.02.2020 08:34] – vulgrim | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
Aufgabe 1 | Aufgabe 1 | ||
+ | (Warnung: Diese Aufgabe ist potentiell so nicht richtig) | ||
Wir definieren ein Termersetzungssystem über das aus zwei binären | Wir definieren ein Termersetzungssystem über das aus zwei binären | ||
Zeile 21: | Zeile 22: | ||
Man erinnere sich an folgende auf Church-Kodierung definierte Funktionen: | Man erinnere sich an folgende auf Church-Kodierung definierte Funktionen: | ||
+ | < | ||
• Church-Numerale | • Church-Numerale | ||
succ n = λ f a. f(n f a) | succ n = λ f a. f(n f a) | ||
Zeile 32: | Zeile 34: | ||
pair a b = λ select.select a b | pair a b = λ select.select a b | ||
f st p = p(λxy.x) | f st p = p(λxy.x) | ||
- | snd p = p(λxy.y) | + | snd p = p(λxy.y)</ |
Man erinnere sich ferner, dass die Zahl n durch den λ-Term n = λ f a. f | Man erinnere sich ferner, dass die Zahl n durch den λ-Term n = λ f a. f | ||
n | n | ||
Zeile 67: | Zeile 69: | ||
length(Nil) = 0 | length(Nil) = 0 | ||
+ | |||
length(Cons x xs) = 1 + length(xs) | length(Cons x xs) = 1 + length(xs) | ||
Nil ⊕ ys = ys | Nil ⊕ ys = ys | ||
+ | |||
( Cons x xs ) ⊕ ys = Cons x ( xs ⊕ ys ) | ( Cons x xs ) ⊕ ys = Cons x ( xs ⊕ ys ) | ||
cMap f Nil = Nil | cMap f Nil = Nil | ||
+ | |||
cMap f ( Cons x xs ) = Cons ( f x ) ( cMap f xs ) | cMap f ( Cons x xs ) = Cons ( f x ) ( cMap f xs ) | ||
+ | |||
Beweisen Sie mittels struktureller Induktion, dass | Beweisen Sie mittels struktureller Induktion, dass | ||
Zeile 86: | Zeile 92: | ||
Alternierender Signalwert zwischen x und y | Alternierender Signalwert zwischen x und y | ||
+ | < | ||
codata Signal where | codata Signal where | ||
cur : Signal −> Boolean | cur : Signal −> Boolean | ||
next : Signal −> Signal | next : Signal −> Signal | ||
+ | </ | ||
Dann konstruiert die wie folgt korekursiv definierte Funktion square | Dann konstruiert die wie folgt korekursiv definierte Funktion square | ||
aus ihren Argumenten x,y ein zw. x und y alternierendes Signal: | aus ihren Argumenten x,y ein zw. x und y alternierendes Signal: | ||
- | cur ( square x y ) = ... | + | < |
- | next ( square x y ) = ... | + | next ( square x y ) = square y x |
+ | </ | ||
1. Definieren Sie korrekursiv eine Fuktion alt: Signal -> Signal, so | 1. Definieren Sie korrekursiv eine Fuktion alt: Signal -> Signal, so | ||
dass alt s den jeweils gesetzten Wert für ein gesetztes Bit ausgibt ( Ist x gesetzt, gebe x aus. Sind beide Werte gesetzt, nichts) | dass alt s den jeweils gesetzten Wert für ein gesetztes Bit ausgibt ( Ist x gesetzt, gebe x aus. Sind beide Werte gesetzt, nichts) | ||
Zeile 111: | Zeile 120: | ||
erläutern Sie, warum dieser L definiert. Andernfalls zeigen Sie mittels des | erläutern Sie, warum dieser L definiert. Andernfalls zeigen Sie mittels des | ||
Pumping-Lemma, | Pumping-Lemma, | ||
+ | |||
+ | Das darf gerne noch jemand in ,tex übertragen, | ||
+ | by Cerox |