Johannes Kepler Universität Linz
Altenberger Straße 69, 4040 Linz
Weitere Beispiele der Hochschule

Berechenbarkeit und Komplexität (Introduction to Computational Complexity)

Ziele/Motive/Ausgangslage/Problemstellung

*Ziel:* Als ich an die JKU kam, war mein erklärtes Ziel die theoretische Flanke des Informatikstudiums zu modernisieren und dort meine eigenen Impulse zu setzen. Die Vorlesung 'Berechenbarkeit und Komplexität' ist die einzige theoretische Pflichtveranstaltung in unserem Informatik-Bachelor und somit der ideale Fokuspunkt. Unser Ziele sind ein moderner Blick auf alle relevanten Themenbereiche der theoretischen Informatik, sowie Synergien mit anderen Informatik-Fächern (Logik, Algorithmen, Hardwaredesign). Eine sinnstiftende Abstimmung von Vorlesung und Übung ist uns ebenso wichtig wie über den Tellerrand zu blicken und auch unkonventionelle Themen anzusprechen. Schlussendlich sollten wir auch auf die persönlichen Motivation und Ausgangslage verschiedener Studierender eingehen. Die mathematiklastige theoretische Informatik muss kein Albtraumfach sein durch welches man sich irgendwie durchquält. Im Gegenteil, sie kann Denkschablonen für das grosse Ganze liefern, als Inspirationsquelle dienen und komplementäre Lösungsansätze liefern.

*Ausgangslage:* 'Berechenbarkeit und Komplexität' ist die einzige Theorieveranstaltung an der JKU. Das verlangt die Kompression von mehreren Semestern Stoff in eine einzige Veranstaltung. Zudem muss der so komprimierte Stoff für Informatikstudierende zugänglich gemacht werden, welche eine mittelmäßige mathematische Vorbildung und Begeisterung mitbringen. Zudem sind die Beliebtheitswerte bei den Studierenden traditionell schlecht.

Weiter unten, im Abschnitt 'Nähere Beschreibung des Projekts', erläutern wir die Ansätze welche es uns ermöglicht haben diese anspruchsvolle Ausgangslage in den Griff zu kriegen und einige scheinbare Nachteile sogar in *unique selling points* umzuwandeln. 

Kurzzusammenfassung des Projekts

Rechner wurden dazu entwickelt um, naja, zu rechnen. Aber nicht alle Rechenaufgaben sind gleich aufwändig. Manche sind einfach (z.b. multipliziere zwei grosse Primzahlen), aber andere scheinen viel schwieriger zu sein (z.b. faktorisiere ein Produkt von zwei grossen Primzahlen). In diesem Einführungskurs der theoretischen Informatik lernen die Studierenden wie man Fragen zu Berechenbarkeit (können wir 'etwas' berechnen?) und Komplexität (wie schwierig ist es, 'etwas' zu berechnen?) passend formuliert. Ein ausgeprägtes Verständnis ermöglicht es den Studierenden abzuschätzen ob eine spezifische Programmieraufgabe einfach oder untragbar schwierig ist. Schlussendlich werden wir genau diese Themen nochmal aus der Hardwareperspektive (Chips) betrachten. Dieser Perspektivenwechsel erlaubt es uns auch die drei Hauptsäulen der modernen Informatik konzeptionell zu vereinheitlichen: formale Logik, Software (Algorithmen) und Hardware (Chips) sind lediglich verschiedene Blickpunkte auf dieselbe Thematik.

In den Übungsstunden ergänzen wir die Vorlesung mit Gruppendiskussionen, peer-to-peer Interaktion und hands-on Erfahrung. Zudem werden wir 'special topic lectures' veranstalten. Dort blicken wir über den Tellerrand und diskutieren moderne und unkonventionelle Anwendungen des Vorlesungsstoffes. Beispiele sind Schwarm-Intelligenz, Bau eines funktionierenden Rechners in Minecraft, komplexitätstheoretische Erklärungen von Materialeigenschaften (z.b. Glas) und Quantencomputer.

Kurzzusammenfassung des Projekts in englischer Sprache

Computers have been developed to, well, compute things. But not all computational tasks are equally difficult. Some are easy (e.g. multiplying two large prime numbers), while others appear to be much harder (e.g. factorizing a product of two large prime numbers). In this introductory course for theoretical computer science, the students learn how to appropriately formalize questions about computability (can we actually compute something?) and computational complexity (how hard is it to compute something?). A firm grasp of these concepts will allow students to gauge whether a given computational task is easy, or likely to be prohibitively challenging. Finally, we will re-visit these topics through the lens of logical circuits. This does not only provide an alternative vantage point, but also allows us to unify the three main pillars of modern computer science: formal logic, software (algorithms) and hardware (circuits).

In the exercise classes, we complement the lecture with peer-to-peer interaction between students, group discussions and practical hands-on experience. The students learn how to apply complexity-theoretic arguments to reason about concrete problems. We also use half of the exercise classes to discuss modern implications of computational complexity to other scientific disciplines. These special topics lectures address swarm intelligence, building a computer in MineCraft, complexity-based explanations of material properties (e.g. glass) and quantum computing.

Nähere Beschreibung des Projekts

Kriterium 1: Innovative Hochschuldidaktik

Die grosse Informatik-Pflichtveranstaltung 'Berechenbarkeit und Komplexitaet' hat traditionell einen eher schlechten Ruf. Ich habe sie gemeinsam mit Sibylle Moehle-Rotondi (co-lecturer) und Nina Brandl (Tutorin) komplett neugestaltet. Die angehängten Evaluationen zeigen, dass unsere 'Teaching Innovation' von den Studierenden sehr geschätzt wurde. Besonders hervorgehoben wurde unser anglo-amerikanischer Zugang zur Wissensvermittlung, den ich mir als Lecturer am Caltech (USA) angeeignet hatte (in Englischer Sprache):

(a) concrete motivating examples

(b) prioritize high-level understanding

(c) emphasize synergies with other topics

(d) encourage cooperation & independent thought

(e) cater to different student goals

(f) approachability

Ein weiteres wichtiges Leitmotiv sind *equal opportunities*. Es ist kein Zufall, dass zwei Drittel unseres Teams weiblich sind: weibliche role models sind in der Informatik wichtiger denn je. Der automatisierte Prüfungsmodus dient unter anderem auch dazu, subconscious bias zu verhindern.

Kriterium 2: Studierendenzentrierte Lehre

Die 150-200 Studierenden aus Informatik (Pflichtfach), AI, ELIT und Mathematik (Wahlfach) haben extrem diverse Hintergründe, Herangehensweisen und Antriebsgründe. Das macht *catering to different student goals* zu einer wichtigen Challenge, welche wir mit folgenden Ansätzen bewältigen:

(a) Der Vorlesungsstoff ist in einem selbstverfasstes Skript (150 Seiten, angehängt) zusammengefasst. Dieses Script ermöglicht das unabhängige Selbststudium im eigenen Tempo.

(b) Komplementär dazu nutzen wir den Übungsbetrieb für den direkten Informationsaustausch zwischen Studierenden (peer-to-peer).

(c) Transparenter und automatisierter Klausurmodus, der der theoretischen Führerscheinprüfung nachempfunden ist. Moodle erlaubt es 36 Fragen zufällig und individuell aus einem Pool zu ziehen. Dieser Pool beinhaltet genau die Fragen aus den Übungen und ist somit allen bekannt. Eine sehr gute Note verlangt zudem das Meistern zweier (unbekannter) Challenge fragen, i.e. *easy to pass, hard to master*.

Kriterium 3: Kompetenzorientierung und über den Tellerrand.

Wir bemühen uns den Fokus auf Verständnis zu legen und nicht darauf irgendwelche Formeln auswendig zu lernen und/oder blind anzuwenden. Wir nutzen praxisnahe Beispiele um jedes behandelte Thema zu motivieren. Zudem sind diese Themen sehr bewusst gewählt und fügen sich zu einem grossen Ganzen zusammen. Wir schlagen in dieser Vorlesung eine konzeptionelle Brücke von formaler Logik über Algorithmen und Software bis hin zu Hardware und Computerchips. Das übergeordnete Ziel hierfür ist aufzuzeigen, dass diese drei Informatik-Grundsäulen eigentlich nur verschiedene Blickpunkte auf dieselbe Thematik sind (*unification*). Zudem fördern wir positive Lernimpulse, wie Offenheit, Begeisterung und Neugierde, mit *special topics lectures* in den Übungsstunden. Dort behandeln wir aktuelle Themen welche über den Vorlesungsstoff hinausgehen. Ein komplementäres Gruppenprojekt dient dazu, den gelernten theoretischen Stoff auf ein selbstgewähltes Praxisbeispiel anzuwenden und steigert die Teamfähigkeit.

Zudem fördern wir positive Lernimpulse, wie Offenheit, Begeisterung und Neugierde mit special topics lectures in den Übungsstunden. Dort stellen wir aktuelle Themen vor, welche über den Vorlesungsstoff hinausgehen, aber doch mit diesem verwandt sind. Aktuell behandeln wir:

(a) Schwarmintelligenz, oder zelluläre Automaten: radikal andere Ansätze für Computer die auf zellulären Automaten beruhen (Conway’s game of life)

(b) Bau eines funktionierenden Computers in Minecraft: vorgetragen von JKU-Studierenden die genau das in ihrer Freizeit gemacht haben.

(c) Warum existiert Glas: Erklärungen aus der theoretischen Informatik für mikroskopische Effekte in den Naturwissenschaften.

(d) Quantenvorteil und Boson-Sampling: warum können Quanten-Architekturen spezifische Dinge die konventionelle Computer nicht können (sollen).

(e) Quantenalgorithmen und der Deutsch-Josza-Algorithmus: Einführung in die grundlegenden Ideen hinter Qunantencomputern.

Mit diesen special topics lectures blicken wir bewusst über den Tellerrand des etablierten Lehrstoffes

(*think outside the box*).

Kriterium 4: Europäische und internationale Ausrichtung

Unser Script ist in englischer Sprache verfasst und basiert auf modernen Lehrinhalten aus den US. Von dort habe ich zudem ein Faible für flache Hierarchien mitgebracht: wir verwenden ausschliesslich unsere Vornamen und duzen uns alle. Solche kleinen Zeichen erleichtern die Interaktion zwischen Studierenden und Lehrenden, stärken das Zusammengehörigkeitsgefühl und fördern die Bereitschaft zum gegenseitigen Entgegenkommen (falls notwendig). Übungsbetrieb und Klausurmodus sind ebenfalls international inspiriert. Im Grunde ist dies eine Anglo-amerikanische Veranstaltung mit lokalem Anstrich: die Umgangssprache ist (Österreichisches) Deutsch.

Als Österreicher mit fast 15 Jahren Auslandserfahrung ist es mir auch ein persönliches Anliegen, hiesige Studierende zu Auslandssemestern zu ermutigen und unterstütze solche Bestrebungen auch nach Kräften. Dies beinhaltet persönliche Tipps, sowie personalisierte Reference-Letters für Austauschplattformen, z.B. ISEP (https://www.isepstudyabroad.org/).

Nutzen und Mehrwert

Ein Eckpfeiler unserer Neugestaltung war das Erstellen eines komplett neuen Scripts (Latex, ca 150 Seiten) welches sich an modernen Lehrinhalten aus den USA orientiert. Dieses Script ist online frei zugänglich (https://iic.jku.at/files/eda/kueng-complexity.pdf) und führt zu beträchtlichen Vorteilen für Studierende und Lehrende. Studierenden ermöglicht es das Aufarbeiten des Stoffes in selbstgewähltem Tempo. Folgendes Zitat aus den Evaluationen von 2023 zeigt noch einen anderen Mehrwert auf: "Es gibt ein Skript (vom Vorjahr) zum Downloaden (auf der IIC Website), wo insgesamt die VL-Unterrichtsthemen vorkommen, und das verrät einem, was alles Stoff ist. Dass wir immer die Übungen in der Gruppe kontrolliert und besprochen haben, habe ich besonders toll gefunden. Da konnte ich mehr Fragen stellen, wenn mir etwas nicht klar war...."

Unser angloamerikanischer Ansatz die Klausur 'easy to pass but hard to master' zu gestalten, führt ebenfalls zu Lernerleichterung für Studierende ohne die wirklich Motivierten zu unterfordern. Transparenz und Vorhersehbarkeit des Klausurmodus erleichtern die Lernphase und vermindern subconscious bias. Zwei anonyme Evaluationskommentare aus 2022 untermauern diese Faktoren: "Das Angebot diese Klausur wie einen Führerscheintest zu machen ist Gold wert." Und "Die Klausur wird extrem(!) fair abgehandelt und wird so aufgebaut sein, dass jeder die Chance auf eine positive Note bekommt."

Der beträchtliche Anfangsaufwand für unsere Neugestaltung sieht auch substantielle Zeitersparnis für Lehrende in der Zukunft vor. Es gibt nun ein gut funktionierendes Script und ein modernes Klausurkonzept, welche nun lediglich aktualisiert und schrittweise verbessert werden. Dazu nützen wir Feedback von Studierenden und Kolleg*innen aus aller Welt. Der grossteils automatisierte Klausurmodus mit Moodle erspart bei 150 bis 200 Studierenden zusätzlich Korrekturzeit die nun für andere wissenschaftliche Tätigkeiten genutzt werden.

Nachhaltigkeit

Wegen des beachtlichen Anfangserfolges werden wir diese Veranstaltung von jetzt an jedes Wintersemester anbieten. Wir haben zudem wichtige Lehrerfahrungen sammeln können, von denen auch unsere anderen Veranstaltungen profitieren.

Thematisch verwandte Vorprodukte gab es in dieser Form nicht, aber wir haben wertvolle Impulse aus den USA in unsere Neugestaltung einfliessen lassen. Ich war zuvor als Lecturer am renommierten California Institute of Technology tätig, wo ich einen komplett anderen didaktischen Zugang zu komplexen Themenblöcken entwickelt habe. Dazu gehört ein Fokus auf das grosse Ganze, viele Beispiele, sowie positive Lernanreize wie Neugier und Begeisterung.

Ein weiterer Nachhaltigkeit-Erfolg ist die Tatsache, dass die wissenschaftsaffige Online-Community unser Script sehr positiv aufgenommen hat. Dieses ist auf unserer Webpage (https://iic.jku.at/files/eda/kueng-complexity.pdf) frei verfügbar. Der Announcement-Tweet (@RichardKueng) hat 37 000 Impressions, 1530 Engagements und 285 Likes aus aller Welt generiert. Das ist jetzt noch nicht unbedingt viral, aber ein beeindruckendes Ergebnis. Comments waren z.B.:

"These notes are awesome! Definitely one of my favorite resources on the subject now" Ethan Epperly, Doktoratsstudent am California Institute of Technology

"My favourite lecture notes ever. I couldn't attend all the live lectures but the notes where a joy to read and gave me all the information I needed." Alexander Karer, JKU-Student

Dissemination/Transfer

Wir freuen uns sehr darüber, dass unsere Neukonzeption von 'Berechenbarkeit und Komplexität' nun zwei Jahre in Folge sehr gute Evaluationen von Studierendenseite, aber auch von Kolleginnen und Kollegen, erhalten hat. Wir sehen das als Indiz dafür, dass wir auf dem richtigen Weg sind. Allerdings erscheint uns der aktuelle Zeitpunkt noch etwas zu früh um unser Konzept aktiv und gezielt weiterzuverbreiten. Wir tauschen jedoch unsere Erfahrungen - was lief gut? Was lief schlecht? - offen und transparent in unseren Netzwerken aus. Dazu gehören lokale Kolleg*innen, aber vor allem auch junge Professor*innen aus der ganzen Welt welche zum Thema Quantum Computing forschen.

Natürlich verwendenden wir Erfahrungen und Feedback aus dieser Veranstaltungen um unsere anderen Vorlesungen ebenfalls so aktuell, zugänglich und spannend wie möglich zu gestalten. Bei diesen Veranstaltungen handelt es sich jedoch um Master-Wahlfächer zum Thema quantum computing. Da Pflicht- und Wahlfächer sehr verschieden voneinander sind, ist ein voller Transfer unseres Konzepts hier nur bedingt möglich.

Institutionelle Unterstützung

Wegen der hohen Studierendenzahl (150-200) stellt uns die Universität eine bezahlte Tutor*innenstelle (studentische Mitarbeiter*in) im Rahmen von 8-10h pro Woche zur Verfügung. Wir haben mit Nina Brandl die ideale Besetzung für diese Stelle gefunden. Nina hat fast den gesamten Moodle-Übungsbetrieb aufgesetzt und gewartet. Für die Vorlesung erhalten wir gut ausgestattete Vorlesungsräume mit guter Beleuchtung und, vor allem, grossen Tafeln für mathematische Argumente und Beweise.

Neben diesem Standard-Support erlebten wir auch eine erfrischende Bereitschaft unsere Veranstaltung in andere Studiengänge als Wahlfach einzubauen. Dazu gehören bislang Artificial Intelligence, Elektrotechnik und Mathematik. Diese Liste ist noch im Wachsen begriffen. Diesen Herbst durften wir uns jedenfalls über dutzende freiwillig Teilnehmende aus den oben genannten Studiengängen freuen. Diese bringen eine ganz andere Motivation mit und ihr komplementärer Background bereichert die peer-to-peer-Diskussionen in den Übungsstunden enorm.

Positionierung des Lehrangebots

Pflichtfach: Informatik (Bachelor), 3. Semester

Wahlfach: Artificial Intelligence, Elektrotechnik, Mathematik

Links zu der/den Projektmitarbeiter/innen
Links zu Social Media-Kanälen
Das Beispiel wurde für den Ars Docendi Staatspreis für exzellente Lehre 2023 nominiert.
Ars Docendi
2023
Kategorie: Lernergebnisorientierte Lehr- und Prüfungskultur
Ansprechperson
Assoz. Univ.-Prof. Dr. Richard Kueng, MSc ETH
Institute for Integrated Circuits, Department of Computer Science
+43 732 2468 4754
Nominierte Person(en)
Assoz. Univ.-Prof. Dr. Richard Kueng, MSc ETH
Institute for Integrated Circuits, Department of Computer Science
Themenfelder
  • Erfahrungslernen
  • Flexibel Studieren
  • Lehr- und Lernkonzepte
  • Rund ums Prüfen
  • Diversität und Soziales
  • Infrastruktur/Lehrmaterialien
Fachbereiche
  • Mathematik, Informatik, Naturwissenschaften, Technik/Ingenieurwissenschaften