Dr. H.-G. Gräbe:

Grundlegende Algorithmen der Computeralgebra

• VL: freitags, 11.15 - 12.45 Uhr, H 22
• Besprechung der Übungsaufgaben: mittwochs, 13.15 - 14.45 Uhr, SG 3-98 (nicht wöchentlich, am 17.4. im Hs 22)

Teilnehmerkreis:

Studenten im Haupt- oder Nebenfach Informatik oder Mathematik, die sich mit Algorithmen des symbolischen Rechnens intensiver beschäftigen wollen.

Wahlobligatorisch im Kernfach Angewandte oder Theoretische Informatik.

Übersicht:

In der Vorlesung werden die wichtigsten (klassischen) algorithmischen Ideen, die sich um den Begriff der Teilbarkeit gruppieren, vorgestellt. Neben der Primzahleigenschaft und der Faktorisierung ganzer Zahlen stehen dabei gcd-Bestimmung und Faktorisierung im Ring der Polynome in einer bzw. mehrerer Variablen im Mittelpunkt. Die Vorlesung berührt im einzelnen die folgenden Themen:

• Langzahldarstellung ganzer Zahlen
• Primzahltests und Faktorisierung ganzer Zahlen
• Lineare Algebra über Polynomringen
• gcd-Berechnung und Faktorisierung von Polynomen

Literatur :

• A.G. Akritas: Elements of computer algebra with applications. Wiley, New York 1989.
• J.H. Davenport, Y. Siret, E. Tournier: Computer algebra. Systems and algorithms for algebraic computations. Academic Press, London 1988.
• K.O. Geddes, S.R. Czapor, G. Labahn: Algorithms for Computer Algebra. Kluwer, Boston 1992.
• D.E. Knuth: The art of computer programming. Vol. 2: Seminumerical algorithms. Addison Wesley 1981.
• N. Koblitz: A course in number theory and cryptography. Springer, New York 1987.
• E. Kranakis: Primality and Cryptography. Wiley-Teubner Series in Computer Science, Teubner, Stuttgart, 1986
• M. Mignotte: Mathematics for Computer Algebra. Springer 1991.
• H. Riesel: Prime numbers and computer methods for factorization. Birkhäuser, Basel 1994.
• F.Winkler: Polynomial algorithms in computer algebra. Texts and Monographs in Symbolic Computation, Springer, Wien 1996.
• R. Zippel: Effective polynomial computation. Kluwer, Boston 1993.

Erwartete Vorkenntnisse :

Scheinvergabe :

Übungsschein (Umfang 1 SWS) wird bei Erreichen von mindestens 50 % der Punkte aus den Übungsaufgaben erteilt.

Bewerteter Schein oder Note (Modulprüfung) bei erfolgreicher Teilnahme an der Klausur am 8. Juli 2002, 17-18 Uhr.