Tilman
151 lines
6.1 KiB
PHP
151 lines
6.1 KiB
PHP
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
|
|
<html>
|
|
<head>
|
|
<meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
|
|
<link rel="stylesheet" type="text/css" media="all" href="stylesheet.css">
|
|
<title>Aufgaben</title>
|
|
</head>
|
|
<body>
|
|
<span id="menu"><a href="index.php">zurück zur Liste</a></span>
|
|
|
|
<div id="buttons">
|
|
<form action="edit.php" method="POST">
|
|
<input type="hidden" name="filename" value="<?php echo $_SERVER['SCRIPT_FILENAME']?>">
|
|
<p>
|
|
<input type="submit" value="Seite bearbeiten">
|
|
</p>
|
|
</form>
|
|
</div>
|
|
|
|
<h1>Allgemeine Aufgaben in Haskell</h1>
|
|
|
|
<h2>Sortieren</h2>
|
|
<ol start="1" type="1">
|
|
<li>Quicksort</li>
|
|
<li>Mergesort</li>
|
|
<li>Insertionsort</li>
|
|
<li>Selectionsort</li>
|
|
</ol>
|
|
|
|
<h2>Suchen</h2>
|
|
<ol start="5" type="1">
|
|
<li>lineares Suchen</li>
|
|
<li>binäre Suche</li>
|
|
</ol>
|
|
|
|
<h2>diverses in Haskell</h2>
|
|
<ol start="7" type="1">
|
|
<li>reverse</li>
|
|
<li>Fibonacci</li>
|
|
<li>Fakultät</li>
|
|
<li>Summe einer Liste</li>
|
|
<li>map Funktion selbst schreiben</li>
|
|
<li>Binärer Suchbaum mit insert, delete, contains, sum, gib Baum als sortierte List aus...</li>
|
|
<li>Ein Stack in Haskell</li>
|
|
<li>Eine Queue in Haskell</li>
|
|
<li>Eine Menge in Haskell</li>
|
|
</ol>
|
|
|
|
<a href="loesungen.hs">Lösungen</a>
|
|
|
|
<h1>Allgemeine Aufgaben in Java</h1>
|
|
<ol>
|
|
<li>
|
|
<a href="BinTree.java">Binärbaum</a> - ein ziemlicher Klopper, aber man sollte das mal gemacht haben.
|
|
</li>
|
|
<li>
|
|
"1. Spezifizieren Sie ein Interface für einen Stack und implementieren Sie den Stack in Java mit einem Array" - <a href="ArrayStack.java">Lösung</a>
|
|
</li>
|
|
<li>
|
|
"1. Spezifizieren Sie ein Interface für eine Schlange und implementieren Sie die Schlange in Java mit einem Array" - <a href="ArrayQueue.java">Lösung</a>
|
|
</li>
|
|
</ol>
|
|
|
|
<h1>Allgemeine Aufgaben</h1>
|
|
|
|
<a href="loesungenvonbettina.php">Lösungen der folgenden Aufgaben</a>
|
|
<h2>Vollständige Induktion</h2>
|
|
Um die Behauptungen zu beweisen, kann man die vorherigen Aussagen und die bewiesenen Behauptungen mitbenutzen.
|
|
<ol>
|
|
<li>Um das Prinzip zu verstehen: <b>1 + 3 + 5 + ... + (2n-1) = n²</b>, wobei n > 0.</li>
|
|
<li><b>x ++ [] = x</b>, wobei (a) [] ++ v = v und (b) (a:v) ++ w = a:(v ++ w)</li>
|
|
<li><b>rev (a ++ b)= (rev b) ++ (rev a)</b>, wobei (a) rev [] = [] und (b) rev (a:v) = (rev v) ++ [a]</li>
|
|
<li><b>rev (rev xs) = xs</b>, wobei (a) rev [] = [] und (b) rev (a:v) = (rev v) ++ [a] und (c) rev [x] = [x] und (d) [x] = x:[]</li>
|
|
</ol>
|
|
|
|
<h2>Primitiv rekursive Funktion</h2>
|
|
<ol>
|
|
<li>Vorgängerfunktion <b>pred</b></li>
|
|
<li>Gleichheit mit Null <b>eq0</b>, wobei True 1 und False 0 entspricht</li>
|
|
<li>Subtraktion <b>sub</b> von zwei Zahlen, wobei bei Rojas x-y = sub(y, x)</li>
|
|
<li><b>and</b>, <b>not</b>, größer-gleich <b>≥</b></li>
|
|
<li><b>if (x, y, z)</b>, wobei if x then y else z</li>
|
|
</ol>
|
|
|
|
<h2>O-Notation</h2>
|
|
<ol>
|
|
<li>Sortieren Sie die folgenden Laufzeiten aufsteigend.<br>
|
|
(a) n<sup>3</sup> (b) log<sub>2</sub> n (c) 1,8<sup>n</sup> (d) n (e) 3<sup>n</sup> (f) √n (g) n(log<sub>2</sub> n)<sup>2</sup> (h) n<sup>2</sup></li>
|
|
<li>Finden Sie möglichst einfache Ausdrücke der Form Θ(·) für folgende Funktionen:<br>
|
|
(a) 3n<sup>2</sup> − 4n + 32 + 27 n · ⌈log<sub>2</sub> n⌉ / 2<br>
|
|
(b) max{n⌈log<sub>2</sub> n⌉, (⌈log<sub>2</sub> n⌉)<sup>4</sup>}<br>
|
|
(c) 2<sup>2n + ⌈log<sub>2</sub> n⌉</sup></li>
|
|
</ol>
|
|
|
|
<h2>Algorithmen</h2>
|
|
<ol>
|
|
<li><b>Dijkstra</b><br>
|
|
a ist der Startknoten.<br>
|
|
<img src="dijkstra-aufgabe.gif">
|
|
</li>
|
|
<li><b>Kleinster aufspannender Baum</b><br>
|
|
Prim und Kruskal am obigen Graphen.
|
|
</li>
|
|
<li><b>Huffman</b><br>
|
|
Für das Wort <b>ABRACADABRASIMSALABIM</b> die Wahrscheinlichkeiten der einzelnen Buchstaben bestimmen und dann einen Binärcode nach dem Huffman-Algorithmus erstellen.
|
|
</li>
|
|
<li><b>Verschiebefunktion</b><br>
|
|
Aufstellen der Verschiebefunktion des Musters <b>babcabb</b> und überprüfen ob es im Text <b>abbababcababcabbbca</b> entghalten ist.
|
|
</li>
|
|
</ol>
|
|
|
|
<h2>Graphen und Bäume</h2>
|
|
<ol>
|
|
<li><b>AVL-Baum</b><br>
|
|
Erstelle einen neuen AVL-Baum und füge folgende Werte nacheinander ein: 3, 2, 1, 4, 5, 6, 7, 16, 15<br>
|
|
Nun lösche die Werte 4 und 2.
|
|
</li>
|
|
<li><b>B-Baum</b><br>
|
|
Erstelle einen neuen (2,3)-Baum und füge folgende Werte nacheinander ein: 1, 5, 2, 6, 7, 4, 8, 3<br>
|
|
Ich denke, dass man Löschen nicht können muss. Das ist ziemlich kompliziert!
|
|
</li>
|
|
<li><b>Rot-Schwarz-Baum</b><br>
|
|
Wandle den folgenden Rot-Schwarz-Baum in einen einen (2,4)-Baum um.<br>
|
|
<img src="rotschwarz-aufgabe.gif">
|
|
<div class="quelle">Die Grafik ist ein Screenshot von Arsen Gogeshvilis <a href="http://webpages.ull.es/users/jriera/Docencia/AVL/AVL%20tree%20applet.htm">Binärbaum-Applet</a></div>
|
|
</li>
|
|
<li><b>Suffixbaum</b><br>
|
|
Erstelle einen Suffixbaum des Wortes <b>ananas$</b>.
|
|
</li>
|
|
<li><b>Adjazenzliste und -matrix</b><br>
|
|
Gebe für folgenden Graphen eine Adjazenzliste und eine Adjazenzmatrix an und überlege welche Darstellung hier sinnvoller ist.<br>
|
|
<img src="adjazenzaufgabe.gif">
|
|
<div class="quelle">Grafik entnommen aus Saake, Sattler: "Algorithmen & Datenstrukturen"</div>
|
|
</li>
|
|
<li><b>Konvexe Hülle</b><br>
|
|
Folgende Punkte im Koordinatenkreuz bilden einen Graphen: <b>A(1/9), B(3/7), C(4/8), D(5/1), E(7/5), F(7/7), G(9/3), H(10/8)</b><br>
|
|
Nenne die Punkte, die in der komplexen Hülle enthalten sind.
|
|
</li>
|
|
<li><b>Infix, Prefix und Postfix</b><br>
|
|
Folgende Terme in Pre- und Postoder darstellen.<br>
|
|
(a) <b>2 + 3 * 6 - 4 / 1</b><br>
|
|
(b) <b>5 * (6 + 2) - 7 / 4 + 2 * 5</b><br>
|
|
Am Einfachsten geht das mit Hilfe eines Termbaums.<br>
|
|
(c) <b>Pre-, In- und Postorder</b> von folgendem Termbaum<br>
|
|
<img src="prepost3.gif">
|
|
</li>
|
|
</ol>
|
|
|
|
|
|
</body>
|
|
</html> |