Υπολογιστική Άλγεβρα Ι

Θέματα που πρόκειται να καλυφθούν

• Εισαγωγή στην αριθμητική ακριβείας ακεραίων αριθμών και σύγκριση με την αριθμητική κινητής υποδιαστολής (floating point arithmetic).
• Απλός και επεκταμένος Ευκλείδειος αλγόριθμος.
• Εφαρμογές του Ευκλείδειου αλγορίθμου: αριθμητική υπολοίπων θεώρημα Fermat, γραμμικές Διοφαντικές εξισώσεις, συνεχή κλάσματα.
• Εφαρμογές αριθμητικής υπολοίπων: εκτίμηση και παρεμβολή (evaluation and interpolation), o (Ελληνο-) Κινέζικος αλγόριθμος υπολοίπων, παρεμβολή Hermite και Cauchy, προσέγγιση Pade.
• Εφαρμογές στην κρυπτογραφία (knapsack and RSA public-key cryptosystems).
• Γρήγοροι αλγόριθμοι πολλαπλασιασμού: η μέθοδος Karatsuba, ο διακεκριμένος μετασχηματισμός Fourier, ο γρήγορος μετασχηματισμός Fourier (Discrete and Fast Fourier Transform) και ο αλγόριθμος των Schoenhage and Strassen.
• Η επαναληπτική μέθοδος του Newton για την προσέγγιση ριζών πολυωνύμων. Γενικευμένα αναπτύγματα Taylor, υπολογισμός ριζών ακεραίων αριθμών.
• Μέθοδοι απομόνωσης πραγματικών ριζών πολυωνύμων με ακέραιους συντελεστές. Η μέθοδος διχοτόμησης του Sturm (1828) και η μέθοδος των συνεχών κλασμάτων που στηρίζεται στο θεώρημα Vincent (1836).

Διδάσκων

Αλκιβιάδης Γ. Ακρίτας, Αναπληρωτής Καθηγητής.
email: arkitas@uth.gr

Σημειώσεις