KUSSS
Moodle
RISC Courses
Wolfgang Windsteiger
LV Beschreibung: Algorithmische Methoden 1
Einstiegsvoraussetzungen
Keine.Leistungsnachweis/Prüfung
Programmierbeispiel + Dokumentation + mündliche Präsentation.Ziele
Studenten der Lehrveranstaltung Algorithmische Methoden 1 werden:- mit wichtigen mathematischen Problemstellungen konfrontiert,
- mit wichtigen Algorithmen zur Lösung mathematischer Problemklassen vertraut gemacht,
- strukturiertes Herangehen an Problemstellungen lernen und
- die Umsetzung von mathematischem Wissen in Computerprogramme trainieren.
LV–Inhalt
Die Lehrveranstaltung dient als “Brücke” zwischen den beiden Hauptlehrveranstaltungen des 1. Semesters, Lineare Algebra und Analysis. Es werden mathematische Problemstellungen betrachtet ungeachtet dessen, ob sie der linearen Algebra oder der Analysis zurechenbar sind. In vielen Fällen werden zu ein und derselben Problemstellung exakte Lösungsalgorithmen und approximative Verfahren gegenübergestellt. Exakte Algorithmen haben ihren mathematischen Hintergrund eher in der Algebra, approximative Algorithmen stützen sich meist auf Resultate der Analysis.Konkrete Inhalte der Lehrveranstaltung sind:
Begriffsbildung
Bestandteile einer exakten Problembeschreibung, Typen von Algorithmen, Typen von Problemreduktionen.Ein Grundbaukasten für die Mathematik
Hier werden mathematische Grundobjekte, die zum (mathematischen) Modellieren von Problemen notwendig sind, vorgestellt. Quantoren, Mengen und Tupel, Funktionen, Polynome, Matrizen und Vektoren werden in einer computer–exekutierbaren Darstellung präsentiert. Der Schwerpunkt liegt dabei auf Polynomen und Polynomfunktionen, da in den weiteren Abschnitten viele Problemstellungen in Form von Polynomen modelliert werden.Anhand zweier konkreter Problemstellungen werden in der Folge verschiedene mathematische Algorithmen zur Lösung der jeweiligen Problemstellung entwickelt.
Polynominterpolation
Verschiedene Methoden der Polynominterpolation werden vorgestellt: Polynomansatz (Van–der–Monde Matrix), Lagrange–Interpolation, Neville–Algorithmus (Neville–Tableau), Tschebyscheff–Polynome zur Bestimmung der optimalen Stützstellen, Spline–Interpolation, inverse Interpolation.Gleichungen und Gleichungssysteme
Verschiedene Typen von Gleichungen und Gleichungssystemen werden betrachtet. Exakte Verfahren: Lösen linearer Gleichungen durch Äquivalenzumformungen, Lösen quadratischer Gleichungen durch Äquivalenzumformungen, invertierbare Funktionen, Lösen polynomialer Gleichungen durch Faktorisieren. Approximative Verfahren: Regula Falsi, Fixpunkt–Iteration, Newton–Verfahren. Für lineare Gleichungssysteme wird der Gauß–Algorithmus besprochen, polynomiale Gleichungssysteme werden mit Hilfe von Gröbner Basen (Buchberger–Algorithmus) gelöst. Als approximatives Verfahren für polynomiale wie auch nicht–polynomiale Gleichungssyteme wird das mehrdimensionale Newton–Verfahren vorgestellt.Literatur
Ein Skriptum ist vorhanden. Überdies ist das Skriptum in elektronischer Form erhältlich, wodurch alle Berechnungen im Skriptum mit Hilfe von Mathematica nachvollziehbar sind.Mathematische Ausdrücke im Skriptum sind in Theorema–Syntax formuliert. Die Theorema–Sprache ist eine konkrete Form der Prädikatenlogik, die sich dadurch auszeichnet, dass deren Syntax weitgehend jener Form entspricht, wie man sie aus herkömmlichen Mathematik–Publikationen kennt, die aber zugleich computer–exekutierbar ist. Dadurch wird jede Formel im Skriptum “lebendig” und vom Computer exekutierbar. Mit allen Formeln kann somit direkt gerechnet werden, ohne sie in eine Programmiersprache übersetzen zu müssen. Ein weiterer Vorteil ist, dass alles, worauf zu achten ist, wenn mathematische Verfahren auf einem Computer implementiert werden, dem Leser offengelegt wird. “Lästige Details”, die gerne verschwiegen werden, um die Präsentation einfacher erscheinen zu lassen, die aber bei der Umsetzung in ein korrektes Computer–Programm berücksichtigt werden müssen, müssen nicht mehr länger vom Leser selbst entdeckt werden, da die Sprache präzise genug ist, um alle Details zu enthalten.