3.7.2009. Prüfungsanmeldungen von Studenten aus externen Fachbereichen bitte im jeweiligen Heimat-Fachbereich vornehmen sowie per E-Mail an kde-office@cs.uni-kassel.de unter Angabe von Name, Matr.-Nr. und FB.
Für Prüfungsanmeldungen von Studenten aus dem FB 16 genügt die Anmeldung in der OKA. Vielen Dank.
1.9.2009.Die Klausur gliedert sich in Theorie- und Praxisteil à 40 bzw. 90 Minuten. Beide Teile decken jeweils den ganzen Vorlesungs- und Übungsstoff ab. Der Praxisteil zeichnet sich dadurch aus, dass man größere Aufgaben am Stück bearbeitet/rechnet, während im Theorieteil mit mehreren kleineren Aufgaben die thematische Spannweite abgefragt wird. Für den Theorieteil sind keine Unterlagen erlaubt. Für den Praxisteil dürfen beliebige nicht-elektronische Unterlagen, z.B. Bücher, Notizen, Vorlesungsfolien oder Übungsaufgaben mit Lösungen verwendet werden. Nicht erlaubt sind Taschenrechner, Laptops oder ähnliche Geräte.
Erster Veranstaltungstag:
Montag, 20. April 2009, 14:15 in Raum 1603 (Neubau WA 73/Emilienstraße)
Ort und Zeit:
Montags, 14.15 h – 15.45 h, in Raum 1603
Hausaufgaben:
- Hinweise zur Abgabe von Aufgaben.
- Link zum Abgabesystem
- Bitte senden Sie Fragen zur Veranstaltung sowie Fragen zum Abgabesystem an Herrn Eisterlehner oder Herrn Benz.
- Bitte verwenden Sie in allen E-Mails den Betreff “AlgoDS”.
Übungen:
Dienstags, 8.00 h – 9.30 h, in Raum 0446 (Altbau WA 73). Beginn 21. April
Dienstags, 12.00 h – 13.30 h, in Raum 1114 (Altbau WA 71). Beginn 21. April
Donnerstags, 10.00 h – 11.30 h, in Raum -1607 (Neubau WA 73/Emilienstraße). Beginn 23. April
Donnerstags, 16.00 h – 17.30 h, in Raum -1606 (Neubau WA 73/Emilienstraße). Beginn 23. April
Cip-Pool-Übung:
Mittwochs, 8.00 h – 10.00 h, in Raum -1201 (Altbau WA 73). Beginn 22. April
Wettbewerb:
Der Programmierwettbewerb läuft. Eine Beschreibung des Wettbewerbs befindet sich auf dem 9. Hausübungsblatt.
Täglich aktualisierte Zwischenergebnisse sind hier zu finden. Aktuelles (insbesondere der Tagessieger) wird über twitter mitgeteilt.
Vorkenntnisse:
Einführung in die Programmierung
Angesprochener HörerInnenkreis:
Informatik Bachelor, Mathematik Bachelor, Elektrotechnik Diplom I
Leistungsnachweis:
Klausur; Studienleistung (b/nb)
Veranstalter:
Prof. Dr. Gerd Stumme , Dipl.-Inform. Dominik Benz, Dipl.-Inform. Folke Eisterlehner
Wir haben keine festen Sprechstunden, unsere Türen stehen aber meistens offen. Kommen Sie einfach vorbei!
Inhalt:
Die Teilnehmer lernen grundlegende Algorithmen und Datenstrukturen der Informatik wie Such- und Sortierverfahren, rekursive Algorithmen, Bäume, Hashverfahren etc. kennen. Dabei werden neben algorithmischen Ideen verschiedene Techniken für die Analyse des Zeitbedarfs und den Nachweis der Korrektheit vermittelt. Beispielprogramme vertiefen und erweitern die Programmierkenntnisse in Java. In den begleitenden Übungen sammeln die Teilnehmer weitere Programmiererfahrungen in Java und erwerben Fertigkeiten in der Algorithmenanalyse sowie im Entwickeln eigener algorithmischer Ideen.
Errata:
- 3-27: Die return-Zeile muss lauten: return r1.area – r2.area;
- 3-60: Alle runden Klammern hinter “count(…)” durch eckige Klammern ersetzen.
- 3-60: Die letzte for-Schleife geht bis N-1.
- 3-60: Die letzte Zeile muss heissen: a:=b;
- 3-61: In NB-Zeile “dk” durch “dk” ersetzen.
Folien:
- 0_Organisatorisches_Handout.pdf
- 1_Einfuehrung_Handout.pdf
- 2_Eigenschaften_Handout.pdf
- 3_Sortieralgorithmen_Handout.pdf
- 4_GrundlegendeDatenstrukturen_Handout.pdf
- 5_JavaCollectionFramework_Handout.pdf
- 6_Baeume_Handout.pdf
- 7_Hashing_Handout.pdf
- 8_Werbung_Handout.pdf
- 9_Graphen_Handout.pdf
Präsenzübungsblätter:
- 1. Präsenzübung
- 2. Präsenzübung
- 3. Präsenzübung
- 4. Präsenzübung (Vorlage zu den Sortier-Spielkarten: spielkarten-vorlage.pdf)
- 5. Präsenzübung
- 6. Präsenzübung
- 7. Präsenzübung: Kein Übungsblatt, sondern gemeinsame Wiederholung des bisherigen Stoffs
- 8. Präsenzübung
- 9. Präsenzübung
- 10. Präsenzübung
- 11. Präsenzübung
- 12. Präsenzübung
- 13. Präsenzübung
Hausaufgabenblätter:
Errata:
- 3. Hausübung: Bei der Beispielausgabe der main-Methode der Klasse StopWatch ist bei den Werten von n jeweils eine Zehnerpotenz zu wenig (d.h. n=1000 statt n=10000, n=1000000 statt n=10000000, …). Korrekt sind die Werte aus der Aufgabenstellung (jeweils die grössere Zehnerpotenz).
- 8. Hausübung:
- 1. Aufgabe (Queue als Liste) “Im Falle einer leeren Liste soll enqueue null zurückliefern.” Richtig ist: “… soll dequeue null…”
- 2. Aufgabe (Datenstruktur Lectures): An zwei Stellen ist von Namen von Studenten die Rede; korrekterweise muss von Matrikelnummern gesprochen werden, da in der Datenstruktur nur die Matrikelnummer und nicht der Name eines Studenten abgespeichert wird.
- 10. Hausübung: Die Beispielausgabe der Zusatz-Aufgabe (Parsen von Postfix-Notation) muss richtigerweise lauten:
Parsing expression 2 Postfix-Notation: 7 3 5 6 * + * Infix-Notation: (7*(3+(5*6))) Wert des Ausdrucks: 231
(Die alte Ausgabe war semantisch korrekt, jedoch in abgeänderter Reihenfolge)
- 12: Hausübung: Es wird nach der Anzahl strukturell verschiedener (2,4)-Bäume der Höhe 3 gefragt
Lösungsvorschläge:
Die Lösungsvorschläge zu den Präsenz- und Hausaufgabenblättern finden Sie innerhalb der Lernplattform Moodle.
Literatur zur Vorlesung:
- Gunter Saake, Kai-Uwe Sattler: Algorithmen und Datenstrukturen – Eine Einführung mit Java, dpunkt-Verlag, 2006. Die Einzelkapitel sind relativ preiswert als E-Book erhältlich, für die Vorlesung nützlich sind voraussichtlich die Kapitel 5, 7, 8, 13, 14, 15 und 16.
- Robert Lafore: Data Structures & Algorithms in Java, Sams Publishing, 2003.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest: Algorithmen – Eine Einführung, Oldenbourg Verlag, 2007.
- Heinz-Peter Gumm et al.: Einführung in die Informatik. Oldenbourg Verlag, 2006, Kapitel 4.
- Thomas Ottmann, Peter Widmayer: Algorithmen und Datenstrukturen. Spektrum Akademischer Verlag, 2002.
- Gustav Pomberger, Heinz Dobler: Algorithmen und Datenstrukturen, Pearson, 2008
- B. Owsnicki-Klewe: Algorithmen und Datenstrukturen, Wissner, 1994
- Siehe auch Semesterapparat der Bereichsbibliothek 7