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.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
Nächste Überarbeitung		Vorherige Überarbeitung
Nächste ÜberarbeitungBeide Seiten, nächste Überarbeitung
pruefungen:bachelor:thprog-ws15-braindump [15.02.2016 13:21] – Ceroxpruefungen:bachelor:thprog-ws15-braindump [12.02.2020 09:00] – 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 18: Zeile 20:
  
  
-Aufgabe 2+====== Aufgabe 2 ====== 
  
 Man erinnere sich an folgende auf Church-Kodierung definierte Funktionen: Man erinnere sich an folgende auf Church-Kodierung definierte Funktionen:
 +<code>
 • Church-Numerale • Church-Numerale
 succ n = λ f a. f(n f a) succ n = λ f a. f(n f a)
Zeile 32: Zeile 36:
 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)</code>
 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 60: Zeile 64:
 Nicht bekannt... Nicht bekannt...
  
-Aufgabe 3+====== Aufgabe 3 ====== 
  
 Wir erinnern an den Datentyp der Listen und einige hierauf rekursiv Wir erinnern an den Datentyp der Listen und einige hierauf rekursiv
Zeile 67: Zeile 72:
  
 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 83: Zeile 92:
 erläutern Sie alle Schritte des Beweises. erläutern Sie alle Schritte des Beweises.
  
-Aufgabe 4+====== Aufgabe 4 ====== 
  
 Alternierender Signalwert zwischen x und y Alternierender Signalwert zwischen x und y
 +<code>
 codata Signal where codata Signal where
 cur : Signal −> Boolean cur : Signal −> Boolean
 next : Signal −> Signal next : Signal −> Signal
 +</code>
 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 ) = ... +<code>cur ( square x y ) = x 
-next ( square x y ) = ...+next ( square x y ) = square y x 
 +</code>
 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 104: Zeile 117:
 ... ...
  
-Aufgabe 5+====== Aufgabe 5 ====== 
  
 Sei L die Sprache über Σ = {a, b, c}*, die gerade aus allen Worten über Σ Sei L die Sprache über Σ = {a, b, c}*, die gerade aus allen Worten über Σ