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:

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.

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.

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

1
def rec_sum(n):

2
if n = 1:

3
return 1

4
else:

5
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 folgende Funktionen für die Klasse.

(Lösung anzeigen.)

Aufgaben-Typ 5 (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 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]
(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.

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:

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

Die folgenden Angaben sind unter Vorbehalt.

Agenda und Material

Datum Inhalt Unterlagen
25.02.2021
  • Einführung in die Vorlesung (Inhalt und Organisation)
  • Ein erstes Python-Programm
Slides Handout Videoaufzeichnung Links
04.03.2021
  • Einfache Schleifen
  • Listen
  • Strings
  • Cäsar-Verschlüsselung
Slides Handout Videoaufzeichnung Algorithmen
11.03.2021
  • Wahrheitswerte
  • Kontrollstrukturen
  • while-Schleifen
Slides Handout Videoaufzeichnung Algorithmen
18.03.2021
  • Funktionen
  • Lokale und globale Variablen
  • Scope und Lifetime
  • Shadowing
Slides Handout Videoaufzeichnung Algorithmen
25.03.2021
  • Komplexität von Algorithmen
  • Gross-O-Notation
  • Deterministischer Primzahltest
  • Randomisierter Primzahltest
Slides Handout Videoaufzeichnung Algorithmen
01.04.2021
  • Daten einlesen
  • Bubblesort
  • Minsort
Slides Handout Videoaufzeichnung Algorithmen
15.04.2021
  • Stacks und Queues
  • Mergesort
  • Bucketsort
Slides Handout Videoaufzeichnung Algorithmen
22.04.2021
  • List Comprehensions und Slicing
  • Namespaces
  • Das Modul numpy
  • Das Modul matplotlib
  • Das Modul pandas
Slides Handout Videoaufzeichnung Algorithmen
29.04.2021
  • Lineare Suche
  • Binäre Suche
  • Rekursive Algorithmen
  • Rekursive binäre Suche
Slides Handout Videoaufzeichnung Algorithmen
06.05.2021
  • Rekursives Mergesort
  • Rekursives Quicksort
  • Dictionarys
  • Die Fibonacci-Zahlen
  • Memoization
  • Dynamische Programmierung
Slides Handout Videoaufzeichnung Algorithmen
20.05.2021
  • Objektorientierte Programmierung
  • Heaps
  • Heapsort
Slides Handout Videoaufzeichnung Algorithmen
27.05.2021
  • Graphen
  • Adjazenzmatrizen
  • Adjazenzlisten
  • Breitensuche mit einer Queue
  • Tiefensuche mit einem Stack
  • Rekursive Tiefensuche
Slides Handout Videoaufzeichnung Algorithmen
03.06.2021
  • Schriftliche Prüfung