Prof. Dr. Manfred Schmidt-Schauß Fachbereich Informatik (20) Künstliche Intelligenz/Softwaretechnologie Johann Wolfgang Goethe-Universität Frankfurt am Main

Funktionales Programmieren II:

Semantik, statische Analyse, Verifikation und abstrakte Interpretation

Wintersemester 1996/97

Übungsblatt Nr. 3

KISS: the coincidence of two different cryptograms, each transmitted in a different cipher, yet each containing the same original plaintext, the solution of one thereby leading to the solution of the other. aus

A Lexicon of Cryptography: Most Secret, Bletchley Park 1943

zitiert nach: Robert Harris: Enigma

Aufgabe 1

Es sei folgende geordnete Menge als Hasse-Diagramm gegeben:

⊤ a  b c  d  e g  h i  j k  l  m f  ⊥

Geben Sie folgende Werte an:

(i) l ⊓ e  (iv) d ⊔ e  (vii) (j ⊓ l) ⊓ k
(ii) (l ⊓ j) ⊓ k (v) c ⊔ (d ⊔ e) (viii) j ⊓ (l ⊓ k)
(iii) c ⊔ e  (vi) ⊔{c, d, e} (ix) j ⊓ k

Aufgabe 2

Dieses ist die erste Programmieraufgabe. Wir wollen auf Ordnungsrelationen rechnen. Hierzu definieren wir folgende Typvereinbarung:

type Rel a = [(a,a)]

Eine Relation auf einer Menge wird also als Liste von Paaren gespeichert. Das erste Paarelement soll dabei kleiner als das zweite sein. Die Relation ist dann der transitive Abschluß dieser Liste.

• Schreiben Sie zwei Funktionen, die alle größeren bzw. alle kleineren Elemente eines Elementes ausgeben. Die Funktionen sind zu typisieren als:

up :: Eq a => a -> Rel a -> [a]
low :: Eq a => a -> Rel a -> [a]

• Schreiben Sie zwei Funktionen lub und glb, die die größte untere und kleinste obere Schranke berechnet. Die Funktionen sollen dabei folgende Typisierung haben:

lub :: Eq a => [a] -> Rel a -> a
glb :: Eq a => [a] -> Rel a -> a

• Lösen Sie Aufgabe 1 mit ihrem Programm.