Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Prüfungen im Bachelor-Studium (1. - 5. Semester) » Aufgabe 1   (Übersicht)

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
pruefungen:bachelor:thprog-ws15-braindump [15.02.2016 13:08] Ceroxpruefungen:bachelor:thprog-ws15-braindump [12.02.2020 09:05] (aktuell) 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:
-curren tSample ( square x y ) = x +<code>cur ( square x y ) = x 
-discardSample ( square x y ) = square y x +next ( square x y ) = square y x 
-1. Definieren Sie korrekursiv eine Fuktion invert: Signal -> Signal, so +</code> 
-dass invert das Vorzeichen jedes Wertes s umkehrt.+1. Definieren Sie korekursiv eine Funktion ''alt: Signal -> Signal'', so dass ''alt s''  
 +den jeweils gesetzten Wert für ein gesetztes Bit ausgibt ( Ist x gesetzt, gebe x ausSind beide Werte gesetzt, nichts) 
 Hinweis: Sie dürfen bei der Definition die üblichen Operationen auf Hinweis: Sie dürfen bei der Definition die üblichen Operationen auf
-Basistypen (z.B. Arithmetik auf Int) als gegeben annehmen.+Basistypen (z.B. Arithmetik auf Boolean) als gegeben annehmen. 
 2. Geben Sie die Bedingungen an, die eine Relation erfüllen muss, um 2. Geben Sie die Bedingungen an, die eine Relation erfüllen muss, um
 eine Bisimulation auf signal zu sein. (Diese ergeben sich durch Spezialisierung eine Bisimulation auf signal zu sein. (Diese ergeben sich durch Spezialisierung
 des allgemeinen Begriffs aus der Vorlesung auf den Kodatentyp des allgemeinen Begriffs aus der Vorlesung auf den Kodatentyp
 signal) signal)
 +
 3. Beweisen Sie die folgende Eigenschaft durch Koinduktion: 3. Beweisen Sie die folgende Eigenschaft durch Koinduktion:
-∀s ∈ Si g n al ∀x ∈ Int discardSample +... 
-( square x −x ) i n v e r t ( square x −x ) + 
-Rechtfertigen Sie alle Beweisschritte.+====== Aufgabe 5 ====== 
  
-Aufgabe 5+Sei L die Sprache über Σ = {a, b, c}*, die gerade aus allen Worten über Σ 
 +besteht, die w und w gespielt bestehen. Z.B. sind ε, aa und abccba in L, nicht aber ε, aba, abcabc, ... 
 +Ist L regulär? Wenn ja, geben sie einen regulären Ausdruck für L an und 
 +erläutern Sie, warum dieser L definiert. Andernfalls zeigen Sie mittels des 
 +Pumping-Lemma, dass L nicht regulär ist.
  
 +Das darf gerne noch jemand in ,tex übertragen, ich hab' erstmal genug von ThProg...
 +by Cerox