Dr. D. Komm, Dr. H.-J. Böckenhauer — Departement Informatik — HS 2020

Digitale Medizin I: Einführung in die Programmierung

Inhalt

Diese Veranstaltung verfolgt zwei Ziele. Zum einen wird am Beispiel von Python eine Einführung in die Programmierung gegeben, in der die grundlegenden Konzepte der Programmierung wie Wahrheitswerte, Variablen, Datentypen, Bedingungsprüfungen, Schleifen und Funktionen vorgestellt werden.

Zum anderen werden die grundlegenden Datenstrukturen (wie Stacks, Queues und Suchbäume) und wichtige Ideen des Algorithmenentwurfs vorgestellt und in Python implementiert, um auf diesen Datenstrukturen grundlegende algorithmische Aufgaben effizient zu lösen.

Ein Schwerpunkt liegt dabei auf allgemein einsetzbaren Entwurfsmethoden für effiziente Algorithmen wie Greedy-Verfahren, dynamische Programmierung oder Divide-and-Conquer-Strategien, die mit vielen praxisnahen Beispielen vorgestellt werden.

Informationen zur Prüfung

Probeprüfung

Am 3. Dezember, also eine Woche vor der Prüfung, fand eine Probeprüfung statt.

Inhalt der Prüfung

Die folgende Liste gibt eine Übersicht über wesentliche Begriffe und Konzepte hinsichtlich einer Vorbereitung auf die Prüfung am Ende der Vorlesung.

Sie erhebt keinen Anspruch auf Vollständigkeit.

Es werden keine Fragen zu den Modulen numpy, matplotlib und pandas gestellt.

Beispielaufgaben für die Prüfung

Die Aufgaben der Prüfung können jeweils mit wenig Text beantwortet werden. Es wird verschiedene Aufgabentypen geben, die im Folgenden besprochen werden. Im Wesentlichen geht es darum, dass Sie Code lesen und seine Funktionalität verstehen können. Dies bedeutet, dass Sie beispielsweise angeben sollen, was ein gezeigtes Programm ausgibt, oder Fehler in diesem finden sollen. Auch wird es Programme geben, die Lücken enthalten, die Sie ergänzen sollen. Für andere Programme werden Sie nach oberen Schranken für die Komplexität in O-Notation gefragt. Es können auch inhaltliche Fragen kommen, in denen Sie in zwei bis drei Sätzen zeigen sollen, dass Sie ein in der Vorlesung besprochenes Verfahren bzw. einen Algorithmus verstanden haben, z.B. im Zusammenhang mit Suchen und Sortieren.

Auch die folgende Liste erhebt keinen Anspruch auf Vollständigkeit.

Aufgaben-Typ 1 (Code nachvollziehen und Ausgabe angeben).
Betrachten Sie folgenden Code.

1
x = 1

2

3
def f(x):

4
x += 2

5
return x

6

7
x = 6

8

9
if x != False and (True or not f(1) == 1):

10
print(True)

11
else:

12
print(False)
Was ist die Ausgabe? (Lösung anzeigen.)

Aufgaben-Typ 2 (Code und Lückentexte).
Die folgende Funktion reverse_list soll die Reihenfolge der Elemente einer Liste data vertauschen.

1
def reverse_list(data):

2
half = (len(data)-1) // 2

3
for i in range(0, half + 1):

4
tmp =

5

6

7
return data
Füllen Sie Zeilen 4, 5 und 6 aus. (Lösung anzeigen.)

Aufgaben-Typ 3 (Fehlersuche).
Die folgende Funktion enthält einen Fehler. Sie soll die Summe aller Zahlen einer Liste berechnen oder -1 zurückgeben, falls die Liste leer ist.

1
def listsum(data):

2
if len(data) = 0:

3
return -1

4
else:

5
sum_so_far = 0

6
for item in data:

7
sum_so_far += item

8
return sum_so_far
Geben Sie die entsprechende Zeilennummer an und erklären Sie in einem Satz, worin der Fehler besteht und wie er korrigiert werden kann. (Lösung anzeigen.)

Aufgaben-Typ 4 (Komplexität).
Betrachten Sie die folgende Funktion, die 3n für eine gegebene natürliche Zahl n berechnet.

1
def expo(n):

2
i = 1

3
res = 1

4
while i <= n:

5
res *= 3

6
i += 1

7
return res
Wie gross ist die Zeitkomplexit√§t in O-Notation bezüglich n? Verwenden Sie hierfür das Einheitskostenmodell, das heisst, dass insbesondere jede arithmetische Operationen Kosten von 1 verursacht. (Lösung anzeigen.)

Aufgaben-Typ 5 (Inhaltliche Fragen).
Wir wollen die folgende Liste mit Bubblesort sortieren:

data = [8, 6, 1, 9, 10, 4, 2]
(Lösung anzeigen.)

Organisation

Ab dem 29.10. wird die Vorlesung als Distanzunterricht per Zoom durchgeführt. Den Link zur Vorlesung haben alle Studierenden per E-Mail erhalten.

Übungsbetrieb

Während des Semesters erhalten Sie kleinere Projekte, die Sie selbstständig bearbeiten sollen. Die Ergebnisse präsentieren Sie während der √úbungsstunden einer bzw. einem Assistierenden. Dies geschieht online per Zoom. Bitte stellen Sie sicher, dass Sie dieses installiert haben und es nutzen können.

Sie erhalten Feedback zu Ihrer Präsentation, jedoch fliesst die Bewertung nicht in die Endnote ein. Das Bearbeiten der Projekte ist dennoch obligatorisch, allerdings müssen Sie nicht zu den Übungssessions erscheinen; diese sind gedacht, um allfällige Fragen zu beantworten und die Projektpräsentationen online durchzuführen.

Für die Präsentationen werden Sie sich über das PELE-System anmelden. Die Präsentationen können in Zweiergruppen gehalten werden und dauern ca. 15 Minuten.

Agenda und Material

An dieser Stelle werden konkrete Informationen zum Vorlesungsinhalt veröffentlicht. Die Informationen werden während des Semesters laufend aktualisiert.

Datum, Raum Inhalt Unterlagen
01.10.2020, HG F 3
  • Einführung in die Vorlesung
  • Ein erstes Python-Programm
E.Tutorials Slides Handout Video
08.10.2020, HG F 3
  • Listen
  • Strings
  • Einfache Schleifen
Slides Handout Video
15.10.2020, HG F 3
  • Wahrheitswerte
  • Kontrollstrukturen
  • while-Schleifen
Slides Handout Video Algorithmen
21.10.2020, HG F 5
  • Funktionen
  • Rückgabewerte
Slides Handout Video Algorithmen
22.10.2020, HG F 3
  • Scope und Lifetime von Variablen
  • Lokale und globale Variablen
  • Komplexität von Algorithmen
  • Primzahltest
Slides Handout Video Algorithmen
29.10.2020, Online
  • Worst-Case-Analyse
  • 2-Dimensionale Listen
  • Daten einlesen
  • Bubblesort
  • Minsort
Slides Handout Video Algorithmen
12.11.2020, Online
  • Stacks and Queues
  • Mergesort
  • Bucketsort
Slides Handout Video Algorithmen
19.11.2020, Online
  • List Comprehensions
  • Das Modul numpy
  • Das Modul matplotlib
  • Informationen zur Prüfung
Slides Handout Video Algorithmen
26.11.2020, Online
  • Das Modul pandas
  • Lineare Suche
  • Binäre Suche
Slides Handout Video Algorithmen
03.12.2020, Online
  • Probeprüfung
  • Dynamische Programmierung
Slides Handout Video Algorithmen
10.12.2020, Online
  • Prüfung
17.12.2020, Online
  • Hidden-Markov-Modelle
  • Viterbi-Algorithmus
Slides Handout Video Algorithmen