Dr. D. Komm — Departement Informatik — FS 2021

Programmieren und Problemlösen

Inhalt

Diese Vorlesung stellt eine Einführung in die Programmierung mit Python und das Problemlösen mittels Standard-Algorithmen und -Datenstrukturen dar. Ausserdem werden die Python-Module numpy, matplotlib und pandas vorgestellt. Folgende Themen bilden die Schwerpunkte:

Repetition von grundlegenden Programmierkonzepten wie Variablen, Listen, Kontrollstrukturen und Schleifen,
das Einlesen und Darstellen von Daten,
eine Einführung in die Komplexitätstheorie,
Sortieren und Suchen,
Dynamische Programmierung,
Rekursion und
Graph-Algorithmen.

Prüfung

Die Prüfung findet am 03.06.2021 während der Vorlesungszeit statt. Nähere Informationen finden Sie im Moodle-Forum.

Probeprüfung

Um die Gestalt der Prüfung zu sehen, stehen Ihnen hier eine Probeprüfung und deren Lösung zur Verfügung.

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.

Sie haben noch nicht alle Begriffe in der Vorlesung kennengelernt.

Grundbefehle von Python
Grundlagen der vorgestellten Algorithmen und deren Komplexität
Arithmetische Grundoperationen wie % und //
Speichern und Verwalten von Daten in einfachen Variablen, Listen, Strings und Dictionarys
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
Die Konzepte der Memoization, dynamischer Programmierung und Divide-und-Conquer
Funktionsweise und Verwendung von rekursiver Programmierung
Klassen und Objekte aus gegebenen Daten erstellen
Repräsentation von Graphen als Adjazenzmatrizen und -listen und Arbeiten mit ihnen

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 müssen. Für andere Programme werden Sie nach oberen Schranken für die Komplexität in O-Notation gefragt. Ein weiterer Aufgabentyp besteht darin, Klassen zum Abbilden gewisser Daten zu entwerfen. 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.

Sie haben noch nicht alle Begriffe und Konzepte in der Vorlesung kennengelernt.

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 rekursive Funktion, welche die Summe der ersten n natürlichen Zahlen berechnen soll, enthält einen Fehler.

def rec_sum(n):

if n = 1:

return 1

else:

return n + rec_sum(n-1)

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 (Klassen-Design).
Wir wollen eine Datenstruktur erstellen, die ein Girokonto repräsentiert, auf das Geld ein- und von dem Geld ausgezahlt werden kann und dessen aktuellen Stand man auslesen kann.

Schreiben Sie eine entsprechende Klasse Account
Diese soll einen Konstruktor besitzen, der einen Parameter balance übergeben bekommt. In der entsprechenden Variablen soll der momentane Kontostand gespeichert werden.

Schreiben Sie folgende Funktionen für die Klasse.

Eine Funktion deposit(), die eine Zahl als Parameter erhält, die dem Wert entspricht, der eingezahlt werden soll. Der Wert von balance soll entsprechend angepasst werden.
Eine Funktion disburse(), die eine Zahl als Parameter erhält, mit der der entsprechende Wert ausgezahlt wird. Der Wert von balance soll wieder entsprechend angepasst werden.
Eine Funktion get_balance(), die den aktuellen Wert von balance ausgibt und ausserdem eine Warnung, wenn dieser negativ ist.

(Lösung anzeigen.)

Aufgaben-Typ 5 (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 Zeitkomplexitä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 6 (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.)

Organisatorisches

Die Vorlesung findet bis auf Weiteres online statt und wird per Zoom gestreamt. Videoaufzeichnungen aller Vorlesungen werden auf dieser Seite jeweils wenige Tage nach der Übertragung zur Verfügung gestellt.

Wir programmieren während der Vorlesung gemeinsam kleinere Algorithmen. Hierzu wird Ihnen jeweils auf der Plattform Code-Expert eine Sandbox zur Verfügung gestellt. Alternativ können Sie die Plattform WebTigerJython verwenden (achten Sie darauf, dass Sie im Menü rechts Python 3 eingestellt haben).

Für die Login-Daten für die Videos und weitere Fragen steht Ihnen in unserem Moodle-Kurs ein Forum zur Verfügung.

Ü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 22.03.2021: pplExercises_01_de.pdf; Lösungen: pplSolutions_01_de.pdf.
Übungsblatt 2: “Verzweigungen und Funktionen”, veröffentlicht am 05.04.2021: pplExercises_02_de.pdf; Lösungen: pplSolutions_02_de.pdf.
Übungsblatt 3: “Komplexität von Algorithmen”, veröffentlicht am 19.04.2021: pplExercises_03_de.pdf; Lösungen: pplSolutions_03_de.pdf.
Übungsblatt 4: “Listen”, veröffentlicht am 03.05.2021: pplExercises_04_de.pdf; Lösungen: pplSolutions_04_de.pdf.
Übungsblatt 5: “Rekursion”, veröffentlicht am 17.05.2021: pplExercises_05_de.pdf; Lösungen: pplSolutions_05_de.pdf.

Projekte

Während des Semester bearbeiten Sie kleinere Projekt, die auf Code-Expert veröffentlicht werden. Sie bearbeiten diese Projekte in Zweierteams und präsentieren Ihre Ergebnisse online einer Assistenzperson. Hierzu buchen Sie einen Termin für die folgenden Zeiten:

Montags: 13:00 bis 15:00 Uhr
Donnerstags: 10:00 bis 12:00 Uhr

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

Die folgenden Angaben sind unter Vorbehalt.

Projekt 1: “Monoalphabetische Verschlüsselung und Prüfsummen”, veröffentlicht am 19.03.2021, Abgabe bis zum 15.04.2021.
Projekt 2: “Eigenschaften von Listten”, veröffentlicht am 16.04.2021, Abgabe bis zum 06.05.2021.
Projekt 3: “Covid-19-Datenbank”, veröffentlicht am 07.05.2021, Abgabe bis zum 27.05.2021.

Agenda und Material

Datum	Inhalt	Unterlagen
25.02.2021	Einführung in die Vorlesung (Inhalt und Organisation) Ein erstes Python-Programm	Slides pplSlides_01_de.pdf pplSlides_01_en.pdf Handout pplHandout_01_de.pdf pplHandout_01_en.pdf Videoaufzeichnung pplVideo_01_de.mp4 Links Code-Expert Für Interessierte: Turing-Vollständigkeit
04.03.2021	Einfache Schleifen Listen Strings Cäsar-Verschlüsselung	Slides pplSlides_02_de.pdf pplSlides_02_en.pdf Handout pplHandout_02_de.pdf pplHandout_02_en.pdf Videoaufzeichnung pplVideo_02_de.mp4 Algorithmen caesar.py caesar2.py
11.03.2021	Wahrheitswerte Kontrollstrukturen while-Schleifen	Slides pplSlides_03_de.pdf pplSlides_03_en.pdf Handout pplHandout_03_de.pdf pplHandout_03_en.pdf Videoaufzeichnung pplVideo_03_de.mp4 Algorithmen collatz.py
18.03.2021	Funktionen Lokale und globale Variablen Scope und Lifetime Shadowing	Slides pplSlides_04_de.pdf pplSlides_04_en.pdf Handout pplHandout_04_de.pdf pplHandout_04_en.pdf Videoaufzeichnung pplVideo_04_de.mp4 Algorithmen cookiecalc.py
25.03.2021	Komplexität von Algorithmen Gross-O-Notation Deterministischer Primzahltest Randomisierter Primzahltest	Slides pplSlides_05_de.pdf pplSlides_05_en.pdf Handout pplHandout_05_de.pdf pplHandout_05_en.pdf Videoaufzeichnung pplVideo_05_de.mp4 Algorithmen primetest.py primetest2.py primetest3.py
01.04.2021	Daten einlesen Bubblesort Minsort	Slides pplSlides_06_de.pdf pplSlides_06_en.pdf Handout pplHandout_06_de.pdf pplHandout_06_en.pdf Videoaufzeichnung pplVideo_06_de.mp4 Algorithmen readfile.py readfile2.py bubblesort.py minsort.py
15.04.2021	Stacks und Queues Mergesort Bucketsort	Slides pplSlides_07_de.pdf pplSlides_07_en.pdf Handout pplHandout_07_de.pdf pplHandout_07_en.pdf Videoaufzeichnung pplVideo_07_de.mp4 Algorithmen mergesort.py bucketsort.py
22.04.2021	List Comprehensions und Slicing Namespaces Das Modul numpy Das Modul matplotlib Das Modul pandas	Slides pplSlides_08_de.pdf pplSlides_08_en.pdf Handout pplHandout_08_de.pdf pplHandout_08_en.pdf Videoaufzeichnung pplVideo_08_de.mp4 Algorithmen primelist.py anim_bubblesort.py complex_bubblesort.py luftmessungen.py
29.04.2021	Lineare Suche Binäre Suche Rekursive Algorithmen Rekursive binäre Suche	Slides pplSlides_09_de.pdf pplSlides_09_en.pdf Handout pplHandout_09_de.pdf pplHandout_09_en.pdf Videoaufzeichnung pplVideo_09_de.mp4 Algorithmen binsearch.py anim_binsearch.py rec_euclid.py rec_binsearch.py
06.05.2021	Rekursives Mergesort Rekursives Quicksort Dictionarys Die Fibonacci-Zahlen Memoization Dynamische Programmierung	Slides pplSlides_10_de.pdf pplSlides_10_en.pdf Handout pplHandout_10_de.pdf pplHandout_10_en.pdf Videoaufzeichnung pplVideo_10_de.mp4 Algorithmen rec_mergesort.py rec_quicksort.py fibonacci.py alignment.py
20.05.2021	Objektorientierte Programmierung Heaps Heapsort	Slides pplSlides_11_de.pdf pplSlides_11_en.pdf Handout pplHandout_11_de.pdf pplHandout_11_en.pdf Videoaufzeichnung pplVideo_11_de.mp4 Algorithmen Coordinate.py erdbeben-db.py student-db.py Heap.py heapsort.py
27.05.2021	Graphen Adjazenzmatrizen Adjazenzlisten Breitensuche mit einer Queue Tiefensuche mit einem Stack Rekursive Tiefensuche	Slides pplSlides_12_de.pdf pplSlides_12_en.pdf Handout pplHandout_12_de.pdf pplHandout_12_en.pdf Videoaufzeichnung pplVideo_12_de.mp4 Algorithmen BFS_lst.py BFS_mtr.py DFS_lst.py DFS_mtr.py DFS_rec.py coloring.py find_cycle.py
03.06.2021	Schriftliche Prüfung