NummeraprECTS2.0SpezifizierungGrundlegende Algorithmen für wiederkehrende Aufgaben verstehen und implementieren können, sowie Beurteilungskriterien zur Laufzeit und Korrektheit eines Algorithmus anwenden können.AnspruchsniveauIntermediateInhaltNebst der Kompetenz im Umgang mit einer Programmiersprache braucht man Verständnis für grundlegende Verfahren, also die in einer Programmiersprache auszudrückenden Algorithmen und derjenigen Datenstrukturen, auf denen diese Algorithmen operieren.
Für wiederkehrende Aufgaben gibt es bewährte Standardlösungen, die man kennen und deren Funktionsweise man verstehen sollte. Algorithmen auf Graphen lassen sich beispielsweise für viele Aufgaben anwenden, die sich mithilfe dieses mathematischen Modells formulieren lassen.
Um die Funktionsweise von Algorithmen systematisch zu verstehen und darüber argumentieren zu können und um Algorithmen systematisch zu entwickeln, helfen methodische Hilfsmittel wie (Schleifen-)Invarianten.
Bei der Verarbeitung vor allem grosser Datenmengen kommt es besonders darauf an, wie sich die von Algorithmen benötigte Laufzeit und allenfalls der Speicherbedarf entwickeln, wenn die Menge der Daten wächst. Dieses Wachstum lässt sich mit der O-Notation erfassen, welche die asymptotische Komplexität abbildet.LernergebnisseDie Studierenden
verstehen die Konzepte grundlegender Algorithmen und Datenstrukturen wie Suchalgorithmen, Hash-Tables und Algorithmen auf Graphen (z.B. topologisches Sortieren, Tiefen- und Breitensuche) und wenden diese an.
können bestehende Programme anderer Programmierer nachvollziehen und deren Funktionsweise erklären, darin Standardlösungen erkennen.
können grundlegende Algorithmen selbst programmieren und an Aufgaben-Varianten anpassen.
können Rekursion beim Entwurf von Algorithmen bedarfsgerecht einsetzen und programmieren.
Die Studierenden
verstehen das Konzept der «asymptotischen Komplexität» und kennen die relevanten Eigenschaften wichtiger «Komplexitätsklassen».
benutzen die Klassifikation durch die asymptotische Komplexität, um den Ressourcen-Bedarf (insbesondere Laufzeit und Speicher) von Algorithmen zu beurteilen und Vergleiche anzustellen.
kennen untere Grenzen für den Aufwand grundlegender Verfahren bzw. Aufgaben.
können aus Bibliotheken programmierter Algorithmen anhand aufgabenbezogener Parameter und Trade-Offs geeignete auswählen und diese Entscheidung begründen.
Die Studierenden
können die Korrektheit von Programmen sowie die für korrekte Resultate einzuhaltenden Randbedingungen begründen (z.B. mit Schleifen-Invarianten).
können sich bei der Konstruktion eigener Algorithmen und Programme von Überlegungen zur Korrektheit leiten lassen.
ModulbewertungNoteBaut auf folgenden Modulen aufGrundkompetenz Programmieren (gpr)ModultypPortfoliomodul 
