Ea2 mit deckblatt - Einsendeaufgaben PDF

Preview

Summary

Einsendeaufgaben...

Description

FERNUNI VERSI TÄT i nHagen

Bi t t ehi erunbedi ngt Mat r i kel nummerund Adr esseei nt r agen, sonstk ei ne Bear bei t ungmögl i ch.

Post ansc hr i f t :Fer nUni v er si t ät58084Hagen

EI NGANG

__________

MI

____________________________________________________________ ( Name,Vor name) ____________________________________________________________

____________________________________________________________ ( St r aße,Nr . )

Bi t t ez ur ückan: FERNUNI VERSI TÄT 58084Hagen

____________________________________________________________ ( PLZ,Wohnor t ) ____________________________________________________________ ( Land)

__ Fakul t ätf ürMat hemat i kundI nf or mat i k Lehr gebi etWi ssensbasi er t eSyst eme,Pr of .Dr .Bei er l e Kur s01852

For t gesc hr i t t eneKonzept ef unkt i onal erPr ogr ammi er ung

Kur s ei nhei t

02

Ei nsendeauf gaben Hi nwei sezurBear bei t ung Al l eEi nsendeauf gabenzu di esem Kur smüssenüberWebAssi gnei nger ei c htwer den, ei neEi nsendungperPostoderEMai l i stni chtmögl i ch.

Let zt erEi nsendet ag:

Auf gabe

13. 05. 2018

( 23: 59,nurüberWebAssi gn)

1

2

Summe

max i mal ePunkt zahl 40

60

100

bear bei t et er r ei c ht ePunkt zahl

Dat um:___________________

©2017Fer nUni v er si t äti nHagen

Kurs 1852, SS 2018: Aufgaben zur Kurseinheit 2 Hinweis: Die Aufgaben unterteilen sich in Einsendeaufgaben, zu denen Sie L¨osungen zur ¨ bungsaufgaben, die nicht individuell korrigiert werden, jedoch zur Korrektur einsenden, und U Vertiefung und Ein¨ubung des Stoffes empfohlen werden. Zu beiden Aufgabentypen erhalten Sie L¨osungsvorschl¨ age, wenn Sie uns Ihre Bearbeitung zu diesem Aufgabenblatt zuschicken.

Achtung: Alle Einsendeaufgaben zu dieser Kurseinheit m¨ussen u¨ber WebAssign eingereicht werden; eine Einsendung per Post oder E-Mail ist nicht m¨oglich. Allerdings sollten Sie WebAssign nicht als Entwicklungsumgebung benutzen, da WebAssign daf¨ ur nicht ausgelegt ist; verwenden Sie f¨ ur die Entwicklung ein ML-System auf Ihrem eigenen Rechner (vgl. dazu das erste Begleitschreiben zu diesem Kurs). Beachten Sie bitte auch die Hinweise zur Benutzung von WebAssign, die wir am Ende dieses Aufgabenblatts beigef¨ ugt haben.

Einsendeaufgabe 1

Str¨ ome

(40 Punkte)

Diese Aufgabe behandelt unendliche Str¨ome gem¨aß der Definitionen im Kurs. Greifen Sie f¨ ur Ihre Programme auf den im Kurs definierten Datentyp sequ zur¨ uck. Teil 1 (15 Pkt.): Implementieren Sie eine Funktion nat paare, die einen Strom aller Paare nat¨ urlicher Zahlen als Wert zur¨ uck gibt. Dabei soll die Zahl 0 als nat¨ urliche Zahl angesehen werden. Die Auflistung soll fair sein, d.h. jedes Paar erscheint an endlicher Position in dem Strom. Hinweis: Eine faire Aufz¨ ahlung aller Paare nat¨ urlicher Zahlen erhalten Sie z.B. bei Sortierung nach der Gr¨ oße der Summe der beiden Elemente sowie bei gleicher Summe nach der Gr¨oße des ersten Elementes. Teil 2 (8 Pkt.): Implementieren Sie eine Funktion nat paare nicht null die eine faire Auflistung aller Paare nat¨ urlicher Zahlen ohne 0 zur¨ uckliefert. nat paare nicht null soll mit Hilfe der Funktion filters aus dem Kurstext und nat paare implementiert werden. Teil 3 (17 Pkt.): Implementieren Sie eine Funktion brueche die einen Strom aller Paare (a, b) von nat¨ urlichen urzter Bruch ist. Zahlen (ohne 0) zur¨uckliefert, so dass ba ein gek¨

¨ Ubungsaufgabe

Programmverifikation

Gegeben sei das folgende SML-Programm zur Berechnung des gr¨oßten gemeinsamen Teilers zweier nat¨ urlicher Zahlen: fun ggt a b = if a = 0 then b else if b < a then ggt b a else ggt a (b-a)

1

2

Kurs 1852, SS 2018: Aufgaben zur Kurseinheit 2 Beweisen Sie, dass jeder Aufruf ggt a b mit a, b ∈ N terminiert und den gr¨ oßten gemeinsamen Teiler von a und b zur¨ uckliefert.

Einsendeaufgabe 2 Unfold/Fold-Verfahren (60 Punkte) In Kurseinheit 1 wurde ein Datentyp f¨ ur B¨aume beliebigen Typs angegeben: datatype ’a tree = NODE of ’a * ’a tree * ’a tree | EMPTY; Teil 1 (10 Pkt.): Implementieren Sie eine Funktion mapt : (’a −> ’b) −> ’a tree −> ’b tree. Diese erwartet eine Funktion f und einen Baum t als Eingabe und liefert einen Baum t′ als Ausgabe, in dem jedes Element aus der Anwendung von f auf das entsprechende Element in t hervorgegangen ist. Teil 2 (12 Pkt.): Implementieren Sie eine Funktion count : (’a −> bool) −> ’a tree −> int. Diese soll zu einem Pr¨adikat p und einem Baum t die Anzahl der Elemente von t liefern, die p erf¨ullen. Teil 3 (38 Pkt.): Optimieren Sie unter Verwendung des Unfold/Fold-Verfahrens die Funktionsdefinition fun opt t = count (fn m => m = 0) (mapt (fn n => n mod 2) t); so dass nur ein Baumdurchlauf notwendig ist.

Kurs 1852, SS 2018: Aufgaben zur Kurseinheit 2

Hinweise f¨ ur die Benutzung von WebAssign ¨ • WebAssign unterst¨ utzt Sie bei der L¨osung von speziellen Ubungsaufgaben. Dazu sollen Sie die angeforderten Programme schreiben und dann mittels WebAssign kontrollieren. Nutzen Sie zur Entwicklung der Programme nicht WebAssign, sondern ein daf¨ ur geeignetes System auf Ihrem eigenen Rechner (vgl. dazu das erste Begleitschreiben zu diesem Kurs). • Schreiben und sichern Sie Ihre Programme extern! Sollte es bei einer WebAssign-Sitzung ¨ bertragungsfehler kommen, k¨ onnen die Programme verloren gehen. Liegen zu einem U die Programme extern vor, dann sollten Sie zu einem sp¨ateren Zeitpunkt erneut eine ¨ Ubertragung versuchen. • WebAssign kann nur die Programmteile kontrollieren, die es erkennt. Wenn Sie in der Aufgabenstellung z.B. aufgefordert werden, eine Funktion v_v_mult zu entwickeln, dann muss die Funktion in Ihrem Einsende-Programm auch genau so heißen. Jede Abweichung im Namen f¨uhrt zu Fehlermeldungen. • Beachten Sie die Fehlermeldungen von WebAssign! Das Kontrollsystem erkennt nicht nur richtig oder falsch, sondern versucht auch, Fehler zu identifizieren und darauf hinzuweisen. Dazu testet WebAssign Ihr Programm mit einer Reihe von Testeingaben. Tritt bei einer Testeingabe ein Fehler auf, wird die Eingabe zusammen mit der tats¨achlichen und der erwarteten Programmreaktion sowie einer Fehlerbeschreibung ausgegeben.

3...