AuK/Teile und Herrsche 2 SS10/Aufgaben
Aus ProgrammingWiki
Wiki-Quelltext dieser Seite.
<language>Scheme</language>
== Übungsaufgaben ==
===Binäre Suche===
<b>Aufgabe 1</b> Binäresuche<br>
Etwas stimmt beim nachfolgenden Code nicht, es gibt einen Fehler, finden, bennenen und korrigieren sie ihn.<br>
<small>Nur keine Angst, die Übung sieht schlimer aus als sie tatsächlich ist.</small><br>
Für Hilfe: "hilfe-bin-suche" eingeben <br>
Für Tipps: "tipp-xy" wobei x ein Buchstabe ist und y eine Ziffer<br>
Für die Buchstaben: a, b, c und l (für Lösung)<br>
Die Tipps mit gleichen Buchstaben gehören zusammen<br>
Für die Ziffern: 1, 2, 3, 4 die Ziffern stehen für die Tipp-intensitäts-stufe<br>
<small>(Oder sollten das zumindestens)</small><br><br><br>
<small>!!!Achtung!!! für Tipps und hilfe KEINE klammerung : <br>
>tipp-a1</small><br>
<code id="4bcc833096c3d">
(define bin-suche
(lambda (ls wert)
(bin-such ls wert)))
(define bin-such
(lambda (ls wert)
(cond
[(number? wert)
(cond
[(eq? ls '()) "Fehler! Eingegebene Liste ist leer"]
[(eq? wert '()) "Fehler! Eingegebener Wert ist leer"]
[(list? wert) "Fehler! Der zusuchende Wert soll eine Liste sein!?!"]
[(eq? (cdr ls) '())
(cond
[(eq? (car ls) wert) wert]
[else "Element Nicht vorhanden + Liste besteht aus max einem Wert."])]
[else (bint-suc (sort < ls) wert (listen-lang ls))])]
[Else "Ausschließlich Zahlen sind als Suchabfrage erlaubt."])))
(define bint-suc
(lambda (ls wert i)
(cond
[(eq? i 2)(isers ls wert)]
[(< wert (car (liste-r ls)))
(bint-suc (liste-l ls) wert (listen-lang (liste-l ls)))
]
[(>= wert (car (liste-r ls)))
(bint-suc (liste-r ls) wert (listen-lang (liste-r ls)))
]
)))
(define list-lalng1
(lambda (ls i)
(cond
[(not-list? ls)(+ i 1)]
[else (list-lalng (cdr ls) (+ i 1))])))
(define list-lalng
(lambda (ls i)
(cond
[(eq? ls '()) i]
[else (list-lalng (cdr ls) (+ i 1))])))
(define listen-lang
(lambda (ls)
(list-lalng ls 0)))
(define liste-l
(lambda (ls)
(list-linkses ls (/ (listen-lang ls) 2))))
(define list-linkses
(lambda (ls laenge)
(cond
[(< laenge 1) '() ]
[else (cons (car ls) (list-linkses (cdr ls) (- laenge 1)))])))
(define liste-ra
(lambda (ls)
(list-rechtest ls (modulo (listen-lang ls) 2))))
(define liste-r
(lambda (ls)
(list-rechtest ls (/ (listen-lang ls) 2))))
(define list-rechtest
(lambda (ls laenge)
(cond
[(< laenge 1) ls]
[else (list-rechtest (cdr ls) (- laenge 1))])))
(define ist-er-es
(lambda (ls wert)
(cond
[(eq? ls '()) 'no]
[(eq? (car ls) wert) (car ls)]
[else (ist-er-es (cdr ls) wert)]
)))
(define isers1
(lambda (ls wert)
(cond
[(eq? ls '()) 'no]
[(eq? (car ls) wert) (car ls)]
[(eq? (cadr ls) wert) (cadr ls)]
[else 'no]
)))
(define isers
(lambda (ls wert)
(cond
[(eq? ls '()) "unter Umständen ist ein Fehler aufgetreten! Die End-Liste ist leer!!!"]
[(eq? (car ls) wert) "Wert Enthalten"]; für bint-suc i = 2
[(eq? (cadr ls) wert) "Wert Enthalten"]; für bint-suc i = 2
[(eq? (cddr ls) wert) "Wert Enthalten"]; für bint-suc i = 3
[else "Wert nicht Enthalten"]
)))
(define sort
(lambda (rel ls)
(cond
[(eq? '() ls)'()]
[(eq? '() (cdr ls)) ls]
[(Cond
[(eq? rel <)(einf < (sort rel (cdr ls))(car ls) )]
[(eq? rel >)(einf > (sort rel (cdr ls))(car ls) )]
[else "Relation unzulaessig!"])])))
(define einf
(lambda (relatio ls wawert)
(cond
[(eq? ls '())(list wawert)]
[(relatio wawert (car ls))(cons wawert ls)]
[else (cons (car ls)(einf relatio (cdr ls) wawert))])))</code>
<code id="4bcc83309740c" hidden>
(define d
'(93 2 96 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 18))
(define c
'(93 2 96 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 53 19))
(define c2
'(93 2 245 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 53 19))
(define b
'(93 2 96 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 53 233 20))
(define b2
'(91 2 96 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 53 233 20))
(define a
'(93 2 96 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 53 233 17 21))
(define z
'(93 2 4 86 5 6 3 34 7 38 45 3333 44 87 10 27 53 233 17 25 102 23))
(define t
'(1 1 96 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 233 1))
(define hilfe-bin-suche
"Eingabe Format: (bin-such <zu-durchsuchende-Liste> <zu-Suchender-Wert>)")
(define bin-such-wie?
hilfe-bin-suche)
(define bin-suche-wie?
hilfe-bin-suche)
(define hilfe-bin-such
hilfe-bin-suche)
(define hilfe-fehler
"fuer hilfe: hilfe-bin-suche eingeben / oder: tipp-xy wobei x ein Buchstabe ist und y eine Ziffer / fuer die Buchstaben: a, b, c und l(für lösung) die Tipps mit gleichen Buchstaben gehören zusammen / für Ziffern: 1, 2, 3, 4 die Zahlen stehen für die Tipp-stufe")
(define hilfe-zufalls-liste
"Faule !*?#%! Schreib selber ne' Liste!!!!")
(define hilfe-zufallsliste
hilfe-zufalls-liste)
(define tipp-a1 "fuer Tippfaule es gibt Testlisten: a ,b , b2, c, c2, d, t, z")
(define tipp-a2 "> (bin-such a 100) = user break || > (bin-such b 100) = user break || > (bin-such c 100) = Wert nicht Enthalten || > (bin-such c2 100) = user break || > (bin-such d 100) = Wert nicht Enthalten || > (bin-such z 100) = Wert nicht Enthalten || > (bin-such t 100) = Wert nicht Enthalten")
(define tipp-a3
"> (bin-such '(1 1 96 1 1 1 3 1 1 1 1 1 1 1 1 1 1 1 233 1) 100) = Wert nicht Enthalten || > (bin-such '(93 2 96 4 86 5 6 3 34 7 38 45 3333 44 87 10 23 53 233 20) 100) = user break")
(define tipp-a4
"(eq? i 3)(isers... hups...")
(define tipp-b1 " alle Listen werden automatisch aufsteigend sortiert ")
(define tipp-b2 " Testliste a, Zahlen von (einschliesslich) 96 bis 232 hmpf...")
(define tipp-b3 "Die Funktionen mit einer Zahl am ende ihres Namens sind irrelevant, konzentration auf die direkten Funktionen der binaeren Suche")
(define tipp-b4 "der Fehler ist eine Fehlende(!) Zeile")
(define tipp-c1 "gib ein (bin-suche c2 100)")
(define tipp-c2 "bleib beim wert 100 und versuche die anderen Testlisten und vergleiche die Reaktionen von DrScheme!")
(define tipp-c3 "du willst einen Tipp: gib ein (sort < c2) und untersuche die letzten drei Zahlen")
(define tipp-c4 "ernsthaft... versuch es nochmal, denke darueber nach was mit der 100 in der Testliste c2 passiert, wie läuft das ganze ab?! Tipp aus Gnade: 3-er Liste... hmpf...")
(define tipp-l1 "Der Fehler ist eine fehlende Bedingung in einem Cond")
(define tipp-l2 "Wenn eine Liste zerteilt wird und die Suche in eine Drei-Elemente-Liste mündet kommt dieser Quellcode nicht mehr aus der Untersuchung dieser drei Elemente Liste heraus!")
(define tipp-l3 "der Fehler liegt NICHT an den BESTEHENDEN Bedingungen in bint-suc diese sind Richtig aber in bint-suc fehlt noch eine Bedingung!")
(define tipp-l4 "Der Fehler liegt in bint-suc dort fehlt im Cond die Bedingung [(eq? i 3)(isers ls wert)] ziemlich fiess was... ich habe etwa 1h und 45min gebraucht")
</code>
<eval id="4bcc833097bda"></eval>
Es ist sehr zu empfehlen die Datei herunter zu laden und in DrScheme zu verwenden.
<document>Simabrzo_Fehler-Binaersuche.zip</document>
<b>Aufgabe 2</b> <br>
Schritt Vergleich zwischen Linearer Suche und Binärer Suche:
Untersuchen sie fünf verschiedene Eingaben sowohl für die Binäre Suche als auch für die Lineare Suche.<br>
Und untersuchen sie die Unterschiede zwischen den Reaktionen der beiden Funktionen.<br><br>
In der Formatierung von:<br>
(bin-suche <listen-länge> <zu-suchender-Wert>)<br>
(lin-suche <listen-länge> <zu-suchender-Wert>)<br><br>
<code id="4bccc11b6df13" hidden>
(define Mll
(lambda (wert)
(Make-lange-liste wert)))
(define Make-lange-liste
(lambda (wert)
(lgn-lst wert 0 wert)
))
(define lgn-lst
(lambda (wert j i)
(cond
[(eq? i 0) (cons wert '())]
[else (cons j (lgn-lst wert (+ j 1) (- i 1)))]
)))
(define Linear-suche
(lambda (groesse wert)
(lin-such (mll groesse) wert)
))
(define Lin-such
(lambda (ls wert)
(cond
[(eq? ls '()) "Bitte KEINE leere Liste eingeben." ]
[(eq? wert '()) "Bitte einen Wert zum Suchen eingeben."]
[(eq? (car ls) wert) "Best-Case!"]
[Else
(Linil-zuch ls wert (listen-lang ls) 1)]
)))
(define Linil-zuch
(lambda (ls wert i j)
(cond
[(eq? ls '()) (list "Das Element wurden nach" j "Schritten nicht gefunden")]
[(eq? (car ls) wert) (list "das Element wurde nach" j "Schritten gefunden")]
[(eq? i 0) (list "Das Element wurden nach" j "Schritten nicht gefunden")]
[else
(Linil-zuch (cdr ls) wert (- i 1) (+ j 1))])))
(define list-lalng1
(lambda (ls i)
(cond
[(not-list? ls)(+ i 1)]
[else (list-lalng (cdr ls) (+ i 1))])))
(define list-lalng
(lambda (ls i)
(cond
[(eq? ls '()) i]
[else (list-lalng (cdr ls) (+ i 1))])))
(define listen-lang
(lambda (ls)
(list-lalng ls 0)))
(define liste-l
(lambda (ls)
(list-linkses ls (/ (listen-lang ls) 2))))
(define list-linkses
(lambda (ls laenge)
(cond
[(< laenge 1) '() ]
[else (cons (car ls) (list-linkses (cdr ls) (- laenge 1)))])))
(define liste-ra
(lambda (ls)
(list-rechtest ls (modulo (listen-lang ls) 2))))
(define liste-r
(lambda (ls)
(list-rechtest ls (/ (listen-lang ls) 2))))
(define list-rechtest
(lambda (ls laenge)
(cond
[(< laenge 1) ls]
[else (list-rechtest (cdr ls) (- laenge 1))])))
(define ist-er-es
(lambda (ls wert)
(cond
[(eq? ls '()) 'no]
[(eq? (car ls) wert) (car ls)]
[else (ist-er-es (cdr ls) wert)]
)))
(define isers1
(lambda (ls wert)
(cond
[(eq? ls '()) 'no]
[(eq? (car ls) wert) (car ls)]
[(eq? (cadr ls) wert) (cadr ls)]
[else 'no]
)))
(define isers
(lambda (ls wert k)
(cond
[(eq? ls '()) "unter Umständen ist ein Fehler aufgetreten! Die End-Liste ist leer!!!"]
[(eq? (car ls) wert) (list "Wert gefunden nach" k "Schritten" )]
[(eq? (cadr ls) wert) ( list "Wert gefunden nach" k "Schritten" )]
[(eq? (caddr ls) wert) (list "Wert gefunden nach" k "Schritten")]
[else "Wert nicht Enthalten"]
)))
(define Binaer-suche
(lambda (groesse wert)
(bin-such (mll groesse) wert)))
(define bin-such
(lambda (ls wert)
(cond
[(number? wert)
(cond
[(eq? ls '()) "Fehler! Eingegebene Liste ist leer"]
[(eq? wert '()) "Fehler! Eingegebener Wert ist leer"]
[(list? wert) "Fehler! Der zusuchende Wert soll eine Liste sein!?!"]
[(eq? (cdr ls) '())
(cond
[(eq? (car ls) wert) (list "Element nach 1 Schritten gefunden (Best Case)")]
[else "Element Nicht vorhanden + Liste besteht aus max einem Wert."])]
[else (bint-suc (sort < ls) wert (listen-lang ls) 0 )])]
[Else "Ausschließlich Zahlen sind als Suchabfrage erlaubt."])))
(define bint-suc
(lambda (ls wert i k)
(cond
[(eq? i 2)(isers ls wert k)]
[(eq? i 3)(isers ls wert k)]
[(< wert (car (liste-r ls)))
(bint-suc (liste-l ls) wert (listen-lang (liste-l ls)) (+ k 1) )
]
[(>= wert (car (liste-r ls)))
(bint-suc (liste-r ls) wert (listen-lang (liste-r ls)) (+ k 1))
]
)))
(define sort
(lambda (rel ls)
(cond
[(eq? '() ls)'()]
[(eq? '() (cdr ls)) ls]
[(Cond
[(eq? rel <)(einf < (sort rel (cdr ls))(car ls) )]
[(eq? rel >)(einf > (sort rel (cdr ls))(car ls) )]
[else "Relation unzulässig!"])])))
(define einf
(lambda (relatio ls wawert)
(cond
[(eq? ls '())(list wawert)]
[(relatio wawert (car ls))(cons wawert ls)]
[else (cons (car ls)(einf relatio (cdr ls) wawert))])))
</code>
Eingabe Beispiele:<br>
<small>bsp 1</small><br>
(bin-suche 10000 7866)<br>
(lin-suche 10000 7866)<br>
<small>bsp 2</small><br>
(bin-suche 10000 786)<br>
(lin-suche 100000 7866)<br>
<small>bsp 3</small><br>
(bin-suche 100000 7866)<br>
(lin-suche 10000 786)<br><br>
<eval id="4bcc8bd63dcf7">
(bin-such 10000 7866)
(Lin-such 10000 7866)
</eval>
Was stellen sie fest?<br><br>
<small>(Die Listen-Länge wird benötigt da automatisch eine Exemplarische Liste mit angegebener Länge erstellt wird mit der Eigenschaft das ihre Elemente die Zahlen von 0 bis zur angegebenen Zahl sind.)</small>
Laden sie sich herfür nachfolgende Datei herunter und nutzen sie diese in Dr Scheme.
<document>Simabrzo_Binaeresuche-versus-linearesuche.zip</document>
<br><br>
===Multiplikation großer ganzer Zahlen nach KARATSUBA und OFMAN===
Lösen Sie, unter Verwendung der Kenntnisse aus [[AuK/Teile und Herrsche 2 SS10#Der Algorithmus von KARATSUBA und OFMAN|Teile und Herrsche 2: Der Algorithmus von KARATSUBA und OFMAN]], folgende Rechenaufgaben:
#<math>3812 \cdot 3264</math>
#<math>837147 \cdot 479253</math>
#<math>34 \cdot 56</math>
Wie sinnvoll ist der Einsatz des Algorithmus bei kleinen Zahlen?
===Schnelle Matrixmultiplikation nach STRASSEN===
Gegeben sind folgende zwei Matrizen <math>A</math> und <math>B</math>
<math>
A=\begin{pmatrix}
3 & 4 & 8 & 9\\
1 & 5 & 9 & 2\\
5 & 7 & 4 & 3\\
2 & 3 & 8 & 1
\end{pmatrix}</math> und
<math>B=\begin{pmatrix}
3 & 2 & 8 & 6\\
1 & 4 & 9 & 5\\
7 & 6 & 4 & 3\\
2 & 9 & 2 & 3
\end{pmatrix}</math>
Berechnen Sie das Produkt der gegebenen Matrizen mithilfe des [[AuK/Teile und Herrsche 2 SS10#Schnelle Matrixmultiplikation|Algorithmus von Strassen]].
== Lösungen ==
Die Lösungen zu den Aufgaben findet man [[AuK/Teile und Herrsche 2 SS10/Aufgaben_Lösung|hier]].