Informatik II - FS 18

Vorlesungsverzeichnis: 252-0845-00L
Dozenten: Felix Friedrich, Hermann Lehner

Neuigkeiten

Datum Mitteilung
18.6.2018 Prüfung vom Januar 2018 online
28.6.2018 Lösung Prüfung Januar 2018 online

Termine

Vorlesung Montag 12:45-14:30 HIL E 3
Übungen Donnerstag 12:45-14:30, 14:45-16:30 Verschiedene Räume

Lernziel und Überblick

Wir behandeln gängige Datenstrukturen und Algorithmen und Prinzipien für das Design und die Nutzung relationaler Datenbanken.

Es wird generell das formale Denken und Notwendigkeit zur Abstraktion, sowie die Bedeutung geeigneter Modellbildungen für die Informatik motiviert. Der Schwerpunkt der Vorlesung liegt auf der praktischen Informatik. Konkrete Themen sind u.a.: Komplexität von Algorithmen, Divide and Conquer-Prinzip, Rekursion, Sortieralgorithmen, Backtracking, Datenstrukturen (Listen, Stacks, Warteschlangen, binäre Bäume).

Die Konzepte der Vorlesung werden jeweils durch Algorithmen und Anwendungen motiviert und illustriert. Verwendete Programmiersprache in der Vorlesung und den praktischen Übungen ist Java.

Für das effiziente Praktizieren der vorgestellten Inhalte wird in den Übungen ein Online-Compiler mit Abgabesystem verwendet.

Codeboard IDE Sandbox

Um eigene Programme auszuprobieren, empfehlen wir folgendes Sandbox Projekt:

Sandbox Öffnen

Slack Channel

Hier können Sie Fragen an alle richten und Feedback geben:

Slack Channel

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.

Zeitplan, Folien und Übungen

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

Woche Datum Thema Vorlesung Übung PPrerequisites to unlock bonus exercises BBonus exercises
1 19.02. Einführung. Begriff des Algorithmus, Beispiel: Altägyptische Multiplikation
Komplexität. Random Access Machine Model, Effizienz von Algorithmen, Asymptotik: O-Notation, Omega, Theta
 Organisation (english)
Folien 1 (en)
Handout 1 (en) 		Einschreibung Uebungen
Asymptotics (Theory). Artificial Words
Folien (english) 		Ant Algorithm
2 26.02. Suchen und Auswählen. Lineare Suche, Binäre Suche, Divide and Conquer, untere Schranken, Das Auswahlproblem, Randomisierte Berechnung des Medians Folien 2 (en)
Handout 2 (en) 		Recursive Function Analysis, Throwing Eggs, Binary Search, Hottest Path, Quickselect
Folien (english)
3 05.03. Sortieren Einfache Sortieralgorithmen, Mergesort und Quicksort Folien 3 (en)
Handout 3 (en) 		Compare Sort Algortihms, Online Mean , MergeSort Bonus exercise: Ant-Algorithm (Shortest Path)
Folien (english) 		Ant algorithm
4 12.02. Java I/O Files und Exceptions
Streams Das Java Streams API 		Folien 4 (en)
Handout 4 (en)
Code Beispiele 		Using the scanner, input from a file, parse a CSV file and sort earth quake data by several criteria.
Folien (english) Fruits Beispiel 		Heap Datastructures
5 19.03. Streams II (Slides von letzter Woche)
Elementare Datenstrukturen Repetition aus Informatik I + Effizienzbetrachtungen 		Folien 5 (en)
Handout 5 (en)
Code Beispiele (Streams) 		Functional Programming: prime numbers, furthest coordinate, sorting strings from imperative to functional
Folien (english)
6 26.03. Wörterbücher I Natürliche Suchbäume, Balancierte Bäume (konzeptuell), Heaps Folien 6 (en)
Handout 6 (en) 		Insertions and Deletions in Binary Trees, Min-/Max-Heaps, siftDown and siftUp Method for Heaps
Folien (english) 		Streams and Heaps
-- 02.04. -- --Ostern-- --Ostern-- Shortest Paths
7 09.04. Wörterbücher II Prinzip des Hashing, Hashfunktionen, Kollisionsauflösung durch Verkettung, offene Hashverfahren Folien 7 (en)
Handout 7 (en) 		Open Hashing, Cuckoo Hashing, Sliding window hash functions for String Searching
Folien (english)
-- 16.04. -- --Sechseläuten-- Self-Assessment (Solution)
Debugging in Codeboard
8 23.04. Graphen Notation und Repräsentations, Traversieren (DFS, BFS), Topologisches Sortieren Folien 8 (en)
Handout 8 (en) 		Topological Sorting, DFS and BFS, BFS Shortest Paths
Folien (english)
9 30.04. Graphen Kürzeste Wege Folien 9 (en)
Handout 9 (en) 		Dijkstra's Algorithm, Shortest Paths and Distances, Priority Queues
Folien (english) 		Shortest Paths Graph
10 07.05. Graphen Flüsse in Graphen Folien 10 (en)
Handout 10 (en) 		Flow application: Football Championship
-- Auffahrt (keine Übungsstunde) --
11 14.05. Datenbanken Folien 11
Handout 11 		ETutorial SQLite
and Instructions (read me!)
-- 21.05. -- --Pfingsten-- SQLite Project (register until May 22!)
12 28.05. Datenbanken Folien 12
Handout 12 		VBZ Hotspots - Visualisierung (Java & SQL)
Java Projekt (Sourcen)
Ausführbares JAR file (braucht Java 8)

Übungen

Einschreibung für die Übungen

Die Einschreibung zum Übungssystem erfolgt online. Weitere Informationen während der ersten Vorlesung.

Orte und Zeiten

Die Übungsgruppen sind derzeit wie folgt zugeteilt:
Zeit Assistent Ort Sprache
Donnerstag 13-15 Max Rossmannek HIT F 12deutsch
Donnerstag 13-15 Patrick Gruntz HIT F 13 deutsch
Donnerstag 13-15 Chris Wendler HIT F 31.1 deutsch
Donnerstag 17-19 Andreea Ciuprina CAB G 52 (Zentrum) deutsch

Chefassistenz

Andreas Baertschi

Literatur

Wir versuchen, den Kurs grundsätzlich selbsterklärend zu gestalten. Trotzdem lohnt sich es sich natürlich immer, auch andere Quellen heranzuziehen.
  • Hanspeter Mössenböck, Sprechen Sie Java?, dpunkt Verlag, 5. Auflage 2014.
  • Robert Sedgewick, Kevin Wayne, Einführung in die Programmierung mit Java. Pearson, 2011
  • Thomas Ottmann, Peter Widmayer, Algorithmen und Datenstrukturen, Springer, auch online
  • T. Cormen, C. Leiserson, R. Rivest, C. Stein, Algorithmen - Eine Einführung, Oldenbourg, 2010
  • Kemper, Eickler: Datenbanksysteme: Eine Einführung. Oldenbourg Verlag, 9. Auflage, 2013
Folgende Links könnten Ihnen beim Erlernen der verwendeten Programmiersprache Java und als Nachschlagequellen hilfreich sein

Zur Prüfung

Modus

Prüfungsstoff für die Endprüfung, welche in der Prüfungssession Sommer 2018 stattfinden wird, schliesst Vorlesungsinhalt und Übungsinhalte ein.

Die Prüfung ist schriftlich. Erlaubte Hilfsmittel: Vier A4 Seiten (zwei A4 Blätter), handgeschrieben oder min. Fontgrösse 11 Pkt.

Vergangene Prüfungen