Symbolic computation

2022/2023
Programme:
Computer Science and Mathematics, Second Cycle
Year:
1 ali 2 year
Semester:
first or second
Kind:
optional
Group:
B
ECTS:
6
Language:
slovenian, english
Hours per week – 1. or 2. semester:
Lectures
2
Seminar
1
Tutorial
2
Lab
0
Content (Syllabus outline)
  1. Rewrite systems (reduction relations, Newman's lemma, completion) 2. Operations with polynomials (resultants and subresultants, modular arithmetic, Hensel lifting, polynomial factorization and decomposition) 3. Operations with ideals (monomial orders, Gröbner bases, solving systems of algebraic equations, applications in geometry and robotics) 4. Solving linear difference and differential equations (polynomial solutions, hypergeometric and hyperexponential solutions, summation and integration in closed form, automated proofs of identities)
Readings

David Cox, John Little, Donal O’Shea: Ideals, Varieties, and Algorithms. Third edition. Springer, New York , 2007. ISBN: 978-0-387-35650-1.
Joachim von zur Gathen, Jürgen Gerhard: Modern Computer Algebra. Third edition. Cambridge University Press, Cambridge, 2013. ISBN: 978-1-107-03903-2.
The Concrete Tetrahedron. Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates. Texts and Monographs in Symbolic Computation. Springer, Dunaj, 2011. ISBN: 978-3-7091-0444-6

Objectives and competences

Students acquire competency to use tools for automated solving of mathematical problems, important in applications, such as the problem of representation of algebraic structures, the problem of simplification of expressions, solving systems of algebraic equations, solving linear difference and differential equations, and summation and integration in closed form.

Intended learning outcomes

Knowledge and understanding: Complete rewrite systems. Operation of algorithms for polynomial factorization and decomposition. Algorithms for solving systems of algebraic equations. Algorithms for solving linear difference and differential equations. Algorithms for closed-form summation and integration and for proving identities.
Application: Solving problems in robotics, geometry, combinatorics, and analysis of complexity of algorithms.
Reflection: Relations among problems of representation, simplification, and computation.
Transferable skills: The ability to solve certain mathematical problems exactly by means of a computer.

Learning and teaching methods

Lectures, exercises, homeworks, consultations, projects.

Assessment

Homeworks or project
Written exam
Oral exam
grading: 5 (fail), 6-10 (pass) (according to the Statute of UL)

Lecturer's references

doc. Matija Pretnar:

  • LUKŠIČ, Žiga., PRETNAR, Matija. Local algebraic effect theories. Journal of Functional Programming, ISSN - 1469-7653, 2020, vol. 30, E13, 27 strani [COBISS-SI-ID – 53281795]
  • FORSTER, Y., KAMMAR, O., LINDLEY, S., PRETNAR, M. (2019). On the expressive power of user-defined effects: Effect handlers, monadic reflection, delimited control. Journal of Functional Programming, ISSN - 1469-7653, 2019, vol. 29, E15, 43 strani [COBISS-SI-ID – 18852441]
  • LOKAR, Matija, PRETNAR, Matija. A low overhead automated service for teaching programming. Koli Calling '15: Proceedings of the 15th Koli Calling Conference on Computing Education Research, 2015, 132–136 [COBISS-SI-ID – 17536089]