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

Informatikgrundlagen für Humanmedizin

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

Die Prüfung findet statt am 16. Dezember um 8:15 Uhr
Die Prüfungszeit beträgt 60 Minuten
Die Teilnahme ist obligatorisch
Die Prüfung wird mit Stift und Papier bearbeitet
Es sind keine weiteren Hilfsmittel erlaubt
Die Aufteilung auf die Räume erfolgt alphabetisch nach Nachnamen:
- A-F: HG D 7.1
- G-P: HG D 7.2
- R-Z: HG G 3

Probeprüfung und Prüfung

Die folgende Probeprüfung gibt eine Idee über den Inhalt und die Form der Prüfung.

Hier finden Sie die tatsächliche Prüfung.

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.

Grundbefehle von Python
Grundlagen der vorgestellten Algorithmen und deren Komplexität
Arithmetische Grundoperationen wie % und //
Speichern und Verwalten von Daten in einfachen Variablen, Listen und Strings
Funktionsweise und Verwendung von List-Comprehensions
Funktionsweise und Verwendung von 2- und mehrdimensionalen Listen
Funktionsweise und Verwendung von Stacks und Queues
if-elif-else-Kontrollstrukturen und Boolesche Ausdrücke
while-Schleifen und break
for-Schleifen mit Listen-Elementen und Indizes mit range()
Komplexität von gegebenen Programmen, z.B. mit verschachtelten Schleifen, in O-Notation angeben
Funktionen und Rückgabe mit return
Globale und lokale Variablen, Scope, Lifetime und Shadowing
Das Konzept von Divide-and-Conquer

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.

x = 1

def f(x):

x += 2

return x

x = 6

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

print(True)

else:

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.

def reverse_list(data):

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

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

tmp =

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.

def listsum(data):

if len(data) = 0:

return -1

else:

sum_so_far = 0

for item in data:

sum_so_far += item

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 3ⁿ für eine gegebene natürliche Zahl n berechnet.

def expo(n):

i = 1

res = 1

while i <= n:

res *= 3

i += 1

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]

Stellen Sie die erste Bubble-Sequenz dar, indem Sie angeben, wie die Liste jeweils nach den einzelnen Schritten der inneren Schleife aussieht.
Was gilt nach dieser ersten Bubble-Sequenz?
Wie ist die Komplexität von Bubblesort auf Listen mit n Elementen?
Macht es für die Anzahl der Vergleiche einen Unterschied, ob die Liste bereits sortiert ist?
Macht es für die Anzahl der Vertauschungen einen Unterschied, ob die Liste bereits sortiert ist?

(Lösung anzeigen.)

Durchführung der Vorlesung

Die Vorlesung findet bis auf Weiteres in Präsenz statt, wird aber gleichzeitig gestreamt (siehe unten). Zusätzlich stehen für Fragen Übungsstunden zur Verfügung.

Vorlesung: donnerstags, 8–10, Raum HG D7.2
Übungsstunde 1: donnerstags, 10–12, Raum HG D7.2
Übungsstunde 2: mittwochs, 14–16, Raum CAB H56

Beachten Sie: Am 11. November findet keine Vorlesung statt, dafür am Mittwoch, dem 20. Oktober, von 14–16 Uhr.

Fragen zur Vorlesung

Für Fragen zur Organisation und zum Inhalt der Vorlesung verwenden Sie bitte unser Moodle-Forum.

Sie können ausserdem während der Übungsstunden online Fragen stellen. Hierzu steht Ihnen ein Zoom-Raum zur Verfügung, dessen Link Sie dem Moodle-Forum entnehmen.

Streams und Aufzeichnungen

Die Vorlesung wird live gestreamt und die Videos werden Ihnen danach zur Verfügung gestellt. Die Zugangsdaten zu den Streams und aufgezeichneten Vorlesungsvideos erhalten Sie in unserem Moodle.

Ü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 Code-Expert anmelden. Die Präsentationen können in Zweiergruppen gehalten werden und dauern ca. 15 Minuten.

Hier finden Sie eine Schritt-für-Schritt-Anleitung für die Abgabe der Projekte.

Projekt 1: «Monoalphabetische Verschlüsselung», veröffentlicht am 21.10.2021, Abgabe bis zum 18.11.2021.
Projekt 2: «Einfache Eigenschaften von Messdaten berechnen», veröffentlicht am 18.11.2021, Abgabe bis zum 16.12.2021.

Übungsblätter

Zusätzlich zu den Projekten veröffentlichen wir im 2-Wochen-Takt freiwillige Übungsblätter, die unterschiedliche Themen der Vorlesung vertiefen. Die Übungen werden nicht besprochen, allerdings werden jeweils eine Woche nach Veröffentlichung Lösungen veröffentlicht.

Übungsblatt 1: «Grundoperationen und Listen», veröffentlicht am 21.10.2021: infMedExercises_01_de.pdf; Lösungen: infMedSolutions_01_de.pdf.
Übungsblatt 2: «Verzweigungen und Funktionen», veröffentlicht am 04.11.2021: infMedExercises_02_de.pdf; Lösungen: infMedSolutions_02_de.pdf.
Übungsblatt 3: «Komplexität von Algorithmen», veröffentlicht am 18.11.2021: infMedExercises_03_de.pdf; Lösungen: infMedSolutions_03_de.pdf.
Übungsblatt 4: «Listen», veröffentlicht am 03.05.2021: infMedExercises_04_de.pdf; Lösungen: infMedSolutions_04_de.pdf.

Prüfung

Die Note der Vorlesung ergibt sich vollständig aus der Note einer 60-minütigen, schriftlichen Prüfung, die in den letzten Wochen des Semesters geschrieben wird. Wie oben erwähnt, ist Voraussetzung für die Teilnahme, dass Sie alle Projekte bearbeiten und präsentieren.

Agenda und Material

An dieser Stelle werden konkrete Informationen zum Vorlesungsinhalt veröffentlicht. Die Informationen werden während des Semesters laufend aktualisiert und sind unter Vorbehalt zu verstehen.

Datum, Raum	Inhalt	Unterlagen
07.10.2021, HG D7.2	Einführung in die Vorlesung Ein erstes Python-Programm	Slides infMedSlides_01_de.pdf infMedSlides_01_en.pdf Handout infMedHandout_01_de.pdf infMedHandout_01_en.pdf
14.10.2021, HG D7.2	Listen Strings Einfache Schleifen	Slides infMedSlides_02_de.pdf infMedSlides_02_en.pdf Handout infMedHandout_02_de.pdf infMedHandout_02_en.pdf
20.10.2021, ML F36	Cäsar-Verschlüsselung Wahrheitswerte Kontrollstrukturen while-Schleifen	Slides infMedSlides_03_de.pdf infMedSlides_03_en.pdf Handout infMedHandout_03_de.pdf infMedHandout_03_en.pdf Algorithmen caesar.py Links Präzedenzen
21.10.2021, HG D7.2	Funktionen Rückgabewerte	Slides infMedSlides_04_de.pdf infMedSlides_04_en.pdf Handout infMedHandout_04_de.pdf infMedHandout_04_en.pdf Algorithmen collatz.py cookiecalc.py
28.10.2021, HG D7.2	Scope und Lifetime von Variablen Lokale und globale Variablen Komplexität von Algorithmen Primzahltest	Slides infMedSlides_05_de.pdf infMedSlides_05_en.pdf Handout infMedHandout_05_de.pdf infMedHandout_05_en.pdf Algorithmen primetest.py primetest2.py primetest3.py
04.11.2021, HG D7.2	Worst-Case-Analyse 2-Dimensionale Listen Daten einlesen Bubblesort Minsort	Slides infMedSlides_06_de.pdf infMedSlides_06_en.pdf Handout infMedHandout_06_de.pdf infMedHandout_06_en.pdf Algorithmen readfile.py readfile2.py bubblesort.py minsort.py
18.11.2021, HG D7.2	Stacks and Queues Mergesort Bucketsort	Slides infMedSlides_07_de.pdf infMedSlides_07_en.pdf Handout infMedHandout_07_de.pdf infMedHandout_07_en.pdf Algorithmen mergesort.py bucketsort.py
25.11.2021, HG D7.2	List Comprehensions Das Modul numpy Das Modul matplotlib Informationen zur Prüfung	Slides infMedSlides_08_de.pdf infMedSlides_08_en.pdf Handout infMedHandout_08_de.pdf infMedHandout_08_en.pdf Algorithmen primelist.py anim_bubblesort.py
02.12.2021, HG D7.2	Visualisierung der Komplexität von Bubblesort Das Modul pandas	Slides infMedSlides_09_de.pdf infMedSlides_09_en.pdf Handout infMedHandout_09_de.pdf infMedHandout_09_en.pdf Algorithmen complex_bubblesort.py luftmessungen.py
09.12.2021, HG D7.2	Lineare Suche Binäre Suche Kadanes Algorithmus	Slides infMedSlides_10_de.pdf infMedSlides_10_en.pdf Handout infMedHandout_10_de.pdf infMedHandout_10_en.pdf Algorithmen binsearch.py complex_binsearch.py kadane.py
16.12.2021, HG D7.2	Schriftliche Prüfung
23.12.2021, HG D7.2	Jupyter-Notebooks Eine erste Einführung in Data Science für Humanmedizin	Jupyter-Notebooks clinical_example.ipynb introduction.ipynb Online-Version