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

Die Prüfung findet statt am 10. Dezember um 8:15 Uhr
Die Prüfungszeit beträgt 60 Minuten
Die Teilnahme ist obligatorisch
Sie werden die Prüfung als PDF erhalten, welches Sie auf dem Bildschirm betrachten können
Sie sind gleichzeitig per Zoom verbunden und Ihre Webcam ist aktiviert
Die Prüfung wird mit Stift und Papier bearbeitet
Es sind keine weiteren Hilfsmittel erlaubt
Sie scannen Ihre Lösung mit Ihrem Smartphone ein und schicken sie uns per Mail
Weitere Informationen zum Prüfungsmodus finden Sie hier.
Beachten Sie auch unbedingt den hier verlinkten Leitfaden.

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.

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.)

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.

Die Vorlesung findet donnerstags von 8–10 Uhr statt.
Beachten Sie: Am 5. November findet keine Vorlesung statt, dafür am Mittwoch, dem 21. Oktober, von 14–16 Uhr.
Für Fragen stehen Ihnen die Assistierenden
- dienstags von 10–12 Uhr und
- donnerstags von 10–12 Uhr
zur Verfügung. Ihre Ergebnisse präsentieren Sie einem bzw. einer Assistierenden per Zoom während dieser Zeiten. Weiter unten folgenden detailiertere Informationen.
Details zur Prüfung werden hier rechtzeitig bekanntgegeben.

Ü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.

Projekt 1: Monoalphabetische Verschlüsselung, Veröffentlichung am 15.10., Abgabe bis 29.10.
Projekt 2: Arbeiten mit Listen, Veröffentlichung am 29.10., Abgabe bis 18.11.
Projekt 3: Fallzahlen-Analyse der aktuellen Covid-19-Pandemie, Veröffentlichung am 18.11., Abgabe bis 17.12.

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 Installation von PyCharm Einführung in Python Slides digiMedSlides_01_de.pdf digiMedSlides_01_en.pdf Handout digiMedHandout_01_de.pdf digiMedHandout_01_en.pdf Video digiMedVideo_01_de.mp4
08.10.2020, HG F 3	Listen Strings Einfache Schleifen	Slides digiMedSlides_02_de.pdf digiMedSlides_02_en.pdf Handout digiMedHandout_02_de.pdf digiMedHandout_02_en.pdf Video digiMedVideo_02_de.mp4
15.10.2020, HG F 3	Wahrheitswerte Kontrollstrukturen while-Schleifen	Slides digiMedSlides_03_de.pdf digiMedSlides_03_en.pdf Handout digiMedHandout_03_de.pdf digiMedHandout_03_en.pdf Video digiMedVideo_03_de.mp4 Algorithmen caesar.py caesar2.py
21.10.2020, HG F 5	Funktionen Rückgabewerte	Slides digiMedSlides_04_de.pdf digiMedSlides_04_en.pdf Handout digiMedHandout_04_de.pdf digiMedHandout_04_en.pdf Video digiMedVideo_04_de.mp4 Algorithmen cookiecalc.py
22.10.2020, HG F 3	Scope und Lifetime von Variablen Lokale und globale Variablen Komplexität von Algorithmen Primzahltest	Slides digiMedSlides_05_de.pdf digiMedSlides_05_en.pdf Handout digiMedHandout_05_de.pdf digiMedHandout_05_en.pdf Video digiMedVideo_05_de.mp4 Algorithmen primetest.py primetest2.py primetest3.py
29.10.2020, Online	Worst-Case-Analyse 2-Dimensionale Listen Daten einlesen Bubblesort Minsort	Slides digiMedSlides_06_de.pdf digiMedSlides_06_en.pdf Handout digiMedHandout_06_de.pdf digiMedHandout_06_en.pdf Video digiMedVideo_06_de.mp4 Algorithmen readfile.py readfile2.py bubblesort.py minsort.py
12.11.2020, Online	Stacks and Queues Mergesort Bucketsort	Slides digiMedSlides_07_de.pdf digiMedSlides_07_en.pdf Handout digiMedHandout_07_de.pdf digiMedHandout_07_en.pdf Video digiMedVideo_07_de.mp4 Algorithmen mergesort.py bucketsort.py
19.11.2020, Online	List Comprehensions Das Modul numpy Das Modul matplotlib Informationen zur Prüfung	Slides digiMedSlides_08_de.pdf digiMedSlides_08_en.pdf Handout digiMedHandout_08_de.pdf digiMedHandout_08_en.pdf Video digiMedVideo_08_de.mp4 Algorithmen primelist.py anim_bubblesort.py complex_bubblesort.py
26.11.2020, Online	Das Modul pandas Lineare Suche Binäre Suche	Slides digiMedSlides_09_de.pdf digiMedSlides_09_en.pdf Handout digiMedHandout_09_de.pdf digiMedHandout_09_en.pdf Video digiMedVideo_09_de.mp4 Algorithmen luftquali.py binsearch.py complex_binsearch.py
03.12.2020, Online	Probeprüfung Dynamische Programmierung	Slides digiMedSlides_10_de.pdf digiMedSlides_10_en.pdf Handout digiMedHandout_10_de.pdf digiMedHandout_10_en.pdf Video digiMedVideo_10_de.mp4 Algorithmen alignment.py
10.12.2020, Online	Prüfung
17.12.2020, Online	Hidden-Markov-Modelle Viterbi-Algorithmus	Slides digiMedSlides_11_de.pdf digiMedSlides_11_en.pdf Handout digiMedHandout_11_de.pdf digiMedHandout_11_en.pdf Video digiMedVideo_11_de.mp4 Algorithmen viterbi.py