Informatik II (252-0846-00)

Felix Friedrich

Vorlesung am D-BAUG der ETH Zürich, FS 2014

Neuigkeiten

• 15.01.2015 -- Lösung zur Prüfung vom August 2014 hier online erhältlich.
• 26.11.2014 -- Die Prüfung vom August ist nun hier online erhältlich. Vorerst ohne Lösung.
• 22.7.2014 -- Die Lösung für 11.2.d (relationale Algebra / SQL) wurde überarbeitet und sollte nun die Frage beantworten, welche gestern im Rahmen der Fragestunde aufgetaucht ist.
  - Hier finden Sie die in der Fragestunde erwähnten Resourcen von A.Kemper (TU München)
• 22.7.2014 -- Serie 11 1.2.d) und 1.3.d) Es hat einen Fehler in der Musterlösung: Bei 11.2d) sollte bei den Alpen ein "=" stehen.

  Eine mögliche Lösung für 11.3 d) lautet:
  (SELECT ISBN FROM KAT_BUCH WHERE Kategoriename = "Alps") EXCEPT (SELECT ISBN FROM KAT_BUCH WHERE Kategoriename = "Switzerland")

• 20.6.2014 -- Wir akzeptieren auch PC-geschriebene Zusammenfassungen an der Infk2-Prüfung.

Material

Die Vorlesungsunterlagen bestehen aus Vorlesungsfolien und Übungsunterlagen. Die Vorlesungsfolien sind auf Deutsch verfasst und stellen zusammen mit den Übungsblättern den Prüfungsstoff dar.

Übungsserien und Vorlesungsfolien

Die erste Übungsserie und die Folien zur Vorlesung werden in der ersten Vorlesungswoche aufgeschaltet.

Termine

Vorlesung	Montag	12:45-14:30	HPH G2
Übungen	Donnerstag	11:45-12:30, 12:45-13:30, 13:45-14:30	Verschiedene Räume
Präsenzübung	Donnerstag	15:00-18:00	Verschiedene Räume, meist HIL E15.2

Lernziel und Überblick

Aufbauend auf dem erworbenen Wissen der Vorlesung Informatik I sind die primären Primäre Lernziele der Vorlesung

• die Befähigung zum objektorientierten Programmieren,
• die konstruktive Kenntnis von Datenstrukturen und Algorithmen
• die Kenntnis von relationalen Datenbanken und
• deren Anbindung an eine Programmierumgebung
Sie beherrschen nach erfolgreichem Abschluss der Vorlesung die Mechanismen zur Erstellung eines Programmes im objektorientierten Kontext. Sie haben eine Vorstellung davon, was "hinter den Kulissen" passiert, wenn ein Programm übersetzt und ausgeführt wird. Sie kennen die gängigen Datenstrukturen und Algorithmen. Sie können korrekte und ausreichend effiziente Programme entwickeln, um eine klar formulierte Problemstellung zu lösen. Sie wissen, wie man Datenbankanfragen formuliert und wie man einfache Datenbanken entwirft. Sekundäre Lernziele der Vorlesung sind das Computer-basierte, algorithmische Denken, Verständnis der Möglichkeiten und der Grenzen der Programmierung und die Vermittlung der Denkart eines Computerwissenschaftlers.

Zeitplan, Folien und Übungen

Dies ist ein Plan und als solcher unterliegt er Änderungen -- auch und insbesondere nach Semesterbeginn.

Woche	Datum	Thema	Folien / Material	Übungen	Präsenzübung im
1	17.02.	0. Organisatorisches 1. Einführung Überblick, die Turing-Maschine, von Pascal zu Java, Rekursion, Exceptions, Terminierung und Korrektheit, das Halteproblem, Fallstudie Altägyptische Multiplikation, Endrekursion und Iteration, Invarianten, Effizienz	Folien Kapitel 0-1 Handout Kapitel 0-1 Code Kapitel 1	Übung 1 Slides: English Deutsch Handout: English Deutsch Template: MixMiddle.java Testdatei: test.txt Lösung: CountE.java
2	24.02.	2. Java Aufbau einer Kompilationseinheit, Qualified Identifer und Scopes, Prozedurales Programmieren in Java, Typkonversionen, Arrays,	Folien Kapitel 2 Handout Kapitel 2 Code Kapitel 2	Übung 2 Slides: English Deutsch Handout: English Deutsch Template: VectorMatrixMult.java HiLoGame.java Lösung: VectorMatrixMult.java HiLoGame.java	Do 27.2. HIL E15.2
3	03.03.	(2. Java) Fallstudie Zufallssurfer (MCMC I) 3. Klassen Klassen und Objekte, Dynamische Speicherallokation, Überladen,	Folien Kapitel 3 Handout Kapitel 3 Code Kapitel 3	Übung 3 Slides Handout Lösungen: HiLo HiloWithPlayer	Do 6.3. HIL E15.2
4	10.03.	(3. Klassen) Eine Klasse für rationale Zahlen, Datenkapselung, Klassen, Verstecken der Daten, Fallstudie Online Statistik	Folien Kapitel 4 Handout Kapitel 4	Übung 4 Slides Handout Lösungen: GrowingArray	Do 13.3. HIL C29
5	17.03.	4. Komplexität Komplexität eines Algorithmus, Grössenordnung, Landau-Symbole, Beispiel einer Komplexitätsberechnung (Mergesort) 5. Dynamische Datenstrukturen I Container, verkettete Listen, Stapel, Warteschlange, sortierte Liste,	Folien Kapitel 5 Handout Kapitel 5 Code Kapitel 5	Übung 5 Template Slides Handout Lösungen: Fibonacci LinkedList	Do, 20.3. HIL E15.2
6	24.03.	(5. Dynamische Datenstrukturen I) Fallstudie Point-In-Polygon Algorithmus (Jordan Kurven) 6. Objektorientierte Programmierung Motivation Zeichenprogramm, Vererbung,	Folien Kapitel 6 Handout Kapitel 6 Code Kapitel 6	Übung 6 Slides Handout Lösungen: LinkedListHighscore Komplexitätsvergleich GenericLinkedList GenericGrowingArray	Do 27.3. HIL E15.2
7	31.03.	(6. Objektorientierte Programmierung) Vererbung, Polymorphie, Fallstudie Numerische Integration: Rechteck-, Trapez- und Simpson-Regel, Monte-Carle Integration		Übung 7 Slides Handout EasyGraphics: EasyGraphics.java Demo.java Lösungen: Fahrzeuge Figures	Do 3.4. HIL C 29
8	07.04.	7. Dynamische Datenstrukturen II Bäume, Binäre Suchbäume, Balancierte Bäume	Folien Kapitel 7 Handout Kapitel 7 Code Kapitel 7	Übung 8 Slides Handout Lösungen: JavaMath Matlab	Do 10.4. HIL E15.2
9	14.04.	(7. Dynamische Datenstrukturen II) Binärer Heap, Effizienter Online-Median, Graphen und Fallstudie Kürzeste Wege (Dijkstra) 8. Tabellen und Hashing Datensätze und Schlüssel, Suchen nach Schlüssel, Indizieren, Hashtabellen	Folien Kapitel 8 Handout Kapitel 8 Code Kapitel 8	Übung 9 Highscore: Highscore.java Player.java Slides Handout Lösungen: SelfmadeTree PersistentHighscore BouncingSmily Winning Project	Do 17.4. HIL E15.2
--	21.04.	--- Osterferien ---			---
--	28.04.	--- Sechseläuten ---			---
10	05.05.	(8. Tabellen und Hashing) Einfache Hashfunktion, Hashtabellen, Kollisionen und deren Behandlung, Hashfunktionen für Strings, dynamische Hashtabellen 9. Datenbanksysteme: Das ER Modell Einführung in Datenbanksysteme, das Entity Relationship Modell, Funktionalitäten, schwache Entities, Generalisierung und Aggregation, Sichtenintegration	Folien Kapitel 9 Handout Kapitel 9	Übung 10 Exercise 10 Slides Slides z.T. in Deutsch Handout Lösungen: Slides	Do 8.5. HIL F15.4
11	12.05.	10. Datenbanksysteme: Das relationale Modell Formalismus des Relationalen Modells, Transformation eines ER-Modells, Relationale Algebra: Selektion, Projektion, kartesisches Produkt, Umbenennung und Joins 11. Datenbanksysteme: SQL Datendefinition, Einfache SQL-Anfragen, Anfragen über mehrere Relationen	Folien Kapitel 10 Folien Kapitel 11 Handout Kapitel 10 und 11 Dump der Beispieldatenbank der Vorlesung (leichte Variation der Uni DB von Prof. Kemper, TU München). Installation wie in Uebung 10.3	Übung 11 Exercise 11 Slides Slides deutsch Handout Lösungen: Slides	Do 15.5. HIL E15.2
12	19.05.	(11. Datenbanksysteme: SQL) Aggregatfunktionen und Gruppierung, Geschachtelte Anfragen, Nullwerte, Dreiwertige Logik, Syntactic Sugar 12. Datenbanksysteme: Programmierschnittstelle JDBC	Folien Kapitel 12 Handout Kapitel 12 Code Kapitel 12	Übung 12 Exercise 12 Slides Slides deutsch Handout Mysql JDBC Connector Projekt Übung 12.2 (Vier Gewinnt) Lösungen: Slides VierGewinnt Klassendiagramm	Do 22.5. HIL C29
13	26.05.	Zusammenfassung und Wiederholung	Folien Zusammenfassung Zusammenfassung auf 12 Seiten (englisch)		Do 29.5. HIL E15.2

Übungen

Einschreibung für die Übungen

Die Einschreibung erfolgt online. Sie bekommen eine email zugesendet.

Orte und Zeiten

Die Übungsgruppen sind derzeit wie folgt zugeteilt:

Zeit	Assistent	Mail	Ort	Sprache
Do, 11:45-12:30	Oskar Triebe		HCI J 8	deutsch
Do, 11:45-12:30	Lei Zhong		HIT J 52	englisch
Do, 12:45-13:30	Fabian Schewetofski		HIT J 52	deutsch
Do, 12:45-13:30	Renzo Roth		HCI D 4	deutsch
Do, 12:45-13:30	Nico Previtali		HCI D 6	deutsch
Do, 12:45-13:30	Robin Guldener		HCI F 2	deutsch
Do, 12:45-13:30	Urs Müller		HCI F 8	deutsch
Do, 12:45-13:30	Severin Wischmann		HIT F 13	deutsch
Do, 12:45-13:30	Raffaele Lauro		HIT F 31.1	italienisch
Do, 12:45-13:30	Fabian Stutz		HIT F 31.2	deutsch
Do, 12:45-13:30	Chahat Bhatia		HIT J 53	englisch
Do, 13:45-14:30	Sandro Huber		HIT F 13	deutsch
Do, 13:45-14:30	Temmy Bounedjar		HIT F 31.1	deutsch, französisch
Do, 13:45-14:30	Simon Lösing		HIT F 31.2	deutsch
Do, 15:00-18:00 (TA 15:45)	Präsenzstunden: Timon Gehr & Lei Zhong		(siehe Wochenplan)	deutsch, english

Chefassistent

Lars Widmer,

Fragen & Probleme

• 123456789 als Schleifenendwert in Übung 4.2 scheint zu hoch. Je nach VM resultiert ein Absturz. Verwenden Sie 12345678 nach Bedarf.
• Bei Aufgabe 9.1 i) ist das Resultat viel klarer, wenn Sie nur die Zahlen von 100 bis 999 in den Binärbaum einfügen.

Zur Prüfung

Prüfungsstoff für die zweistündige Endprüfung, welche in der Prüfungssession 2014 gemeinsam mit Informatik I stattfinden wird, schliesst Vorlesungsinhalt und Übungsinhalte ein.

Genaues Vorgehen: Teil I: Zweistündige Prüfung Informatik I -- dreissig Minuten Pause -- Teil II: Zweistündige Prüfung Informatik II.
Studenten, die die Informatik II als Semesterleistung belegen, schreiben gemeinsam mit dem Jahreskurs im zweiten Teil.

Die Prüfung ist (Hand-)schriftlich. Als Hilfsmittel ist eine selbstverfasste Zusammenfassung auf maximal 8 A4-Seiten (respektive 4 Blatt doppelseitig) zugelassen.

Aus unserer Sicht ist es empfehlenswert die Zusammenfassung selber und handschriftlich zu verfassen. Wir wollen Ihnen dies aber nicht aufzwingen und erlauben an der Prüfung zu Informatik II auch PC-Ausdrücke als Zusammenfassungen.

Zur Vorbereitung: Liste von möglichen Prüfungsfragen. Wir werden keine Lösungen für die möglichen Prüfungsaufgaben herausgeben. Erfahrungsgemäss erscheinen Aufgaben im Anbetracht der fertigen Lösung zu einfach. Also, stets wenn wir Lösungen herausgegeben haben, war das Verständnis für ähnliche Probleme an der Prüfung schlechter, also ohne Lösungen. Gründe sind wahrscheinlich, dass sich die StudentInnen ohne Lösung detailierter mit den Aufgaben auseinandersetzen und anschliessend gegenseitig austauschen, wenn Sie ihre Lösungen miteinander vergleichen.

Nichtsdestotrotz können wir in den Fragestunden gerne durch die Liste von möglichen Prüfungsaufgaben gehen. Der Modus ist dann aber, dass wir die Lösungen nicht selber aufzeigen, sondern kommentieren, was die StudentInnen herausgefunden habt. Das heisst, dass jede und jeder in der Fragestunde eine Teilfrage der möglichen Prüfungsfragen selber beantworten muss.

• Fragestunde 1: Montag 21. Juli 2014, 13:15 Uhr, IFW A36
• Fragestunde 2: Donnerstag 7. August 2014, 13:15 Uhr, IFW A36

Literatur

Wir versuchen, den Kurs grundsätzlich selbsterklärend zu gestalten. Trotzdem lohnt sich es sich natürlich immer, auch andere Quellen heranzuziehen. Folgende Bücher haben wir bei der Vorbereitung verwendet.
• Robert Sedgewick, Kevin Wayne, Einführung in die Programmierung mit Java. Pearson, 2011
  Englisch: Robert Sedgewick, Kevin Wayne, Introduction to Programming in Java: An Interdisciplinary Approach, Addison-Wesley, 2008
• Christian Ullenboo, Java ist auch eine Insel,http://openbook.galileocomputing.de/javainsel/
• Guido Krüger, Heiko Hansen, Handbuch der Java-Programmierung Standard Edition Version 7, Addison-Wesley, 2011, http://www.javabuch.de
• Thomas Ottmann, Peter Widmayer, Algorithmen und Datenstrukturen, Springer, pdf derzeit auch online bei Springer
Folgende Links könnten Ihnen beim Erlernen der verwendeten Programmiersprache Java und als Nachschlagequellen hilfreich sein
• Pascal vs. Java
• Vergleich Pascal / C / Java
• Java Tutorial bei Oracle
• Java Language Specification

[ Computer Science Department | Computer Systems Institute | Native Systems Group ]