Institut für MathematikHome > Veranstaltungen > Vorlesungen > 4227

  English  |  Kontakt  |  Druck  |  Suchen  

FÜR SCHÜLERiNNEN
INSTITUT
VERANSTALTUNGEN
KOLLOQUIA/SEMINARE
STUDENTENSEMINARE
VORLESUNGEN
MODULE
KONFERENZ/ANLÄSSE
VORKURSE
FÜR STUDIERENDE
FÜR DOKTORANDiNNEN


MAT007Aspects of Computer AlgebraFelix FonteinFS 13
Di13.00-14.45Y27H12


Lecture notes
Chapter 1: Basic Arithmetic
Chapter 2: A Short Introduction to Python for Mathematicians
Chapter 3: Fast Arithmetic (updated: 27.03.2013)
Chapter 4: Algorithms and Data Structures (updated: 27.03.2013)
Chapter 5: Interpolation and the Chinese Remainder Theorem (updated: 26.04.2013)
Chapter 6: Linear Algebra (updated: 21.05.2013)
Chapter 7: Finite Groups (with end of Chapter 6, bibliography, list of algorithms and listings, and index)
Complete lecture notes (02.08.2013)

Python modules from the lecture notes and exercises

Exercises
Exercise sheet 1 — ringstest.py (for Exercise 3)
Exercise sheet 2 — moduloint.py (for Exercise 9; updated 21.03.2013)
Exercise sheet 3
Exercise sheet 4
Exercise sheet 5
Exercise sheet 6
Exercise sheet 7 (updated 09.04.2013
Exercise sheet 8 (updated 26.04.2013)
Exercise sheet 9
Exercise sheet 10
Exercise sheet 11

The following document contains solutions to certain exercises. It will be updated with new solutions throughout the semester.
Solutions to exercises 5, 8, 16, 22, 25, 28, 29, 30, 31, 32, 37, 38, 39 and 44 (May 17, 2013)

Slides from the lectures
Lecture 1, theoretical part — Lecture 1, practical part — Python code (26.02.2013)
Lecture 2, practical part
Lecture 3, practical part
Lecture 4, practical part
Lecture 5, practical part
Lecture 6, practical part
Lecture 7, practical part
Lecture 8, practical part
Lecture 9, practical part
Lecture 11, practical part
Lecture 12, practical part
Lecture 13, practical part

Corrections of the lecture notes
  • Chapter 3, page 86, line 6: The subscript of rev in "Since revm(g)(0) = ..." should be m-1 and not m. (13.03.2013)
  • Chapter 3, page 90, Algorithm 3.6, line 4: both occurences of q̂ should be a p̂. (13.03.2013)
  • Chapter 3, page 91, Proposition 3.4.7, second line of the first displaystyle formula: M(m,n) should be M(mn). (13.03.2013)
  • Chapter 3, page 94, Algorithm 3.7, line 6: the return value should be g + p̂ · h. (13.03.2013)
  • Chapter 3, page 95, Theorem 3.4.10: both asymptotic running times should be O(M(log N + log d) log log N) instead of O(M(log N + log d) log d). (13.03.2013)
  • Chapter 3, page 103, at the bottom in the displaystyle formula for deg(r - r'), second line: the -deg g after the equality should be deg g. (13.03.2013)
  • Chapter 3, page 97, line 1 of Algorithm 3.9: "2-adic" instead of "b-adic". (20.03.2013)
  • Chapter 3, page 99, Algorithm 3.11 and page 100, proof of Theorem 3.5.6: everything having exponent e3 should be 3 (and not 2). (Appears twice in the algorithm and twice in the proof.) (20.03.2013)
  • Chapter 3, page 112, Definition 3.7.4(a): the in the definition of the map DFTω should be an R. (20.03.2013)
  • Chapter 3, page 106, Algorithm 3.12: after line 7, another line should be inserted which tests whether âj+1 = 0. (21.03.2013)
  • Chapter 3, page 109, Algorithm 3.13: in the last case, (a, b, c) should be computed from (1 0) A and not from (0 1) A. (21.03.2013)
  • Chapter 3, page 109, Algorithm 3.13: in the last lines, a does not need to be normalized anymore. Therefore, the second last line can be removed. (27.03.2013)
  • Chapter 3, page 109, Theorem 3.6.8: the constant in the running time should be modified to -13. This also applies to the corresponding cases in the proof. (27.03.2013)
  • Chapter 3, page 111, Lemma 3.7.3 (c): l can also be 1. 27.03.2013)
  • Chapter 3, page 112, Definition 3.7.4 (a): in the definition of bi, the index of a should be k and not i. (27.03.2013)
  • Chapter 3, page 114, Algorithm 3.14, lines 2 and 3: b should be an a. (27.03.2013)
  • Chapter 3, page 117, Algorithm 3.15, line 1: the condition should be m ≤ 2 and not n ≤ 2. (27.03.2013)
  • Chapter 4, page 145, Theorem 4.2.26: in the second displayed formula, f' should be used instead of f at the beginning, and h should be denoted hT in the first displayed equation and hT' in the second. (27.03.2013)
  • Chapter 4, page 146, the large graph: inside the red boxes sometimes p was used instead of f. (27.03.2013)
  • Chapter 5, page 160, Algorithm 5.1: the loop in 3(b) should only go until lk-2 and not until lk-1. (26.04.2013)
  • Chapter 5, page 160, Algorithm 5.1: in step 3(c), i must be replaced by lk-1. (26.04.2013)
  • Chapter 5, page 171, Algorithm 5.4: the loop in 3(b) should only go until lk-2 and not until lk-1. (26.04.2013)
  • Chapter 5, page 171, Algorithm 5.4: in step 3(c), i must be replaced by lk-1. (26.04.2013)
  • Chapter 5, page 174, Algorithm 5.6: the loop in 3(b) should only go until lk-2 and not until lk-1. (26.04.2013)
  • Chapter 5, page 174, Algorithm 5.6: in step 3(c), i must be replaced by lk-1. (26.04.2013)
  • Chapter 5, page 176, Algorithm 5.9: the loop in 3(b) should only go until lk-2 and not until lk-1. (26.04.2013)
  • Chapter 5, page 176, Algorithm 5.9: in step 3(c), i must be replaced by lk-1. (26.04.2013)
  • Chapter 6, page 193, Algorithm 6.3: in step 6, D has format k2 × (m - k1), and the top-left entry of the first displaystyle matrix in the note should be L1Ũsub>1. (17.05.2013)
  • Chapter 6, page 197, Algorithm 6.6: in step 2(c), Ui• should be swapped with Ur+1,• and not with Ar+1,•. (17.05.2013)
  • Chapter 6, page 197, Algorithm 6.6: in step 2(g), mUr• should be subtracted from Ui• and not mAr•. (21.05.2013)
  • Chapter 6, page 202, proof of Theorem 6.5.6: in the first line, 0.65 should be replaced with 1.1; the same is true for the next two occurences of 0.65 throughout this proof on the next page. (17.05.2013)
  • Chapter 6, page 203, Algorithm 6.9, step 2: the constant 0.65 should be replaced by 1.1. (17.05.2013)
  • Chapter 6, page 204, Algorithm 6.10, step 4: the CRT algorithm's number is 5.10. (17.05.2013)
  • Chapter 6, page 207, Algorithm 6.11, step 5(a): it should be b' := b - Ax. (17.05.2013)
  • Chapter 6, page 207, Algorithm 6.11, step 5(c): it should be b' := b'/pk. (17.05.2013)
  • Chapter 6, page 213, Algorithm 6.12, step 2, first line: mi/2||A||i/2 should be mi/2||A||i. (17.05.2013)
  • Chapter 6, page 216, Algorithm 6.14, step 4: i should run up to t and not d. (17.05.2013)
  • Chapter 6, page 218, Algorithm 6.15, output description: the sum inside the gcd should sum over cibi. (21.05.2013)
  • Chapter 6, page 218, Corollary 6.9.5: the number of basic e-operations is in O((n + m)M(m)logm) (the logm factor was missing). (21.05.2013)
  • Chapter 6, page 220, Algorithm 6.16, step 2: the for loop should range from s = 1 to s = k (and not from 3 to k+2). (21.05.2013)
  • Chapter 6, page 220, Algorithm 6.16, step 2: the for loop should range from s = 1 to s = k (and not from 3 to k+2). (21.05.2013)
  • Chapter 6, page 225, Algorithm 6.19, step 6: instead of (j2, ..., jr-1), return (j2-1, ..., jr-1-1). (21.05.2013)

Exercise classes in April and May
  • April 9/10: exercise classes as usual
  • April 16/17: no exercise classes (and no lecture)
  • April 23/24: exercise classes as usual
  • April 30: exercise class in Y27 H28
  • May 1: no exercise class
  • May 7/8: exercise classes in Y27 H28
  • May 14/15: exercise classes as usual
  • May 21/22: exercise classes as usual
  • May 28/29: exercise classes as usual
(From April 16 to May 8, the computer room Y27 H52 is most of the time used for block course STA 220.)

Exam
The projects will be handed out and have to be returned and presented during August 2013. Alternatively, it is possible to pass a written exam instead of working on a project.

Module: 26.08.2013 9:00-12:00, Room:Y27H12, Typ: schriftlich

http://www.vorlesungen.uzh.ch/

 
Semester: vorheriges   FS 13   nächstes